Computational social choice is a new discipline emerging at the interface of social choice theory and computer science. It is concerned with the application of computational techniques to the study of social choice 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. It is similar to last year's Multiagent Systems course, but with more material on classical topics in social choice theory, and somewhat less emphasis on autonomous software agents.
| Week | Date | Content | Coursework |
|---|---|---|---|
| 1 | 6 February 2007 |
NO CLASS (KNAW-AC on Games and Interaction) |
|
| 2 | 13 February 2007 |
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:
|
|
| 3 | 20 February 2007 |
Game Theory (4up). This lecture has been an introduction to game theory. More specifically, we have discussed non-cooperative strategic games with perfect information. We have defined the concepts of dominant strategies, pure Nash equilibria, and mixed Nash equilibria, and we have seen how to compute the mixed Nash equilibria of a simple game. Most books on Game Theory would cover this material. One that is particularly accessible is the textbook by Osborne:
|
Coursework #1 (Deadline: 06/03/2007) |
| 4 | 27 February 2007 |
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:
|
|
| 5 | 6 March 2007 |
Computational Issues in Voting (4up). This lecture has given an overview of some of the computational issues that arise in the context of voting. We have concentrated on results regarding the computational complexity of problems related to voting, in particular winner determination and manipulation. Here are the main papers for this lecture:
|
Coursework #2 (Deadline: 19/03/2007) |
| 6 | 12 March 2007 |
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:
This lecture took place on MONDAY, 12 March 2007, 3-5pm (room P.018), to make space for the Workshop on Logics and Collective Decision Making in Lille. |
|
| 7 | 19 March 2007 |
Guest Lecture by Joel Uckelman on Preference Representation with Weighted Formulas. While the previous lecture has given a broad overview of languages for compact preference representation in combinatorial domains, this one has looked at one of these languages in detail, namely the language of weighted propositional formulas for representing utility functions. We have seen examples for technical results regarding expressive power, uniqueness of representation, comparative succinctness, and computational complexity, as well as a discussion of ongoing research on utilising this kind of language in the context of committee elections. This lecture took place on MONDAY, 19 March 2007, 3-5pm (room P.018), to make space for a minicourse on Algorithmic Game Theory in Eindhoven. |
Coursework #3 (Deadline: 03/04/2007) |
| 8 | 27 March 2007 |
NO CLASS (EXAM WEEK) |
|
| 9 | 3 April 2007 |
Social Welfare Orderings (4up). We have introduced the concepts 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".
|
Fix the topic of your paper by the end of the week. |
| 10 | 10 April 2007 |
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 #4 (Deadline: 24/04/2007) |
| 11 | 17 April 2007 |
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 last week. 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:
|
|
| 12 | 24 April 2007 |
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:
|
Meet me to discuss your first draft by the end of the week. |
| 13 | 1 May 2007 |
NO CLASS (DAG VAN DE ARBEID) |
|
| 14 | 8 May 2007 |
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:
|
Coursework #5 (Deadline: 22/05/2007) |
| 15 | 15 May 2007 |
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:
|
|
| 16 | 22 May 2007 |
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:
|
|
| 17 | 29 May 2007 |
The student presentations will take place on TUESDAY, 29 May 2007, in room P.327. We will start at 11:00 (sharp) in the morning with the first four talks, and resume in the afternoon at 15:00 (also sharp) with the remaining four. Each talk will take roughly 30 minutes (including 5-10 minutes of questions), and there will be a 15 minute break after the second talk in each of the two sessions. MORNING SESSION
|
Submit your final paper by 8 June 2007. |
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.