Social choice theory is the study of mechanisms for collective decision making, such as voting rules or protocols for fairly dividing a set of goods, and computational social choice addresses problems at the interface of social choice theory with computer science. This course provides a thorough introduction to both classical and computational social choice, so as to enable students to conduct independent research in this field. This is an advanced, research-oriented course in both the Master of Logic and the MSc Artificial Intelligence. Students from Computer Science, Mathematics, Economics, Philosophy, etc. are also very welcome to attend (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 writing up mathematical proofs.
Focus 2017: For this edition of the course, I plan to specifically focus on voting theory. Other topics in computational social choice will get introduced briefly as time permits; interested students will be able to further explore those later on during (individual) projects outside of this course.
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 available free of charge.
See also: previous editions of the course, the Computational Social Choice Seminar at the ILLC, and the Dutch Social Choice Colloquium.
| Date | Content | Homework |
|---|---|---|
| Wednesday 5 April 2017 |
Introduction. 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. For the remainder of the course, we are going to largely focus on voting theory, but revisit some of the ideas and techniques we had so far only mentioned in the context of other domains of aggregation. |
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. |
| Thursday 6 April 2017 |
Voting Rules. 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. We have also looked into different ways in which to classify voting rules to get a better overview over the landscape of rules as a whole: in terms of the axioms they satisfy, in terms of the information they require, and in term of the computational complexity of using them. Some of this material (and a lot more) is covered in Chapter 2 of the Handbook:
|
Homework #1 (due: Wednesday, 12 April 2017) |
| Wednesday 12 April 2017 |
Characterisation Results. In this lecture we have seen three different approaches to the characterisation 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; (2) the truth-tracking approach, under which voting rules are taken to be maximum likelihood estimators to recover the objectively "best" alternative; and (3) the distance-based approach, under which we try rationalise a voting rule in terms of a notion of distance between profiles and a notion of consensus profile, where winners can be determined unambiguously. 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 two approaches, the best source is the chapter by Elkind and Slinko in the Handbook.
|
|
| Thursday 13 April 2017 |
Impossibility Results. 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.
|
Homework #2 (due: Thursday, 20 April 2017) |
| Wednesday 19 April 2017 |
Strategic Manipulation. 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:
|
|
| Thursday 20 April 2017 |
Tutorial on Computational Complexity by Ronald de Haan (only for those who need it). |
|
| Friday 21 April 2017 |
Coping with Strategic Manipulation. 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 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:
|
Homework #3 (due: Tuesday, 2 May 2017) |
| Friday 21 April 2017 |
Suggestion: You may be interested in the Special Session in Honour of Kenneth J. Arrow (1921-2017) of the Dutch Social Choice Colloquium, which will take place in the city centre in the afternoon. Note that advance registration is required. |
|
| Wednesday 26 April 2017 |
Information and Communication in Voting. In this lecture we have discussed a number of problems arising in situations in which only partial information regarding the ballots of the voters is available. We have modelled this partial information as a profile of partial orders over the set of alternatives. The main problem we discussed is the possible winner problem, in which we ask, for a given alternative x, whether it is possible to refine the given partial ballots to yield complete linear ballots such that x is a winner for the election. We have also seen how this problem, as well as the necessary winner problem, relate to questions in preference elicitation and election manipulation. On the technical side, we have discussed various complexity results for deciding whether a given alternative is a possible winner, for different voting rules and different assumptions regarding the nature of the missing information. Next, we have discussed the problem of compiling the information inherent in a partial ballot profile so as to still be able to compute the election winners once the remaining ballot information arrives. The minimum number of bits required to do this, for a given voting rule, is called the compilation complexity of that rule.
|
|
| Wednesday 3 May 2017 |
Iterative Voting. This lecture has been about iterative voting, a model in which voters keep on updating their own ballots in response to the sequence of profiles of ballots they observe. We have focused on understanding the circumstances under which such a process converges to a stable situation in which no voter wishes to change their ballot again. The main result discussed is taken from the following paper:
|
|
| Thursday 4 May 2017 |
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 #4 (due: Wednesday, 10 May 2017) |
| Wednesday 10 May 2017 |
Logic for Social Choice. In this lecture we have discussed three different approaches to formally modelling preference aggregation scenarios using logic. One approach has been to develop a tailor-made modal logic for preference aggregation, one has been to explore how far we can get by using classical first-order logic, and one has been to express representative small cases in propositional logic. We have exemplified these approaches by showing how to encode Arrow's Theorem. Here are three representative papers that were also mentioned in class:
|
|
| Thursday 11 May 2017 |
We discussed how to write a paper and reviewed progress on your projects. |
|
| Tuesday 16 May 2017 |
Suggestion: You may be interested in the talk by Yuliya Veselova in the Computational Social Choice Seminar. |
|
| Wednesday 17 May 2017 |
Multiwinner Voting Rules. This lecture has been an introduction to the topic of designing voting rules that can be used to elect a set of exactly k winning alternatives. We have seen how different application scenarios impose different (axiomatic) requirements and we have discussed several concrete proposals for rules. We have also briefly reviewed the related problem of fairly dividing parliamentary seats amongst political parties. As a starting point for finding out more about multiwinner elections, have a look at this paper:
|
|
| Thursday 18 May 2017 |
Guest Lecture on Judgment Aggregation by Sirin Botan. This has been an introduction to judgment aggregation, covering the doctrinal paradox, the basic formal framework and some axioms, examples for impossibility and characterisation results, and a brief discussion of strategic manipulation. For general background, consult these survey papers:
|
Homework #5 (due: Wednesday, 24 May 2017) |
| Friday 19 May 2017 |
We discussed how to give a talk. |
|
| Friday 19 May 2017 |
Suggestion: You may be interested in the talk by Umberto Grandi in the Computational Social Choice Seminar. |
|
| Wednesday 24 May 2017 |
Fair Allocation. This has been a short introduction to fair allocation problems. First, we have seen several criteria that can be used to assess the fairness and economic efficiency of an allocation of goods to the members of a group of agents. Then we have focussed on the allocation of indivisible goods and seen examples for two types of results: the complexity of computing a socially optimal allocation and the convergence to a socially optimal allocation by means of a sequence of local deals. Most of what we have discussed is also covered in my lecture notes, and much additional material can be found in the Handbook.
|
|
| Thursday 1 June 2017 |
Presentations. Start at 14:00 (sharp, arrive at least five minutes in advance). Each talk is for a maximum of 30 minutes, followed by questions for a maximum of 15 minutes. Talks are open to the public.
|
|
| Friday 2 June 2017 |
Presentations. Start at 10:00 (sharp, arrive at least five minutes in advance). Each talk is for a maximum of 30 minutes, followed by questions for a maximum of 15 minutes. Talks are open to the public.
|
|
| August 2017 |
Suggestion: You may be interested in the European Agent Systems Summer School in Gdańsk, which this year will cover several topics that are directly relevant to this course, such as decision making, game theory, mechanism design, and judgment aggregation, besides a number of other interesting topics, including epistemic logic, argumentation theory, reinforcement learning, model checking, verification, and machine ethics. The application deadline for student grants is on 5 June 2017. |
Mini-projects: During the second part of the course you will work on a small research project on a topic related to voting of your choice, 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. Information on possible topics will become available here during the initial phase of the course. Projects are to be worked on in groups of three (or possibly four) people each. Each group will present their project during a 30-minute talk in the exam week. You must be present for all talks. Your paper must be 4-5 pages long, including 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). Finally, you must meet all of the deadlines below (what these involve excatly 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, as long as a large component of your project is related to voting theory and as long as you make some use of some of the methods introduced in the course. Here are a few suggestions for how to go about identifying a topic:
Requesting approval of your project. Start talking to me about your tentative ideas sometime before the deadline mentioned above. To formally request approval of your project, send me an email in which you answer the following three questions:
Approved projects. Below is the list of approved projects: