Computational Social Choice 2022

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: Julian Chingoma and Simon Rey
• Assessment: homework (50%) and mini-project (50%)
• Canvas: homework submission and announcements
• Datanose: schedule

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 2022: For this edition of the course, we will focus on judgment aggregation. Suppose you have a number of statements that might be either true or false, and several agents each give you their opinion on which of those statements they consider true. How should you aggregate this information to come to a collective decision that accurately reflects the views of the group as a whole? And is that the same as asking which of those statements actually are true? This problem shows up in a wide variety of domains, ranging from judicial courts to applications in AI such as multiagent systems or crowdsouring. We will investigate it from all sorts of different angles, using methods that would commonly be associated with Philosophy, Economics, Mathematics, Logic, and Computer Science. Other topics in computational social choice will get introduced briefly as time permits.

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 Seminars: You are always welcome to attend our local COMSOC Seminar as well as the international COMSOC Video Seminar.

Date	Content	Homework
Tuesday 6 September 2022	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 will largely focus on judgment aggregation and revisit some of the ideas and techniques so far only mentioned in the context of other domains of aggregation. The main example for a technical result we saw was May's Theorem on the axiomatic characterisation of the simple majority rule in elections with just two alternatives. The original paper is a great example for a seminal piece of work that's still very much readable today, 70 years after it was published. K.O. May. A Set of Independent Necessary and Sufficient Conditions for Simple Majority Decision. Econometrica, 1952.	Please read the historical (not the technical) parts of 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 7 September 2022	Basic Judgment Aggregation. This has been an introduction to the basic theory of judgment aggregation. We started with a discussion of the famous doctrinal paradox and then defined the main formal model of judgment aggregation we shall be working with. We then discussed the majority rule, quota rules, and premise-based aggregation as concrete examples for how to take a collective decision. Finally, we introduced the axiomatic method for judgment aggregation, discussed three specific axioms, and proved the impossibility theorem due to List and Pettit. I strongly recommend that you read their original paper, which also was the first to propose a formal social choice-theoretic model to study the kinds of questions raised by the observation of the doctrinal paradox by legal scholars some years earlier: C. List and P. Pettit. Aggregating Sets of Judgments: An Impossibility Result. Economics and Philosophy, 2002. The following two expository papers cover most of the material discussed in this lecture (and much more) and may serve as general references also for a significant part of the rest of the course: C. List. The Theory of Judgment Aggregation: An Introductory Review. Synthese, 2012. 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 #1 (due: Tuesday 13 September 2022)
Tuesday 13 September 2022	Axiomatic Method. This lecture has been about several examples for the use of the axiomatic method. In the first part, we explored different ways of circumventing the basic impossibility theorem of judgment aggregation, by using domain restrictions or by weakening some of our axioms or collective rationality requirements. In the second part, we had a closer look at our axioms and discussed how to think about them in terms of winning coalitions. We then used the insights gained to establish several axiomatic characterisation results for the quota rules (and the majority rule in particular). The latter results come from the following paper, which also discusses a number of other issues related to quota rules: F. Dietrich and C. List. Judgment Aggregation by Quota Rules: Majority Voting Generalized. Journal of Theoretical Politics, 2007.
Wednesday 14 September 2022	Embedding Preference Aggregation. In this lecture I tried to illustrate how we can use judgment aggregation as a powerful modelling tools to talk about collective decision making scenarios in other domains (that are not, at least not in an immediate sense, about forming judgments). Specifically, we saw how to embed preference aggregation into judgment aggregation and how to use this embedding simulate a number of well-known voting rules with the framework of judgment aggregation. To do so, we slightly generalised our model of judgment aggregation to allow for the distinction between rationality (input) and feasibility (output) constraints. We also defined two judgment aggregation rules we had not seen before, namely the Kemeny and the Slater rule. To find out more about this approach of modelling voting in judgment aggregation, consult the following paper: U. Endriss. Judgment Aggregation with Rationality and Feasibility Constraints. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.	Homework #2 (due: Tuesday 20 September 2022)
Tuesday 20 September 2022	Crash Course on Complexity Theory 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.
Wednesday 21 September 2022	Outcome Determination. In this lecture we analysed the computational complexity of the core problem in judgment aggregation, namely that of computing the outcome for a given profile under a given aggregation rule. We saw that the complexity of this problem can range from the trivial to the highly intractable, depending on the aggregation rule at hand. Specific technical results aside, two important insight we gained were, first, that subtle details of the formal model we use to specify aggregation scenarios can have a significant impact on our ability to design efficient algorithms for them and, second, that formulating a suitable decision problem for our formal analysis that adequately reflects the practice of solving real-world search problems is not always straightforward. For further reading, you could have a look at this paper about identifying scenarios of practical interest for which aggregation rules that in general are intractable can be implemented efficiently: R. de Haan. Hunting for Tractable Languages for Judgment Aggregation. Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2018.
Tuesday 27 September 2022	Strategic Behaviour In this lecture we considered what happens when agents act strategically when choosing what judgment set to report. We saw that, for certain assumptions on the preferences of the agents, a judgment aggregation rule is strategyproof (i.e., never gives an agent an incentive to misreport their judgments) if and only if that rule is both independent and monotonic, and we argued that this means full protection against strategic behaviour is only possible in the rarest of circumstances. We then discussed the idea of using computational complexity as a barrier against strategic manipulation and showed that the premise-based rule is NP-hard to manipulate. Finally, we briefly reviewed a number of other approaches of bringing strategic behaviour into JA, namely coordinated manipulation by groups of agents, bribery, and various forms of control of the set of agents taking part. Here are the papers containing the technical results proved in class: F. Dietrich and C. List. Strategy-Proof Judgment Aggregation. Economics and Philosophy, 2007. U. Endriss, U. Grandi, and D. Porello. Complexity of Judgment Aggregation. Journal of Artificial Intelligence Research (JAIR), 2012.	Homework #3 (due: Tuesday 4 October 2022)
Wednesday 28 September 2022	Safety of the Agenda. The problem of the safety of the agenda is the problem of checking whether a given agenda is safe for a given class of aggregation rules in the sense of guaranteeing that there will never be an inconsistent outcome for any admissible profile for that agenda and any rule from that class. We have given logical characterisations of the agendas that are safe for (a) just the majority rule and (b) the class of rules we obtain when we drop the monotonicity axiom for the axiomatisation of the majority rule. We have also discussed the (very high!) computational complexity of deciding whether a given agenda has one of the relevant properties. Besides the original papers on the slides, you can consult the Handbook chapter on judgment aggregation for full details.
Tuesday 4 October 2022	Agenda Characterisation This lecture has been devoted to agenda characterisation results that establish correspondences between the logical properties of the agenda and the axioms satisfied by an aggregation rule. More specifically, such results identify those agendas for which there exists an aggregation rule meeting certain axioms that will always return a consistent judgment set. Thus, these existential agenda characterisation results are dual to the universal agenda characterisation results, establishing the safety of the agenda for all rules meeting certain axioms, discussed in the previous lecture. We have also briefly discussed the connection of one of these results to Arrow's Theorem, the seminal result in preference aggregation that started modern social choice theory. The agenda characterisation theorems for judgment aggregation discussed are taken from the following two papers: K. Nehring and C. Puppe. The Structure of Strategy-proof Social Choice. Part I: General Characterization and Possibility Results on Median Space. Journal of Economic Theory, 2007. E. Dokow and R. Holzman. Aggregation of Binary Evaluations. Journal of Economic Theory, 2010.
Wednesday 5 October 2022	Overview of JA + Plenary Progress Meeting. We talked about how to write a paper and how to write a review.
Friday 7 October 2022	Participatory Budgeting (Guest Lecture by Simon Rey). This has been an introduction to participatory budgeting, a popular tool now used across the world to improve civic participation in democratic decision making---and also a hot topic in contemporary computational social choice research. Simon touched upon several of the methodological themes we saw earlier on in the course, notably axiomatic, computational, and game-theoretical concerns, and he discussed how to embed participatory budgeting into judgment aggregation.	Homework #4 (due: Tuesday 18 October 2022)
Friday 14 October 2022	Plenary Progress Meeting
Tuesday 18 October 2022	Cancelled: Automated Reasoning and Explainability in Social Choice
Wednesday 19 October 2022	Plenary Progress Meeting. We talked about how to give a talk.

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 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. 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 19:00 on Tuesday 27 September 2022
• Progress meeting (one per group): Monday-Wednesday, 3-5 October 2022
• Submission of 2-page draft: by 19:00 on Tuesday, 11 October 2022
• Bidding for reviews: by 15:00 on Wednesday, 12 October 2022
• Submission of review: by 19:00 on Monday, 17 October 2022
• Submission of slides: by 19:00 on Sunday, 23 October 2022 (evening before the talks)
• Submission of paper: by 19:00 on Friday, 28 October 2022
• Submission of collaboration statement: by 19:00 on Monday, 31 October 2022

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 judgment aggregation 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 we are a few weeks into course. 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 good number of papers on judgment aggregation 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 fairly 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 (because I will have to grade your project and naturally will be somewhat biased when it comes to my own work).
• Find an intersting domain of collective decision making and try to embed it into judgment aggregation. During lectures, we have seen this (or will see this) for two such domains, namely voting to elect a single alternative and participatory budgeting.
• Invent something new. For example, you could suggest a new aggregation rule and analyse its properties. Maybe this will be a rule that is particularly suited to specific aggregation problems, but not to others. Or you could suggest a new domain restriction, argue why this is a realistic restriction, and analyse to what extent it helps circumvent known problems in judgment aggregation.
• Analyse an existing aggregation rule For example, you could try to axiomatise an existing rule for which no axiomatisation is known to date. Or you could investigate the truth-tracking capabilities of an existing rule. Or you could analyse the complexity of an existing rule. Note that even the very best papers on JA by economists or philosophers are likely to not have considered the algorithmic aspects of the problem studied at all, so it may be perfectly feasible to fill in some gaps here.
• Explore the usefulness of judgment aggregation in the real world. You could investigate what kind of aggregation rules people are using in the real world (e.g., in the courts of different countries, or for crowdsourcing experiments), and how they justify those choices. In fact, while it is intuitively clear that judgment aggregation should be useful in many very different domains, nobody so far has tried to provide an overview of these domains. You could identify a new domain of application and investigate it in some detail, or you could try to compile an overview of actual and potential applications.
• 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 judgment aggregation rule can be manipulated in some profiles, it may be that those profiles are very rare in certain scenarios of practical relevance. For preference aggregation, you can find a lot of real-world data regarding people's preferences at PrefLib.org. You might be able to find similar data for judgment aggregation elsewhere, or you could think about using what we learned about embedding preference aggregation into judgment aggregation to generate relevant data yourself.
• Implement one or several aggregation rules. One option is to focus on a computationally intractable (but otherwise attractive) rule and develop an algorithm for it (e.g., based on heuristic-guided search, mathematical programming, or any other algorithmic technique you are familiar with). A second option is to focus on providing a user-friendly environment that allows for easy inspection, application, and comparison of several different rules. In the latter case, think about what a researcher may want to do with such a tool and demonstrate that your tool is indeed useful in this respect.

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 individual progress meeting with me.

Drafts and reviewing. As an intermediate step, each group will produce a 2-page draft, consisting of most of Section 2 (often called "The Model" in social choice papers), a few sentences of motivation (from Section 1), and a tentative outline (in the form of a bullet list) of what they still hope top do. Each draft will be anonymously reviewed by several students from the other groups (see how to write a review).

Talks. In the final week of the course, we are going to organise a mini-workshop where each group will present their work (see how to give a talk). Probably 20 minutes talk + 10 minutes for questions per group (to be confirmed). Every group member should contribute in some form.