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

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 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) 
Thursday 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 NPcompleteness and definitions of a few complexity classes beyond NP that are of particular relevance to computational social choice.  
Tuesday 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 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 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 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:

Homework #2 (due: Tuesday 13 April 2021) 
Tuesday 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:
 
Wednesday 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 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 20 April 2021) 
Thursday 15 April 2021 
Plenary Discussion: Project Ideas  
Tuesday 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:
 
Wednesday 21 April 2021 
TruthTracking 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:
 
Thursday 22 April 2021 
Plenary Discussion: Project Progress 
Homework #4 (due: Friday 30 April 2021) 
Wednesday 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:
 
37 May 2021 
Holidays  
Tuesday 11 May 2021 
Plenary Discussion: Project Progress  
Wednesday 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, logicbased 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) 
Wednesday 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 cakecutting problem. You can read up on the basics in my lecture notes:
 
Thursday 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 5minute 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 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: