Tutorial on Voting Theory at AAAI-2010
Voting theory is the study of methods for conducting elections. It has attracted a lot of interest from AI researchers in recent years: there are important applications of voting theory in AI (for example, in multiagent systems) and the tools and techniques of AI have proven useful for the study of voting methods (for example, complexity theory, knowledge representation, and automated reasoning).
This tutorial will provide an introduction to the theory of voting for AI researchers. We will present the most important voting procedures and cover some of the classical theorems in the field. We will also see examples for recent work in computational social choice, which brings together ideas from social choice theory (including voting theory) and computer science (including AI).
No specific background knowledge will be assumed; the tutorial will be accessible to anybody working in AI.
Interest in the AI community in problems of voting and social choice has grown rapidly in recent
years (e.g., there are at least a dozen papers on voting at this edition of AAAI). Nevertheless,
most AI researchers are probably not familiar with the basics of the field, which has had a long
and distinguished history in mathematical economics and political science.
The goals of this tutorial are twofold:
- to provide those with little or no background in
the field with a thorough overview of the fundamentals of voting theory; and
- to highlight opportunities for AI researchers to make a contribution to the emerging
field of computational social choice, with special emphasis on voting-related topics.
The tutorial will consist of three parts:
- Voting Procedures and their Properties.
I will introduce the most important voting procedures used in practice and
studied in theory, including the plurality rule, the Borda count and other positional scoring
rules, single transferable vote, the family of Condorcet extensions, and the system of
approval voting. We will also see to what extent these procedures do and do not satisfy
desirable properties such as anonymity, neutrality, monotonicity, and strategy-proofness.
- Major Theorems in Voting Theory.
I will cover some of the most important theorems in the theory of voting, including May's
Theorem on the characterisation of the majority rule for elections with two candidates,
Young's axiomatisation of the positional scoring rules, and the Gibbard-Satterthwaite Theorem
on the impossibility of devising a nondictatorial voting rule that cannot be manipulated.
- Voting Theory and Computational Social Choice.
I will give an overview of how recent work in COMSOC has applied a variety
of techniques from AI and Computer Science to problems related to voting, including: complexity theory
(uses of prohibitive complexity as a barrier against strategic manipulation); knowledge representation
(compact representation of preferences and voting in combinatorial domains);
and automated reasoning (full formalisation and ongoing attempts to produce
fully automated proofs of classical results in voting and social choice theory).