Computational Social Choice 2015 (February-March)

Social choice theory is the study of mechanisms for collective decision making, such as voting rules or protocols for fair division, and computational social choice addresses problems at the interface of social choice theory with computer science. This course will introduce some of the fundamental concepts in social choice theory and related disciplines, and it will expose students to current research at the interface of social choice theory with logic and computation. This is an advanced, research-oriented course in the Master of Logic programme. Students from AI, Computer Science, Mathematics, Economics, Philosophy, etc. are also very welcome to attend (contact me if you are unsure about your qualifications).

This page will be updated throughout the semester, with links to the slides used in class, literature recommendations, homework assignments, and information on possible changes in the schedule. Please check it regularly.

Update (January 2016): This edition of the course has be particularly fruitful, with three of the student mini-projects leading to peer-reviewed publications.

Scheduling: We have slots for classes on Tuesdays, Wednesdays and Fridays, but we won't use all of these slots, and we will not always stick to the label ("lecture" vs. "tutorial") shown in the official schedule. You are expected to be available during the exam week for presentations (details to be announced around the middle of the course).

Prerequisites: I will expect what is sometimes called mathematical maturity, meaning that you should have some experience with writing up mathematical proofs. The required background in logic is minimal (basic concepts from propositional logic only).

Focus 2015: For this edition of the course, I plan to specifically 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. As a fully fledged research area, JA is only a little over 10 years old, so you will not only be able to get a fairly complete view of the field, but you will also be exposed to current research. Other topics in computational social choice will get introduced briefly as time permits; interested students will be able to further explore those later on during (individual) projects outside of this course.

See also: previous editions of the course and the Computational Social Choice Seminar at the ILLC

4 February 2015

Introduction. This first lecture has been a bit of a sightseeing tour of computational social choice, with lots of examples for problems addressed, results obtained, and techniques employed in four different subfields of this research area: fair allocation of goods, voting in elections, two-sided matching, and judgment aggregation. 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. For an introduction to computational social choice, focusing mostly on voting (and a little on fair allocation), consult this paper:

Please spend some time with this paper, to allow you to appreciate the wider field of computational social choice and to be able to put in context the more specific material we will explore in the coming weeks. For more details on, first, fair allocation and, second, the axiomatic method (two of the larger topics explored in this lecture), consult these references: And here are two famous classical papers mentioned during this lecture, both of which are very short and still highly readable today: At the end of the lecture we have also discussed various organisational aspects of the course.

6 February 2015

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 formal framework of judgment aggregation we shall be working with (in fact, later on in the course we will also see an alternative such framework). The specific aggregation rules discussed were the majority rule, premise-based rules, and quota rules. 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 framework to study the kinds of questions raised by the observation of the doctrinal paradox 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: 11 February 2015)
11 February 2015

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. 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. Besides the survey paper cited earlier, the main reference for this lecture is the following paper on quota rules:

13 February 2015

Aggregation Rules. In the first part of this lecture we have introduced a second framework for aggregation, namely binary aggregation with integrity constraints (BA). In some sense (left imprecise), it can be used to model the same types of problems we can model using the formula-based framework of judgment aggregation (JA). We have then seen how to translate both JA and classical preference aggregation into BA. Our main goal for this lecture has been to enrich our corpus of specific aggregation rules, beyond the very simplistic idea of working with quotas treated before. We did so taking inspiration from classical rules for voting and preference aggregation (specifically: Slater, Kemeny, Tideman, Copeland, Borda, and Maximin) and we have shown how to simulate these rules in BA by combining a suitable integrity constraint with a suitable optimisation rule awarding points for respecting (weighted) majorities in the outcome as much as possible. Here are the two main references for this lecture:

Homework #2
(due: 18 February 2015)
17 February 2015

