| paper | d4-conf-atal-2008-0189 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) (polynomial-time solvable), including with unequal weights. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given candidates \(C\), a target \(c^\star\), and types \(t\in T\) with rational masses \(\mu_t\), per-member weights \(w_t\), and distributions \(p_t\) over rankings, determine whether there are masses \(x_{t,\pi}\ge 0\), restricted to rankings with \(p_t(\pi)>0\), such that \(\sum_{\pi}x_{t,\pi}=\mu_t\) for each \(t\) and \(c^\star\)'s weighted Plurality score is at least every other candidate’s. The instance is the type list and its binary-rational data; report the complexity in \(|C|\), \(|T|\), the number of supported type-ranking pairs, and the input bit length.
A continuum population with finitely many types. Each type has a fixed per-member weight and a support of possible rankings; decision variables split its mass among those rankings. Feasibility asks whether some supported mass profile makes the target a weighted Plurality co-winner.
Covers Theorem 9’s Plurality possibility question. It does not mirror the exact winning-probability results, including Theorem 4, or the paper’s results for other voting rules.
The strongest case I believe is narrow: mirror Theorem 9’s possibility question, not the paper’s exact probability-evaluation problem.
Theorem 9, proved in this paper, says that when the numbers of voters and candidates are unbounded, deciding whether a designated candidate has *any chance* to win under Plurality is NP-complete in the weighted-voter setting. The reduction is from Bin Packing; the paper notes that the hardness persists even when voter weights are polynomially bounded. This is a strong anchor because it asks whether a candidate can win in at least one supported election, rather than asking for the probability of every possible outcome.
A plausible high-multiplicity setting is a large weighted electorate whose members fall into a modest number of classes. Members of a class have the same voting weight and the same estimated distribution over preference rankings—for example, a large association with several established voting classes and shared historical preference models. There may be many members but relatively few distinct types. A type \(t\) is the pair of its per-member weight \(w_t\) and its distribution \(p_t\) over rankings. Its mass \(\mu_t\) is the fraction of the population in that class.
My lead problem is Continuous Plurality Possibility. The input is a finite candidate set \(C\), a target \(c^\star\), and types \(t\in T\) with rational masses \(\mu_t\) summing to \(1\), rational weights \(w_t\), and distributions \(p_t\) over complete rankings. Let \(K\) be the total number of supported type–ranking pairs, and include the input bit length \(L\). The question is whether there are nonnegative masses \(x_{t,\pi}\), one for each ranking \(\pi\) with \(p_t(\pi)>0\), such that
\[
\sum_{\pi} x_{t,\pi}=\mu_t
\quad\text{for every }t,
\]
and
\[
\sum_t w_t\sum_{\pi:\,\operatorname{top}(\pi)=c^\star}x_{t,\pi}
\;\ge\;
\sum_t w_t\sum_{\pi:\,\operatorname{top}(\pi)=c}x_{t,\pi}
\quad\text{for every }c\in C.
\]
Here \(x_{t,\pi}\) is the fraction of the whole population in type \(t\) whose realized ranking is \(\pi\). A solution is a feasible rational allocation, or a proof that none exists. I use co-winner semantics: with random tie-breaking, a candidate has positive chance to be selected exactly when it can be a top scorer in some supported profile.
This is an LP feasibility problem, polynomial in \(m=|C|\), \(\tau=|T|\), \(K\), and \(L\). It gives a natural Class A prediction: the continuous problem is tractable. The fractional variables do not give anyone a fractional ballot; they divide a type’s mass among complete rankings, as a continuum population permits. In the finite paper model, independent positive-probability choices make “has any chance” equivalent to “some supported profile makes the candidate a winner.” The continuous version asks the corresponding support-feasibility question for population mass. Thus it keeps the paper’s possible-winner question while replacing indivisible voter assignments with population fractions.
The scope is deliberately just Theorem 9’s Plurality possibility result. I would not claim this LP mirrors Theorem 4’s #P-hard problem of computing the *exact winning probability*: in a nonatomic population, independent individual draws do not give the same nontrivial distribution over aggregate profiles as a finite election. The weakest point is also specific to my anchor: Theorem 9’s Bin Packing reduction represents items as voters, so it can use many distinct weights and types. It does not establish hardness in the low-\(\tau\), high-multiplicity regime that makes this mirror most compelling. The continuous question is still well-posed and recognizably about the paper’s possible-winner problem, but the reduction alone does not show that the LP’s tractability resolves hardness within that same regime.
The next questions are how this LP relates to finite electorates with many repeated types; when a feasible mass allocation can be rounded to an actual finite winning profile; and how much rounding error is tolerable when the target has a positive plurality margin.
Theorem 9 is the proponent’s strongest anchor, and the type construction is sensible: put each voter’s weight and preference distribution into their type. The difficulty is preserving what “chance” means. In the paper, voters draw independently. The proposed LP uses the distributions only to determine which rankings are possible; it can split each type’s mass among any supported rankings, regardless of their probabilities. That asks whether *some aggregate composition* makes the target win, effectively allowing correlations across voters that the paper rules out.
If independence is preserved in the continuous population, type \(t\) contributes mass \(\mu_t p_t(\pi)\) to ranking \(\pi\). Plurality scores are then fixed at \(\sum_t \mu_t w_t p_t(c)\), where \(p_t(c)\) is the probability that type \(t\) ranks \(c\) first. The target has positive chance exactly when it is a top scorer; with random tie-breaking, its winning probability is determined by the tie. This is a direct, deterministic calculation. The nontrivial evaluation problem disappears in the continuum limit.
The LP is nevertheless a coherent high-multiplicity *possible-winner* problem. Its mass assignments can represent profiles of sufficiently replicated finite electorates, and each such profile has positive probability under the paper’s model. So the mismatch is not that the question is meaningless: it is that the LP treats support feasibility as the object, while the paper studies probability under independent draws. A richer stochastic mirror could retain finite-population fluctuations or add uncertainty over aggregate masses, but those require a population-size scale or a different dependence model.
That makes the negative case weak. I can argue that the proposed LP is not a faithful mirror of the paper’s probabilistic question, but I cannot honestly rule out the mass-level possible-winner problem as a worthwhile, recognizable mirror. If the authors accept that reinterpretation, this anchor survives.
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.