Voting Rules and the Metric Distortion Framework

Abstract:
The study of voting rules – algorithms mapping voters’ rank-ordered ballots to a winner of an election – dates back centuries. Many different desirable axioms have been formulated, and frequently found to be incompatible with each other.
An alternative perspective has been proposed and studied more recently, mostly by the computer science community. This perspective views the goal of the voting rule implicitly as optimizing a (cardinal) objective function such as utility or cost, but about which the voting rule only receives ordinal information, namely, a ranking. Missing from this ranking is the strength of preferences, and the goal of the voting rule is to select an approximately best candidate despite lacking this information. The currently most actively studied instantiation of this framework is when the voters and candidates jointly form a metric space, and voters rank candidates by increasing distance from themselves.

This viewpoint has led to interesting differentiations between known voting rules, as well as the discovery of elegant new voting rules with strong guarantees. The mathematical analysis is often quite elegant and insightful.

In this talk, I will begin with a self-contained introduction to (metric) distortion as an analysis framework for voting rules. Subsequently, we will review some of the basic results, as well as a recent elegant voting rule giving the best possible metric distortion guarantees. We will explore connections between voting rules and matchings in certain bipartite graphs, and discuss recent results and open questions on randomized metric distortion and other related topics.

(This talk represents mostly joint work with Fatih Kizilkaya, and will also discuss earlier and recent work by other groups.)

Bio:
David Kempe received his Ph.D. from Cornell University in 2003, and has been on the faculty in the computer science department at USC since the Fall of 2004, where he is currently a Professor.

His primary research interests are in computer science theory and the design and analysis of algorithms. His current research focus is on social choice theory (analysis of voting rules); past work includes algorithmic problems on social networks, information design, algorithms related to online and other learning models, and game-theoretic and pricing questions.

He is a recipient of the NSF CAREER award, the VSoE Junior Research Award, the ONR Young Investigator Award, a Sloan Fellowship, and an Okawa Fellowship, in addition to several USC mentoring awards and Best Paper awards.