| paper | d4-conf-atal-2017-0359 |
| 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 is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), even without single-peakedness. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
Given candidates \(C\), a common axis, a target \(p\), registered masses \(\mu_t\), eligible capacities \(a_t\), and a budget \(\rho\), where every type \(t\) is a complete ranking single-peaked on the axis, decide whether there are additions \(0 \le x_t \le a_t\) with \(\sum_t x_t \le \rho\) such that \(\sum_t (\mu_t+x_t)(s(t,p)-s(t,c)) \ge 0\) for every \(c \in C\), where \(s(t,c)\) is the Borda score of \(c\) in type \(t\).
Types are complete single-peaked rankings with registered mass or eligible mass capacity. The decision variables \(x_t\) are added masses, bounded by each type’s eligible capacity and the total budget; the objective is to make \(p\) a Borda co-winner. The score comparisons form a rational LP with size polynomial in the number of candidates \(m\), support size \(\tau\), and input bit length \(L\).
The LP is generic for Borda and does not use single-peakedness, so it explains the loss of hardness through divisibility rather than through the paper’s axis restriction.
fatal: False
The mirror covers Theorem 1’s constructive control by adding votes clause; it leaves the vote-deletion clause and the paper’s single-dived and truncated-vote results aside.
The strongest case is the CCAV part of Theorem 1, proved in this paper by reductions from X3C. The theorem says that, for Borda, constructive control by adding votes and by deleting votes are each NP-hard even when the election is unweighted and single-peaked; this holds in both the unique-winner and nonunique-winner models. The paper’s reductions establish both claims, with a small modification for the unique-winner case. I would anchor on the adding-votes result: choose at most \(R\) unregistered votes so that the target wins.
A plausible high-multiplicity setting is a very large party or membership election in which candidates lie along a common policy axis. Registered members and eligible members who have not yet voted submit full rankings that are single-peaked on that axis. Many people may share each ballot type, with the electorate’s size \(n\) much larger than the number \(\tau\) of distinct types. A type records the full ranking and whether its members are registered or available to be added. The action is to bring in mass from the available pool, measured as a fraction of the registered population. That fits the paper’s control question: it still asks whether adding votes can make the target win. Fractional mass is appropriate in the regime where control acts on large cohorts rather than at one-person granularity.
I would hand a prover the following problem, Single-Peaked Borda CCAV\(_\infty\). An instance gives candidates \(C\), a common axis \(\prec\), a target \(p\), a registered society \(\mu\), and an available pool whose type proportions are \(\sigma\) and whose total mass is \(H\) relative to the registered society. The masses and a control budget \(\rho\le H\) are binary rationals. Both populations contain only complete rankings single-peaked with respect to \(\prec\); let \(\tau\) be the number of types appearing in either population. As in the paper’s nonunique-winner model, assume \(p\) is not already a winner.
The question is whether one can add mass \(x_t\) of each available type \(t\), with
\[
0\le x_t\le H\sigma_t,\qquad \sum_t x_t\le \rho,
\]
so that \(p\) is a Borda co-winner. Equivalently, minimize \(\sum_t x_t\) subject to those pool limits and the winning condition. With \(s(t,c)=m-\operatorname{rank}_t(c)\), that condition is
\[
\sum_t(\mu_t+x_t)\bigl(s(t,p)-s(t,c)\bigr)\ge 0
\qquad\text{for every }c\in C.
\]
Normalizing the resulting population by its total mass does not change the winners. A solution is an allocation vector \(x\) meeting the budget and making all these inequalities hold. This states the control problem itself; the linear program is the method for solving it.
I expect this mirror to be Class A: tractable. The support-list input gives one variable per available type and one score comparison per candidate. The resulting feasibility problem is a rational LP, solvable in polynomial time in \(m,\tau\), and the input bit length \(L\). The key change is that the controller may select part of each type’s mass. That removes the indivisible vote choices that the X3C reduction uses. This is the intended high-multiplicity relaxation of the same control objective, rather than continuity in the outcome space or a noise model over discrete elections.
The scope here is deliberately the CCAV clause of Theorem 1. The deletion clause is a natural sibling question, and the paper’s single-dived and truncated-vote results may motivate other mirrors, but they are not needed for this case. The continuous model also raises useful follow-up questions: how well can an LP solution be rounded when the population is finite, and how does the answer depend on \(n\), \(\tau\), and the winning margin?
The weakest point is the regime assumption. In an ordinary election, control may turn on whether particular named people vote, while this mirror lets the controller add a fractional share of each type. The case is strongest when the population is large, types are genuinely repeated, and recruitment or registration is naturally handled at cohort scale. If the authors or a referee reject that as a sensible regime for vote control, the LP remains a clean relaxation, but the claimed mirror loses its force.
The strongest case against the proponent’s anchor is that the continuous version strips away the feature that makes Theorem 1 notable. Once the controller may add any fraction of each ballot type, Borda’s linear scores give an immediate LP, and single-peakedness plays no role. With support size \(\tau\), there is one variable per available type and one score constraint per candidate. The same is true for deleting fractional mass from registered types. This is a generic consequence of scoring rules, not an explanation of why vote control is hard even on a single-peaked domain. The result may therefore be a short baseline theorem rather than a substantial analysis of this paper’s complexity border.
That objection limits the mirror’s distinctiveness, but it does not defeat it. Theorem 1 is a named computational result, and the continuous question is well formed: given registered mass \(\mu\) and a bounded pool of eligible single-peaked types, choose \(x_t\) with \(0\le x_t\le H\sigma_t\) and \(\sum_t x_t\le\rho\) so that
\[
\sum_t(\mu_t+x_t)\bigl(s(t,p)-s(t,c)\bigr)\ge 0
\quad\text{for every }c.
\]
The input has polynomially many variables and constraints in \(m\) and \(\tau\), with rational coefficients. This is a genuine Class A result, even if it is easy and does not use the axis.
The best practical objection is that real vote control usually acts on named people: a controller recruits or registers particular eligible voters, not a fractional share of every ballot type. But that objection is weaker in a large membership or party election where recruitment is handled by cohorts. Type-level grouping preserves the relevant attributes if type is defined completely, and mass is the intended unit in the programme. The paper’s finite voter pool and the mirror’s fractional pool are different models, but that is the permitted high-multiplicity change, not a fatal loss of meaning.
So the negative case can make a credible claim about limited paper-specific yield: the mirror would tell us that fractional Borda control is easy, not why single-peaked Borda control over indivisible voters is hard. It cannot honestly establish that no worthwhile scenario exists. This anchor survives the strongest objection.
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.