Abstract:The communication complexity of a voting rule is the worst-case number of bits that n voters must transmit to a central authority under the most efficient elicitation protocol in an election with m candidates. We study the communication complexity of Instant-Runoff Voting (IRV). Conitzer and Sandholm [2005] established an upper bound of O(n (log m)${}^2$), but did not provide a matching lower bound beyond $\Omega$(n log m). We resolve this open problem by raising the lower bound to $\Omega$(n (log m)${}^2$) using the fooling set technique, thereby showing that the communication complexity of IRV is $\Theta$(n (log m)${}^2$). We further show that this complexity drops to $\Theta$(n log m) under the single-peakedness restriction, and that both the IRV-Average variant and Single Transferable Vote (STV), the multiwinner extension of IRV, have the same asymptotic communication complexity as IRV.
| Subjects: | Multiagent Systems (cs.MA) |
| Cite as: | arXiv:2605.23743 [cs.MA] |
| (or arXiv:2605.23743v1 [cs.MA] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23743 arXiv-issued DOI via DataCite (pending registration) |
From: Francois Durand [view email] [via CCSD proxy]
[v1]
Fri, 22 May 2026 15:18:25 UTC (31 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。