| paper | d4-conf-atal-2008-0349 |
| 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: In \(\mathrm{P}\) for every fixed rational \(\alpha\in[0,1]\), with \(m=3\); an exact algorithm uses \(O(\tau)\) arithmetic operations and \(O(\tau L^2)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Fix \(C=\{p,a,b\}\) and rational \(\alpha\in[0,1]\). An instance gives rational masses \(\nu_{r,w}\) of fixed voters by ranking \(r\) and weight \(w\), and masses \(\lambda_w\) of controllable voters by weight, with total mass \(1\). Choose \(x_{w,\pi}\ge 0\) for each weight \(w\) and ranking \(\pi\in S_3\), with \(\sum_{\pi\in S_3}x_{w,\pi}=\lambda_w\). Is there an allocation \(x\) for which \(p\) is a Copeland\(_\alpha\) winner, using weighted pairwise margins from the fixed and allocated masses?
Types record whether a voter is fixed or controllable, their ranking when fixed, and their voting weight. The input is a rational distribution over those types; the decision variables distribute each controllable weight class’s mass among the six rankings. The weighted pairwise margins determine Copeland\(_\alpha\) scores, and the question is whether the target candidate is a winner; there is no cost objective.
The mirror covers the three-candidate weighted manipulation classifications in Theorems 4.1 and 4.2. It leaves aside Theorem 3.1’s unweighted coalition hardness and the paper’s broader-candidate cases.
The strongest mirror I believe is in the weighted-manipulation results of Section 4. They keep the candidate set fixed at three and vary the tie rule or the winner requirement, so the central question remains the paper’s: can a coalition choose ballots that make its preferred candidate win?
My lead anchor is Theorem 4.1. It says that for exactly three candidates, Copeland\(_\alpha\)-weighted manipulation is NP-complete for every fixed rational \(0\le\alpha<1\), while for \(\alpha=1\) it is in P. This is a result of this paper; the supplied text omits the NP-completeness proof for space and gives the polynomial algorithm for \(\alpha=1\).
A concrete regime is a large online community or multiagent platform voting among three proposals. Many fixed and strategically coordinated voters share one of a small number of preference rankings and role-based voting weights. The population might have millions of members but only a few dozen types: a type records the voter’s role, ranking when fixed, and voting weight. The manipulable cohort is also large, with only a few weight classes. Mass is the fraction of the whole society in each type.
Here is the continuous problem I would hand to a prover. Fix rational \(\alpha\) and \(C=\{p,a,b\}\). The input is a rational distribution \(\nu_{r,w}\) of fixed voters over strict rankings \(r\) and weights \(w\), plus a rational distribution \(\lambda_w\) of controllable voters over weights, with total mass \(1\). For each controllable weight class \(w\), choose nonnegative masses \(x_{w,\pi}\) for the six rankings \(\pi\in S_3\), subject to \(\sum_{\pi\in S_3}x_{w,\pi}=\lambda_w\). For candidates \(u,v\), their weighted head-to-head margin is \(M(u,v)=\sum_{r,w}\nu_{r,w}w\,\sigma_r(u,v)+\sum_{w,\pi}x_{w,\pi}w\,\sigma_\pi(u,v)\), where \(\sigma\) is \(1\) when \(u\) is ranked above \(v\) and \(-1\) otherwise. The question is whether some such allocation makes \(p\) a Copeland\(_\alpha\) winner. A solution is the allocation \(x\); there is no cost objective in the paper’s manipulation problem.
This is a population continuation of weighted manipulation: voting power remains part of a voter’s type, and the target and Copeland rule stay the same. What changes is that a fraction of a repeated type can report each ranking. For three candidates, that version appears tractable: enumerate the \(3^3=27\) possible win, tie, or loss patterns for the head-to-head contests, and test each feasible pattern with a rational linear program. The number of variables is bounded by six per manipulable weight type, so this gives a polynomial-time algorithm in the support size and bit length. I expect this mirror to land in Class A. It raises the next question of whether tractability persists when the number of candidates is part of the input, and how closely a fractional witness can be rounded to a finite election.
A second, distinct anchor is Theorem 4.2. For exactly three candidates, the paper shows that Copeland\(_\alpha\)-weighted unique-winner manipulation is NP-complete at \(\alpha=0\), and is in P for \(0<\alpha\le1\). This too is a result of this paper; the supplied text sketches the Partition reduction for the hard case and omits proof details due to space.
The continuous version uses the same input and allocation variables as the lead problem, but asks whether \(p\)’s Copeland\(_\alpha\) score is strictly greater than both \(a\)’s and \(b\)’s. A solution is again a rational allocation of the controllable mass among rankings. I also expect this version in Class A: once a pairwise outcome pattern is fixed, the three candidates’ Copeland scores are fixed, so we can discard patterns that do not make \(p\) the unique winner and use linear feasibility to test the rest. This mirror makes the paper’s distinction between “a winner” and “the unique winner” explicit; it invites a further question about the score gap needed for a continuous unique-winner solution to survive finite-population rounding.
My case covers Theorems 4.1 and 4.2, and only their three-candidate weighted-manipulation problems. The weakest point is that the paper’s discrete hardness can depend on indivisible manipulator weights: a weighted voter must cast one ballot for all of that weight, while the continuous allocation can split a type’s mass across ballots. Also, the paper’s hard instances need not have the few-type structure of the proposed large-population regime. So I am not claiming the continuum preserves those NP-hard instances. The case is that the resulting question remains their weighted Copeland manipulation problem, with the same weighted pairwise tallies and winner condition, applied to a society whose types have divisible mass. Whether that removes the hardness is exactly the computational question the mirror puts on the table.
The strongest case against is about how much these anchors add, not whether they admit a valid mirror. Theorem 4.1 and Theorem 4.2 are two slices of the same three-candidate weighted-manipulation problem: they vary \(\alpha\) and whether \(p\) must be a winner or the unique winner. One continuous model covers both by allocating each manipulable weight class across the six possible rankings and computing the resulting pairwise margins. So the two results do not provide independent evidence for two different continuization directions.
That shared mirror is also unusually small. With three candidates, there are only 27 possible win, tie, and loss patterns for the pairwise contests. The weighted manipulation question can be checked by linear feasibility for each pattern. This makes the fixed-three-candidate mirror look like a limited payoff for ChoCo’s broader computational programme. But a simple Class A result is still a result; low complexity does not make the question out of scope.
The strongest objection to the model itself is that a weighted voter casts one indivisible ballot for its entire weight. A mirror that splits its mass among ballots changes that constraint, and the paper’s NP-hard instances need not contain large cohorts of identical weighted voters. Yet this does not defeat the better mirror: in a platform with many voters in a few role and weight classes, each individual can still cast one ballot while the aggregate mass divides among rankings. That is a sensible high-multiplicity regime. Its departure from the paper’s hard instances is precisely something the continuous question would investigate, not a reason the question is ill-posed.
I therefore cannot honestly make the requested universal negative case. Both anchors name computational results, and a plausible population regime gives them a recognizable continuous counterpart. The case against is weak: these particular anchors may be low-priority because their fixed-candidate versions collapse to small feasibility problems, but that does not establish that no worthwhile continuous mirror 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.