Distortion-based Analysis of Voting: Limited Communication, and an Analysis Framework based on LP Duality and Flows

Abstract:

based on two papers in AAAI 2020:

https://arxiv.org/abs/1911.08129

https://arxiv.org/abs/1911.07162

One recent and successful way of comparing voting rules has been through a utilitarian lens. The n candidates and voters are jointly embedded in a metric space; the distance between a candidate and a voter captures their difference in opinions, and thus the cost the voter would incur if this candidate were elected. The (implicit) goal of the election is to select a candidate minimizing the total cost of all voters. However, voters cannot quantify the distances, and are only able to compare which of two candidates they like better. As a result, voting rules typically only allow submitting a (partial) rank-ordered list of candidates, but no numerical values. The “distortion” of a voting rule is then the worst-case ratio between the total cost of the candidate the voting rule selects (using limited information) and the total cost of the optimum candidate.

Prior work by Anshelevich et al. had shown that while many widely used voting rules have distortion linear in the number of candidates or worse, there are some rules – such as the Copeland rule – whose distortion is upper-bounded by 5. However, all known deterministic rules with constant distortion require voters to communicate their entire ranking, while rules with small communication – such as Plurality, Veto, or k-approval – have large distortion. Our main question is whether this is simply a flaw in the known rules, or an inherent consequence of limited communication.

We show that the latter is the case: every deterministic voting rule in which each voter communicates only the candidates in a set of k positions has distortion at least (2n-k)/k. More generally, every deterministic voting rule that allows each voter to communicate only b bits of information about her ranking has distortion at least \Omega(n/b). On the positive side, we define a new voting rule which generalizes the Copeland rule to ballots in which each voter only ranks her top k candidates, and which achieves distortion O(n/k).

The proof of this upper bound is based on a new technique for analyzing the distortion of voting rules. We start from a well-known linear program for finding worst-case instances of a given voting rule, and use its dual as an upper bound on the distortion. The dual admits a natural interpretation in terms of certain types of flows, and drastically simplifies prior proofs for the distortion of different voting rules. As an additional application, we use this analysis technique to resolve the distortion of the well-known Ranked Pairs and Schulze rules, showing that both have distortion \Theta(\sqrt{n}). Finally, our technique naturally suggests a deterministic voting rule that might achieve distortion 3 – proving that it does would resolve the major open question in the area, and close the gap with an (easy-to-prove) lower bound of 3 on the distortion of every deterministic voting rule.

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, with a particular emphasis on social networks, 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.