Computation and Incentives in Social Choice

Motivation

Computational social choice is an active research area that combines tools and techniques of theoretical computer science and AI with those of mathematics, social sciences and economics. It studies algorithmic aspects of social choice procedures, i.e. rules and principles of collective decision making, as well as applications of social choice ideas in the context of computing. In many situations considered by both classic and computational social choice, individual agents may try to act strategically, i.e., manipulate the outcome of the social choice procedure in their favor. The goal of this seminar is to develop a better understanding of game-theoretic and computational aspects of social choice issues. To this end, we would like 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 is to foster a discussion of computational aspects of various forms of strategic behavior in social choice contexts. Specific topics of interest include (but are not limited to):

• Worst-case and average-case complexity of manipulation of voting rules, either by individual voters or by coalitions of voters, under realistic assumptions about the voters' preference distributions.
• Properties and outcomes of the voting procedures when all voters act strategically; efficient algorithms for computing voters' equilibrium strategies for various voting rules.
• Social choice in dynamic settings, where voters can change their vote in response to the observed behavior of other voters; algorithmic aspects of adaptive behavior in social choice scenarios.
• The complexity of mechanisms implementing social choice procedures.
• Strategy-proof methods of fair division and their computational aspects.
• Efficient mechanisms for truthful elicitation of voters' preferences.