http://www.dagstuhl.de/15241

07. – 12. Juni 2015, Dagstuhl Seminar 15241

Computational Social Choice: Theory and Applications

Organisatoren

Craig Boutilier (University of Toronto, CA)
Britta Dorn (Universität Tübingen, DE)
Nicolas Maudet (UPMC – Paris, FR)
Vincent Merlin (Caen University, FR)


1 / 3 >

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 5, Issue 6 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl's Impact: Dokumente verfügbar

Press Room

Summary

Computational social choice is an interdisciplinary research area dealing with the aggregation of preferences of groups of agents in order to reach a consensus decision that realizes some social objective. Economists typically view markets as an optimal mean for coordinating the activities and allocation of resources across a group of heterogeneous agents based on their utilities or preferences. By contrast, the methods of social choice, broadly defined, focus on coordination mechanisms that do not rely on prices, monetary/resource transfer or market structures, while still defining social objectives that account for individual preferences. Some classic (but certainly not exhaustive) topics of study in social choice topics include:

  • voting procedures, where a single alternative must be taken given the preferences of individuals group members;
  • fair division, which deals with the distribution of goods among a group reflecting individual preferences and fairness criteria;
  • matching problems, in which agents/items are matched in a way that respects both preferences and other constraints.

The theoretical treatment of these problems is concerned with the existence of solutions which could be defended on normative grounds. In classical social choice, desirable solution concepts satisfy certain properties, such as: efficiency, non-discriminatory treatment of agents; envy-freeness; stability (or equilibrium) with respect to incentives; non-manipulability; and a variety of others. Over the past 15 years, the computational properties of these solution concepts have emerged as critically important to their theoretical viability and practical impact. Computer scientists in both AI and theoretical computer science have developed efficient algorithms for realizing certain social choice functions, proven the computational intractability of others, studied the theoretical and practical communication requirements of these procedures, and developed computational tools to sharpen our understanding of incentives, manipulation, and other important phenomena. Applying a computational lens to these theoretical investigations has led to breakthroughs that have supported a variety of real-world applications like web-page ranking, fair buy-sell/exchange protocols, and the development of much more socially efficient exchanges for organ transplantation.

At the same time, the era of networked communication and "big data" has made it easier than ever to infer people's preferences and have them engage with ever larger groups. This has opened up tremendous opportunities for the application of social choice to a wider range of "lower stakes, higher frequency" group decisions. Hence, it introduces new challenges for social choice - many mechanisms for the problems above have been designed using assumptions that - while suitable for "high stakes" domains like political voting, or matching in labor markets and organ donations - are entirely untenable in other domains.

The objective of the seminar was to continue the series of meetings on theoretical computational social choice previously held in Dagstuhl, but the emphasis was on problems which have practical relevance. We have addressed in particular three lines of works concerning issues in social choice: voting, matching, and fair division. The seminar brought together 41 researchers from 18 countries and various fields such as computer science, mathematics, social choice theory, economics, political sciences, and industry. The meeting gathered both participants focusing on the theoretical foundations of computational social choice, and those seeking to apply social choice mechanisms to real-world problems of both the high-stakes/low-frequency and the low-stakes/high-frequency variety.

The technical program of the seminar included overview talks, regular seminar talks, a rump session and slots for communication and work on open problems. The three overview talks presented open questions and challenges in multiwinner voting (complemented by a panel discussion), economics and computation, and in matching in the context of assignments of teachers to schools. The 26 regular seminar talks covered the three lines of work concerning voting, matching, and fair division/resource allocation. Current trends in these fields as reflected by the contributions include allocation of indivisible items under ordinal preferences, the study of well-behaved preference structures (e.g. single-peaked, single-crossing), multiwinner elections, mixed voting systems, and several highly challenging special cases of matching problems. Challenges from real-world applications included online fair division for the distribution of food donations to a food bank, assignments of referees to papers for scientific reviewing, peer grading in massive online open courses, online voting and online participation, sharing cars, junior doctor allocation, and house swapping. Furthermore, several online platforms dedicated to social choice were presented and discussed during the seminar. Precious feedback was collected by the teams of developers.

The program offered the possibility to present open problems and provided slots for working groups on these topics as well as a final session for presentation of outcomes. Several working groups were formed some of which obtained first results during the seminar week. The research projects initiated in these groups are still ongoing. Many participants also used these slots for collaboration with their co-authors that were present at the seminar.

The rump session consisted of 17 five minute contributions, ranging from announcements of events related to the community, over presentation of tools for preference aggregation and online voting, preference libraries for datasets, applications like sharing cars, to short research talks and presentations of open problems.

To conclude, the seminar acknowledged that more and more contributions in computational social choice are driven by real world issues, with many potential applications for industry and policy making. It confirmed that theoretical considerations enable, justify and guarantee the quality of practical applications. Conversely, the specific features and constraints of applications provide novel theoretical challenges and new directions for foundational research.

The participants greatly appreciated the time devoted to working group sessions and benefited from the seminar in various ways: by learning about new problems, many of them being directly inspired from real world issues; by being introduced to several existing tools; by having the possibility to interact and to develop new collaborations. A next event will be the COMSOC workshop in Toulouse in June 2016. It will be co-located with the meeting of the COST Action IC1205 "Computational Social Choice", and one day will be devoted to applications and interactions with industry, in line with the 15241 Dagstuhl seminar.

We would like to thank all participants for their contributions, discussions, ideas and collaborations, making this seminar a very productive and enjoyable one. In particular, we sincerely thank the team of Schloss Dagstuhl for the great support and excellent organization.

License
  Creative Commons BY 3.0 Unported license
  Britta Dorn and Nicolas Maudet and Vincent Merlin

Dagstuhl Seminar Series

Classification

  • Artificial Intelligence / Robotics
  • Data Structures / Algorithms / Complexity
  • Modelling / Simulation

Keywords

  • Computational Social Choice
  • Artificial Intelligence
  • Multi Agent Systems
  • Collective Decision Making
  • Matching
  • Voting
  • Preference Aggregation
  • Fair Division
  • Preference Elicitation and Preference Learning
  • Mechanism Design

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.