Tutorial on Complexity Theory. This has been a quick review of basic concepts from the theory of computational complexity. We have seen the definition of several complexity classes, including P, NP, coNP, PSPACE, and some of the less well-known classes defined in terms of NP-oracles. We have also seen what it means for a problem to be hard or complete with respect to such a class, and we have gone over a couple of NP-completeness proofs using polynomial-time reductions.

18 February 2015

Winner Determination. This has been a lecture on the computational complexity of the winner determination problem in judgment aggregation. We discussed the best way of defining the problem in some detail, and then saw that winner determination is easy for quota rules and the premise-based rule (in case our usual assumptions guaranteeing consistent and complete outcomes for this rule hold), and that the max-sum rule (also known as the Kemeny rule of the distance-based rule) is highly intractable. These results were taken from the following paper:

At the end of the lecture we have also discussed possible approaches you could take to identify a suitable topic for a mini-project.

20 February 2015

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 characterisation of the agendas that are safe for (a) just the majority rule and (b) the class if 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, and we have discussed the connections to some axiomatic impossibility and characterisation results reviewed earlier on in the course. Here are the two main original papers from which the definitions and results presented are drawn:

Most of this material is also covered in this expository paper:
  • 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. In press (2015).

Homework #3
(due: 25 February 2015)
24 February 2015

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 to 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 original papers:

But note that the formal frameworks used in those papers differ somewhat from the framework used in the course. For a clear exposition of these theorems and most other known existential agenda characterisation theorems, refer to the survey by List and Puppe listed below. For full proofs of the two theorems discussed in class, consult my handbook chapter.
  • C. List and C. Puppe. Judgment Aggregation: A Survey. In P. Anand, P. Pattanaik, and C. Puppe (eds.), Handbook of Rational and Social Choice. Oxford University Press, 2009.
  • 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. In press (2015).

25 February 2015

Lifting Integrity Constraints. At the beginning of this lecture we have introduced the framework of binary aggregation with integrity constraints a little more systematically than last time. Then we have used it to investigate the concept of collective rationality in some depth and asked what kinds of rules can "lift" what kinds of integrity constraints from the individual to the collective level, in the sense of ensuring that the outcome will satisfy the constraint whenever all of the individual ballots do. This has allowed us to make connections between axioms, on the one hand, and syntactic restrictions on the language used to express integrity constraints, on the other. In the end, we have asked whether there are any rules that would lift all possible integrity constraints. There indeed are such rules, including some very bad rules (e.g., dictatorships) as well as some intuitively attractive rules (e.g., the average-voter rule). The lecture was based on the following two papers:

Homework #4
(due: 4 March 2015)
3 March 2015

We met to discuss your project ideas and to clarify what you need to submit to me to get your project approved.

4 March 2015

