| paper | d4-conf-atal-2021-0170 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem belongs to \(\mathrm P\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given candidates \(C\), registered ranking types \(t\) with masses \(\mu_t\), eligible ranking types \(t\) with available masses \(\nu_t\), and a target \(c\), decide whether there exist admitted masses \(x_t\in[0,\nu_t]\) such that, for every \(d\ne c\), \(\sum_{t\in\mathcal B}\mu_t\bigl(s_B(t,c)-s_B(t,d)\bigr)+\sum_{t\in\mathcal A}x_t\bigl(s_B(t,c)-s_B(t,d)\bigr)\ge 0\), where \(s_B(t,d)=m-\operatorname{pos}_t(d)\).
A population with finite support over complete Borda ranking types, each marked registered or eligible; the input gives rational masses \(\mu_t\) and \(\nu_t\), and the decision variables \(x_t\) are admitted eligible masses. The objective is feasibility: can these masses make the target a co-winner? The resulting constraints form a linear feasibility problem in \(m\), the support size \(\tau\), and the input bit length \(L\).
Covers Theorem 10’s Borda CCAUV and positive-winning-probability reachability question; leaves exact probability computation, approximation results, and results for other voting rules aside.
My lead is continuous Borda add-voter reachability, a narrow mirror of the paper’s named Theorem 10. The theorem is proved in this paper: under Borda, Constructive Control by Adding an Unlimited number of Voters (CCAUV) is NP-complete, and therefore it is NP-complete to decide whether the target’s winning probability is positive. CCAUV asks, given registered voters \(M\), eligible but unregistered voters \(Q\), and a target \(c\), whether *some* sublist \(Q'\subseteq Q\)—of any size—makes \(c\) a winner of \(M\circ Q'\). The proof reduces from Borda-CCAV, whose NP-completeness is cited from Russell [25]. This is a stronger anchor for a continuous mirror than the paper’s exact-probability hardness: Theorem 10 already isolates a reachability question tied directly to voter participation.
Here is the continuous problem. There are \(m\) candidates and two finite supports of complete rankings: registered types with masses \(\mu_t\), and eligible-to-be-added types with available masses \(\nu_t\). The masses are nonnegative binary rationals, normalized so their combined total is \(1\). A type includes its ranking and its registered or eligible status; let \(\tau\) be the number of supported types. Given a target \(c\), choose \(x_t\in[0,\nu_t]\) for each eligible type: \(x_t\) is the mass of that type admitted to the election. With \(\operatorname{pos}_t(d)\) denoting candidate \(d\)’s position in ranking \(t\), define
\[ S_x(d)= \sum_{t\in\mathcal B}\mu_t\bigl(m-\operatorname{pos}_t(d)\bigr) + \sum_{t\in\mathcal A}x_t\bigl(m-\operatorname{pos}_t(d)\bigr). \]
The question is whether there is an \(x\) such that \(S_x(c)\ge S_x(d)\) for every candidate \(d\). Ties count, as they do in the paper. A solution is the vector of admitted masses \(x\); the objective is yes/no reachability, with no added cost function. This is a linear-feasibility problem with \(m-1\) winner inequalities and bounds on the \(\tau\) variables, so it is solvable in time polynomial in \(m,\tau,L\), where \(L\) is the binary input length. Its expected class is A, tractable.
A plausible regime is a large membership or constituency election with a substantial eligible pool that can be mobilized, where many people share a relatively small set of complete rankings and mobilization is planned by type as population shares. There may be hundreds of thousands of people but only tens or hundreds of supported ranking-and-status types. The campaign decision is then honestly about “what fraction of this bloc can we bring in?”, rather than which named individuals to select. This is a population continuization: the input and decision are masses over voter types, not fractional outcomes or a new randomness model.
The connection to the paper is unusually direct. Theorem 10 links positive winning probability to the existence of an eligible-voter subset: when optional voters have positive attendance probability, the target’s probability is positive exactly when some subset can make the target win. The continuous question asks the corresponding type-mass reachability question. An author or referee could recognize it as the population version of CCAUV, which the paper itself introduces and uses to prove its probability-positivity result.
The scope is only the Borda CCAUV/positive-probability result of Theorem 10. I am not claiming a continuous version of the paper’s #P-hard exact probability computation, its approximation results, or its results for other rules. The weakness is that continuous reachability changes the semantics: it permits splitting a type’s available mass, so \(c\) may win after a fractional addition even when no discrete sublist works. And a reachability problem does not compute the probability of winning. This is a credible mirror of the paper’s named positivity anchor, not of its full probabilistic inference problem.
That gap generates a useful next question: when can a feasible continuous mass vector be rounded to an integral voter subset without losing the win? The answer may depend on the margin, support size, and population denominator. Characterizing those conditions would give the mirror a precise bridge back to the discrete result; a cost-per-type version could also ask for the least mass needed to reach a winning state.
The strongest objection is that the paper’s central object is random attendance, and that part does not pass cleanly to a continuous population. If each person attends independently, then in a continuum the mass of each type that attends is almost surely exactly its expected mass. The probability of winning collapses to a deterministic yes-or-no test. To retain a nontrivial probability, one would need randomness in aggregate type masses or some finite-population correction; that adds a different uncertainty model. So the continuous version would not preserve the paper’s main probabilistic inference problem.
That objection does not defeat the proponent’s anchor, though. Theorem 10 separately establishes the complexity of CCAUV, and the paper explicitly connects it to whether winning probability is positive. A continuous CCAUV is well-defined: with base Borda margin \(b_d\) against each opponent \(d\), and eligible mass \(x_t\) of each ranking type \(t\), ask whether
\[
b_d+\sum_t x_t\bigl(s(t,c)-s(t,d)\bigr)\ge 0
\quad\text{for every }d\ne c,
\qquad 0\le x_t\le \nu_t.
\]
That is a linear-feasibility problem. The fact that it allows splitting a type’s mass changes which instances are feasible, but that is the intended population relaxation. Mobilizing fractions of large blocs is also a plausible scenario, and voter control is explicitly within the programme’s scope.
One could object that this LP is immediate and does not retain the paper’s attendance uncertainty. But ease of solution is not a sound reason to reject a well-posed mirror under the programme’s criteria. Adding per-type mobilization costs would make the question more operational, yet would still leave a natural LP.
So the negative case is weak at the point that matters: I can argue that this mirror does not capture the paper’s central probability-computation problem, but I cannot honestly rule out the CCAUV mirror. It is a computational result, its continuous population model is coherent, and a plausible high-multiplicity scenario exists.
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.