Computational Social Choice 2021

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 AI. 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).

This page will be updated throughout the course, with links to the slides used in class, literature recommendations, and homework assignments. Please check it regularly. You may also be interested in previous editions of the course as well as the international COMSOC Video Seminar.

Prerequisites: I will expect what sometimes is called mathematical maturity, meaning that you should have some prior experience with working out and writing up mathematical proofs.

Special theme for 2021: The special theme for this edition of the course is the study of innovations in democratic decision making. This covers ideas such a liquid democracy and participatory budgeting. Still, most lectures will be about more established topics in computational social choice, starting with the study of voting rules to elect a single representative. During these lectures you will learn about many of the techniques typically used in the field, which you can then apply to the less well-studied topics belonging to our special theme.

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.


30 March 2021

Introduction. Following a brief introduction to the scope and nature of this course, we have reviewed a large number of voting rules, to illustrate some of the ideas people had over the years for how to conduct an election. Some of this material (and a lot more) is covered in Chapter 2 of the Handbook:

  • W.S. Zwicker. Introduction to the Theory of Voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (eds.), Handbook of Computational Social Choice. Cambridge University Press, 2016.

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 over the coming weeks.

30 March 2021

Voting Rules and Characterisation Results. In the first part of this lecture we have seen a few more examples for voting rules and we have observed that seemingly reasonable voting rules sometimes fail to satisfy certain natural axiomatic principles: runoff methods might violate the Participation Principle, cup rules might violate the Pareto Principle, and positional scoring rules might violate the Condorcet principle. We then have discussed the axiomatic method as an approach to characterising voting rules, where we explore the logical consequences of a number of normatively appealing postulates regarding the desired behaviour of a rule. I recommend reading May's classic paper, which is a nice example for an early application of the axiomatic method and still highly accessible today.

Homework #1
(due: Wednesday 7 April 2021)
1 April 2021

Crash Course in Complexity Theory. 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.

6 April 2021

Impossibility Theorems in Voting 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.

7 April 2021

Strategic Manipulation in Voting. 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 have 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:

We have then reviewed three approaches to circumventing the problem of manipulation: domain restrictions, computational barriers, and informational barriers. To find out more, have a look at these papers:

Homework #2
(due: Tuesday 13 April 2021)
13 April 2021

Liquid Democracy. This lecture has been an introduction to the topic of liquid democracy, centred around the fundamental idea of allowing voters to delegate their right to vote to a fellow voter. We discussed relevant research directions in this emerging field and we reviewed a sample of recent contributions to the study of liquid democracy in the area of computational social choice. Here are the two papers we discussed in slightly more technical depth than the rest:

I had also mentioned several papers that provide some broader discussion of liquid demiocracy and related research questions. You may want to start with this one:

14 April 2021

Participatory Budgeting. This has been an introduction to the topic of participatory budgeting, where we are looking for mechanisms to decide on a list of public projects to fund given the preferences of citizens and the constraints imposed by budget limitations. We have seen the widely used greedy approval mechanism as well as two variants, the max-approval mechanism and the greedy load-balancing mechanism. We have analysed the computational complexity of computing outcomes under these mechanisms and we have compared them in terms of a number of axiomatic properties, notably strategyproofness and proportionality. Here are the three main papers mentioned during this lecture:

Homework #3
(due: Tuesday 20 April 2021)
15 April 2021

Plenary Discussion: Project Ideas

20 April 2021

Multiwinner Voting. This has been an introduction to the topic of multiwinner voting, i.e., scenarios in which we need to elect a set of exactly k alternatives. We have considered two types of multiwinner voting rules, those based on approval ballots (which we may think of as a special case of the participatory budgeting mechanisms we discussed earlier) and those based on ranked ballots (generalising the classical model of voting discussed at the beginning of the course). For an introduction to the literature on multiwinner voting, have a look at this survey paper:

21 April 2021

Truth-Tracking in Voting (Guest Lecture by Simon Rey). This has been an introduction to the epictemic approach to social choice, where we interpret ballots as noisy views on some ground truth and try to use a social choice mechanism to recover that ground truth. Here are the main papers mentioned during the lecture:

22 April 2021

Plenary Discussion: Project Progress

Homework #4
(due: Friday 30 April 2021)
28 April 2021

Judgment Aggregation (Guest Lecture by Sirin Botan). This has been an introduction to judgment aggregation. We discussed the famous doctrinal paradox, saw how judgment aggregation generalises preference aggregation, reviewed a number of basic results in the field. A good place to start if you want to find out more is the original paper introducing the formal model of judgment aggregation:

3-7 May 2021


11 May 2021

Plenary Discussion: Project Progress

12 May 2021

Further Topics in Voting. In this lecture we have briefly reviewed a number of additional research topics in computational social choice regarding the theory of voting: combinatorial domains, incomplete preferences, possible and necessary winners, the compilation of intermediate election results, communication complexity, logic-based modelling of social choice scenarios, the use of automated reasoning tools, and justifying election outcomes. Our focus has been on voting in combinatorial domains. The technical results discussed in a little more detail come from this early paper on the topic:

Homework #5
(due: Wednesday 19 May 2021)
19 May 2021

Cake Cutting. We concluded the course with a brief excursion into the world of fair allocation problems and, more specifically, the famous cake-cutting problem. You can read up on the basics in my lecture notes:

Here is the paper mentioned briefly near the end of the lecture, with that great result showing that it is possible to design cake-cutting protocols with a bounded (albeit still very large) number of cuts that produce envy-free solutions for any number of agents:
  • H. Aziz and S. Mackenzie. A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016. (revised version)

20 May 2021

Plenary Discussion: Paper Writing




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 produce a 5-minute video to advertise that paper (this last part replaces the talks we would have organised under normal circumstances). 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):

A few general tips for how to write a paper are available.

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 innovations in democratic decision making and you must make use of some of the COMSOC techniques introduced during the course. My advice is to start thinking about possible ideas early, but to not settle on a specific topic until the third week of the course (when we'll get into the special theme). Here are some pointers to get you started:

Requesting approval of your project. Start talking to me about your tentative ideas well before the deadline mentioned above. To formally request approval of your project, upload a one-page PDF on Canvas in which you answer the following three questions: