Dagstuhl Seminar 12101
Computation and Incentives in Social Choice
( Mar 04 – Mar 09, 2012 )
- Edith Elkind (Nanyang TU - Singapore, SG)
- Christian Klamler (Universität Graz, AT)
- Jeffrey S. Rosenschein (The Hebrew University of Jerusalem, IL)
- M. Remzi Sanver (Istanbul Bilgi University, TR)
- Annette Beyer (for administrative matters)
- A characterization of the single-crossing domain : article pp. 989-998 - Bredereck, Robert; Chen, Jiehua; Woeginger, Gerhard J. - Berlin : Springer, 2013. - pp. 989-998 - (Social Choice and Welfare : 41. 2013, 4).
- A hardness result for core stability in additive hedonic games : article : pp. 101-104 - Woeginger, Gerhard J. - Amsterdam : Elsevier, 2013 - (Mathematical Social Sciences ; 65. 2013, 5/6).
- Group Activity Selection Problem : COMSOC 2012 : Accepted Paper - Darmann, Andreas; Elkind, Edith; Kurz, Sascha; Lang, Jerome; Schauer, Joachim; Woeginger, Gerhard J. - Krakow : COMSOC 2012, 2012. - 12 pp. - International Workshop on Computational Social Choice <4, 2012, Krakow>.
- Vote trading and subset sums : article : pp. 99–102 - Bervoets, Sebastian; Merlin, Vincent; Woeginger, Gerhard J. - Amsterdam : Elsevier, 2015. - pp. 99–102 - (Operations Research Letters ; 43. 2015, 1).
The aim of classic social choice theory is to explain how groups of agents can come to a joint decision that reflects the heterogeneous preferences of individual agents. This covers a wide range of scenarios, such as, for example, voting, fair division and ranking. As such, social choice theory enhances our understanding of human societies and can be used as a theoretical foundation for the design of multiagent systems.
In recent years, the study of computational aspects of social choice received a lot of attention from AI and theoretical computer science communities. This interest was motivated by existing and potential applications of social choice ideas in AI settings, which, in turn, highlighted the importance of understanding which of the recommendations of social choice theory are computationally feasible.
The value of algorithmic analysis in the context of social choice stems from the fact that, to be practically applicable, a decision-making rule needs to be efficiently implementable. Indeed, the analysis of computational complexity of well-known voting rules, both in the general case, and in interesting special cases (such as, e.g., single-peaked preferences) is one of the most actively studied topics in computational social choice, with a number of impressive results obtained so far.
However, computational tractability is not the only criterion for selecting a social choice procedure: an equally desirable feature is incentive compatibility, i.e., resilience to dishonest behavior by self-interested participants, who may want to manipulate the outcome of the procedure in their favor. There is an exciting interplay between incentive compatibility and computational tractability: in many settings of interest, computing one's optimal strategy requires solving a hard optimization problem, while acting honestly is computationally easy. Thus, one may view computational complexity as a barrier against strategic behavior, and try to design or identify social choice procedures that make strategizing difficult. This research direction was initiated more than 20 years ago and remains a major research focus of the computational social choice community.
Alternatively, one can deal with manipulative agents in the context of social choice by embracing the strategic behavior rather than trying to prevent it. This can be done either by investigating the outcomes of standard social choice procedures under the assumption that all agents act strategically, or, more ambitiously, by designing social choice procedures that result in desirable outcomes even if agents are not truthful; these two approaches are associated, respectively, with game theory and mechanism design. Both game-theoretic and mechanism design approaches are widely used by the classic social choice community; however, their computational aspects have received relatively little attention so far.
In contrast, algorithmic aspects of strategic behavior in other settings, such as, e.g., matrix games or auctions, have been studied extensively in the last few years. Indeed, computational game theory and algorithmic mechanism design are among the fastest-growing subfields of both AI and theoretical computer science. Thus, in organizing this seminar, we aimed to bring together the researchers in the areas of computational and classic social choice and those in the area of algorithmic game theory. Our goal was to foster a discussion of computational aspects of various forms of strategic behavior in social choice contexts.
The seminar took place on March 4--9, 2012. It was interdisciplinary in nature: among the participants, there were computer scientists, mathematicians, social choice theorists and political scientists. There were 32 regular talks, as well as an after-dinner talk by Virginia Vassilevska-Williams, who spoke about her groundbreaking work on algorithms for matrix multiplication. The seminar talks covered a broad range of topics, such as, e.g., the complexity of dishonest behavior in voting, judgement aggregation, coalitional game theory, and fair division. The program also featured a rump session consisting of short (5--8 minute) talks; these included announcements about events that were likely to be of interest to the seminar participants, short research talks, and presentations of open problems. The participants also used the seminar as an opportunity to continue ongoing research projects or start new ones. We are aware of two research papers that are largely based on discussions that happened during this Dagstuhl seminar; both of them have been recently submitted to the 4th International Workhop on Computational Social Choice. Moreover, several speakers who presented work in progress received useful feedback from other seminar participants, and, as a result, were able to improve or extend their papers significantly. To summarize, the participants of the seminar benefitted from it in a variety of ways: by being exposed to new research results and directions, by getting fresh perspectives on their work, by learning about open problems and initiating new collaborations, and by having an opportunity to work with their co-authors from all over the world on ongoing research projects.
- Craig Boutilier (University of Toronto, CA) [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 München, DE) [dblp]
- Ioannis Caragiannis (CTI & University of Patras, GR) [dblp]
- Jiehua Chen (TU Berlin, DE) [dblp]
- Yann Chevaleyre (University of Paris North, FR) [dblp]
- Vincent Conitzer (Duke University - Durham, US) [dblp]
- Andreas Darmann (Universität Graz, AT) [dblp]
- Britta Dorn (Universität Tübingen, DE) [dblp]
- Daniel Eckert (Universität Graz, AT)
- Edith Elkind (Nanyang TU - Singapore, SG) [dblp]
- Ulle Endriss (University of Amsterdam, NL) [dblp]
- Gabor Erdelyi (Universität Siegen, DE) [dblp]
- Piotr Faliszewski (AGH University of Science & Technology - Krakow, PL) [dblp]
- Felix Fischer (University of Cambridge, GB) [dblp]
- Umberto Grandi (University of Amsterdam, NL) [dblp]
- Paul Harrenstein (TU München, DE) [dblp]
- Edith Hemaspaandra (Rochester Institute of Technology, US) [dblp]
- Lane Hemaspaandra (University of Rochester, US) [dblp]
- Marc Kilgour (Wilfrid Laurier University, CA) [dblp]
- Christian Klamler (Universität Graz, AT) [dblp]
- Sascha Kurz (Universität Bayreuth, DE) [dblp]
- Jérôme Lang (University Paris-Dauphine, FR) [dblp]
- Kate Larson (University of Waterloo, CA)
- Omer Lev (Hebrew University - Jerusalem, IL) [dblp]
- Vangelis Markakis (Athens University of Economics and Business, GR) [dblp]
- Nicolas Maudet (UPMC - Paris, FR) [dblp]
- Vincent Merlin (Caen University, FR) [dblp]
- Ilan Nehama (Hebrew University - Jerusalem, IL) [dblp]
- Svetlana Obraztsova (St. Petersburg Electrotechnical University, RU) [dblp]
- Ulrich Pferschy (Universität Graz, AT)
- Francesca Rossi (University of Padova, IT) [dblp]
- Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
- Lena Schend (Heinrich-Heine-Universität Düsseldorf, DE)
- Arkadii Slinko (University of Auckland, NZ) [dblp]
- Isabelle Stanton (University of California - Berkeley, US)
- Virginia Vassilevska Williams (Stanford University, US) [dblp]
- Toby Walsh (Data61 / NICTA - Sydney, AU) [dblp]
- Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
- Michael Zuckerman (Hebrew University - Jerusalem, IL)
- 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 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)
- artifical intelligence
- robotics / data structures
- computational social choice
- algorithmic game theory