Computational Social Choice: Spring 2008

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.

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.

15 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:

You could also have a look through the proceedings of COMSOC-2006, the 1st International Workshop on Computational Social Choice, held in Amsterdam in 2006.

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.

212 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:

319 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)
425 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:

The issue of preference representation will come up again at various points throughout the course in the context of specific applications.

54 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)
611 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".

  • H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.
  • Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

718 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:

  • Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

Coursework #3
(Deadline: 04/04/2008)
825 March 2008


94 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.
108 April 2008


1115 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)
1222 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.
1329 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:

  • L.M. Asubel and P. Milgrom. The Lovely but Lonely Vickrey Auction. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (authors' version)
  • H.R. Varian. Economic Mechanism Design for Computerized Agents. Proc. Usenix Workshop on Electronic Commerce, 1995. (author's version)

Coursework #5
(Deadline: 16/05/2008)
146 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:

  • N. Nisan. Bidding Languages for Combinatorial Auctions. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (author's version)

1513 May 2008


1620 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.


  • Nicolas: Distributed MARA in Diminishing Marginal Return Domains (Bachrach and Rosenschein)
  • Marlouke: Complexity of Cake-Cutting (Sgall and Woeginger)
  • Ernst: Social Software (Parikh)
  • Floor: Cooperative Boolean Games (Dunne et al.)
  • Sara: Complexity of Computing the Winners of a Tournament (Hudry)
  • Vahid: PageRank as a Weak Tournament Solution (Brandt and Fischer)
  • Thomas: Complexity of Manipulation in Elections with Few Candidates (Conitzer et al.)

1727 May 2008


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.