Computational Foundations of Social Choice

Summary

This seminar addressed some of the key issues in computational social choice, a novel interdisciplinary field of study at the interface of social choice theory and computer science. Computational social choice is concerned with the application of computational techniques to the study of social choice mechanisms, such as voting rules and fair division protocols, as well as with the integration of social choice paradigms into computing. The seminar brought together many of the most active researchers in the field and focussed the research community currently forming around these important and exciting topics.

Classical social choice theory deals with the design and analysis of methods for collective decision making and plays an important role within economic theory as witnessed by the Nobel prizes awarded to social choice theorists such as Kenneth Arrow and Amartya Sen. Examples of collective decision making mechanisms are voting rules and methods for the fair division of one or more goods among several agents. For a few years now, researchers from computer science, in particular AI and theory, have been taking an ever increasing interest in social choice. There are two main reasons for that, leading to two different lines of research.

The second line of research within computational social choice goes in the other direction, i.e., concepts and procedures from social choice theory are imported to solve questions that arise in computer science and AI application domains. This is, for instance, the case for managing societies of autonomous software agents, which calls for negotiation and voting procedures. Other examples are the application of techniques from social choice to the development of webpage ranking systems for Internet search engines or recommender systems for electronic commerce.

The seminar brought together 44 researchers who have worked on various aspects of computational social choice, and who have come to this area from very different backgrounds: theoretical computer science, artificial intelligence, economics, operations research, mathematics, and political science. Only half of the participants were computer scientists. Despite---or maybe because of---this heterogeneity, every talk was followed by a long and lively discussion. There was a total of 34 talks plus a rump session consisting of about ten short (5-minute) presentations. Participants originated from 19 different countries with the majority being from France, Germany, and the USA.

A wide variety of topics were discussed during the seminar. Common research themes that emerged included manipulability, approval voting, cake-cutting algorithms, tournaments, and abstention. We are currently preparing a special issue of the journal Mathematical Social Sciences (edited by Felix Brandt and Bill Zwicker) consisting of work presented at this seminar.