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.
| Week | Date | Content | Coursework |
|---|---|---|---|
| 1 | 5 February 2008 |
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 may want to 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:
Throughout the course we are occasionally going to refer to some basic concepts from game theory. As everybody taking the course already has some background in game theory, there will be no lecture devoted specifically to an introduction to the field. If you do want to refresh your memory though, you can read through the slides of the second lecture of the 2007 edition of the course. |
|
| 2 | 12 February 2008 |
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:
|
|
| 3 | 19 February 2008 |
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:
|
Coursework #1 (Deadline: 04/03/2008) |
| 4 | 25 February 2008 |
Preference Representation in Combinatorial Domains (4up). We have reviewed several languages for representing the preferences of individual agents and discussed their expressive power and comparative succinctness. The latter, 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 2008 |
Vote 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/2008) |
| 6 | 11 March 2008 |
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".
|
|
| 7 | 18 March 2008 |
Multiagent Resource Allocation I (4up). The problem of allocating a number of resources amongst a group of agents is a typical collective decision making problem in which computational considerations are paramount. This lecture has given an overview of the field and also put some of the topics covered in previous lectures into perspective. 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). Besides reviewing material relevant to the specification of MARA problems, we have also set up a formal framework for resource allocation and discussed several complexity results for that framework. All of this is covered in more detail in the MARA Survey:
|
Coursework #3 (Deadline: 04/04/2008) |
| 8 | 25 March 2008 |
NO CLASS (EXAM WEEK) |
|
| 9 | 4 April 2008 |
Multiagent Resource Allocation II (4up). This lecture has started by giving a broad overview of different types of allocation procedures that may be used to solve the kinds of MARA problems introduced in the previous lecture. The technical results discussed all pertain to an abstract negotiation framework for distributed resource allocation. Under different assumptions regarding the interests of individual agents and the structural types of deals admitted by the protocol (local perspective), we would like to understand what kind of allocations can be reached in terms of different types of social welfare measures (global perspective). We have discussed convergence properties and different aspects of computational and communication complexity. The following paper is a starting point for finding out more about convergence and related properties in distributed resource allocation:
|
Fix the topic of your paper by the end of the week. |
| 10 | 8 April 2008 |
CLASS CANCELLED |
|
| 11 | 15 April 2008 |
Cake-Cutting Procedures (4up). This lecture has been an introduction to the literature on 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. 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:
|
Coursework #4 (Deadline: 29/04/2008) |
| 12 | 22 April 2008 |
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:
|
Meet me to discuss your first draft by the end of the month. |
| 13 | 29 April 2008 |
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 (Deadline: 16/05/2008) |
| 14 | 6 May 2008 |
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 excellent paper by Nisan gives an overview of the area:
|
|
| 15 | 13 May 2008 |
CLASS CANCELLED |
|
| 16 | 20 May 2008 |
Student Presentations: 11:00-13:15 and 14:00-16:00 (Room P.015/A). 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
|
|
| 17 | 27 May 2008 |
NO CLASS (EXAM WEEK) |
Submit your final paper by Sunday, 8 June 2008. |
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.
The website for the 2007 edition of the course is still available.