Computational social choice is concerned with the design and analysis of mechanisms for collective decision making. This course provides a thorough introduction to both classical social choice theory, originating in Economics and Political Science, and modern computational social choice, emphasising its interface with Computer Science and AI. The intention is to enable students to conduct independent research in this exciting and fast-moving field. This is an advanced, research-oriented course in the Master of Logic that is also listed as an elective for the MSc AI and the MSc Computational Science. Students from other programmes, such as Computer Science, Mathematics, Economics, or Philosophy, are equally welcome (contact me if you are unsure about your qualifications).
Nature of the Course and Prerequisites: The focus of this course is on theory: we will mostly be concerned with developing formal models of collective decision making and with proving theorems about those models. Therefore, I will expect what sometimes is called mathematical maturity, meaning that you need to have prior experience with working out and writing up mathematical proofs.
Special Theme for 2023: The special theme for this edition of the course is representation and reasoning. In particular, we will see how to use tools from the field of automated reasoning (notably SAT solvers) to support the research process in social choice theory.
Literature: We will mostly rely on original research papers, which I will post on this website as we go along. Beyond these papers, the main reference for this course is the Handbook of Computational Social Choice, the electronic edition of which is freely available online.
Research Seminars: You are always welcome to attend our local COMSOC Seminar as well as the international COMSOC Video Seminar.
Please note that the outline below is tentative only. We will use some of the tutorial slots in the official schedule to discuss your progress with the mini-projects, and possibly to cover some background material some of you might not yet be familiar with. But there won't be any regular tutorials (in the sense of exercise classes). It's also possible that we might use some of the tutorial slots for lectures and/or some of the lecture slots for other activities. In principle, you should be available during all officially scheduled course activities.
| Date | Content | Homework |
|---|---|---|
| Tuesday 31 October 2023 |
This first lecture has been a bit of a sightseeing tour of computational social choice, with various examples for problems addressed, results obtained, and techniques employed in different subfields of this research area. |
Read the historical (not the technical) parts of Chapter 1 of the Handbook and prepare the presentation of your assigned voting rule. |
| Wednesday 1 November 2023 |
We started with student presentations of a large number of voting rules, illustrating the many different ideas people have had over the centuries for how to run an election. We then tried to put some order into this large space and specifically focussed on the family of positional scoring rules and the family of Condorcet extensions (which, somewhat surprisingly, do not overlap). Finally, we turned our attention to the axiomatic method and proved the seminal result of May, providing a characterisation of the simple majority rule in terms of three simple and convincing axioms. I recommend having a look May's original paper, which is a nice example for an early application of the axiomatic method and still highly accessible today.
|
Homework #1 |
| Tuesday 7 November 2023 |
As a further application of the axiomatic method, we proved three of the classic impossibility theorems in social choice theory, namely Sen's Theorem on the Impossibility of a Paretian Liberal, Arrow's Theorem, and the Muller-Satterthwaite Theorem. You can find these proofs in my review paper linked below. Sen's original paper is still highly readable today and I recommend that you have a look at it.
|
|
| Wednesday 8 November 2023 |
We have introduced the problem of strategic manipulation in voting: sometimes a voter can improve the outcome of an election for herself by misrepresenting her preferences. While in earlier lectures we had treated voting rules merely as mechanisms that map a profile of ballots supplied by the voters to election winners, the notions of truthful voting and strategic manipulation provide the missing link between actual preferences and ballots cast in an election. The main theorem in this area of social choice theory is the Gibbard-Satterthwaite Theorem, which shows that no resolute voting rule (that does not exclude some alternatives from winning to begin with) can be immune to manipulation without also being dictatorial. We proved the theorem to be a simple corollary to Arrow's Theorem (via the Muller-Satterthwaite Theorem). You can read up on the proof here:
|
Homework #2 |
| Friday 10 November 2023 |
Tutorial: SAT Solving via Python We went over a simple Jupyter Notebook (view, download) that illustrates how to access a SAT solver via Python. |
|
| Tuesday 14 November 2023 |
The slides of this and the next two lectures are accompanied by a Jupyter Notebook (view, download) illustrating the use of SAT-solving technology to support axiomatic research in voting theory. In this first lecture on the use of automated reasoning tools in social choice theory, we saw that for an impossibility theorem such as the Gibbard-Satterthwaite Theorem the most intersting case is the smallest possible case, in terms of the number of voters and the number of alternatives, that is not trivial (as would be the case for just a single voter). We then started to prepare the grounds for modelling voting rules and the axioms governing them in propositional logic. This includes a set of simply Python function to operate on voters, alternatives, preferences, and profiles—all expressed as integers. |
|
| Wednesday 15 November 2023 |
In this lecture we completed the computer-aided proof of the Gibbard-Satterthwaite Theorem by encoding the relevant axioms in propositional logic, using a SAT solver to find the resulting formula to be unsatisfiable, and eventually generalising, by means of an inductive argument, the observed impossibility from the base case of two voters and three alternatives to the general case. We also discussed some of the advantages and shortcomings of this proof technique. For a discussion of how economists think about this (after all unconventional) approach to proving theorems in their domain, you could have a look at this position paper (which came out at a time when only a couple of papers using this approach had been published):
|
Homework #3 |
| Friday 17 November 2023 |
Discussion: Project Startup |
|
| Tuesday 21 November 2023 |
In this final lecture of our three-part introduction to the SAT technique for proving impossibility theorems in voting theory, we saw how to use MUS extraction to construct human-readable proofs for the impossibilities we may identify for specific (small) problem parameters. We then reviewed the literature on the SAT approach to get a glimpse of, first, some of the other domains in which it has been used and, second, how it has been refined beyond what we saw in class. This would be a good moment to read the review paper by Geist and Peters, who cover roughly the same material as we did, but do so in a slightly different way:
|
|
| Wednesday 22 November 2023 |
We reviewed a large number of ways in which one could change the standard model of voting so as to better account for certain features we might care about in practice. This included incomplete preferences, approval-based preferences, multiwinner voting, apportionment, participatory budgeting, and liquid democracy. Here are some of the key references cited on the slides:
|
Homework #4 |
| Friday 24 November 2023 |
Discussion: Project Ideas |
|
| Tuesday 28 November 2023 |
In this lecture we discussed the idea of trying to provide a level of explainability regarding the normative adequacy of collective decisions. We focused on one specific approach where explanations for why certain axioms entail the choice of a specific outcome are generated with the help of SAT-solving technology. This short paper explains the basic idea:
|
|
| Wednesday 29 November 2023 |
In this lecture we have reviewed a couple of approaches for formally modelling social choice scenarios in logic, focusing on one approach using classical first-order logic and another using a tailor-made modal logic. We also have reflected on the reasons for attempting such a formalisation and on the shortcomings of existing approaches. For a brief overview, consult Section 3 of this survey:
|
|
| Friday 1 December 2023 |
Tutorial: Basic Complexity Theory |
|
| Tuesday 5 December 2023 |
Complexity theory is one of the core tools used in the field of computational social choice. In this lecture, we have exemplified its use in three different areas related to the study of voting rules: to analyse how difficult it is to apply of given voting rule to compute the winners of an election, to analyse how difficult it is to manipulate elections under a given voting rule, and to analyse the difficulty of determining whether a given alternative is a possible winner under a given voting rule when the preferences of the voters have not yet been fully elicited. Here's the paper with the results on the coalitional manipulation problem we discussed in a little more depth:
|
|
| Wednesday 6 December 2023 |
When the decision to be made by a group of voters can be described in terms of a range of possible assignments to each of a set of variables, then we are dealing with a case of voting in combinatorial domains. In fact, most collective decision making problems faced in practice will have this kind of combinatorial structure. In this lecture we have reviewed several possible approaches to dealing with such problems and we have remarked that none of them currently provides a fully satisfactory solution. Here's the paper introducing the approach of voting with ballots that are compact representations of individual preferences, the approach we spent most time on:
|
Homework #5 |
| Friday 8 December 2023 |
Discussion: Paper Writing and Reviewing We discussed how to write a paper and how to write a review. |
|
| Tuesday 12 December 2023 |
This has been an introduction to the field of judgment aggregation. We discussed the famous doctrinal paradox at the origin of the field, saw how judgment aggregation generalises preference aggregation, reviewed a number of specific judgment aggregation rules, and proved two simple results making use of the axiomatic method. I recommend that you have a look at the original paper introducing the formal model of judgment aggregation:
|
|
| Wednesday 13 December 2023 |
Discussion: Presenting We discussed how to give a talk. |
During the second part of the course you will work on a small research project on a topic related to the special theme, write a short paper about it, and present your insights and results in a talk. The purpose of this exercise is to give you some exposure to what it is like to do research, including not only the lofty feeling associated with expanding the boundaries of human knowledge, but also all the hard bits, such as identifying a topic that is worth investigating, finding competent people to collaborate with, and sticking to the relentless deadlines and seemingly arbitrary constraints imposed on you by those higher up the food chain. Projects are to be worked on in groups of three people each. Your paper must be 4-5 pages long, excluding references, using the IJCAI LaTeX style (IJCAI is the International Joint Conference on Artificial Intelligence, the kind of conference where a lot of work on computational social choice gets published). I have a strong preference for your paper not having an appendix, but if you feel that you need to put some material in an appendix, get in touch to discuss this well before you finalise your paper. Finally, you must meet all of the deadlines below (what these involve exactly will get announced in due time):
Identifying a Topic. Finding a good topic for a project is difficult and you should set aside a significant amount of time for this task. You have a lot of freedom about what to work on, but your project must be related to the special theme of representation and reasoning. My advice is to start thinking about possible ideas early, but to not settle on a specific topic until we are a few weeks into course. The first project discussion session in particular is intended to help you generate ideas.
Another natural approach is to look through the literature and see whether you can extend an existing paper in some way. For example, maybe you can come up with better proofs of the main results, maybe you can generalise or extend some of the results, maybe you can strengthen some of the results by restricting attention to interesting special cases, or maybe you can obtain new insights by varying the methods used in the original paper (e.g., by adding an algorithmic perspective to a paper that is largely axiomatic, or vice versa).
Good places to look for relevant papers are recent editions of AAMAS, IJCAI, and AAAI. For papers published in the AI literature, I recommend checking these conferences first, but note that in some cases you may find a longer and more mature version in a journal, such as JAIR or AIJ. In the economics literature, you will find good number of papers on social choice theory in the specialised journal Social Choice and Welfare and a few more in the much broader JET. At the interface with philosophy, a relevant journal is Economics and Philosophy. At the interface with theoretical computer science, have a look at EC (a conference) and TEAC (a journal). While this is not a hard rule, I recommend that you focus your search on papers that have been published fairly recently. This makes it more interesting and gives you a better chance managing to do something original. Please note that my own papers are off limits for this exercise (because I will have to grade your project and naturally will be somewhat biased when it comes to my own work).
Requesting approval of your project. Start talking to me about your tentative ideas early on. To formally request approval of your project, upload a one-page PDF on Canvas in which you answer the following three questions:
Drafts and reviewing. As an intermediate step, each group will produce a 2-page draft, consisting of most of Section 2 (often called "The Model" in social choice papers), a few sentences of motivation (from Section 1), and a tentative outline (in the form of a bullet list) of what they still hope top do. Each draft will be anonymously reviewed by several students from the other groups (see how to write a review).
Talks. In the final week of the course, we are going to organise a mini-workshop where each group will present their work (20 minutes talk + 10 minutes for questions). Every group member should contribute in some form. Every course participant will be expected to attend all talks.