TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 07431

Computational Issues in Social Choice

( Oct 21 – Oct 26, 2007 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/07431

Organizers

Contact



Summary

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


Participants
  • Thomas Agotnes (Bergen University College, NO) [dblp]
  • Alon Altman (Stanford University, US)
  • Krzysztof Apt (CWI - Amsterdam, NL)
  • Haris Aziz (University of Warwick - Coventry, GB) [dblp]
  • Nadja Betzler (Universität Jena, DE)
  • Sylvain Bouveret (ONERA - Toulouse, FR) [dblp]
  • Felix Brandt (LMU München, DE) [dblp]
  • Archie Chapman (University of Southampton, GB)
  • Yann Chevaleyre (University Paris-Dauphine, FR) [dblp]
  • Vincent Conitzer (Duke University - Durham, US) [dblp]
  • Sylvie Coste-Marquis (Artois University - Lens, FR) [dblp]
  • Harrie de Swart (Tilburg University, NL)
  • Daniel Eckert (Universität Graz, AT)
  • Edith Elkind (University of Southampton, GB) [dblp]
  • Ulle Endriss (University of Amsterdam, NL) [dblp]
  • Sylvia Estivie (Univ.de Valenciennes, FR)
  • Patricia Everaere (IUT de Lille A - Villeneuve d'Ascq, FR)
  • Boi Faltings (EPFL - Lausanne, CH) [dblp]
  • Paul Harrenstein (LMU München, DE) [dblp]
  • Edith Hemaspaandra (Rochester Institute of Technology, US) [dblp]
  • Lane Hemaspaandra (University of Rochester, US) [dblp]
  • Sebastien Konieczny (CNRS - Lens, FR) [dblp]
  • Jérôme Lang (Paul Sabatier University - Toulouse, FR) [dblp]
  • Michel Lemaître (ONERA - Toulouse, FR) [dblp]
  • Pierre Marquis (CNRS - Lens, FR) [dblp]
  • Nicolas Maudet (University Paris-Dauphine, FR) [dblp]
  • Gabriella Pigozzi (University of Luxembourg, LU) [dblp]
  • Maria Silvia Pini (University of Padova, IT) [dblp]
  • Ariel Procaccia (The Hebrew University of Jerusalem, IL) [dblp]
  • Valentin Robu (CWI - Amsterdam, NL)
  • Francesca Rossi (University of Padova, IT) [dblp]
  • Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
  • Tuomas Sandholm (Carnegie Mellon University - Pittsburgh, US) [dblp]
  • Arkadii Slinko (University of Auckland, NZ) [dblp]
  • Alexis Tsoukias (University Paris-Dauphine, FR) [dblp]
  • Joel Uckelman (University of Amsterdam, NL)
  • Wiebe van der Hoek (University of Liverpool, GB) [dblp]
  • Leon van der Torre (University of Luxembourg, LU) [dblp]
  • Kristen Brent Venable (University of Padova, IT) [dblp]
  • Jörg Vogel (Universität Jena, DE) [dblp]
  • Toby Walsh (UNSW - Sydney, AU) [dblp]
  • Michael J. Wooldridge (University of Liverpool, GB) [dblp]
  • Lirong Xia (Duke University - Durham, US) [dblp]
  • William S. Zwicker (Union College - Schenectady, US) [dblp]

Related Seminars
  • Dagstuhl Seminar 10101: Computational Foundations of Social Choice (2010-03-07 - 2010-03-12) (Details)
  • Dagstuhl Seminar 12101: Computation and Incentives in Social Choice (2012-03-04 - 2012-03-09) (Details)
  • Dagstuhl Seminar 15241: Computational Social Choice: Theory and Applications (2015-06-07 - 2015-06-12) (Details)
  • Dagstuhl Seminar 17261: Voting: Beyond Simple Majorities and Single-Winner Elections (2017-06-25 - 2017-06-30) (Details)

Classification
  • artificial intelligence / robotics
  • verification / logic
  • interdisciplinary with non-informatics-topic
  • social choice theory
  • game theory
  • decision theory

Keywords
  • preference representation and aggregation
  • fair division
  • negotiation
  • voting theory
  • mechanism design
  • social software
  • computational complexity