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

This page will be updated throughout the course, with links to the slides used in class, literature recommendations, and homework assignments. Please check it regularly. You may also be interested in previous editions of the course.

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.

Schedule

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

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:

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:

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:

 

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:

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:

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:

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:

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.

 

Mini-Projects

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

A few general tips for how to write a paper are available.

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:

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:

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.