AAMAS'10 Tutorial: Computational Voting Theory

Vincent Conitzer and Ariel Procaccia

Short Description

Social choice theory deals with the aggregation of individual preferences. This is a well established and well studied field---the mathematical investigation of social choice dates back to the 18th century. In recent years computer scientists have become involved with social choice theory, giving rise to a new field called computational social choice. One of the main focal points of this field is the computational aspects of elections, or computational voting theory. Computational voting theory provides key techniques for multiagent settings where a decision must be made based on the preferences of multiple agents (e.g., multiple agents that have to decide on a joint plan, in spite of having conflicting preferences over the plans). In this tutorial we give an overview of computational voting theory. We touch on subjects such as the complexity of manipulation in elections, and algorithms (exact and approximate) for winner determination under intractable voting rules, which lie at the intersection of multiagent systems, artificial intelligence, theoretical computer science, economics, and social choice.

Target Audience

Our target audience is researchers who are interested in multiagent systems, electronic commerce (and economic paradigms in general), game theory, and computational complexity. No background is needed beyond graduate knowledge of the foundations of computer science (computational complexity, basic probability theory, approximation algorithms). We feel that this tutorial would be of interest to researchers who work on the mathematical foundations of multiagent systems, but would also be a boon to more applied researchers searching for effective and practical ways of aggregating the preferences of multiple agents.


Vincent Conitzer is an Assistant Professor of Computer Science and Economics at Duke University. He received Ph.D. (2006) and M.S. (2003) degrees in Computer Science from Carnegie Mellon University, and an A.B. (2001) degree in Applied Mathematics from Harvard University. His research focuses on computational aspects of microeconomics, in particular game theory, mechanism design, voting/social choice, and auctions. This work uses techniques from, and includes applications to, artificial intelligence and multiagent systems. Conitzer received an Alfred P. Sloan Research Fellowship (2008), an Honorable Mention for the 2007 ACM Doctoral Dissertation Award, the 2006 IFAAMAS Victor Lesser Distinguished Dissertation Award, the AAMAS Best Program Committee Member Award (2006), and an IBM Ph.D. Fellowship (2005). He is a co-author on papers that received a AAAI-08 Outstanding Paper Award and the AAMAS-08 Pragnesh Jay Modi Best Student Paper Award.

Ariel Procaccia is a CRCS fellow at Harvard's School of Engineering and Applied Sciences. His research interests include Computational Social Choice, Algorithmic Game Theory, and the interplay between these fields and Artificial Intelligence. He received his Ph.D. summa cum laude from the Hebrew University of Jerusalem, under the supervision of Prof. Jeffrey Rosenschein, and subsequently spent a year as a postdoctoral researcher at Microsoft Israel R&D Center. His dissertation, entitled "Computational Voting Theory: Of the Agents, By the Agents, For the Agents", has won the 2008 IFAAMAS Victor Lesser Distinguished Dissertation Award and Hebrew University's Schlomiuk Prize. His work in Harvard SEAS is also supported by a Rothschild Postdoctoral Fellowship.