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.