| paper | d4-conf-atal-2013-0084 |
| 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 for \(m=3\), with an exact \(O((m\tau+1)L^2)\) bit-operation algorithm. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 7
statement extracted from the paper’s text layer
Let \(C=\{p,a,b\}\), let \(R\) be its six rankings, and let \(T=\{(p,a,b),(p,b,a)\}\) be the sincere-ranking types of manipulators who prefer \(p\). An instance gives binary-rational masses \(\nu_r\) of fixed voters of each ranking \(r\in R\), and \(\kappa_t\) of manipulators of each type \(t\in T\), with \(\sum_{r\in R}\nu_r+\sum_{t\in T}\kappa_t=1\). Decide whether there exist \(x_{t,r}\ge 0\) such that \(\sum_{r\in R}x_{t,r}=\kappa_t\) for every \(t\), and \(p\) wins CondorcetTHENPlurality on the resulting masses \(\lambda_r=\nu_r+\sum_{t\in T}x_{t,r}\), using the paper’s tie-breaking convention.
A distribution over fixed-voter ranking types and manipulator types, with coalition status and sincere ranking included in the type. Decision variables \(x_{t,r}\) allocate each manipulator type’s mass across reported rankings; the objective is to determine whether an allocation makes \(p\) win under the unchanged two-stage rule.
Covers the three-candidate slice of Proposition 7 for weighted coalition manipulation. It does not cover the arbitrary-scoring-rule result in Proposition 8, Black’s procedure as such, unweighted manipulation, or the re-voting results.
My strongest positive case is weighted-coalition manipulation of Condorcet-then-Plurality with three candidates. A plausible regime is a large association or electorate where many members share a small number of complete rankings, and a coordinated bloc wants its preferred candidate elected. With three candidates there are only six possible rankings, so the population can be large while the number of types stays at most twelve if coalition membership is counted as part of a type.
The anchor is Proposition 7, proved in this paper: deciding whether a coalition can manipulate CondorcetTHENPlurality is NP-complete with weighted votes and three or more candidates. The authors reduce from number partitioning using three candidates. Their construction assigns each manipulator an integer weight and relies on dividing those indivisible weights between strategic ballots.
Here is the continuous problem I would hand to a prover: Fractional Coalition Manipulation for Condorcet-then-Plurality. Let \(C=\{p,a,b\}\), and let \(R\) be its six rankings. The instance gives binary-rational masses \(\nu_r\) for the fixed nonmanipulators and \(\kappa_t\) for the manipulators’ sincere-ranking types \(t\in R\) with \(p\) ranked first; these masses sum to one. Ask whether there are nonnegative allocations \(x_{t,r}\), where \(x_{t,r}\) is the mass of manipulator type \(t\) that casts report \(r\), such that
\[
\sum_{r\in R}x_{t,r}=\kappa_t
\quad\text{for each manipulator type }t,
\]
and \(p\) wins Condorcet-then-Plurality on the resulting society
\[
\lambda_r=\nu_r+\sum_t x_{t,r}.
\]
A solution is the allocation \(x\); the objective is simply to decide whether one exists. Use the paper’s Condorcet test and tie-breaking convention.
This remains their manipulation question: the coalition has the same target, faces the same fixed society, chooses strategic rankings, and must make \(p\) win under the same two-stage rule. The population itself is now a distribution over sincere preference types. For three candidates, the continuous problem appears to be Class A. There are only six report rankings and two sincere types with \(p\) first. Whether \(p\) wins can be split into finitely many linear-feasibility cases: either \(p\) is the Condorcet winner, or there is no Condorcet winner and \(p\) wins the plurality round. With three candidates, the “no Condorcet winner” condition has only a constant number of cases to check. The variables and outcome conditions are linear in \(x\), so the instances reduce to a constant number of rational linear-feasibility problems.
That makes this a useful mirror of the *three-candidate hardness slice* of Proposition 7. Its number-partitioning reduction depends on assigning each weighted manipulator’s entire block to a ballot. In the continuous model, mass of the same sincere type can split across ballots, so that particular source of hardness plausibly disappears. This does not settle the version with unbounded \(m\): there, the report space has \(m!\) rankings, and the Condorcet condition may require more sophisticated optimization. That wider question, and whether a continuous solution can be rounded back to an election of a specified size while controlling winner margins, are natural next questions.
My weakest point is that divisibility changes a real feature of the paper’s weighted model: each weighted manipulator casts one ballot for their whole weight. The mirror allows their mass to divide among reports. But the paper also describes a weighted vote as a block of identical unit voters. In a nonatomic population, splitting such a preference block across strategic choices is a natural continuous relaxation. It preserves the underlying manipulation problem while relaxing the action granularity; it does not claim that the paper’s NP-hardness result itself vanishes.
The strongest case against Proposition 7’s mirror is that it relaxes the strategic unit that creates the paper’s hardness. In the reduction, a weighted manipulator casts one ballot for the entire block; the partition question asks how to assign those indivisible blocks. The proposed model lets members of a same-preference bloc report different rankings. That is a sensible fractional coalition problem, but it changes what a weighted coalition can do.
That objection does not defeat the mirror under ChoCo’s stated standard. A weighted vote represents a block of identical voters, and a nonatomic version can let those voters choose reports individually while preserving their sincere preference type and coalition membership. The problem still asks whether a coordinated coalition can make its preferred candidate win. For three candidates, the society has only six rankings; the winning condition can be split into finitely many linear-feasibility cases. The resulting easy algorithm would be a meaningful answer to whether this source of manipulation hardness survives a continuous-population model. Treating that answer as evidence against the question would rely on exactly the kind of “continuous does not help” objection the programme rules out.
The narrowest remaining concern is that the three-candidate version may be too routine to sustain a substantial standalone result. But allowing the candidate set to grow gives a better mirror: keep the same distribution-over-rankings model and ask how the problem scales with \(m\), support size, and input bit length. The ranking space and Condorcet condition then raise real computational questions. I cannot make the case that no worthwhile mirror exists; the objection about indivisible blocks is a caution about interpretation, not a fundamental obstruction.
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.