| paper | Sample Complexity for Winner Prediction in Elections |
| authors | P. Dey, Arnab Bhattacharyya |
| venue | ATAL 2015 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The promise is nonempty exactly when $\epsilon\le(m-k)/(2(m-1))$. For $m\ge3$, writing $\beta=(m-k)/m$ and $\Lambda=\log((k+1)/\delta)$, the minimax sample complexity is $\Theta(\beta\epsilon^{-2}\Lambda)$ when $\epsilon\le\beta/16$, and $\Theta(1+\Lambda/\log(1/(1-2\epsilon)))$ otherwise, with universal constants and the infinite-denominator convention at $\epsilon=1/2$. For $m=2$, it is exactly the smallest positive $n$ for which the randomized-majority binomial error at probability $1/2+\epsilon$ is at most $\delta$; at $\epsilon=1/2$ it is one. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given candidates \(C\), a voting rule, \(\epsilon,\delta\), and i.i.d. sampling access to an unknown society distribution \(\mu\) over complete rankings, promised \(\mathrm{MOV}_\infty(\mu)\ge\epsilon\), what is the minimum worst-case number of samples needed to output the true winner with probability at least \(1-\delta\)?
Types are complete rankings \(t\in\mathcal L(C)\) with masses \(\mu_t\); samples return i.i.d. \(t\sim\mu\). For \(k\)-approval, estimate \(p_c=\sum_t\mu_t\mathbf 1[c\text{ is top-}k]\) and output \(\arg\max_c p_c\) under the normalized mass-transfer margin promise.
For every finite profile, the sampling transcript and all aggregate estimates depend only on its empirical distribution, so replacing rational empirical distributions by arbitrary \(\mu\) contributes little new computational structure.
fatal: False
The mirror directly covers Theorems 7 and 6 and the \(k\)-approval and Borda clauses of Theorem 3; it leaves the other rule-specific bounds, elicitation discussion, and social-network questions aside.
There is a credible mirror, but it is a sampling-and-query mirror rather than an LP mirror. The paper contains no named NP-hardness or polynomial-time theorem of its own; its computational results are sample-complexity bounds. I would therefore anchor on those results, not on the paper’s uncited discussion of Kemeny or Dodgson hardness.
The continuous society is a distribution \(\mu\) over complete rankings \(T=\mathcal L(C)\), where \(\mu_t\) is the fraction of the population having ranking \(t\). A query samples an anonymous resident uniformly at random and reveals that resident’s ranking, equivalently returning an independent \(t\sim\mu\). For a voting rule \(r\), define the continuous margin of victory by the minimum mass that must be transferred between ranking types to change the winner: \(\mathrm{MOV}_\infty(\mu)\) is the infimum of \(\sum_{t\ne t'}x_{t,t'}\) over all transfers \(x_{t,t'}\ge 0\) producing a distribution \(\mu'\) with \(r(\mu')\ne r(\mu)\). Thus changing one finite vote corresponds exactly to moving mass \(1/n\).
The continuous problem is therefore: given \(C\), the rule, \(\epsilon,\delta\), and sampling access to an unknown \(\mu\) promised to satisfy \(\mathrm{MOV}_\infty(\mu)\ge\epsilon\), design a randomized algorithm that outputs \(r(\mu)\) with probability at least \(1-\delta\), while minimizing the worst-case number of samples. The action variable is the queried mass points; the objective is sample complexity.
This is a sensible high-multiplicity regime for large polls, national elections, consumer surveys, or recurring preference panels. There may be millions of respondents but only a moderate number of recurring ranking types, with \(n\gg |T|\) or, more realistically, \(n\) much larger than the support of \(\mu\). For \(k\)-approval, one can even quotient types by their top-\(k\) set when only the winner matters. The authors would recognise this as their problem: the paper’s central task is already to predict the full-population winner from a small number of queried votes.
My lead mirror is \(\textsc{Continuous-k\)-Approval-Winner-Prediction}\). Its instance consists of \(C\), \(k\), \(\epsilon\), \(\delta\), and a sampling oracle for \(\mu\). The promise is \(\mathrm{MOV}_\infty(\mu)\ge\epsilon\). A solution is a randomized sampling algorithm that returns the \(k\)-approval winner of \(\mu\) with probability at least \(1-\delta\); the question is the minimum worst-case number of queries.
The anchor is Theorem 7, proved in this paper: “There is an \((\epsilon,\delta)\)-winner determination algorithm for the \(k\)-approval voting rule with sample complexity \(O(\log(k/\delta)/\epsilon^2)\).” The theorem’s proof transfers directly. If \(X_i(c)\) indicates whether candidate \(c\) appears in the top \(k\) positions of the \(i\)-th sampled ranking, then \(\frac{1}{\ell}\sum_i X_i(c)\) estimates the continuous approval mass of \(c\). The proof uses the same multiplicative Chernoff argument and the fact that the total \(k\)-approval mass is \(k\). Hence this mirror is Class A: tractable, with sample complexity independent of the population size and, in the sparse-\(k\) regime, essentially independent of \(m\).
The paper’s Theorem 3, also proved here, supplies an important lower-bound companion. Its \(k\)-approval clause states that every \((\epsilon,\delta)\)-winner-determination algorithm needs \(\Omega((\log k/\epsilon^2)(1-\delta))\) samples; Table 1 writes the equivalent \(\log(k+1)\) form. The proof constructs distributions over votes with different winners and transfers them directly to continuous societies. Thus the continuous problem is not merely made easy by replacing voters with masses: its information-theoretic sample requirement remains. For fixed \(\delta\), the upper and lower bounds match up to constants.
A second useful mirror is \(\textsc{Continuous-Scoring-Winner-Prediction}\). Here the instance additionally contains a normalized scoring vector \(\alpha=(\alpha_1,\ldots,\alpha_m)\), and the score of \(c\) is \(\mathrm{sc}_\mu(c)=\sum_t\mu_t\alpha_{\operatorname{pos}_t(c)}\). The solution is again a sampling algorithm returning the scoring winner under the continuous margin promise.
The anchor is Theorem 6, proved in this paper: for every normalized scoring vector, there is an \((\epsilon,\delta)\)-winner-determination algorithm with sample complexity \(O(\log(m/\delta)/\epsilon^2)\). In the continuous model, each sample gives a bounded random contribution to every candidate’s score, so the paper’s concentration proof applies without any finite-\(n\) modification. This covers Borda, approval, veto, and every other scoring rule in the theorem. It is again Class A in the query-complexity sense.
For the Borda specialization, the relevant lower-bound question can be stated precisely as \(\textsc{Continuous-Borda-q-Sample-Feasibility}\): given \(m,\epsilon,\delta\), and a budget \(q\), does there exist an algorithm using at most \(q\) samples that succeeds for every continuous society with \(\mathrm{MOV}_\infty(\mu)\ge\epsilon\)? The Borda clause of Theorem 3, proved here, says that every such algorithm needs \(\Omega((\log m/\epsilon^2)(1-\delta))\) samples. Its lower-bound distributions \(\mu_1,\ldots,\mu_m\) can be taken as the continuous societies themselves, each having a different Borda winner, continuous margin \(\Omega(\epsilon)\), and only \(O(\epsilon^2)\) statistical separation. Thus the continuum version preserves the paper’s \(\log m\) barrier. Together with Theorem 6, this gives matching dependence on \(m\) for constant \(\delta\).
The mirror therefore covers the paper’s winner-prediction results, especially Theorems 3, 6, and 7. It does not claim to continuize the paper’s discussion of preference elicitation, social-network structure, or the cited NP-hard winner-determination rules. Further questions would include whether partial rankings can reduce continuous sample complexity, whether adaptive sampling helps when the margin is unknown, and how the bounds change when \(m\) and the number of active ranking types grow together.
The weakest point is that this mirror is close to the paper’s own statistical viewpoint. The paper already represents a finite profile by its empirical distribution and uses distributions in its lower-bound proofs. In rational finite instances, the sampling law is literally the same. An opponent can therefore argue that the mirror adds little beyond allowing irrational masses and removing voter identities. That criticism is real. Still, the paper’s formal society is a finite set of named voters, whereas the mirror makes \(\mu\) itself the object of study, defines margin by transferred mass, and asks for algorithms over an actual high-multiplicity population. The resulting question is not a different, weakened voting problem: it is the paper’s winner-prediction problem in the regime where population mass, rather than individual enumeration, is the honest input.
The strongest negative case is that the proposed mirror is not a continuization of the paper at all: it is the paper’s own statistical model, rewritten with arbitrary rather than rational probabilities.
For every finite profile \(V\), the paper already forms the empirical distribution \(\mu_V\) over rankings. Under the sampling access model, querying a uniformly random voter is exactly sampling from \(\mu_V\). The transcript distribution, every score estimate, and every lower-bound argument depend only on \(\mu_V\), not on voter names or on the fact that its coordinates have denominator \(n\). The paper makes this identification explicitly in its proof of Lemma 1. Its lower bounds are already stated in terms of distributions \(\mu_i\), and its upper bounds estimate expectations under the empirical distribution.
Thus replacing rational empirical distributions by arbitrary points of the simplex is merely taking a closure of the paper’s instance space. It does not make the population a new computational object. There is a useful dichotomy:
The proponent’s mirror chooses the second option, so it inherits the collision.
This defeats Theorem 7 as an anchor. For \(k\)-approval, define
\[ p_c(\mu)=\sum_t \mu_t\,\mathbf 1[c\text{ is in the top }k\text{ positions of }t]. \]
The winner is simply the candidate maximizing \(p_c(\mu)\), and \(\sum_c p_c(\mu)=k\). Theorem 7 estimates these expectations from samples. Nothing in the proof uses the population as a manipulable continuum, or even the full ranking type. One can quotient every ranking to its top-\(k\) set and obtain precisely the same distribution-learning problem over \(k\)-subsets.
The proposed \(\mathrm{MOV}_\infty\) does not create new structure either. With unit cost for changing a vote, moving mass from type \(t\) to type \(t'\) is exactly the normalized version of changing one finite vote. For every rational \(\mu\), the continuous mass-transfer problem is just the finite MOV divided by \(n\). The mass formulation is a useful notation, but not a new problem for the authors’ theorem.
Theorem 3 is an even weaker anchor. Its \(k\)-approval lower bound is already proved by constructing distributions \(\mu_1,\ldots,\mu_{k+1}\) and giving a sampling lower bound for distinguishing them. Those \(\mu_i\) are literally the proposed continuous societies. The finite elections are only rational realizations of those distributions. Calling the same oracle distributions “continuous populations” adds no new theorem or model.
The same objection applies to Theorem 6. For a scoring vector \(\alpha\),
\[ \mathrm{sc}_\mu(c) = \sum_t \mu_t\,\alpha_{\operatorname{pos}_t(c)} \]
is already the expectation of the bounded random variable revealed by a sampled vote. Theorem 6 is consequently a uniform mean-estimation result over the empirical sampling law. Borda’s lower-bound distributions in Theorem 3 are likewise already continuous objects in every operational sense relevant to the theorem.
A stronger proposed mirror could introduce explicit compressed representations of \(\mu\), nonuniform query costs, partial-ranking queries, or nontrivial distances between ranking types. But each move changes the paper’s problem. Explicit access removes the sampling problem; compressed access adds a new representation model; partial queries change the oracle; and swap or transport costs turn MOV into a bribery problem absent from the paper. Those may be worthwhile ChoCo problems, but they cannot serve as continuous mirrors of Theorems 3, 6, or 7.
I concede that the high-multiplicity story itself is entirely sensible: national elections, polls, and recurring surveys can naturally contain many voters of each ranking type. That is not the objection. The objection is that this paper has already abstracted away the population into its empirical distribution and studies sampling from it. The continuous-population version therefore collides with the paper’s operational model rather than extending it.
This negative case is not airtight as a claim about every conceivable extension. A formally packaged “finite-versus-arbitrary sampling law” theorem could still be useful to the programme. But if a continuous mirror must introduce a genuinely new population-level computational object, the three proposed anchors do not provide one.
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.