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

• Lecturer: Ulle Endriss (ILLC, University of Amsterdam)
• Teaching Assistants: Suzanne Bloks, Arthur Boixel, Simon Rey, Zoi Terzopoulou
• Assessment: homework (50%) and mini-project (50%)
• Canvas: online lectures, homework submission, and announcements

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.

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: 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. K.O. May. A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision. Econometrica, 20(4):680-684, 1952. E. Elkind and A. Slinko. Rationalizations of Voting Rules. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A.D. Procaccia (eds.), Handbook of Computational Social Choice. Cambridge University Press, 2016.	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. U. Endriss. Logic and Social Choice Theory. In A. Gupta and J. van Benthem (eds.), Logic and Philosophy Today. College Publications, 2011. A.K. Sen. The Impossibility of a Paretian Liberal. Journal of Political Economics, 78(1):152-157, 1970.
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: U. Endriss. Logic and Social Choice Theory. In A. Gupta and J. van Benthem (eds.), Logic and Philosophy Today. College Publications, 2011. 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: D. Black. On the Rationale of Group Decision-Making. The Journal of Political Economy, 56(1):23-34, 1948. V. Conitzer, T. Sandholm, and J. Lang. When are Elections with Few Candidates Hard to Manipulate? Journal of the ACM, 54(3), Article 14, 2007. A. Reijngoud and U. Endriss. Voter Response to Iterated Poll Information. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012.	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: M. Brill and N. Talmon. Pairwise Liquid Democracy. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018. A. Kahng, S. Mackenzie, and A.D. Procaccia. Liquid Democracy: An Algorithmic Perspective. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018. 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: J. Green-Armytage. Direct Voting and Proxy Voting. Constitutional Political Economy 26:190-220, 2015.
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: A. Goel, A.K. Krishnaswamy, S. Sakshuwong, and T. Aitamurto. Knapsack Voting for Participatory Budgeting. ACM Transactions on Economics and Computation, 7(2):8, 2019. N. Talmon and P. Faliszewski. A Framework for Approval-based Budgeting Methods. Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019. H. Aziz, B.E. Lee, and N. Talmon. Proportionally Representative Participatory Budgeting: Axioms and Algorithms. Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018. 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: P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon. Multiwinner Voting: A New Challenge for Social Choice Theory. In U. Endriss (ed.), Trends in Computational Social Choice. AI Access, 2017.
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: C. Geist and D. Peters. Computer-Aided Methods for Social Choice Theory. In U. Endriss (ed.), Trends in Computational Social Choice. AI Access, 2017. 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: C. List and P. Pettit. Aggregating Sets of Judgments: An Impossibility Result. Economics and Philosophy, 18(1):89-110, 2002.
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: U. Endriss. Lecture Notes on Fair Division. ILLC, University of Amsterdam, 2009. 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)

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

• Project approval request: by 18:00 on Tuesday, 28 April 2020
• Progress meeting: must be sometime during 11-15 May 2020 (upload meeting agenda at least 24 hours before the meeting)
• Submission of paper, video, and contribution statement: by 23:59 AoE on Friday, 29 May 2020

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:

• Find a relevant paper you like and complement it in some way. For example, maybe you can come up with better proofs of the main results, maybe you can generalise or extend some of the results, maybe you can strengthen some of the results by restricting attention to interesting special cases, or maybe you can obtain new insights by varying the methods used in the original paper (e.g., by adding an algorithmic perspective to a paper that is largely axiomatic, or vice versa). Good places to look for relevant papers are recent editions of AAMAS, IJCAI, and AAAI. For papers published in the AI literature, I recommend checking these conferences first, but note that in some cases you may find a longer and more mature version in a journal, such as JAIR or AIJ. In the economics literature, you will find large number of papers on voting in the specialised journal Social Choice and Welfare and a few more in the much broader JET. At the interface with philosophy, a relevant journal is Economics and Philosophy. At the interface with theoretical computer science, have a look at EC (a conference) and TEAC (a journal). While this is not a hard rule, I recommend that you focus your search on papers that have been published very recently. This makes it more interesting and gives you a better chance managing to do something original. Please note that my own papers are off limits for this exercise.
• Find a real-world instance of democratic decision making and provide a social choice-theoretic analysis. For example, think of primaries to choose the candidate to represent a political party in a national election, the famous electoral college, or the problem of gerrymandering during redistricting. And there certainly are also still lots of unexplored questions in the areas of participatory budgeting (e.g., exploring models that do not rely on approval ballots), liquid democracy, and decision making in the context of social networks more generally.
• Find a theoretical concept or result that appeals to you and analyse it experimentally. To date, most research in COMSOC is of a theoretical nature and aimed at uncovering fundamental principles. This theoretical perspective is important and a strict requirement for any serious domain of scientific inquiry, but it should eventually be complemented with suitable empirical studies. For your project, you could choose a theoretical result from the COMSOC literature (possibly, but not necessarily, one we have covered in class) and investigate its practical relevance. For example, while we know that every rule can be manipulated in some profiles, it may be that those profiles are very rare in certain voting scenarios of practical relevance. You can find a lot of real-world data regarding people's preferences at PrefLib.org.

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:

• What are the names and email addresses of the members of your group?
• What is the goal of your project?
• How will you get started on your project? For example, what paper will you study in depth, or what definitions will you write up properly, or what data will you collect, or what basic methods will you implement? This should be something you can do before you have your progress meeting with me.