Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science, with knowledge flowing in either direction. On the one hand, computational social choice is concerned with importing concepts and procedures from social choice theory for solving questions that arise in computer science and AI application domains. This is typically the case for managing societies of autonomous agents, which calls for negotiation and voting procedures. On the other hand, computational social choice is concerned with importing notions and methods from computer science for solving questions originally stemming from social choice, for instance by providing new perspectives on the problem of manipulation and control in elections. This Dagstuhl Seminar has been devoted to the presentation of recent results and an exchange of ideas in this growing research field.

For a few years now, computer scientists (especially in Artificial Intelligence) have been taking more and more of an interest in collective decision making. There are two main reasons for that, leading to two different lines of research. Roughly speaking, the first one is concerned with importing concepts and procedures from social choice theory for solving questions that arise in computer science and AI application domains. This is typically the case for managing societies of autonomous agents, which calls for negotiation and voting procedures. The second line of research goes the other way round: it is concerned with importing notions and methods from computer science for solving questions originally stemming from social choice.

Social choice theory is concerned with designing and evaluating methods of collective decision making. Solving a problem in social choice theory often amounts to proving the existence (or non-existence) of a procedure for collective decision making meeting certain requirements. However, to date computational issues have not received enough attention in social choice. This is one place where computer science comes into play. For instance, the classical impossibility result stating that any non-dictatorial voting procedure is manipulable can be bypassed by ensuring that manipulation is sufficiently hard to compute, which has called for complexity studies of manipulation problems. Another example is the study of elicitation, compact representation, and aggregation of preferences in combinatorial domains. This line of research has emerged from work in the AI community on logical and graphical representation languages. These languages are designed to allow for representing, in as little space as possible, a preference structure whose size would be prohibitively large if it were to be represented explicitly. Yet another example is the field of social software originating in the computational logic community, which is concerned with the application of logic-based techniques for specification and verification to the analysis of social choice procedures, to prove, for instance, the correctness of a fair division algorithm. As a final example of how the application of methods from computer science to problems of social choice can open up new research areas we mention here the idea of automated mechanism design, which aims at developing algorithms to generate social mechanisms for specific problem instances automatically. This approach can sometimes circumvent classical impossibility results from economics, which apply to the design of mechanisms for entire classes of problems, rather than to the specific problem instances at hand.

The aim of this Dagstuhl Seminar was to address all lines of work concerning computational issues in social choice, to a broad extent: this includes algorithmic and complexity-theoretic studies of social choice problems (both at the level of the agent and at that of the mechanism), but also, more generally, research that aims at importing concepts or methods from computer science to study social choice mechanisms.

e found the seminar successful, especially in terms of the following achievements: First, the seminar made participants aware of a commonality of interests across different disciplines. Second, it suggested new directions for research that will probably be taken up by researchers in the next couple of years; in particular, some new areas of social choice emerged from interaction with computer scientists (such as the computational barriers to strategic behaviour, false-name proofness, or voting on very large domains). Last, student participants got very involved in the discussions.

The field is more promising than ever, and we expect the community to broaden up in the next couple of years. The next event aiming at gathering the community will be the 2nd International Workshop on Computational Social Choice (Liverpool, September 2008).