Borda count is Stablest Conjecture

Let SkS_k be the set of rankings of kk candidates, and let f ⁣:SknΔkf\colon S_k^n\to\Delta_k be a ranked-choice voting method, where Δk\Delta_k is the simplex of randomized outcomes on the candidates. For each coordinate function fjf_j, voter ii has influence Infi(fj)\operatorname{Inf}_i(f_j); the method is balanced when Ef=1ki=1kei\mathbb{E}f=\frac{1}{k}\sum_{i=1}^k e_i, and it satisfies the Condorcet Loser Criterion when a candidate who loses pairwise to every other candidate cannot be selected. Let SρS_\rho denote noise stability under independent ranking corruption, and let Bork,n\operatorname{Bor}_{k,n} be the Borda count method. Borda count is Stablest Conjecture. For any k2k\geq2, ρ[0,1]\rho\in[0,1], and ε>0\varepsilon>0, there exists τ>0\tau>0 such that, for all n1n\geq1, if Infi(fj)τ\operatorname{Inf}_i(f_j)\leq\tau for every voter ii and candidate jj, if ff is balanced, and if ff satisfies the Condorcet Loser Criterion, then

SρflimnSρBork,n+ε.S_\rho f\leq\lim_{n\to\infty}S_\rho\operatorname{Bor}_{k,n}+\varepsilon.

This is the paper's formal ranked-choice analogue of Plurality is Stablest. The source does not report a resolution, so it remains open.

Sources & referencesView supporting material

Primary source

Steven Heilman, “Noise Stability of Ranked Choice Voting”, arXiv:2209.11183 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.