Abstract:We study the limit CM rate of single-winner voting rules under Impartial Culture, defined as the probability that a preference profile is coalitionally manipulable in the limit of large electorates. For m = 3 candidates, Lepelley and Valognes [1999] derived a closed-form expression for Plurality with Runoff, or equivalently Instant-Runoff Voting (IRV), and showed that its limit CM rate is strictly below 1. This is remarkable because Kim and Roush [1996] established a limit of 1 for several major rules, including Maximin and all positional scoring rules except Veto. In this paper, we generalize the result of Lepelley and Valognes to any number of candidates m $\ge$ 4. We show that Plurality with Runoff has a limit CM rate equal to 1 for all m $\ge$ 4, whereas IRV retains a limit CM rate strictly below 1. To this end, we rely on the notion of Super Condorcet Winner, recently introduced by Durand [2025], which yields an upper bound on the CM rate of IRV. We prove that this bound is asymptotically tight and compute the probability that a Super Condorcet Winner exists, thereby obtaining the exact limit CM rate of IRV.
| Subjects: | Computer Science and Game Theory (cs.GT) |
| Cite as: | arXiv:2605.23742 [cs.GT] |
| (or arXiv:2605.23742v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23742 arXiv-issued DOI via DataCite (pending registration) |
From: Francois Durand [view email] [via CCSD proxy]
[v1]
Fri, 22 May 2026 15:16:27 UTC (325 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。