Tree plurality veto improves voting efficiency with fewer rounds

Tree Plurality Veto: Voting in Few Rounds with Efficient Communication and Low Metric Distortion

Computer Science and Game TheoryArtificial IntelligenceDiscrete MathematicsData Structures and Algorithms

Summary

Choosing the best candidate based on voters’ ranked preferences can be slow or communication-heavy when many people and options are involved. This paper looks at how to balance the number of communication rounds and the total amount of data exchanged while still picking a candidate close to the best possible choice. The authors introduce a new voting method called TreePluralityVeto that organizes voters into groups and collects limited preference information in parallel, achieving good accuracy with fewer rounds and less communication. This approach allows a flexible tradeoff between how many rounds of communication happen and how much data is sent overall.

What this means in practice

  • For distributed system designers: Optimize protocols that aggregate user preferences with fewer communication rounds and less data exchange while maintaining result accuracy.
  • For online polling platforms: Implement voting mechanisms that quickly approximate group consensus with controlled communication overhead to improve scalability.

Authors

Gabriel Chen, Yu Cheng, Alice Wang

Abstract

We consider the metric distortion framework for voting, where $n$ voters and $m$ candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of $3$ in one round by eliciting complete rankings using $Θ(nm\log m)$ bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only $O(n\log m)$ bits but requires $Θ(n)$ rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every $r\ge 2$, achieves distortion at most $2r-1$ using at most $r$ rounds and $O(n\log m+n s^{1/(r-1)}\log s)$ bits of total communication, where $s = \min\{n, m\}$. The protocol runs PluralityVeto on a hierarchical partition of the voters, collecting restricted rankings in parallel at each level. The branching factor controls the tradeoff between rounds and communication, and a matching-based analysis shows that each level increases the distortion bound by at most $2$.
View PDFOpen arXiv