Dagstuhl Seminar 19381
Application-Oriented Computational Social Choice
( Sep 15 – Sep 20, 2019 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/19381
Organizers
- Umberto Grandi (University Toulouse Capitole, FR)
- Stefan Napel (Universität Bayreuth, DE)
- Rolf Niedermeier (TU Berlin, DE)
- Kristen Brent Venable (IHMC - Pensacola, US)
Contact
- Shida Kunz (for scientific matters)
Impacts
- Closing the Loop : Bringing Humans into Empirical Computational Social Choice and Preference Reasoning : article in IJCAI-20 - Mattei, Nicholas - IJCAI, 2020. - 5 pp..
- Deliberative Coalition Formation : article - Elkind, Edith; Grossi, Davide; Shapiro, Ehud; Talmon, Nimrod - Cornell University : arXiv.org, 2020. - 8 pp..
- Egalitarian Deliberative Decision Making : Cornell University : arXiv.org, 2020. - 7 pp. - Elkind, Edith; Grossi, Davide; Shapiro, Ehud; Talmon, Nimrod - Cornell University : arXiv.org, 2020. - 7 pp..
- Heuristic Strategies in Uncertain Approval Voting Environments : article - Scheuerman, Jaelle; Harman, Jason L.; Mattei, Nicholas; Venable, Kristen Brent - Cornell University : arXiv.org, 2020. - 9 pp..
- Heuristic Strategies in Uncertain Approval Voting Environments : article in AAMAS 2020 - Scheuerman, Jaelle; Harman, Jason L.; Mattei, Nicholas; Venable, Kristen Brent - ifaamas.org : ifaamas, 2020. - pp. 1993-1995.
- Heuristics in Multi-Winner Approval Voting : article - Scheuerman, Jaelle; Harman, Jason L.; Mattei, Nicholas; Venable, Kristen Brent - Cornell University : arXiv.org, 2019. - 17 pp..
- Isomorphic Distances Among Elections : article in International Computer Science Symposium in Russia CSR 2020 - Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii; Szufa, Stanislaw; Talmon, Nimrod - Berlin : Springer, 2020. - pp 64-78 - (Lecture notes in computer science ; 12159 : article).
- PeerNomination : Relaxing Exactness for Increased Accuracy in Peer Selection : article in IJCAI-20 - Mattei, Nicholas; Turrini, Paolo; Zhydkov, Stanislav - IJCAI, 2020. - 7 pp..
- Smart Voting : article in IJCAI-20 - Colley, Rachael; Grandi, Umberto; Novaro, Arianna - IJCAI, 2020. - 7 pp..
- The Constrained Round Robin Algorithm for Fair and Efficient Allocation : article - Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel - Cornell University : arXiv.org, 2019. - 13 pp..
- Unravelling multi-agent ranked delegations - Colley, Rachael; Grandi, Umberto; Novaro, Arianna - Cornell University : arXiv.org, 2021. - 47 pp..
Schedule
Computational social choice (COMSOC) combines models from political science and economics with techniques from computer science, to analyze collective decision processes from a computational perspective. Classical contributions include the study of the computational barriers to various forms of manipulation in elections, the definition of novel procedures for distributed resources among a group of human or artificial agents, as well as the study of complex collective decisions such as multi-winner voting rules and voting in combinatorial domains. COMSOC is a thriving field of research, with an international bi-annual workshop now at its 7th edition and a handbook published in 2016 which structures more than a decade of research, but future success will depend on the practical applicability of its findings. The purpose of this seminar is to address this challenge by stimulating application-driven research in computational social choice, i.e., theoretical studies modeling existing practical problems in all their complexity.
The seminar shall set up a fruitful feedback loop between practical applications and theoretical research, feeding researchers with novel research problems. It aims to open up the community to players from industry, policy-making, and startup environments. The seminar provides a platform to meet and to stimulate the debate among researchers on how to reach out to these sectors. Four areas of COMSOC, which have already proven or bear particular potential for synergies and applicability to real-life problems, will be in the focus. Namely, the seminar attracts researchers and meaningful contributions on group recommendation systems, fair allocation, interactive democracy, and electoral systems.
Each of these areas addresses present-day challenges that provide an opportunity for an interdisciplinary approach building on contributions from computer scientists, economists, mathematicians, and political scientists:
- Recommender systems is a very successful application that combines several artificial intelligence techniques. Indeed, there have been few other examples of autonomous reasoning tools with comparable impact and pervasiveness in practice. The seminar aims at producing a detailed picture of the state of the art, identify gaps and put forward ideas to fully exploit the synergy between classical social choice techniques and modern recommender systems.
- Fair division has already proven a successful testbed for the application of theoretical work, thanks for the recently launched Spliddit webpage, which provides a user-friendly implementation for a number of algorithms in this field. This experience poses a number of questions and challenges for application-oriented research in fair division and beyond, such as data collection and analysis, possibly leading to new theoretical problems.
- Interactive democracy comprises a variety of approaches to make democratic processes more engaging and responsive. For instance, successful design and implementation of online decision platforms presents a multidisciplinary research challenge. The seminar will explore how voting theory can be employed to aid decision platforms and other tools to deal with challenges like providing minority protection, budget constraints, or avoiding cycles in delegated voting.
- Real electoral systems often have features that are absent in the single or multi-winner systems analyzed in textbooks and scientific papers. Voting theory and computational methods can help to identify non-monotonicity problems of real electoral systems, to provide normative benchmarks for institutional design, and to conduct influence and performance comparisons of different voting arrangements.
Creative Commons BY 3.0 DE
Umberto Grandi, Stefan Napel, Rolf Niedermeier, and Kristen Brent Venable
Computational social choice (COMSOC) combines models from political science and economics with techniques from computer science, to analyze collective decision processes from a computational perspective. Classical contributions include the study of the computational barriers to various forms of manipulation in elections, the definition of novel procedures for distributed resources among a group of human or artificial agents, as well as the study of complex collective decisions such as multi-winner voting rules and voting in combinatorial domains. COMSOC is a thriving field of research, with an international bi-annual workshop now at its 7th edition and a handbook published in 2016 which structures more than a decade of research, but future success will depend on the practical applicability of its findings. The purpose of this seminar was to address this challenge by stimulating application-driven research in computational social choice, i.e., theoretical studies modeling existing practical problems in all their complexity.
Four areas of COMSOC, which have already proven or bear particular potential for synergies and applicability to real-life problems, were identified as the focus of the seminar. Each of these areas addresses present-day challenges that provide an opportunity for an interdisciplinary approach building on contributions from computer scientists, economists, mathematicians, and political scientists:
- Recommender systems is a very successful application that combines several artificial intelligence techniques. Indeed, there have been few other examples of autonomous reasoning tools with comparable impact and pervasiveness in practice.
- Fair division has already proven a successful testbed for the application of theoretical work, thanks for the recently launched Spliddit webpage, which provides a user-friendly implementation for a number of algorithms in this field. This experience poses a number of questions and challenges for application-oriented research in fair division and beyond, such as data collection and analysis, possibly leading to new theoretical problems.
- Interactive democracy comprises a variety of approaches to make democratic processes more engaging and responsive. For instance, successful design and implementation of online decision platforms presents a multidisciplinary research challenge.
- Real electoral systems often have features that are absent in the single or multi-winner systems analyzed in textbooks and scientific papers. Voting theory and computational methods can help to identify non-monotonicity problems of real electoral systems, to provide normative benchmarks for institutional design, and to conduct influence and performance comparisons of different voting arrangements.
The Dagstuhl Seminar 19381 "Application-Oriented Computational Social Choice" brought together 46 invited participants of 15 different nationalities from 4 different continents, with three additional participants choosing to attend our seminar before participating to the Heidelberg Laureate Forum. The list of participants included researchers in Computer Science, Economics, and Political Science, three researchers from the industry (Microsoft, IBM, WinSet Group), and a lab technician.
For each of the focus topics described above, a 1-hour survey was prepared by one of the participants, obtaining an up-to-date overview of current research in the field and its main open problems. Each survey was scheduled on a different day, with 26 regular talks by participants complementing them in the program. Two rump sessions at the beginning of the week allowed a number of the participants to present recent findings, open problems and on-going research in a quick and informal way, stimulating the discussion for the rest of the week.
Given the focus of the seminar on application-oriented research, a special session was dedicated to the presentation of software developed by researchers participating to the seminar. Voting platforms were presented (Whale https://whale.imag.fr/ and OPRA https://opra.cs.rpi.edu/polls/main), a library for preference data (Preflib http://www.preflib.org/), a platform for online deliberation and consensus building (Vilfredo https://www.vilfredo.org/), as well as a number of tools to support experimental research in social choice. Moreover, the seminar hosted three live voting experiments during the week, two of which used a mobile experimental laboratory that was brought to Dagstuhl thanks to French CNRS and the help of a lab technician from University of Rennes. A detailed report of the experiments and an abstract of all the talks can be found below.
At the beginning of the week short sessions were reserved for individual self-introductions and for the proposition of potential group work. The organisers chose not to organize groups in advance, but to let them form in an iterative fashion during the seminar. A number of proposals were first made, then discussed and adapted, before participants signed up for specific group sessions. A total of 6 hours during the week was dedicated to group works, which led to significant advancements - a detailed report can be read below.
Overall, judging both from anecdotal personal feedback as well as the official results from the anonymous "Survey for Dagstuhl Seminar 19381" (with a median score of 10 out of 11 on the summary question "All in all, how do you rate the scientific quality of the seminar?" and similarly positive answers on the mix of participants, working atmosphere, etc.), the seminar was a very successful experience. It stimulated an already thriving research field to explore more applied research topics and scout for real-world problems. It allowed researchers to get first hand experience on how to run voting experiments, either on an Internet voting platform or in a laboratory, and allowed them to share their research practices. The work conducted in the groups was overall fruitful, already resulting in some paper drafts under preparation. The few suggestions for improvements mostly related to further broadening the mix of participants (more PhD students and junior researchers, more colleagues from nearby fields) and having a slightly less dense program (shorter talks, more time for work in small groups or unplanned activities).
The organisers wish to thank all the Dagstuhl staff for their professional support, the participants of the seminar for their positive attitude and enthusiasm, and the two collectors for putting together the abstracts that compose this report.
Umberto Grandi, Stefan Napel, Rolf Niedermeier, and Kristen Brent Venable
- Haris Aziz (UNSW - Sydney, AU) [dblp]
- Dorothea Baumeister (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Abdelhak Bentaleb (National University of Singapore, SG) [dblp]
- Sylvain Bouveret (University of Grenoble, FR) [dblp]
- Florian Brandl (Stanford University, US) [dblp]
- Felix Brandt (TU München, DE) [dblp]
- Robert Bredereck (TU Berlin, DE) [dblp]
- Markus Brill (TU Berlin, DE) [dblp]
- Jiehua Chen (TU Wien, AT) [dblp]
- Cristina Cornelio (IBM T.J. Watson Research Center - Yorktown Heights, US) [dblp]
- Ronald de Haan (University of Amsterdam, NL) [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]
- Joseph Godfrey (WinSet Group, LLC - Falls Church, US) [dblp]
- Umberto Grandi (University Toulouse Capitole, FR) [dblp]
- Davide Grossi (University of Groningen, NL) [dblp]
- Ayumi Igarashi (University of Tokyo, JP) [dblp]
- Christian Klamler (Universität Graz, AT) [dblp]
- Sascha Kurz (Universität Bayreuth, DE) [dblp]
- Martin Lackner (TU Wien, AT) [dblp]
- Jérôme Lang (University Paris-Dauphine, FR) [dblp]
- Annick Laruelle (University of the Basque Country - Bilbao, ES) [dblp]
- Omer Lev (Ben Gurion University - Beer Sheva, IL) [dblp]
- Andrea Loreggia (University of Padova, IT) [dblp]
- Nicola Frederike Maaser (Aarhus University, DK) [dblp]
- Janelle C. Mason (North Carolina A&T State University - Greensboro, US)
- Nicholas Mattei (Tulane University - New Orleans, US) [dblp]
- Nicolas Maudet (Sorbonne University - Paris, FR) [dblp]
- Reshef Meir (Technion - Haifa, IL) [dblp]
- Vincent Merlin (Caen University, FR) [dblp]
- Stefan Napel (Universität Bayreuth, DE) [dblp]
- Rolf Niedermeier (TU Berlin, DE) [dblp]
- Arianna Novaro (Paul Sabatier University - Toulouse, FR) [dblp]
- David Pennock (Microsoft - New York, US) [dblp]
- Dominik Peters (University of Oxford, GB) [dblp]
- Elven Priour (University of Rennes, FR)
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- M. Remzi Sanver (University Paris-Dauphine, FR) [dblp]
- Ehud Shapiro (Weizmann Institute - Rehovot, IL) [dblp]
- Karishma Rajesh Sharma (USC - Los Angeles, US)
- Piotr Skowron (University of Warsaw, PL) [dblp]
- Arkadii Slinko (University of Auckland, NZ) [dblp]
- Pietro Speroni di Fenizio (Dublin, IE) [dblp]
- Nimrod Talmon (Ben Gurion University - Beer Sheva, IL) [dblp]
- Paolo Turrini (University of Warwick - Coventry, GB) [dblp]
- Kristen Brent Venable (IHMC - Pensacola, US) [dblp]
- Toby Walsh (UNSW - Sydney, AU) [dblp]
- Lirong Xia (Rensselaer Polytechnic Institute - Troy, US) [dblp]
Classification
- artificial intelligence / robotics
- data structures / algorithms / complexity
Keywords
- Social Choice
- Multi-Agent Systems
- AI for the Social Good
- Collective Decision Making