Strategic Behaviour. In this lecture we have considered what happens when agents act strategically when choosing what judgment set to report. We have seen that, for certain assumptions on the preferences of the agents, a judgment aggregation rule is strategy-proof (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 have argued that this means full protection against strategic behaviour is only possible in the rarest of circumstances. We have then discussed the idea of using computational complexity as a barrier against strategic manipulation and showed that the premise-based procedure is NP-hard to manipulate. Finally, we have briefly reviewed a number of other approaches of bringing strategic behaviour into JA, namely bribery and various forms of control of the set of agents taking part. Here are the main papers in which this material is covered:

6 March 2015

Truth-Tracking. The first part of this lecture has been a short introduction to the epistemic approach to judgment aggregation, where we assume that there is an objectively correct answer to the questions under consideration and each agent reports a perturbed copy of this ground truth. The task of an aggregation rule then becomes to recover the ground truth as well as possible. This idea goes back to the classical Condorcet Jury Theorem of the 18th century, and we have discussed a small number of variants of this result, including the computation of optimal weights for the agents in view of their accuracy and the estimation of those accuracies from the perturbed input data itself.

In the second part of the lecture I have tried to offer a high-level overview of the ground covered in the nine lectures on judgment aggregation, focusing on the range of different methodologies employed: adopting either a philosophical, mathematical, computational, game-theoretical, or statistical perspective on the same problem of aggregating the judgments of a group of agents into a single judgment.

Homework #5
(due: 13 March 2015)
10 March 2015

We met to discuss how to write a paper.

12 March 2015

Suggestion: You might be interested in attending the seminar talk by Christian List (London School of Economics), entitled From Degrees of Belief to Beliefs: Lessons from Judgment-Aggregation Theory, at 15:00.

13 March 2015

Fair Allocation. This has been a short introduction to fair allocation problems. First, we have seen several criteria that can be used to assess the fairness and economic efficiency of an allocation of goods to the members of a group of agents. Then we have focussed on the allocation of indivisible goods and seen examples for two types of results: the complexity of computing a socially optimal allocation and the convergence to a socially optimal allocation by means of a sequence of local deals. Much of what we have discussed is also covered in my lecture notes:

17 March 2015

We met to discuss how to give a talk.

18 March 2015

Matching. This lecture has been a brief introduction to the theory of two-side matching. We have discussed the classical stable marriage problem, analysed the Gale-Shapely algorithm for computing a stable matching for this setting, talked about various extensions of the basic model, and considered various requirements beyond stability, notably fairness and strategy-proofness. Here is the classical paper on the topic by Gale and Shapley:

Further information on the use of the Gale-Shapley algorithm to match school children to schools in Amsterdam is available here and here (in Dutch).

19-20 March 2015

Suggestion: You are welcome to attend the ILLC Workshop on Collective Decision Making (but please make sure you register at least one week in advance).

24-25 March 2015

Here is the the programme for the final presentations:

  • Arianna, Merlijn and Sirin
    Group Manipulation in Judgment Aggregation
  • Edwin, Maarten, Marysia and Richard
    Virtuous Manipulation in Binary Aggregation
  • Elise and Sharon
    Empirical Evaluation of Quota Rule Consistency in Binary Aggregation
  • Kristina and Zeno
    New Complexity Results for Bundling Attacks
  • Roelof and Tim
    Judgment Aggregatio with Abstentions
  • Carla and Marco
    Binary Aggregation under Issue Dependencies
We start at 11:00 sharp on both days.

21 April 2015

Suggestion: You might be interested in the ABC Symposium on Decision Making. At this event people will be looking into decision making (probably mostly individual rather than collective decision making) from a somewhat different angle, including in particular the perspective of cognitive science. Note that space is limited and to ensure you get in you will have to register early.

13-17 July 2015

Suggestion: Apply for the Summer School on Fair Division in Grenoble, organised by COST Action IC1205 on Computational Social Choice. There are a number of travel grants available, which should cover most of your expenses. MSc Logic students can get 2EC for this (but see the rules). Students from other programmes should check with their programme director first.


Mini-Projects: During the second part of the course you will work on a small research project on a topic related to JA of your choice, 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.

Here are some suggestions for possible topics:

Projects are to be worked on in groups. I strongly prefer groups of three people each, but if necessary will approve a couple of groups of size two or four as well. The final deadline for seeking approval of your project (group composition and topic) by me is Wednesday, 4 March 2015. To make this deadline, you will need to approach me with fairly concrete ideas at least a week in advance. To request approval of your project, send me an email in which you answer the following three questions:

Arrange a meeting with me, preferably in the period of 13-18 March 2015. You should be half-done with your project by the time we meet and have a list of concrete issues you want my advice on.

The groups and project topics are now (6 March 2015) fixed:

Each group will present their project during a 20-minute talk in the exam week. The presentations will be held on Tuesday, 24 March 2015 at 10:30-13:00 and Wednesday, 25 March 2015 at 11:00-13:00. You are expected to be present for all talks and contribute by asking relevant questions.

Your paper must be 4-5 pages long, including 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). Keep in mind that the paper you write is your main deliverable, even if your project has a large implementation or experimental component. The submission deadline is at 23:59 AoE on Wednesday, 1 April 2015.