Computational Social Choice 2019 (April-May)


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

This page will be updated throughout the duration of the course, with links to the slides used in class, literature recommendations, and homework assignments. Please check it regularly. We are going to cover a broad range of topics, including the fair allocation of goods, voting theory, and judgment aggregation. Please note that the list of topics for each lecture indicated in the table below is tentative and still subject to change. Also note that we will only use a subset of the tutorial slots currently listed on Datanose (this will get updated as we go along).

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.

DateContentHomework
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:

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)

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:

  • Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

 
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:

  • S. Bouveret, Y. Chevaleyre, and N. Maudet. Fair Allocation of Indivisible Goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (eds.), Handbook of Computational Social Choice. Cambridge University Press, 2016.
Here are the two main papers, on picking sequences and on negotiating individually rational deals, we have discussed in this lecture:

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:

  • 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.
We have then seen two different approaches for characterising of 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.

 
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:

We have also briefly discussed the Duggan-Schwartz Theorem, which establishes a similar result for irresolute voting rules. A good exposition is available 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:

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

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.

  • 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 #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:

  • 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:

 
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:

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

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.