Computational Social Choice: Spring 2007


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.

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.

WeekDateContentCoursework
16 February 2007

NO CLASS (KNAW-AC on Games and Interaction)

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

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

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:

 
320 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)
427 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:

 
56 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)
612 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.

 
719 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)
827 March 2007

NO CLASS (EXAM WEEK)

 
93 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".

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

Fix the topic of your paper by the end of the week.
1010 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:

  • 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 #4
(Deadline: 24/04/2007)
1117 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:

 
1224 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.
131 May 2007

NO CLASS (DAG VAN DE ARBEID)

 
148 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)
1515 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:

  • 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)

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

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

 
1729 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

  • Mark: complexity of election control (Hemaspaandra et al.)
  • Qi-Qi: communication complexity of voting (Conitzer and Sandholm)
  • Cédric: vote in combinatorial domains (Lang)
  • Iris: small binary voting trees (Trick)
AFTERNOON SESSION
  • Szymon: judgement aggregation (List and Pettit)
  • Maarten: axioms for ranking systems (Altman and Tennenholtz)
  • Matthijs: logic of social welfare (Ågotnes et al.)
  • Johan: false-name bidding (Yokoo et al.)

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.