| paper | d4-conf-atal-2011-0070 |
| 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: \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Fix a pure scoring rule whose vector for \(|C|+1\) candidates is \((\alpha_1,\alpha_2,1,0,\ldots,0)\), with \(\alpha_1>\alpha_2>1\). Given an initial candidate set \(C\), a new candidate \(a\), a target \(c^\star\in C\), and a rational distribution \(\mu\) over a finite support \(T\) of strict rankings of \(C\), is there a mass assignment \(q_{t,p}\ge 0\), for \(t\in T\) and \(p\in\{0,\ldots,|C|\}\), with \(\sum_p q_{t,p}=\mu_t\), such that inserting \(a\) after position \(p\) for mass \(q_{t,p}\) makes \(c^\star\) a co-winner?
The society is a rational distribution \(\mu\) over supported rankings \(T\) of \(C\). The decision variables \(q_{t,p}\) allocate each type’s mass among the integral ballot completions formed by inserting \(a\) at position \(p\). The objective is feasibility: satisfy the mass constraints and the linear score inequalities that make \(c^\star\) a co-winner under the fixed scoring rule.
The mirror covers Theorem 3.1; Theorem 4.3 also has a rational-mass version of its scoring-rule choice question. It leaves the weighted PcWNA results, Theorem 4.4 on Copeland elections, and the approval-system results outside the stated mirror.
My lead is the paper’s one-new-candidate hardness result. It has a direct population mirror, and the resulting question has a compact linear-programming formulation.
Take a fixed pure scoring rule from the class in Theorem 3.1, proved in this paper: for unweighted voters, PcWNA is NP-complete when one candidate is added and the scoring vector is \((\alpha_1,\alpha_2,1,0,\ldots,0)\), with \(\alpha_1>\alpha_2>1\). The reduction is from 3-Dimensional Matching.
In the mirror, an instance has an initial candidate set \(C\), a new candidate \(a\), a target \(c^\star\in C\), and a distribution \(\mu\) over a finite support \(T\) of strict rankings of \(C\), with rational masses \(\mu_t\) summing to one. A type is one such initial ranking. For each type \(t\) and each insertion position \(p\in\{0,\ldots,|C|\}\), let \(q_{t,p}\) be the mass whose completed ranking inserts \(a\) after the first \(p\) candidates of \(t\). Require \(q_{t,p}\ge 0\) and \(\sum_p q_{t,p}=\mu_t\). The question is whether there is such an assignment for which \(c^\star\) is a co-winner under the fixed rule. A solution is the mass assignment \(q\); every unit of mass still receives a complete, integral ranking. PcWNA is a decision problem, so its objective remains feasibility: can the designated candidate win?
This is a plausible large-election regime: many voters share one of relatively few initial ballot types, and voters who share a type need not make the same insertion choice. For one added candidate, there are only \(|C|+1\) choices per type. Each candidate’s score is linear in \(q\), so the winning conditions give a rational LP with \(O(|T||C|)\) variables and polynomially many constraints. The mirror is therefore tractable, in Class A, even though the finite problem in Theorem 3.1 is NP-complete. Its natural further question is how the fractional feasibility answer relates to elections at a specified finite electorate size, and how the formulation changes when more than one candidate is added.
A second, independent mirror comes from Theorem 4.3, also proved here. It states that, assuming succinct vote representation, both \(S\)-PcWUVS and \(S\)-PWUVS are NP-complete for \(m\ge4\), where \(S\) consists of scoring vectors \((\alpha_1,\ldots,\alpha_{m-4},x_1,x_2,x_3,0)\) with valid nonincreasing nonnegative integer entries and at least one \(x_i=1\). The theorem covers both making the target a co-winner and making it the unique winner.
Its continuous question takes a rational distribution \(\mu\) over strict rankings of \(C\), a target \(c^\star\), and asks whether some allowed integer scoring vector makes \(c^\star\) a co-winner—or, in the unique-winner version, gives it strictly greater score than every rival. The vector remains discrete; only the population is represented by masses. This is an exact high-multiplicity mirror: divide each succinct ballot count by the electorate size to obtain \(\mu\), and clear the denominators of any rational \(\mu\) to recover a succinct finite profile. Winner comparisons are unchanged by this scaling. Thus the theorem’s NP-completeness carries over, placing this mirror in Class B: the difficult choices lie in the candidate-dependent scoring vector, not in indivisible population units. It also suggests questions about whether fixing the number of candidates or restricting the scoring-vector class restores tractability. The paper’s succinct-vote theorem supports the plausibility of the high-multiplicity regime; it is not a reason to dismiss the mirror.
These mirrors cover Theorem 3.1 and the scoring-rule result in Theorem 4.3. They do not try to continuize the weighted PcWNA results, or the paper’s Copeland and approval-system results.
The soft spot is the lead mirror’s permission to split one type’s mass among different completions. That changes the finite problem’s all-or-nothing assignment of each listed vote. I think authors would recognize it as a sensible high-multiplicity relaxation: voters still cast individual complete ballots, and identical initial rankings do not force identical choices. But if they require every copy of a type to share one completion, the LP mirror would not capture their intended question. The second mirror survives that objection: it keeps the paper’s rule-choice question intact and gives a precise population-distribution formulation with an exact finite-profile dictionary.
The strongest negative case is that the two anchors offer less *new* computational structure than their descriptions suggest. Theorem 4.3 already takes succinct ballot multiplicities as input. Normalizing those counts gives rational masses, and clearing the denominators reverses the mapping with polynomially bounded encoding length. So its proposed mirror is nearly an exact recoding of the paper’s problem; it may add little beyond making the high-multiplicity interpretation explicit.
Theorem 3.1 has a similar limitation in the other direction: its LP works by letting voters with the same initial ranking split across different insertions. That erases the indivisibility used by the hardness reduction, so the polynomial result may say more about this particular fractional relaxation than about the finite problem’s structure.
But neither point defeats the anchors under ChoCo’s stated standard. The second mirror is a well-posed high-multiplicity question, and an exact complexity correspondence is not a collision with prior continuous work. The first is precisely a population-mass relaxation, with integral ballots for each unit of mass; its tractability is a meaningful continuization result even if it comes from dropping indivisibility. I cannot honestly argue that both fail. The negative case is weak: it raises questions about novelty and priority, but leaves two credible mirrors standing.
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.