Dagstuhl-Seminar 17261
Voting: Beyond Simple Majorities and Single-Winner Elections
( 25. Jun – 30. Jun, 2017 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/17261
Organisatoren
- Dorothea Baumeister (Heinrich-Heine-Universität Düsseldorf, DE)
- Piotr Faliszewski (AGH University of Science & Technology - Krakow, PL)
- Annick Laruelle (University of the Basque Country - Bilbao, ES)
- Toby Walsh (TU Berlin, DE)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Annette Beyer (für administrative Fragen)
Programm
Computational social choice is an interdisciplinary field of research, focused on computational and algorithmic issues pertaining to aggregating preferences of agents—perhaps self-interested and strategic—and providing them with joint decisions. Computational social choice combines the tools and approaches of social choice theory, computer science (with particular focus on artificial intelligence and theoretical computer science), economics, and operations research. The distinctive feature of computational social choice—as opposed to the classic social choice theory— is that computational considerations (e.g., efficiency of computing outcomes of the preference aggregation processes) are given significant attention. Nonetheless, the two research areas are deeply connected and there is significant interaction between them. The best studied model of (computational) social choice regards single-winner elections. Agents (voters) express their preferences regarding the available candidates (often in the form of rankings, from the most to the least desirable candidate) and then a voting rule (i.e., an appropriate algorithm) specifies the election winner. Due to the fantastic progress in social choice (over the last half a century) and in computational social choice (over the last fifteen years or so), essentially all the stages of the above-described process are quite well studied. However, in the modern world—especially in the era of ubiquitous use of social media—it appears that there is a great range of preference aggregation settings where the classic approach falls short.
The goal of this seminar is to discuss:
- multi-winner elections: parliamentary elections are perhaps the most archetypal example of a multi-winner election, but there are applications far beyond the world of politics.
- multi-issue elections: decisions on a sequence of interdependent issues.
- elections where voters express their preferences in various non-standard ways (ranging from extensions of dichotomous preferences to complex languages allowing one to express condi- tional statements).
- other voting-related settings, including peer selection, and judgement aggregation.
Although voting theory is usually associated with political elections, its possible applications are found in all aspects of collective decision making. Applications in computer science include webpage ranking, online recommendation systems for products and services, and various scheduling tools (such as, e.g., Doodle). Further, there are relevant applications of (multi-winner) voting in the industry (for example finding the best set of products for a given group of clients). A consequence of this diversity of applications is the interdisciplinary approach of the seminar. We intend the seminar to be a place where researchers from various areas of research (including computer science, economics, political science, etc.) can exchange their views, ideas, and experiences regarding these new preference aggregation problems.
This seminar is related to four previous seminars on Computational Social Choice (2007, 2010, 2012, 2015), which contributed to the development of the community.
Creative Commons BY 3.0 DE
Dorothea Baumeister, Piotr Faliszewski, Annick Laruelle, and Toby Walsh
- Wie man die Informatik für die Wahlforschung nutzen kann
Article about this seminar published in the "Saarbrücker Zeitung" on July 16, 2017 (in German) - The computer science of voting
Press release in English - Wahlforschung mit Informatik
Press release in German
Computational social choice is an interdisciplinary field of research, focused on the issue of aggregating preferences of agents--perhaps self-interested and strategic -- and providing them with joint decisions. Computational social choice combines the tools and approaches of social choice theory, computer science (with particular focus on artificial intelligence and theoretical computer science), economics, political science, and operations research. The distinctive feature of computational social choice--as opposed to the classic social choice theory -- is that computational considerations (e.g., efficiency of computing outcomes of the preference aggregation processes) are given significant attention. Further, researchers working on computational social choice often study virtual elections where either people vote through electronic means (such as in Doodle polls for scheduling of meetings) or the elections are used as a tool and the votes are derived automatically in some way (e.g., voting can be used as a selection procedure in a genetic algorithm). Nonetheless, the two research areas are deeply connected and there is significant interaction between them.
One of the most classic problems studied within (computational) social choice regards conducting a single-winner election. For example, consider the situation where members of some society wish to choose their president. They collect the set of candidates (who usually have to register well ahead of time, typically by gathering necessary popular support), then the candidates run their campaigns, argue who would be the best president, air commercials, etc. Eventually, the voters form their preferences (either they simply decide who would be the best president, or they form rankings of the candidates, or they decide on a set of acceptable presidents, depending on the voting rule used) and, on the election day, they cast their votes. In the end, an electoral commission gathers the votes and applies an agreed upon voting rule to decide who would be the next president.
Due to the fantastic progress in social choice (since the middle of the twentieth century) and in computational social choice (over the last fifteen years or so), essentially all the stages of the above-described process are quite well understood. However, In the modern world -- especially in the era of ubiquitous use of social media -- it appears that there is a great range of preference aggregation settings where the classic approach falls short. For example, consider a situation where a company wants to hire a team of specialists. There may be quite a large number of possible candidates to employ (as opposed to the few candidates in a typical presidential election), each of the candidates may have quite different skills and abilities, various employees may either complement each other or be counter-productive if teamed up (as opposed to our presidential election, where we pick a single person for the whole task). Finally, the recruiting committee typically consists of just a few people (few voters, as opposed to the millions of people voting for presidents), but their preferences might have a very involved structure (for example, if we hire a specialist in X then we also need a specialist in Y, but otherwise a specialist in Z would suffice; on top of that, each member of the recruitment committee may judge candidates' abilities differently).
The goal of the seminar was to bring together researchers who work on various aspects of aggregation problems that go beyond the classic high-stake, rarely conducted, single-winner elections, and to discuss the following issues:
- Scenarios with multiple winners and/or settings where each aggregation outcome may consist of separate entities (e.g., multi-winner elections and single-winner elections in combinatorial domains).
- Various non-typical ways of expressing preferences, going from (variants of) non-binary preferences to settings where the agents can express complex statements, including conditional ones (e.g., CP-nets).
The seminar also dealt with some real-world applications, such the question of drawing constituency boundaries in the United States of America or the choice of the voting rule in EU Council of Ministers.
The seminar brought together 42 researchers from 14 countries, working in artificial intelligence, theoretical computer science, mathematics, economics, social choice, and political science. Discussions regarding the new challenges in the area of preference aggregation should fertilize research in all these areas.
The technical program of the seminar was structured over five working groups. On the first day the participants were invited to give 5-minute presentations of research topics that they found interesting and, based on those presentations, the organizers suggested five working groups:
- Working Group 1: Voting Experiments.
- Working Group 2: Understanding Diversity in Multiwinner Elections.
- Working Group 3: Aggregation Procedures with Nonstandard Input and Output Types.
- Working Group 4: Voting in Larger Contexts.
- Working Group 5: Proportionality in Multiwinner Elections.
The seminar attendees accepted these groups and each chose one to participate in the discussions. During the seminar each group met twice for extended discussions. Also, one afternoon was free for unstructured discussions (of which many were used for in-depth discussions of topics initiated during the working group discussions). Finally, on the last day of the seminar representatives of each group presented the results of their discussions (which ranged from making actual technical contributions to presenting research agendas for future work). The working groups were supported by 21 regular scientific presentations, and extended presentation of the real-life experiments regarding French presidential elections, and 6 survey talks.
The seminar acknowledged that there are new, exciting research topics regarding computational social choice. In particular, multiwinner elections were represented very prominently and it became clear that work on them has only started. We hope and believe that one of the effects of the seminar was convincing many more people (also outside of the core computational social choice community) that studying more general forms of elections (such as multiwinner elections, or elections with nonstandard input formats) is important and promising.
Given the personal feedback we received, we believe that the participants were very happy with the setting of working groups (from the process of forming them based on surveyed interest, through actual meetings, to presentation of results). We also receive very strong, positive feedback regarding leaving one afternoon unstructured, for the participants to use as they preferred. We have seen many ad-hoc discussions, meetings of coauthors, and problem-solving sessions. Indeed, it seems that for seminars with well-established communities, such an unstructured afternoon is far more useful than the traditional excursion (which, on the other hand, seems to be very effective for not as well-established communities).
We are very grateful to all the participants for their contributions, ideas, and discussions, which made this seminar truly enjoyable. We would also like to thank the Schloss Dagstuhl team for their support and excellent organization and patience.
Dorothea Baumeister, Piotr Faliszewski, and Annick Laruelle
- Haris Aziz (Data61 - Sydney, AU) [dblp]
- William Bailey (University of Kentucky - Lexington, US) [dblp]
- Dorothea Baumeister (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Sirin Botan (University of Amsterdam, NL) [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 (TU Berlin, DE) [dblp]
- Jiehua Chen (Ben Gurion University of the Negev - Beer Sheva, IL) [dblp]
- Marcin Dziubinski (University of Warsaw, PL) [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]
- Judy Goldsmith (University of Kentucky - Lexington, US) [dblp]
- Bernard Grofman (University of California - Irvine, US) [dblp]
- Marc Kilgour (Wilfrid Laurier University, CA) [dblp]
- Werner Kirsch (FernUniversität in Hagen, DE) [dblp]
- Christian Klamler (Universität Graz, AT) [dblp]
- Martin Lackner (University of Oxford, GB) [dblp]
- Jérôme Lang (University Paris-Dauphine, FR) [dblp]
- Annick Laruelle (University of the Basque Country - Bilbao, ES) [dblp]
- Jean-Francois Laslier (Paris School of Economics, FR) [dblp]
- Andrea Loreggia (University of Padova, IT) [dblp]
- Nicholas Mattei (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Vincent Merlin (Caen University, FR) [dblp]
- Stefan Napel (Universität Bayreuth, DE) [dblp]
- Svetlana Obraztsova (Nanyang TU - Singapore, SG) [dblp]
- Dominik Peters (University of Oxford, GB) [dblp]
- Clemens Puppe (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Lisa Rey (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- M. Remzi Sanver (University Paris-Dauphine, FR) [dblp]
- Ann-Kathrin Selker (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Sujoy Sikdar (Rensselaer Polytechnic Institute - Troy, US) [dblp]
- Piotr Skowron (TU Berlin, DE) [dblp]
- Arkadii Slinko (University of Auckland, NZ) [dblp]
- Krzysztof Sornat (University of Wroclaw, PL) [dblp]
- Nimrod Talmon (Weizmann Institute - Rehovot, IL) [dblp]
- Kristen Brent Venable (Tulane University - New Orleans, US) [dblp]
- Gerhard J. Woeginger (RWTH Aachen, DE) [dblp]
- William S. Zwicker (Union College - Schenectady, US) [dblp]
Verwandte Seminare
- 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 15241: Computational Social Choice: Theory and Applications (2015-06-07 - 2015-06-12) (Details)
Klassifikation
- artificial intelligence / robotics
- data structures / algorithms / complexity
- modelling / simulation
Schlagworte
- Social Choice
- Artificial Intelligence
- Multi Agent Systems
- Collective Decision Making
- Voting
- Preference Aggregation
- Preference Elicitation and Preference Learning
