Computational social choice is an interdisciplinary field of research at the interface of social choice theory and computer science. Social choice theory is the study of mechanisms for collective decision making, such as different election systems or protocols for fair division. Computational social choice is concerned with the application of computational techniques to the study of such mechanisms, and with the integration of social choice paradigms into computing. This course will introduce some of the fundamental concepts in social choice theory and related disciplines, and expose students to current research at the interface of social choice theory with logic and computation. This is an advanced course in the Master of Logic programme. Students from AI, 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, coursework assignments, and information on possible changes in the schedule. Please check it regularly.
See also: the 2008 edition of this course and the Computational Social Choice Seminar at the ILLC
| Week | Date | Content | Coursework |
|---|---|---|---|
| 1 | 4 February 2009 |
Introduction (4up). This introductory lecture consisted of two parts. The first part has been about illustrating some of the problems we are going to address in the course, mostly by way of example. To get a better impression what the field is about you should also browse a little through the following papers:
In the second part of the lecture we have discussed the proof of Arrow's famous impossibility theorem. Here are links to the two (very short) papers I have used to prepare the slides for this part:
Tutorial on Thursday: Game Theory (4up) |
|
| 2 | 11 February 2009 |
Voting Theory (4up). This has been an introduction to voting theory. Voting is a central topic in social choice theory, because voting rules provide fundamental means of reaching a collective decision. The aim of the lecture has been to introduce a large number of alternative voting rules, and to discuss how they either satisfy or violate various desirable properties. We have paid particular attention to the issue of manipulation and briefly introduced the Gibbard-Satterthwaite Theorem. Most of the material covered may be found in more detail in the following paper:
Tutorial on Thursday: Complexity Theory (4up) |
Coursework #1 (Deadline: 25/02/2009) |
| 3 | 18 February 2009 |
Complexity of Voting (4up). This lecture has given an introduction to research into the computational complexity of voting. This is an interesting perspective to take for several reasons. First, for an attractive voting rule it should not be too hard to determine who won the election, and complexity theory can help make this issue precise. Second, computational intractability may serve as a barrier against manipulation or other forms of election control, and complexity theory can help us to identify voting rules with that property. Here are the main papers for this lecture:
|
|
| 4 | 25 February 2009 |
Preference Representation (4up). We have reviewed several languages for representing the preferences of individual agents and discussed their properties, including expressive power, comparative succinctness, and complexity. Succinctness, in particular, is important in combinatorial domains, such as negotiation over indivisible goods or elections of committees. We have covered both utility functions and ordinal preference relations; the languages discussed include explicit representations, the k-additive form, weighted propositional formulas, and prioritised goals. Refer to the following papers for further details:
|
|
| 5 | 4 March 2009 |
Voting in Combinatorial Domains (4up). The alternatives to vote for in an election often have a combinatorial structure: a collective decision regarding the instantiation of several variables needs to be made. Examples include elections of committees and multiple referenda. Voting for combinations of values explicitly is problematic, because of the prohibitively large number of alternatives, while voting issue-by-issue can easily lead to unrepresentative results. In this lecture we have explored some of the approaches that have been suggested to address this problem. This includes, in particular, the ideas of combinatorial vote and of sequential vote. Here are some of the papers cited during the lecture:
|
Coursework #2 (Deadline: 18/03/2009) |
| 6 | 11 March 2009 |
Judgement Aggregation (4up). This has been an introduction to the theory of judgement aggregation, which studies the problem of aggregating a set of individual judgements on the acceptability of a range of logically related propositions into a single collective set of judgements. We have seen that there are impossibility results, showing that no judgement aggregation procedure can satisfy a number of seemingly reasonable axioms, and we have also seen that there are several ways around such impossibilities, if we are willing to weaken some of the axioms. This approach has led to several concrete judgement aggregation procedures. We have also discussed various connections to the the standard model of social choice, which is concerned with preference aggregation. For an outline of much of the material covered as well as references to the original sources, consult the following paper:
|
|
| 7 | 18 March 2009 |
Social Welfare Orderings (4up). We have introduced the concept of a social welfare ordering (SWO) and that of a collective utility function (CUF), and we have discussed some of their properties. These concepts provide well-defined ways of assessing the quality of a collective agreement (such as an allocation of resources to agents) in terms of social welfare. The lecture has concentrated on some of the fundamental results in the field, such as the representability of certain SWOs by means of CUFs and the axiomatisation of certain SWOs. We have largely followed the first two chapters of the book by Moulin. The actual SWOs and CUFs introduced, and a few more, are also listed in the "MARA Survey".
|
Coursework #3 (Deadline: 01/04/2009) |
| 8 | 25 March 2009 |
NO CLASS (EXAM WEEK) |
Fix the topic of your paper by the end of the week. |
| 9 | 1 April 2009 |
Cake-Cutting Procedures (4up). This lecture has been an introduction to the literature on the fair division of a single divisible good. Such a good may be thought of as a "cake" to be divided amongst several players, and the algorithms proposed to achieve this are commonly known as cake-cutting procedures. We have seen several different procedures for achieving either proportional or envy-free divisions. We have also briefly touched upon some typical COMSOC concerns: complexity (here in the sense of the number of cuts required to achieve a certain type of division) and the logical modelling of social procedures (also known as social software). The following paper is a good introduction to the literature. Besides putting forward a (then) novel procedure for achieving an envy-free division for four (or more) players, it also presents many of the classical procedures in a systematic manner:
|
|
| 10 | 8 April 2009 |
Multiagent Resource Allocation (4up). At the beginning of this lecture we have briefly discussed the general problem of multiagent resource allocation (MARA) and its many specific forms. Specifying a MARA problem requires clarifying the type of resource under discussion, it requires fixing and deciding on a way of representing the preferences of individual agents, and it requires deciding on a criterion for what would be considered an optimal allocation (often in terms of a suitable social welfare ordering). We have then discussed two specific topics in some more detail, both pertaining to the problem of allocating sets of indivisible goods. The first has been the computational complexity of finding an allocation that is socially optimal, for different notions of optimality, and we have seen this problem can be NP-complete or of even higher complexity. In the second part of the lecture we have introduced a distributed negotiation framework and discussed under what circumstances a sequence of deals that satisfy each certain rationality criteria as well as structural properties can be expected to converge to an allocation that is socially optimal. Here are the main references for this lecture:
|
Coursework #4 Meet me to discuss ideas for your paper by the end of the week. |
| 11 | 15 April 2009 |
Bidding Languages for Combinatorial Auctions (4up). Bidding languages are languages for (cardinal) preference representation developed specifically for the purpose of transmitting the (declared) valuations of bidders in combinatorial auctions. We have discussed expressive power and succinctness results for different languages built from the basic operations of OR and XOR; and we have seen how dummy items can be used to express exclusiveness constraints without having to include XOR in the language. The review paper by Nisan gives an overview of the area:
|
|
| 12 | 22 April 2009 |
CLASS CANCELLED |
|
| 13 | 29 April 2009 |
Combinatorial Auctions (4up). Auctions provide simple protocols for deciding on an allocation of goods to agents. After a brief introduction to basic auction theory (covering the English, Dutch, first- and second-price sealed-bid auction protocols), we have concentrated on the computational and algorithmic aspects of combinatorial auctions, which are mechanisms for deciding on the allocation of sets of goods. In particular, we have seen that winner determination is an NP-hard optimisation problem, but we have also seen how a combination of well-known search techniques from Artificial Intelligence together with domain-specific heuristics can often solve the problem in practice. From the cited literature, I particularly recommend the paper by Rothkopf et al. for an introduction and for a discussion of tractable subclasses of the general winner determination problem, and the review article by Sandholm for a discussion of search techniques and heuristics:
|
|
| 14 | 6 May 2009 |
Mechanism Design (4up). This lecture has been about the design of mechanisms for collective decision making that favour a particular desired outcome despite agents pursuing their individual interests. We have introduced the Vickrey-Clarke-Groves mechanism, which is a direct-revelation mechanism that makes reporting your true valuation a dominant strategy, and we have discussed this mechanism in the context of combinatorial auctions. Here are links to two introductory papers on the topic:
|
Coursework #5 Meet me to discuss your first draft by the end of the week. |
| 15 | 13 May 2009 |
CLASS CANCELLED |
|
| 16 | 20 May 2009 |
Guest Lecture by Stéphane Airiau on Tournament Solutions (4up). |
|
| 17 | 27 May 2009 |
Student Presentations: Wednesday 27 May 2009 in Room C1.112 (Science Park 904) at 10:30 (morning session) and 14:00 (afternoon session). Each talk will take roughly 30 minutes (including 5-10 minutes of questions), and there will be a short break after the second talk in each of the two sessions. Morning Session
|
Submit your final paper by Sunday, 7 June 2009. |
Papers: During the second block you are supposed to write a paper about a recent result from the literature and present your findings in a talk at the end of the semester. The main aim of your paper (and of your talk) should be to make an important recent result, related to the topics covered in the course, accessible to your class mates (and to me). Apart from that, your paper should also have some modest original content. This could, for instance, be a new proof of an existing result, an improved presentation or formalisation of a particular model from the literature, pointing out an unexpected connection between two different lines of work, or casting an economics-related result in a fashion that is more accessible to "us" (people with a background in logic and/or AI). Any of the following papers would be a good starting point (and I'd also be happy to hear your own proposals). You should have settled on a topic by the end of March. So do discuss your interests with me early on.