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).
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
| Date | Content | Homework | ||
|---|---|---|---|---|
| Wednesday 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:
|
|||
| Friday 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:
|
Homework #1 (due: 11 February 2015) | ||
| Wednesday 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:
|
|||
| Friday 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) | ||
| Tuesday 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. |
|||
| Wednesday 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:
|
|||
| Friday 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:
|
Homework #3 (due: 25 February 2015) | ||
| Tuesday 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:
|
|||
| Wednesday 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) | ||
| Tuesday 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. |
|||
| Wednesday 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:
|
|||
| Friday 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) | ||
| Tuesday 10 March 2015 |
We met to discuss how to write a paper. |
|||
| Thursday 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. |
|||
| Friday 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:
|
|||
| Tuesday 17 March 2015 |
We met to discuss how to give a talk. |
|||
| Wednesday 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:
|
|||
| Thursday-Friday 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). |
|||
| Tuesday-Wednesday 24-25 March 2015 |
Here is the the programme for the final presentations:
|
|||
| Tuesday 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. |
|||
| Monday-Friday 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.