Computational Social Choice 2020


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

The course will be taught online, with the main meeting times being Tuesdays and Wednesday from 11:00 to 13:00. 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 2020: 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.

Schedule

DateContentHomework
Tuesday
31 March 2020
11:00

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 variety of 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.

Wednesday
1 April 2020
11:00

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 have then seen two different approaches for characterising voting rules: (1) the axiomatic method, which is about exploring the logical consequences of a number of normatively appealing postulates regarding the desired behaviour of a voting rule and (2) the truth-tracking approach, under which voting rules are taken to be maximum likelihood estimators to recover the objectively "best" alternative. 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. For the other approach, the best source is the chapter by Elkind and Slinko in the Handbook.

Homework #1
(due: Tuesday 7 April 2020)
Tuesday
7 April 2020
11:00

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.

 
Wednesday
8 April 2020
11:00

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 discussed the Duggan-Schwartz Theorem, which generalises this result to the case of irresolute voting rules. This required us to specify what assumptions we are willing to make about how a voter who is considering to manipulate will extend her preferences defined on individual alternatives to sets of alternatives.

Finally, we have briefly 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 14 April 2020)
Tuesday
14 April 2020
11:00

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:

 
Wednesday
15 April 2020
11:00

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:

Correction: The load-balancing mechanism defined on slide 16 in fact is different from the mechanism proposed by Aziz et al. (but it is similar to one of the mechanisms discussed by Brill et al. for the simpler setting of multiwinner voting, cited on the same slide).

Homework #3
(due: Tuesday 21 April 2020)
Tuesday
21 April 2020
11:00

Plenary Discussion of Project Ideas

 
Wednesday
22 April 2020
11:00

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:

 
Tuesday
28 April 2020
11:00

Plenary Discussion of Project Ideas

 
Wednesday
29 April 2020
11:00

Set Preferences. We often need to be able to model and reason about preferences that are combinatorial in nature, for instance, when electing a set of alternatives rather than a single alternative or when modelling strategic manipulation of an irresolute social choice function. While this issue has surfaced in various places earlier in the course, in this lecture it has been our main point of focus. We have reviewed ideas and results from two strands of the literature, preference extensions and voting in combinatorial domains. Here are two survey articles on these topics:

  • S. Barberà, W. Bossert, and P.K. Pattanaik. Ranking Sets of Objects. In S. Barberà, P. Hammond, and C. Seidl (eds.), Handbook of Utility Theory, Volume 2. Kluwer Academic Publishers, 2004.
  • J. Lang and L. Xia. Voting in Combinatorial Domains. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (eds.), Handbook of Computational Social Choice. Cambridge University Press, 2016.

Homework #4
(due: Thursday 7 May 2020)
Wednesday
6 May 2020
11:00

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:

We have also briefly discussed other applications of logic and automated reasoning in computational social choice.

 
Friday
8 May 2020
11:00

Tutorial: Help with Python and SAT Solving

Homework #5
(due: Tuesday 19 May 2020)
Wednesday
13 May 2020
11:00

Judgment Aggregation. 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. Much of this material is covered in Chapter 17 of the Handbook:

  • U. Endriss. Judgment Aggregation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (eds.), Handbook of Computational Social Choice. Cambridge University Press, 2016.
I also recommend that you have a look at the original paper introducing the formal model of judgment aggregation:

 
Tuesday
19 May 2020
11:00

Plenary Discussion of Project Progress, Paper Writing, and Video Production

 
Wednesday
20 May 2020
11:00

Cake Cutting. We concluded the course with a brief excursion into the world fair divsion 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)

 

 

Mini-Projects

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 organised for previous editions of the course). 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: