07.06.15 - 12.06.15, Seminar 15241

Computational Social Choice: Theory and Applications

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Press Room

Motivation

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 ig 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.