Computational Voting Theory: Of the Agents, By the Agents, For the Agents

Jeffrey S. Rosenschein

The School of Engineering and Computer Science, The Hebrew University of Jerusalem, Israel

Classical social choice theory deals with the design and analysis of methods for collective decision making. Heterogeneous, self-interested agents may have conflicting preferences, which can be aggregated by voting over possible outcomes. The winning outcome is then designated by a voting rule, a function from the preferences of the voters to the set of candidates.

Recent years have seen a surge of interest in the computational aspects of social choice, motivated by applications of voting theory to electronic commerce, electronic voting, and multiagent systems. The candidates in automated multiagent systems can be beliefs, joint plans, schedules, movies, or indeed entities of almost any conceivable sort. Computational voting theory is concerned both with the application of computer science techniques to the study of social choice mechanisms, and with the importing of social choice concepts into computing.

This talk will present an overview of some of the issues that have been dealt with in recent years within computational voting theory, including distortion, robustness, the use of complexity as a guard against manipulation, the automated design of voting rules, and the calculation of power indices.

This talk covers joint work with Ariel D. Procaccia, Aviv Zohar, Michael Zuckerman, Yoni Peleg, Gal Kaminka, Yoram Bachrach, and Reshef Meir.