An Analysis Framework for Metric Voting based on LP Duality

David Kempe

Abstract

Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. $m$ voters and $n$ candidates are jointly embedded in an (unknown) metric space, and the voters submit rankings of candidates by non-decreasing distance from themselves. Based on the submitted rankings, the social choice rule chooses a winning candidate; the quality of the winner is the sum of the (unknown) distances to the voters. The rule's choice will in general be suboptimal, and the worst-case ratio between the cost of its chosen candidate and the optimal candidate is called the rule's distortion. It was shown in prior work that every deterministic rule has distortion at least 3, while the Copeland rule and related rules guarantee distortion at most 5; a very recent result gave a rule with distortion $2 + \sqrt{5} \approx 4.236$. We provide a framework based on LP-duality and flow interpretations of the dual which provides a simpler and more unified way for proving upper bounds on the distortion of social choice rules. We illustrate the utility of this approach with three examples. First, we show that the Ranked Pairs and Schulze rules have distortion $\Theta(\sqrt{n})$. Second, we give a fairly simple proof of a strong generalization of the upper bound of 5 on the distortion of Copeland, to social choice rules with short paths from the winning candidate to the optimal candidate in generalized weak preference graphs. A special case of this result recovers the recent $2 + \sqrt{5}$ guarantee. Finally, our framework naturally suggests a combinatorial rule that is a strong candidate for achieving distortion 3, which had also been proposed in recent work. We prove that the distortion bound of 3 would follow from any of three combinatorial conjectures we formulate.

Introduction

In the field of social choice theory, the goal is to aggregate individual voter preferences to select a single winner from a set of candidates. The metric voting model provides a robust framework for this by assuming that voters and candidates are embedded in a common metric space. In this model, a voter's "cost" for a candidate is the distance between them, and voters provide ordinal rankings based on these distances.

The central challenge is distortion: because the voting rule only observes ordinal rankings rather than cardinal distances, it may select a candidate whose total distance from all voters is significantly higher than that of the optimal candidate (the one minimizing total distance). While it is known that no deterministic rule can achieve a distortion lower than 3, finding rules that approach this bound has historically required complex, ad-hoc case analyses.

The Flow-Based Framework

The primary contribution of this work is a novel analysis framework based on Linear Programming (LP) Duality. The problem of finding the worst-case distortion for a given rule can be formulated as a primal LP: maximizing the ratio of total costs over all possible metric spaces consistent with the observed rankings.

By taking the dual of this LP, the author derives a flow interpretation. The problem is transformed into routing flow on a graph where nodes represent (voter, candidate) pairs. In this dual graph, "preference edges" (moving along a voter's ranking) have zero cost, while "sideways edges" (moving between different voters) incur costs based on the metric properties.

The flow interpretation of the dual LP, showing how units of flow are routed between nodes representing voter-candidate pairs.

To prove an upper bound on distortion, one simply needs to construct a valid flow from the chosen winner to the optimal candidate. This unified approach replaces intricate case distinctions with a single, intuitive tool: if "mass" can be moved from the winner to the optimum primarily using preference edges, the distortion is guaranteed to be low.

The framework reveals surprising results for well-known voting rules. Ranked Pairs and the Schulze rule, despite their popularity and adherence to various axiomatic properties, are shown to have high distortion—specifically $\Theta(\sqrt{n})$. This implies that as the number of candidates $n$ grows, these rules can perform significantly worse than simpler alternatives like the Copeland rule, which maintains a constant distortion bound.

A graph construction used to establish lower bounds on distortion for complex voting rules like Ranked Pairs and Schulze.

The analysis of these rules involves constructing specific preference profiles that force high distortion, often represented through complex graph structures like the one shown above.

Toward Optimal Distortion

The flow framework also points toward a potential path for achieving the optimal distortion of 3. The author proposes a combinatorial rule based on the existence of perfect matchings in specific bipartite graphs of voters. If a candidate $w$ exists such that for every other candidate $x$, a certain matching condition is met, the distortion is guaranteed to be 3.

The author formulates three equivalent combinatorial conjectures—ranging from graph Hamiltonicity to probability distributions—that would prove the existence of such a candidate for any number of candidates. While these conjectures have been verified via computer search for $n \le 7$, a general proof remains an open challenge.

Conclusion and Future Work

This research provides a powerful new lens for social choice theory, simplifying the analysis of distortion and exposing the limitations of popular voting rules. Future work includes proving the "distortion 3" conjectures for general $n$ and extending the framework to randomized voting rules, where the goal is to bound expected distortion. Additionally, exploring the framework's applicability in non-metric spaces where the triangle inequality may not hold remains a fertile ground for investigation.

Summary updated

Abstract

Distortion-based analysis has established itself as a fruitful framework for comparing voting mechanisms. m voters and n candidates are jointly embedded in an (unknown) metric space, and the voters submit rankings of candidates by non-decreasing distance from themselves. Based on the submitted rankings, the social choice rule chooses a winning candidate; the quality of the winner is the sum of the (unknown) distances to the voters. The rule's choice will in general be suboptimal, and the worst-case ratio between the cost of its chosen candidate and the optimal candidate is called the rule's distortion. It was shown in prior work that every deterministic rule has distortion at least 3, while the Copeland rule and related rules guarantee distortion at most 5; a very recent result gave a rule with distortion 2 + √5 ≈ 4.236.We provide a framework based on LP-duality and flow interpretations of the dual which provides a simpler and more unified way for proving upper bounds on the distortion of social choice rules. We illustrate the utility of this approach with three examples. First, we show that the Ranked Pairs and Schulze rules have distortion Θ(√n). Second, we give a fairly simple proof of a strong generalization of the upper bound of 5 on the distortion of Copeland, to social choice rules with short paths from the winning candidate to the optimal candidate in generalized weak preference graphs. A special case of this result recovers the recent 2 + √5 guarantee. Finally, our framework naturally suggests a combinatorial rule that is a strong candidate for achieving distortion 3, which had also been proposed in recent work. We prove that the distortion bound of 3 would follow from any of three combinatorial conjectures we formulate.
BibTeX
@inproceedings{kempe2020analysis,
  author = {David Kempe},
  title = {{An Analysis Framework for Metric Voting based on LP Duality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=AoanR3WsDS},
}
Figure