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 fastmoving field. This is an advanced, researchoriented 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).
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 wellstudied 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.
Date  Content  Homework 

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:

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 truthtracking 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 MullerSatterthwaite 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 GibbardSatterthwaite 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 MullerSatterthwaite Theorem). You can read up on the proof here:
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:


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 maxapproval mechanism and the greedy loadbalancing 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 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:

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 indepth exposition of how this technique can be used to prove the GibbardSatterthwaite Theorem. Consult this paper for an introduction to the approach:


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:


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 cakecutting problem. You can read up on the basics in my lecture notes:

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 5minute 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 45 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):
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 onepage PDF on Canvas in which you answer the following three questions: