| paper | Sampling Winners in Ranked Choice Voting |
| authors | Matthew Iceland, Anson Kahng, Joseph Saber |
| venue | IJCAI 2024 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The numbered results establish probability bounds and structural sampling guarantees, but none asserts complexity, an algorithm, or a parameterized result for a computational problem. Theorem 1 has a faithful high-multiplicity restatement, and Proposition 2 suggests a sensible mass-robustness extension, so the population analogue itself is not the problem. The required computational anchor is absent, making the grade red under the explicit gate.
fails bit a — no named computational result to mirror
The explicit-μ formulation gives the evaluator the hidden society and reduces the task to computing weighted RCV and summing masses; keeping μ hidden instead requires a new statistical information model.
fatal: True
The proposed mirror covers the one-ballot accuracy identity in Theorem 1 and a new mass-robustness reading of Proposition 2; it leaves the finite-deletion phenomena, Proposition 3, and all synthetic and real-data experiments untouched.
The strongest honest positive case is narrow but real: this paper has a direct continuous mirror for its sampling and winner-robustness results, led by Theorem 1. It is not, however, a paper with named \(P\), NP-hardness, FPT, or W[1]-hardness results. If ChoCo’s anchor gate requires a classical complexity classification, the paper fails that gate. If sample/query complexity and computational robustness count, two anchors are defensible.
The regime is a large ranked-choice electorate with \(n\gg\tau\): many voters belong to a relatively small number of recurring ballot cohorts. A type \(t\) is a complete ranking of the \(m\) candidates, and \(\mu_t\) is the fraction of voters with that ranking. This is plausible for city elections, party or issue coalitions, and survey populations responding to a fixed candidate slate. No preferences are fractionalized; only the population is represented by rational mass.
My lead anchor is Theorem 1, proved in the paper:
\[ \text{For }g(n)=1\text{ and }m\ge2,\qquad A_R(g,m)=\frac{1}{2^{m-1}}. \]
The continuous problem is:
Hidden-Mass One-Draw RCV Prediction. An adversary chooses a rational society \(\mu\) over complete rankings, but the predictor does not see \(\mu\). It observes one ballot type \(t\sim\mu\), runs RCV on that one-ballot sample, and outputs its top-ranked candidate. The true answer is \(w(\mu)=\operatorname{RCV}(\mu)\). Given \(\mu\) to the evaluator and a threshold \(q\), determine whether
\[ \Pr_{t\sim\mu}\!\left[\operatorname{top}(t)=w(\mu)\right]\ge q. \]
A solution is the exact winner \(w(\mu)\) and success probability
\[ p_1(\mu)= \sum_{t:\operatorname{top}(t)=w(\mu)}\mu_t. \]
This is a direct rational-clone mirror. Clearing denominators in \(\mu\) produces the finite profile in the paper, and scaling the paper’s extremal profiles produces arbitrarily large high-multiplicity instances with the same \(\mu\). The proof’s vote-share inequalities are homogeneous, so the bound survives the passage from counts to mass. The continuous worst case is therefore again \(2^{-(m-1)}\).
Its expected classification is Class A for explicit type distributions: compute RCV on \(\mu\), then sum the masses whose first choice is the resulting winner. The global worst-case value is even given in closed form. The important fidelity point is that \(\mu\) is hidden from the predictor, exactly as the full profile is hidden in the paper; revealing \(\mu\) would trivialize the prediction problem.
The second anchor is Proposition 2, derived in this paper rather than merely cited. It states that if \(x\) is the number of first-choice votes for the full-election RCV winner and \(M(\vec\sigma)\) is the margin of victory, then every sample of size at least
\[ \min\!\left( 2(n-x)+1,\, (m-1)\bigl(n-2M(\vec\sigma)\bigr)+1 \right) \]
returns the correct winner.
Its continuous mirror is:
Continuum Universal-Sample Threshold for RCV. Given a society \(\mu\), let \(w=\operatorname{RCV}(\mu)\). A sampled population is any submass \(\nu\) satisfying \(0\le\nu_t\le\mu_t\), with total mass \(\|\nu\|_1>0\); RCV is run on the normalized sample \(\nu/\|\nu\|_1\). Compute
\[ \alpha^\star(\mu)= \inf\left\{ \alpha: \forall \nu\le\mu,\ \|\nu\|_1\ge\alpha \Rightarrow \operatorname{RCV}\!\left(\frac{\nu}{\|\nu\|_1}\right)=w \right\}. \]
A solution is either the exact threshold \(\alpha^\star(\mu)\), or, for a proposed \(\alpha\), a yes-answer or a bad-sample certificate \(\nu\) of mass at least \(\alpha\).
Let
\[ x=\sum_{t:\operatorname{top}(t)=w}\mu_t \]
and let \(\rho(\mu)\) be the minimum mass that must be transferred between ranking types to change the RCV winner. The natural normalized limit of Proposition 2 is the upper bound
\[ \alpha^\star(\mu) \le \min\!\left( 2(1-x),\, (m-1)(1-2\rho(\mu)) \right), \]
with the finite \(+1\) terms disappearing after normalization.
This problem is also expected to be Class A in the explicit-type model. For a fixed elimination order, every RCV condition is a linear inequality in the sample masses \(\nu_t\). A bad sample is therefore certified by an LP corresponding to an elimination order ending in a wrong winner. Maximizing \(\|\nu\|_1\) over those LPs gives the largest bad sample mass. Enumerating the orders is polynomial in the explicit type-universe accounting when \(\tau=m!\), though not necessarily polynomial in \(m\) alone.
These two mirrors are author-recognizable: the first changes profile counts into ballot-type frequencies while preserving the hidden-sampling experiment; the second changes the finite sample-size guarantee into a guarantee over subpopulations of a given mass. They cover the paper’s theoretical sampling section, not the empirical map-of-elections experiments, multiplicative-weights predictors, or real-world datasets.
The main weakness is that Theorems 2–4 do not transfer directly to a pure atomless population model. In Theorem 2, deleting one voter has mass \(1/n\), which becomes zero as \(n\) grows. A uniformly sampled mass from an ideal atomless population can preserve every type proportion exactly, making the sample’s RCV outcome equal to the population outcome. Recovering the paper’s zero-accuracy phenomenon requires finite random draws, finite-resolution sampling, or adversarial type-correlated deletion; each is an additional modelling choice. I would therefore not claim those theorems as direct continuous mirrors.
So the positive case is not that the whole paper becomes a continuous-complexity paper. It is that Theorem 1 gives a clean direct high-multiplicity sample-complexity mirror, while Proposition 2 opens a genuine mass-based winner-robustness problem with an LP formulation and a plausible Class-A boundary.
The proponent has identified coherent weighted restatements, but not a worthwhile ChoCo mirror under the programme’s computational standard. The decisive preliminary point is that this paper contains no named complexity or algorithmic result. Theorems 1–4 and Proposition 2 are probability bounds and structural guarantees, not claims about \( \mathrm P \), hardness, approximation, query complexity, or parameterized computation. Wrapping one of them in a new decision problem does not make that decision problem a result of the paper.
Theorem 1 is the strongest apparent case, and its rational-clone transfer is correct. If \( \mu \) is explicitly given, one can run RCV on \( \mu \), obtain \( w(\mu) \), and compute
\[ p_1(\mu)=\sum_{t:\operatorname{top}(t)=w(\mu)}\mu_t. \]
That is a faithful weighted identity, but it is not a prediction problem any longer. The predictor in the paper sees only a sampled ballot; the proposed computational formulation gives the evaluator the hidden society \( \mu \). Once \( \mu \) is explicit, the unknown-distribution aspect has disappeared and the remaining task is just evaluating RCV and summing masses.
Conversely, if \( \mu \) remains hidden, there is no ordinary continuous-society input on which an algorithm operates. The task becomes statistical learning from observations, not computation over a supplied society. It can certainly be studied, but it is a new distribution-learning problem whose difficulty depends on the information model, sampling oracle, confidence requirement, and whether sampling is with or without replacement. Those choices are not consequences of Theorem 1.
A stronger version—ask for the minimum number of draws needed to identify the RCV winner with confidence \(1-\delta\)—would be a sensible statistical question. It would also be an extension rather than a mirror of a computational result in this paper. The one-draw case is especially weak as a ChoCo anchor because the continuous operation is simply “draw a type according to its mass”; the paper’s theorem already gives the complete minimax answer. Continuization supplies notation, not a new computational object.
Proposition 2 does not repair this. It is a sufficient sample-size bound, not an algorithmic theorem. The proposed quantity
\[ \alpha^\star(\mu)= \inf\left\{ \alpha: \forall \nu\le\mu,\ \|\nu\|_1\ge\alpha \Rightarrow \operatorname{RCV}\!\left(\frac{\nu}{\|\nu\|_1}\right)=w(\mu) \right\} \]
is a new worst-case subpopulation-deletion problem. It replaces the paper’s sampling experiment by an adversary choosing an arbitrary fractional submass. That replacement is recognizable and mathematically defensible, but it is not what the paper studies.
The proposed LP formulation may well be correct: for each elimination order, RCV’s conditions are linear in \( \nu \), and enumerating orders is polynomial in an explicitly represented type universe of size \( \tau=m! \). But this establishes the tractability of a newly designed robustness problem, not the computational content of Proposition 2. The proposition supplies only an upper bound involving \(x\) and \(M(\vec\sigma)\); it neither defines nor analyzes the exact optimization problem \( \alpha^\star \). The LP is therefore evidence for a possible follow-up paper, not an anchor inherited from this one. The objection is not that the LP is easy; it is that the LP is solving a different predicate.
The paper’s genuinely population-sensitive phenomenon is the instability caused by deleting one or \(k\) individual ballots. That content does not survive a pure mass limit. A missing \(k\) ballots has mass \(k/n\), which tends to zero, while the normalized sample converges to the full distribution. Theorems 2 and 3 consequently collapse in an atomless model. They can be recovered only by retaining a finite-resolution parameter \(1/n\), adding an explicit finite sampling layer, or replacing deletion by a positive-mass adversarial coalition. Each repair is reasonable, but each introduces new structure absent from the continuous society itself.
Thus the negative case is strongest under a strict ChoCo gate: Theorem 1 is a rational weighted restatement of a statistical bound, Proposition 2 motivates a new robustness optimization rather than mirroring a computational result, and the remaining worst-case sampling results depend on finite individual granularity. There is no identity or multiplicity obstruction—ranked ballots are perfectly legitimate types—and that is why the negative case is not airtight. If ChoCo admits statistical extensions and newly formulated robustness problems as anchors, the proponent’s narrow case survives. But under the programme’s stated computational remit, this paper does not furnish a worthwhile continuous-complexity mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.