| paper | d4-conf-aldt-2015-0036 |
| 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: The divisible-mass problem is polynomial-time solvable, hence belongs to \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given candidates \(C\), a preferred candidate \(p\), and supported weak-order ballot types \(t\) with registered masses \(\mu_t\) and eligible unregistered masses \(\nu_t\), all binary-rational, decide whether there are additions \(x_t\) with \(0 \le x_t \le \nu_t\) and \(\sum_t x_t \le \kappa\) such that \(p\) wins under average-extension plurality. For a type whose top tied group is \(G_1(t)\), each candidate in that group receives score \(1/|G_1(t)|\), and every other candidate receives zero; the resulting score is \(\sum_t a_t(c)(\mu_t+x_t)\).
Types are weak-order ballots with registered and eligible masses \(\mu_t,\nu_t\); the chair chooses added mass \(x_t\), minimizing \(\sum_t x_t\) subject to \(0 \le x_t \le \nu_t\) and the linear constraints \(\sum_t (a_t(p)-a_t(c))(\mu_t+x_t) \ge 0\) for every \(c \in C\).
The mirror covers the average-extension plurality CCAV result for bottom and weak orders in Theorem 8. It leaves the paper’s other manipulation, control, bribery, Copeland, and tournament results unaddressed.
My lead is a continuous version of constructive control by adding voters. It preserves the chair’s decision and the paper’s tie-aware voting rule: the chair chooses how much of each eligible ballot type to add, and wants the preferred candidate to win.
The anchor is Theorem 8, proved in this paper: *Plurality CCAV for bottom orders and weak orders using average is NP-complete.* Here CCAV is the unweighted decision problem: given registered voters, a collection of unregistered voters, a preferred candidate \(p\), and an addition limit \(k\), is there a subset of at most \(k\) unregistered voters whose addition makes \(p\) a winner? The theorem’s proof reduces from Exact Cover by 3-Sets.
For Continuous Plurality-CCAV-average, let \(C\) be the candidates and let \(\mathcal T\) be the supported weak-order ballot types. A type is a complete ranking, including its ties; its members are interchangeable because the problem uses only their ballots. Let \(\mu_t\) be the registered mass of type \(t\), and \(\nu_t\) the eligible unregistered mass. These are binary-rational fractions of the combined eligible population, with \(\sum_t(\mu_t+\nu_t)=1\). The support size is \(\tau\). Given a preferred candidate \(p\) and a mass budget \(\kappa\), the chair chooses an added mass \(x_t\) of each type, where \(0\le x_t\le\nu_t\) and \(\sum_t x_t\le\kappa\).
Under the paper’s average extension of plurality, if \(G_1(t)\) is a type’s top tied group, each candidate in that group gets \(a_t(c)=1/|G_1(t)|\), and every other candidate gets zero. The post-addition score of \(c\), up to a common normalization that does not affect the winner, is \(\sum_t a_t(c)(\mu_t+x_t)\). A solution is a vector \(x\) satisfying the bounds and budget for which
\[
\sum_t a_t(p)(\mu_t+x_t)\ \ge\ \sum_t a_t(c)(\mu_t+x_t)
\quad\text{for every }c\in C.
\]
Equivalently, minimize \(\sum_t x_t\) subject to those winner constraints and ask whether the minimum is at most \(\kappa\).
This is an LP with \(\tau\) variables and one winner constraint per candidate, so it is solvable in time polynomial in \(m\), \(\tau\), and the rational input length \(L\). I expect this mirror to be tractable: the discrete exact-cover reduction depends on selecting whole voters, while the continuous chair can select fractional mass from each type. This does not establish that every finite instance is easy; it identifies the fractional, high-multiplicity version of this particular control problem.
The regime I have in mind is a very large election or membership drive with recurring complete ballot profiles: many eligible people share each supported preference type, and outreach can enroll a percentage of a type rather than targeting individuals one by one. Then the population size \(N\) can be much larger than \(\tau\), and “add \(0.5\%\) of this ballot group” is a sensible action. The authors should recognize the mirror: it keeps the same chair, eligible pool, ballots, average plurality scores, and winner condition. It changes the unit of control from whole voters to population mass.
My weakest point is that fractional registration may be a useful relaxation without being an operationally available action in every election. The theorem’s Exact Cover construction also does not establish a large gap between population size and the number of distinct types. So the case rests on a plausible repeated-type regime for CCAV, not on the theorem’s hard instances already exhibiting high multiplicity. The mirror covers Theorem 8’s CCAV result only. It leads to questions about the integrality gap and rounding from mass additions to whole voters, and whether the same bridge holds for the paper’s other control and bribery results.
Theorem 8 is a real computational anchor: it proves NP-completeness of a specific control problem, so “there is no result to mirror” does not apply. Nor do identity dependence or a vanishing continuum defeat the proposed model. Voters with the same complete ballot are interchangeable for this problem, and the chair’s objective depends only on candidate scores. Existing high-multiplicity election work supports the plausibility of the regime; it is not a collision.
The strongest objection is narrower: the continuous question is almost immediate once the model is written down. For each supported ballot type \(t\), let \(a_t(c)\) be the average-plurality score given to candidate \(c\). Choosing added mass \(x_t\) requires only \(0\le x_t\le\nu_t\), a mass budget, and the linear winner constraints
\[
\sum_t (a_t(p)-a_t(c))(\mu_t+x_t)\ge 0
\quad\text{for every }c.
\]
That is an explicit LP with \(\tau\) variables. The paper’s exact-cover reduction gives each encoded set its own unregistered ballot type, so its hard instances do not themselves demonstrate a large population with a small, recurring set of types. One can question whether this yields enough paper-specific algorithmic insight to merit much effort.
But that objection does not defeat the stronger mirror. A large electorate with recurring tie-aware ballot profiles and an enrollment drive that can reach a fraction of each profile is a coherent high-multiplicity scenario. Eligibility or outreach cost can be included in the type description, and the same LP formulation still captures the chair’s choice. The continuous model preserves CCAV’s action and winner condition while asking a computational question the paper does not answer. The result may be a simple tractability classification, but simplicity is not a sound reason to dismiss it: the programme treats tractability after continuization as a meaningful outcome.
So the honest negative case is weak. The best criticism is that Theorem 8 motivates this mirror less directly than its unit-capacity reduction suggests, and that the LP may be a short, generic result rather than a substantial project. I cannot support the universal claim that no worthwhile continuous mirror exists for this anchor.
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.