| paper | Complexity of Manipulating Elections with Few Candidates |
| authors | Vincent Conitzer, T. Sandholm |
| venue | AAAI 2002 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
Given rational fixed masses \(\nu_{\rho}\) over rankings \(\rho\in S_3\), rational controllable mass \(W\), and a preferred candidate \(p\), decide whether there exist masses \(x_{\rho}\ge 0\) with \(\sum_{\rho}x_{\rho}=W\) such that \(\mu_{\rho}=\nu_{\rho}+x_{\rho}\) makes \(p\) a Borda winner under the paper's tie convention.
The types are complete rankings \(\rho\in S_3\) together with fixed-versus-controllable status. The decision variables are controllable report masses \(x_{\rho}\), the resulting society is \(\mu\), and feasibility requires \(\mathrm{sc}_{\mu}(p)\ge \mathrm{sc}_{\mu}(c)\) for every \(c\ne p\); the objective is to find such a mass allocation.
The discrete theorems let one weighted voter submit one indivisible ballot, whereas the mirror lets its corresponding mass split among rankings; the cases do not establish that every weighted-bloc interpretation accepts independent control within the bloc. This is a fidelity limitation, especially for STV where one bloc affects several elimination rounds, but it is nonfatal under the paper's \(k\)-identical-voters and high-multiplicity interpretation.
fatal: False
The mirror covers the complete-information weighted constructive Borda manipulation of Theorem 1 and destructive STV manipulation of Theorem 6. Theorem 8 is only sketched as a further randomized-Cup question, while the remaining protocol results and the uncertainty reductions in Theorems 2–5, 7, and 9–11 are left outside the proposed mirror.
There is a credible continuous mirror here. My lead anchor is Theorem 1, with Theorem 6 as a useful second anchor. Both are hardness results proved in this paper, and both derive their hardness from indivisible voter weights while keeping the number of candidates fixed. That is exactly the regime in which continuization has something substantive to test.
Take the many agents to be members of a large, coordinated organization voting on a small number of proposals. With three candidates there are only six possible rankings. Millions of members may therefore occupy only a constant number of complete types: ranking plus coalition status, eligibility, and any relevant reporting constraints. Thus \(n\) is very large while \(\tau\le 12\), counting fixed and controllable versions of each ranking. The mass of a type is its fraction of the organization.
For a controlled type \(q\) of mass \(w_q\), let \(x_{q,\rho}\) be the mass instructed to submit ranking \(\rho\). The constraints are \(x_{q,\rho}\ge0\) and \(\sum_\rho x_{q,\rho}=w_q\). Fixed voters have masses \(\nu_\rho\), and the resulting society has \(\mu_\rho=\nu_\rho+\sum_q x_{q,\rho}\). The action is therefore a mass allocation among reports. The objective is the same feasibility objective as in the paper: make a designated candidate win, or make a designated candidate lose. Reporting transfers have cost zero for coalition members and infinite cost for fixed voters.
The regime is plausible when the voters are party members, automated representatives, employees in a coordinated organization, or members of a large platform community. They can be numerous but interchangeable in their relevant characteristics. I am not claiming that every weighted voter in the paper is already a continuum type; rather, I am taking seriously the paper’s own interpretation of weights as voting mass and replacing indivisible blocs by many unit agents who may be assigned different reports.
My lead question is Borda-CCWM\(_\infty\). Its discrete anchor is Theorem 1: “In the Borda protocol, CCWM is NP-complete even with 3 candidates.” The paper proves this here by reduction from PARTITION. CCWM is given a set \(S\) of weighted votes whose rankings are fixed, a coalition \(T\) whose voters have specified weights but whose rankings are still open, and a preferred candidate \(p\); the question is whether the voters in \(T\) can cast their votes so that \(p\) wins.
The continuous version is: given rational fixed masses \(\nu_\rho\), rational controllable masses \(w_q\), three candidates, and a preferred candidate \(p\), does there exist a feasible mass allocation \(x_{q,\rho}\) such that \(p\) wins under Borda? Explicitly, with \(s_B(\rho,c)\) denoting the Borda score of \(c\) in ranking \(\rho\), require \( \sum_\rho \mu_\rho s_B(\rho,p)\ge \sum_\rho \mu_\rho s_B(\rho,c) \) for every other candidate \(c\), with the paper’s tie convention if ties are not allowed. A solution is the mass-allocation matrix \(x\), not an individual ballot profile.
This is a linear program over the six rankings. I therefore expect Borda-CCWM\(_\infty\) to be in Class A. The PARTITION reduction disappears because the coalition can divide mass fractionally rather than assign each indivisible weight \(k_i\) wholly to one side of a partition. The continuous problem remains recognisably the authors’ problem: same candidates, same Borda rule, same complete information, same coalition action, same constructive objective. Only the population regime changes.
The second anchor is Theorem 6: “In the STV protocol, DCWM is NP-complete even with 4 candidates.” This theorem is also proved in the paper, by reducing from three-candidate constructive manipulation. DCWM asks whether a weighted coalition can cast its votes so that a disliked candidate \(h\) does not win. The result holds with only four candidates.
The corresponding question, STV-DCWM\(_\infty\), gives rational fixed masses, rational controllable mass, four candidates, a disliked candidate \(h\), and asks whether the controllable mass can be distributed among rankings so that \(h\) is not the STV winner. STV is run on masses: first-round scores are masses ranking each candidate first; after eliminating the lowest candidate, that mass transfers to the highest-ranked remaining candidate. Ties use the paper’s adversarial convention. A solution is again the matrix \(x_{q,\rho}\).
For the four-candidate version, I expect this continuous problem also to be tractable. Enumerate the finitely many possible elimination orders and tie branches. Once an order is fixed, every round’s score is a linear function of \(x\), so the conditions enforcing that order and excluding \(h\) are linear inequalities. Feasibility can therefore be checked by a finite collection of linear programs. Here too, the paper’s hardness appears to be population-multiplicity hardness: the reduction needs weighted indivisible votes, while the fixed four-candidate continuous problem has only finitely many report types.
These mirrors do not claim to cover the entire paper. They cover the complete-information weighted-coalition results, especially Theorems 1 and 6. A natural further question is the continuous version of Theorem 8, where the coalition allocates mass over rankings and asks whether \(p\) wins with probability greater than \(r\) under a randomized Cup schedule. With seven fixed candidates, one could enumerate pairwise-majority sign patterns and test the resulting linear regions. The uncertainty results in Theorems 9–11 need more care: independent finite-voter uncertainty tends to disappear in a population limit by concentration, whereas common shocks or correlated type-level uncertainty may survive.
My weakest point is that the mirror permits a coalition’s mass to split across several rankings, whereas one weighted voter in the paper submits one indivisible weighted ballot. If the intended agents are genuinely indivisible constituency blocs, this objection is serious. The case survives only under the high-multiplicity interpretation in which the weight represents many interchangeable agents whose reports can be coordinated at unit-mass granularity. That is a natural scenario for a large organization, and it is precisely the population interpretation that makes the continuous question meaningful.
The strongest negative case is a fidelity objection. In Theorem 1, a voter of weight \(6k_i\) is one strategic agent who must submit one ranking. The proposed \(x_{q,\rho}\) formulation lets that mass split across several rankings. Preserving the paper’s semantics would require every \(6k_i\)-cohort to act synchronously, an all-or-nothing constraint that effectively restores the Partition variable. Without that constraint, the LP is a new fractional-coalition problem, not merely a continuous encoding of CCWM.
The same objection applies to Theorem 6. In weighted STV manipulation, a bloc’s single ballot affects every elimination round. Splitting the bloc into independently reportable mass changes the feasible strategic actions, even if the resulting STV calculation can be expressed by enumerating elimination orders and solving linear programs. A party or platform with many individually controllable members is a plausible new scenario, but it is no longer the paper’s weighted-voter model in the strict sense.
Theorem 8 offers little support for the negative case, however. Randomization over Cup schedules survives the population limit: pairwise margins are linear in type masses, and the schedule remains an external random device. The uncertainty results are more vulnerable: independent individual uncertainty concentrates away, while type-level common shocks or perfect correlations preserve a nontrivial problem only by changing the information model.
This is nevertheless not enough to defeat the mirror under ChoCo’s stated standard. The paper itself explicitly identifies a weight \(k\) with \(k\) identical unweighted voters. A large organization with many interchangeable unit members is therefore an author-recognizable high-multiplicity regime, not an artificial rescue. Rational mass allocations can be cleared to denominators and realized by repeated unit voters; Borda scores, STV scores, and pairwise margins scale exactly. The coalition objective depends only on aggregate reports, not on personal identities or histories.
Thus the loss of Partition is precisely the phenomenon the programme is designed to test. Theorem 1 yields a canonical finite-type LP, and Theorem 6 yields a finite union of LPs. They may be scientifically thin because the paper fixes \(m=3\) or \(m=4\), but “the continuous answer is easy” is expressly not an objection. The honest negative conclusion is therefore limited: the mirrors should be labelled high-multiplicity extensions rather than exact semantics-preserving translations of weighted blocs. A universal claim that no worthwhile continuous mirror exists cannot be sustained; Theorem 1 alone survives.
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.