| paper | d4-conf-atal-2011-0148 |
| 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: Both the co-winner and unique-winner decision problems are in \(\mathrm{P}\), with running time \((m\tau+L)^{O(1)}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given existing alternatives \(C\), one new alternative \(y\), a target \(c\in C\), and a rational distribution \(\mu\) over rankings of \(C\), can the mass of each ranking type be split among its full-ranking extensions to \(C\cup\{y\}\) so that \(c\) is a Maximin co-winner? The unique-winner version asks whether \(c\) can be the sole winner.
For each old-ranking type \(t\) and each full ranking \(\pi\) extending it, choose mass \(\lambda_{t,\pi}\ge 0\) with \(\sum_{\pi}\lambda_{t,\pi}=\mu_t\). The resulting society has mass \(\nu_\pi=\sum_t\lambda_{t,\pi}\). Decide whether these variables can make \(c\) a Maximin co-winner (or sole winner); the objective is feasibility.
The proposed mirrors cover Theorems 2, 3, and 4: Bucklin with three entrants, and Copeland\(0\) and Maximin with one. They leave the approval extensions and the plurality-with-runoff result untouched.
The strongest mirror is continuous Maximin PcWNA/PWNA with one new alternative. The paper’s problem already asks what can happen when voters’ rankings of the existing alternatives are known but their rankings of an entrant are unrestricted. Replacing voter counts with population mass preserves that question while making the society itself continuous.
For an instance, let \(C\) be the existing alternatives, \(y\) the new alternative, and \(\mu\) a rational distribution over the \(\tau\) rankings of \(C\) in its support. A type is a ranking of the existing alternatives; its mass is the fraction of society with that ranking. For every type \(t\) and every full ranking \(\pi\) of \(C\cup\{y\}\) that extends \(t\), choose a nonnegative mass \(\lambda_{t,\pi}\), subject to \(\sum_{\pi}\lambda_{t,\pi}=\mu_t\). The resulting society has mass \(\nu_\pi=\sum_t\lambda_{t,\pi}\) on each full ranking. The question is whether some such assignment makes a designated \(c\in C\) a co-winner—or, in the unique-winner mode, the sole winner—under Maximin. The assignment is the witness; there is no optimization objective.
This describes a plausible high-multiplicity regime: a large election in which rankings of the announced slate have been elicited, then a late candidate enters before the final election. Millions of voters may share a relatively small set of rankings, so \(\tau\) can be far below the electorate size \(n\). For this problem’s information structure, the type records the known ranking of \(C\); the distribution over extensions represents the very information the PcWNA question leaves open. The paper’s existential completion can therefore be read directly as a choice of mass among possible completions.
Theorem 4 is the lead anchor. It is proved in this paper by reduction from X3C: the PcWNA and PWNA problems for Maximin are NP-complete even with one new alternative. Its continuous counterpart is the problem just defined, with a mode specifying co-winner or unique winner.
There is a concrete reason to expect the continuous version to be tractable. For \(a\in C\), let \(q_a=\min_{b\in C\setminus\{a\}}\mu(a\succ b)\), the old-society Maximin score before \(y\) is added, and let \(x_a=\nu(a\succ y)\). After the entrant arrives, \(a\)’s score is \(\min(q_a,x_a)\), while \(y\)’s score is \(\min_{a\in C}(1-x_a)\). The possible vectors \(x\) are generated by the extension-mass variables. To certify that \(c\) wins, one can use a threshold \(r\): require \(q_c\ge r\) and \(x_c\ge r\); for each \(a\) with \(q_a>r\), require \(x_a\le r\); and require some \(x_d\ge 1-r\), so that \(y\)’s score is at most \(r\). Partitioning \(r\)’s range at the fixed values \(q_a\), and trying each \(d\), gives linear feasibility problems. For a unique winner, use strict score gaps. With one entrant there are only \(m+1\) insertion positions per type, so the formulation has polynomial size in \(m,\tau,L\). This is a plausible Class A result, not a theorem of the paper.
Two further anchors are worth keeping because they test different parts of the boundary. Theorem 2, proved here by reduction from 3DM, states that both PcWNA and PWNA are NP-complete for Bucklin even when there are three new alternatives. The mirror, Continuous Bucklin P(c)WNA with three entrants, uses the same mass-assignment instance with \(Y=\{y_1,y_2,y_3\}\), and asks whether an assignment makes \(c\) a co-winner or unique winner under Bucklin. Replace vote counts by mass: a majority at level \(h\) means mass greater than \(1/2\), and top-\(h\) support is the mass ranked in the top \(h\). For fixed three entrants, each old ranking has only \((m+1)(m+2)(m+3)\) extensions. I would expect Class A: guess the target’s Bucklin level, express the relevant cumulative top-position masses and winner comparisons as linear constraints, and solve the resulting polynomial-size feasibility problems. The extra question is whether this remains tractable when the number of entrants is part of the input, where the extension space grows much faster.
Theorem 3, also proved here, states that PcWNA for Copeland\(0\) is NP-complete even with one new alternative. Its mirror, Continuous Copeland\(0\) PcWNA with one entrant, asks whether an extension-mass assignment makes \(c\) a co-winner. If \(\omega(a)\) is \(a\)’s Copeland score among the old alternatives and \(z_a=\nu(a\succ y)\), then \(a\)’s new score is \(\omega(a)+\mathbf{1}[z_a>1/2]\), while \(y\)’s score is \(\lvert\{a\in C:z_a<1/2\}\rvert\); a pairwise tie gives no point. I would put this in the Class C candidate bucket. The extension masses form a linear feasible region, but the Copeland scores jump at majority thresholds, and the entrant’s score counts how many of those thresholds it crosses. That makes the continuous question genuinely combinatorial. The discrete NP-completeness result does not establish hardness here: mass can split across extensions, so a continuous hardness proof would need to survive that relaxation.
All three anchors concern the population receiving ballots; none makes outcome-space continuity, probabilistic social choice, or time the object of study. The mirror covers the paper’s Bucklin, Copeland\(0\), and Maximin PcWNA results, including the unique-winner variants where the theorem supplies them. It does not claim to continuize every result in the paper.
The weakest point is the treatment of hidden rankings of newcomers. A critic could say that voters with the same old ranking may have different full rankings, so they should be different types; then the apparent low-support regime disappears. My reason for accepting the mirror is specific to the paper’s information structure: those extensions are unobserved and are exactly what its possible-winner question quantifies over. Splitting the mass of an old-ranking cohort across extensions is the continuum version of asking whether a completion exists. Whether continuous feasibility also gives a useful approximation to the finite problem remains open: every discrete yes-instance maps to a continuous yes-instance, but a fractional completion need not round to a valid completion at the original electorate size, especially near a majority tie.
The best objection is that these mirrors describe a partially observed population, not a distribution over complete voter types. The input gives a distribution over rankings of the old alternatives; the witness then splits each type’s mass among rankings of the enlarged slate. In a real population, those hidden rankings would be fixed, and might be correlated with other features the old ranking omits. So the proposed formulation treats every coupling consistent with the observed marginal as possible, which can make “could \(c\) win?” a question about ignorance rather than about the population.
That objection is not enough to defeat the mirrors. PcWNA itself asks whether *some* completion of the old rankings makes \(c\) win. Splitting mass across completions is the natural continuous version of that existential quantifier, and for rational masses it corresponds to a finite electorate after scaling. A scenario such as a large participatory vote where a late proposal is added could plausibly have many residents per old-ranking type. Correlations could be added to a richer type model, but their absence here matches the paper’s stated information.
For Theorem 4, the Maximin mirror is especially hard to reject. Old-candidate pairwise support remains fixed, and each type’s mass can be allocated among the \(m+1\) insertion positions for one entrant. The resulting question over the variables \(x_a=\nu(a\succ y)\) is well-defined. The proposed threshold formulation may indeed reduce co-winner feasibility to a polynomial number of linear feasibility problems. That possibility does not invalidate the question; it makes this the strongest surviving anchor.
For Theorem 2, the proponent’s claim that fixed three entrants yield linear feasibility is less established. Guessing \(c\)’s Bucklin level does not by itself resolve the disjunctions over whether each opponent has a worse level or ties at that level with lower support. The mirror may be harder than their proposed LP suggests. But those disjunctions are part of a legitimate continuous computational problem, and neither the complexity of the answer nor the number of entrant placements is a reason to reject it.
For Theorem 3, Copeland’s majority thresholds make the continuous feasibility question combinatorial: the entrant’s score depends on which pairwise masses lie above or below \(1/2\). That weakens any expectation of a simple LP, but it makes the mirror a plausible Class C question. It does not show that the question is uninteresting.
So the negative case is weak. The complete-type concern identifies a modelling choice worth making explicit: whether the input describes a known distribution of full rankings or only a marginal distribution over old rankings with unrestricted completions. The latter is faithful to PcWNA, and the paper’s anonymity leaves room for high multiplicity. I cannot honestly argue that no scenario makes any of these mirrors worthwhile; Maximin in particular survives the strongest objections.
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.