Dagstuhl Seminar 15241
Computational Social Choice: Theory and Applications
( Jun 07 – Jun 12, 2015 )
Permalink
Organizers
- Craig Boutilier (University of Toronto, CA)
- Britta Dorn (Universität Tübingen, DE)
- Nicolas Maudet (UPMC - Paris, FR)
- Vincent Merlin (Caen University, FR)
Contact
- Christina Schwarz (for administrative matters)
Press/News
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 means 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, nondiscrimatory treatment of agents; envy-freeness; stability (or equilibrium) with respect to incentives; nonmanipulability; 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. At the same time, 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 is to continue the series of meetings on theoretical Computational Social Choice previously held in Dagstuhl, but the emphasis will be on problems which have practical relevance. We will address in particular three lines of works concerning issues in social choice: voting, matching, and fair divisions. The seminar will bring together researchers that focus on both the theoretical foundations of computational social choice, and those who seek to apply social choice mechanisms to real-world problems of both the high-stakes/low-frequency and the low-stakes/high-frequency variety. An exchange between these two worlds will fertilize both: theoretical considerations enable, justify and guarantee the quality of practical applications; conversely, the specific features and constraints of specific applications provide novel theoretical challenges and new directions for foundational research.
- Kann ein Computer alles berechnen?
Article about this seminar published in the "Saarbrücker Zeitung" on August 18, 2015 (in German) - Sind gesellschaftliche Entscheidungen durch Computer berechenbar?
Press release in German - Is it possible for computers to calculate social choice?
Press release in English
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.
- Haris Aziz (Data61 / NICTA - Sydney, AU) [dblp]
- Dorothea Baumeister (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Péter Biró (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Sylvain Bouveret (LIG - Grenoble, FR) [dblp]
- Steven J. Brams (New York University, US) [dblp]
- Felix Brandt (TU München, DE) [dblp]
- Robert Bredereck (TU Berlin, DE) [dblp]
- Markus Brill (Duke University - Durham, US) [dblp]
- Ioannis Caragiannis (CTI & University of Patras, GR) [dblp]
- Katarina Cechlarova (Pavol Jozef Šafárik University - Košice, SK) [dblp]
- Jiehua Chen (TU Berlin, DE) [dblp]
- Yann Chevaleyre (University of Paris North, FR) [dblp]
- Andreas Darmann (Universität Graz, AT) [dblp]
- Britta Dorn (Universität Tübingen, DE) [dblp]
- Edith Elkind (University of Oxford, GB) [dblp]
- Ulle Endriss (University of Amsterdam, NL) [dblp]
- Piotr Faliszewski (AGH University of Science & Technology - Krakow, PL) [dblp]
- Christian Geist (TU München, DE) [dblp]
- Judy Goldsmith (University of Kentucky - Lexington, US) [dblp]
- Umberto Grandi (Toulouse 1 Capitole University, FR) [dblp]
- Paul Harrenstein (University of Oxford, GB) [dblp]
- Christian Klamler (Universität Graz, AT) [dblp]
- Bettina Klaus (University of Lausanne, CH) [dblp]
- Flip Klijn (CSIC - Barcelona, ES) [dblp]
- Dominikus Krüger (Universität Ulm, DE) [dblp]
- Jérôme Lang (University Paris-Dauphine, FR) [dblp]
- Annick Laruelle (Ikerbasque - Bilbao, ES) [dblp]
- Michel Le Breton (University of Toulouse I, FR) [dblp]
- David Manlove (University of Glasgow, GB) [dblp]
- Nicholas Mattei (UNSW - Sydney, AU) [dblp]
- Nicolas Maudet (UPMC - Paris, FR) [dblp]
- Vincent Merlin (Caen University, FR) [dblp]
- Trung Thanh Nguyen (Masdar Institute - Abu Dhabi, AE) [dblp]
- Francesca Rossi (University of Padova, IT) [dblp]
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Ildikó Schlotter (Budapest University of Technology & Economics, HU) [dblp]
- Arkadii Slinko (University of Auckland, NZ) [dblp]
- Toby Walsh (UNSW - Sydney, AU) [dblp]
- Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
- Jia Yuan Yu (IBM Research - Dublin, IE) [dblp]
- William S. Zwicker (Union College - Schenectady, US) [dblp]
Related Seminars
- Dagstuhl Seminar 07431: Computational Issues in Social Choice (2007-10-21 - 2007-10-26) (Details)
- 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 17261: Voting: Beyond Simple Majorities and Single-Winner Elections (2017-06-25 - 2017-06-30) (Details)
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