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 both the Master of Logic and the MSc Artificial Intelligence. Students from other programmes, such as Computer Science, Mathematics, Economics, or Philosophy, are also very welcome (contact me if you are unsure about your qualifications).
Prerequisites: I will expect what sometimes is called mathematical maturity, meaning that you should have some experience with working out and writing up mathematical proofs.
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 Projects: We will offer a project course on Advanced Topics in Computational Social Choice in June (for a limited number of participants). This project course will have three components: (i) attending and reporting on a local workshop, (ii) presenting a recent paper from the COMSOC literature, and (iii) carrying out a small original research project in a group.
See also: previous editions of the course, the Computational Social Choice Seminar at the ILLC, and the Dutch Social Choice Colloquium.
| Date | Content | Homework |
|---|---|---|
| Tuesday 2 April 2019 |
Introduction / Cake Cutting. After a brief introduction to the course, we have delved into the first scenario of collective decision making we'll be dealing with, namely the fair allocation of goods, starting with the case of dividing a single continuous resource between several agents. This is the famous cake-cutting problem. You can read up on the basics in my lecture notes:
|
Please read Chapter 1 of the Handbook to get a feel for the history and scope of computational social choice as a discipline, so as to allow you to better place the material we are going to cover in depth over the coming weeks. |
| Wednesday 3 April 2019 |
Axiomatics of Fair Allocation. We have reviewed a large number of different approaches for assessing the fairness, and more generally the social desirability, of an allocation of goods to the members of a group. We have also seen some initial examples for the use of the axiomatic method in social choice theory to analyse mechanisms for collective decision making. Furthermore, we have pondered the implicit choices regarding the nature of individual preferences one has to make when settling on a formal model to study a collective decision making problem, such as fair allocation problem. On a related note, near the end of this lecture, we have discussed the matter of choosing a language to explicitly represent the preferences (in this case, the utility function) of an agent and we have seen a couple of examples for the kind of technical results one may wish to obtain regarding preference representation languages. The MARA Survey reviews many of these issues as well:
|
|
| Thursday 4 April 2019 |
Tutorial on Computational Complexity. This has been a brief recap of basic notions from the theory of computational complexity, with a focus on NP-completeness and definitions of a few complexity classes beyond NP that are of particular relevance to computational social choice. |
|
| Tuesday 9 April 2019 |
Algorithmics of Fair Allocation. We have discussed three different kinds of approaches for arriving at a socially optimal allocation of indivisible goods. First, a central authority may elicit the preferences of all the agents and then compute an optimal allocation. Thus, here we treat fair allocation as a combinatorial optimisation problem. Second, we may design an interaction protocol and try to prove that when agents follow this protocol they are guaranteed to end up in an allocation that satisfies certain fairness properties. Third, we may give up control entirely and simply provide agents with an environment in which to negotiate their own deals in a distributed manner. In this setting, we hope to get fairness guarantees by making reasonable assumptions about the preferences and, more generally, the behviour of agents. We have seen specific instances for research belonging to each of these three strands of work. For a broader overview of the field, consult Chapter 12 of the Handbook:
|
Homework #1 (due: Monday, 15 April 2019) |
| Wednesday 10 April 2019 |
NO CLASS |
|
| Tuesday 16 April 2019 |
Voting Rules and Characterisation Results. We have reviewed a large number of voting rules, to illustrate the rich variety of ideas people had over the years for how to conduct an election. In particular, we have seen two important families of rules, the positional scoring rules and the Condorcet extensions. Some of this material (and a lot more) is covered in Chapter 2 of the Handbook:
|
|
| Wednesday 17 April 2019 |
Impossibility Theorems in Preference Aggregation. As a further application of the axiomatic method, we have 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.
|
|
| Tuesday 23 April 2019 |
Strategic Manipulation in Voting. We have introduced the problem of strategic manipulation: 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 have proved the theorem to be a simple corollary to the Muller-Satterthwaite Theorem. You can read up on the proof here:
|
Homework #2 (due: Monday, 29 April 2019) |
| Wednesday 24 April 2019 |
Barriers to Strategic Manipulation in Voting. In this lecture we have explored three different ways of dealing with the problem raised by the Gibbard-Satterthwaite Theorem. The first approach is to limit the range of profiles on which we expect our voting rule to perform well. The best known such domain restriction is single-peakedness, which is a reasonable assumption in some cases and which constitutes a sufficient condition for the existence of a strategyproof voting rule. The second approach is one of the, by now, classical ideas in computational social choice: look for voting rules that, while not immune to manipulation, are resistant to manipulation in the sense that manipulation is computationally intractable for the manipulators to perform. We have seen that several standard voting rules do not enjoy this property, but STV does. We have also discussed the coalitional manipulation problem, in which computational intractability can often be achieved even for elections with small numbers of candidates (we have proved this for the weighted Borda rule). The third approach we have discussed is to work with the assumption that the manipulator does not possess full information about the voting intentions of others. We have seen the the antiplurality rule is not subject to strategic manipulation when voters only know which alternative is leading the polls (but when they do knot knows its margin of victory). On the other hand, we have also seen that some rules are subject to manipulation even when the manipulator has zero information. Here are a few of the papers that were cited in class:
|
|
| Thursday 25 April 2019 |
Tutorial: Feedback on Homework #1 |
|
| Tuesday 30 April 2019 |
Automated Reasoning for Social Choice Theory. An exciting but still underexplored research direction in computational social choice is to use a SAT solver to automatically reason about social choice scenarios. So far this technique has mostly been used to establish impossibility theorems for specific (small) numbers of voters and alternatives (which can then be generalised to arbitrary numbers of voters and alternatives using theoretical arguments). Much of this lecture has been devoted to an in-depth exposition of how this technique can be used to prove the Gibbard-Satterthwaite Theorem. Consult this paper for an introduction to the approach:
Note: The proof of Lemma 3 on the slides is not entirely correct (F' might not be nondictatorial). To get a working proof, repeat the construction shown for all sets of three alternatives. For at least one of them, the function F' constructed will have all the required properties. |
|
| Wednesday 1 May 2019 |
Voting in Combinatorial Domains. 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. To date, the most promising approaches are distance-based procedures, sequential voting, and voting with compactly expressed preferences.
|
Homework #3 (due: Tuesday, 7 May 2019) |
| Thursday 2 May 2019 |
Tutorial: Feedback on Homework #2 and Help with Working with the SAT Solver |
|
| Tuesday 7 May 2019 |
Basic Judgment Aggregation. In this introductory lecture on judgment aggregation we saw a motivating example (the famous doctrinal paradox), several options for defining a formal model, a number of specific judgment aggregation rules, and the original impossibility theorem for judgment aggregation. Much of this material is covered in Chapter 17 of the Handbook:
|
|
| Wednesday 8 May 2019 |
Strategic Behaviour in Judgment Aggregation (guest lecture by Sirin Botan). Sirin discussed different forms of strategic behaviour in judgment aggregation, focusing on strategic manipulation by a single agent. The main result she presented was the characterisation of the judgment aggregation rules that are strategyproof for agents with arbitrary closeness-respecting preferences as those rules that are both independent and monotonic. You can read up on this result here:
|
|
| Thursday 9 May 2019 |
Tutorial: Feedback on Homework #3 |
|
| Tuesday 14 May 2019 |
Advanced Axiomatics of Judgment Aggregation. We saw several further applications of the axiomatic method on judgment aggregation: an axiomatic characterisation of the quota rules, a logical characterisation of the class of agendas for which the majority rule is guaranteed to return a consistent judgment set, and a logical characterisation of the class of agendas for which there exists a judgment aggregation rule meeting certain axiomatic requirements. The proof technique used to establish the latter result was reminiscent of our proof of Arrow's theorem earlier on in the course. You can read up on all of this material here:
|
Homework #4 (due: Monday, 20 May 2019) |
| Wednesday 15 May 2019 |
Computational Complexity of Judgment Aggregation (guest lecture by Ronald de Haan). Ronald explained how tools from complexity theory are used in the field of judgment aggregation. He discussed the complexity of both the outcome determination and the manipulation problem for the Kemeny rule, as well as the complexity of the safety of the agenda problem for the majority rule. Here is one of his papers on this topic:
|
|
| Tuesday 21 May 2019 |
NO CLASS |
Registration Deadline for Advanced Topics in Computational Social Choice |
| Wednesday 22 May 2019 |
Future Directions. This final lecture has been a review of a number of possible directions for future research in computational social choice that, to me, look particularly promising and exciting. Some of them are discussed in much more detail in this book:
|
|
| Thursday 23 May 2019 |
Tutorial: Feedback on Homework #4 |
|
| Summer 2019 |
There are several great summer schools taking place this year that cover topics that are directly relevant to this course and that some of you may want to consider attending: The biannual Advanced Course in AI sponsored by the European Association for Artificial Intelligence this year will focus on topics in Multiagent Systems and will be held in Chania on 1-5 July 2019. There will be a summer school on Preferences, Decisions and Games in Paris on 25-28 June 2019. And finally there will be a two-day summer school on Voting and Matching on 10-11 June 2019 associated with the Conference on Economic Design taking place in Budapest this year. |