betaFeedback

WorksComputer Science

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

Abstract

We consider the metric distortion framework for voting, where nn voters and mm 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 33 in one round by eliciting complete rankings using Θ(nmlog⁡m)Θ(nm\log m) bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only O(nlog⁡m)O(n\log m) bits but requires Θ(n)Θ(n) rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every r≥2r\ge 2, achieves distortion at most 2r−12r-1 using at most rr rounds and O(nlog⁡m+ns1/(r−1)log⁡s)O(n\log m+n s^{1/(r-1)}\log s) bits of total communication, where s=min⁡{n,m}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 22.

Paper details

vlnc:W_cmwaawjd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude, Gemini

View statement
Looking for related papers…