| paper | Llull and Copeland Voting Computationally Resist Bribery and Constructive Control |
| authors | Piotr Faliszewski, E. Hemaspaandra, Lane A. Hemaspaandra, J. Rothe |
| venue | JAIR 2009 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete for every fixed rational \(\alpha\in[0,1]\), and also when such \(\alpha\) is part of the input, under the standard Copeland victory/loss/tie convention. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.9
statement extracted from the paper’s text layer
Given disjoint candidate sets \(C,D\), a target \(p\in C\), an integer \(k\), a rational distribution \(\mu\) over complete rankings of \(C\cup D\), and rational \(0\le\alpha\le1\), does there exist \(E\subseteq D\) with \(|E|\le k\) such that, after restricting every ranking to \(C\cup E\), \(p\) is a Copeland\(_\alpha\) winner under \(\mu\)?
The candidate agenda remains finite and integral, while the electorate is a continuum of mass distributed over complete ranking types. Pairwise margins are \(M_\mu(a,b)=\sum_t\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])\); the decision variable is the spoiler set \(E\), and feasibility requires \(p\) to maximize the resulting Copeland\(_\alpha\) score.
The mirror covers constructive control by adding at most \(k\) candidates, including both nonunique- and unique-winner variants of Theorem 4.9. It leaves the other control results, FPT results, and the standard bribery hardness results unclassified; the proposed mass-bribery question remains open.
The strongest positive case is a genuine Class B mirror of the paper’s candidate-control results. A second, more exploratory mirror comes from bribery.
Take a finite candidate set \(A\) and a population distribution \(\mu\) over complete voter types \(t\), where each type is a ranking of \(A\). Define the pairwise margin
\[ M_\mu(a,b)=\sum_t\mu_t\bigl(\mathbf 1[a\succ_t b]-\mathbf 1[b\succ_t a]\bigr), \]
and the Copeland score
\[ \mathrm{sc}_{\alpha,\mu}(a) = |\{b:M_\mu(a,b)>0\}| + \alpha|\{b:M_\mu(a,b)=0\}|. \]
The winners are the candidates of maximum score. Rational \(\mu\) is the high-multiplicity representation of a finite electorate: if \(\mu_t=n_t/N\), then \(N\mu_t\) voters have type \(t\).
My lead mirror is Continuous Copeland\(_\alpha\)-CCAC. Its instance consists of disjoint candidate sets \(C,D\), a target \(p\in C\), an integer \(k\), and a rational population distribution \(\mu\) over rankings of \(C\cup D\). The question is whether there exists \(E\subseteq D\) with \(|E|\le k\) such that, after restricting every ranking to \(C\cup E\), \(p\) is a Copeland\(_\alpha\) winner. The unique-winner version asks whether \(p\) is the sole winner. A solution is the chosen spoiler set \(E\).
The anchor is Theorem 4.9, proved in this paper:
For every rational \(\alpha\), \(0\le\alpha\le1\), Copeland\(_\alpha\) is resistant to constructive control by adding candidates (CCAC), in both the nonunique-winner and unique-winner models, for both rational and irrational voters.
Here “resistant” means NP-hard and susceptible. The proof is a reduction from VertexCover. The candidates corresponding to graph vertices are the possible additions; candidates corresponding to graph edges must be held below \(p\). Adding a set of vertex candidates makes \(p\) win exactly when the selected vertices cover all graph edges.
This is a very natural high-multiplicity regime: a large electorate repeatedly votes according to a relatively small collection of standardized preference profiles, while a chair decides which policy options or shortlisted candidates enter the election. The individual voters need not be named, and their identities are irrelevant. Candidate addition remains integral because candidates, unlike population mass, are the objects controlled in the original problem.
I expect this mirror to be Class B. Given any finite CCAC instance, replace its voters by their normalized type frequencies. Every pairwise majority relation, and therefore every Copeland score, is unchanged. Conversely, any rational distribution can be scaled to a finite electorate. The reduction therefore transfers exactly. Its combinatorics live in the candidate agenda and in the integral choice of \(E\), not in the number of individually named voters. Repeating every ballot type \(R\) times gives an arbitrarily large population with the same continuous instance, so the hardness is compatible with a genuine high-multiplicity scenario.
A second mirror is Continuous Copeland\(_\alpha\)-Mass Bribery. Its instance consists of candidates \(C\), a target \(p\), a rational distribution \(\mu\) over rankings of \(C\), and a mass budget \(\beta\). An intervention chooses transfers \(x_{t,t'}\ge0\), where mass of type \(t\) is persuaded to adopt type \(t'\), subject to
\[ \sum_{t'\ne t}x_{t,t'}\le \mu_t. \]
The resulting distribution is
\[ \mu'_{t} = \mu_t-\sum_{t'\ne t}x_{t,t'} +\sum_{u\ne t}x_{u,t}, \]
and the cost is
\[ \sum_{t\ne t'}x_{t,t'}. \]
The constructive question asks whether \(p\) can be made a unique winner with cost at most \(\beta\); the destructive question asks whether \(p\) can be made a nonwinner. This is the direct population analogue of changing at most \(k\) voters at unit cost, with \(\beta=k/N\).
The anchor is Theorem 3.2, proved here:
For every rational \(\alpha\), \(0\le\alpha\le1\), Copeland\(_\alpha\) is resistant to constructive bribery in the unique-winner model and to destructive bribery in the nonunique-winner model.
The proof reduces X3C to both cases. It constructs voters whose rankings encode the three-element sets, together with candidates \(u,v,p\) and element candidates. A successful bribe of at most \(k\) voters exists exactly when \(k\) set-voters form an exact cover.
The high-multiplicity interpretation is plausible in a campaign or organizational electorate where many people share the same standardized preference profile and persuasion acts on a fraction of each profile. The type must include everything relevant to the problem: here, the ranking and the unit cost of changing it. This is not an objection about losing individual prices; the original problem is explicitly the unpriced unit-cost version.
I would not claim that Theorem 3.2’s NP-hardness automatically transfers. Fractional mass can split a set-type, and the exact-cover argument may collapse into a fractional-cover feasibility problem. My tentative classification is therefore Class C: Copeland’s winner condition remains a nonconvex combination of pairwise-win chambers, so hardness might survive for reasons internal to the candidate-side score geometry, but a min-cost-flow or LP formulation might instead place the problem in Class A. The useful follow-up questions are whether fixed pairwise tournaments admit polynomial optimization, whether endpoint values \(\alpha\in\{0,1\}\) behave differently, and whether integrality gaps or approximation guarantees characterize the transition from ordinary bribery to mass bribery.
The weakest point is the lead mirror’s modest novelty: because Copeland depends only on pairwise majority outcomes, normalized finite elections reproduce it exactly. A sceptic could call this merely weighted Copeland control. I think that objection concedes rather than defeats the mirror: the programme explicitly treats high multiplicity as a legitimate regime, and this result shows that population continuization does not necessarily dissolve computational hardness. The paper’s irrational-voter model is not a collision—it changes within-voter preference consistency, not the population into a distribution—and the paper does not formulate the society itself as a continuous object.
I cannot honestly make the requested universal negative. The first anchor survives.
Theorem 4.9 is an explicit computational result, and its continuous-population version is completely natural. If a finite election has \(n_t\) voters of ranking type \(t\), set \(\mu_t=n_t/N\). Then
\[ M_\mu(a,b)=\frac{1}{N}\operatorname{vs}_E(a,b), \]
so every pairwise win, loss, or tie—and hence every Copeland\(_\alpha\) score—is preserved exactly, including after restricting the election to any chosen spoiler set \(E\subseteq D\). Candidate addition remains an integral action; the population, not the agenda, is what has been continuized.
This is also genuinely high-multiplicity. Every ballot type in the reduction can be duplicated \(R\) times, producing an arbitrarily large electorate with the same distribution and the same control instance. Voters are interchangeable, and their identities play no role. A realistic setting with many voters sharing standardized preference profiles and a chair choosing which options enter the ballot is easy to give. Calling this “merely weighted Copeland” does not defeat it: weighted/high-multiplicity instances are precisely the intended regime, and the paper itself never formulates the election as a distribution over voter types.
The bribery anchor is much weaker. Theorem 3.2 does not transfer automatically, because its X3C reduction depends on selecting whole voters. In the mass version, a set-voter can be bribed fractionally. The exact-cover constraints may therefore become fractional-cover constraints, destroying the reduction’s integrality argument. Restoring whole-type actions or fixed setup costs would reintroduce the discrete feature the mirror was meant to relax. Thus the proposed mass-bribery mirror should be presented as an open Class A/C question, not as inherited hardness.
But that does not rescue the universal negative. The candidate-control mirror is already a worthwhile Class B problem: it is computational, population-continuous, high-multiplicity-sensible, and not already formulated in the paper. Since one valid mirror is enough, the strongest honest conclusion is that the paper should be greenlit, although the bribery mirror needs more careful formulation and should not be sold as a theorem transfer.
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.