Llull and Copeland Voting Computationally Resist Bribery and Constructive Control (d4-journals-jair-2009-0004)

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\)?

Definitions

The input explicitly lists a rational probability distribution \(\mu\) of total mass \(1\) over strict complete rankings of \(C\cup D\), where \(C\cap D=\varnothing\), \(p\in C\), and \(k\in\mathbb N\).
For candidates \(x,y\), \(x\) defeats \(y\) when \(\mu[x\succ y]>\tfrac12\); otherwise they tie. In Copeland\(_\alpha\), a victory gives \(1\) point, a loss \(0\), and a tie \(\alpha\); winners have maximum score.
For \(E\subseteq D\), restrict every ranking to \(C\cup E\) before computing the winner set.

Target

Is deciding whether some \(E\subseteq D\) with \(|E|\le k\) makes \(p\) a Copeland\(_\alpha\) winner under \(\mu\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

Nearest known results

For finite lists of voters, constructive control by adding at most \(k\) candidates for Copeland\(_\alpha\) is \(\mathrm{NP}\)-hard for every rational \(0\le\alpha\le1\), in both winner models.
No verified result was found for the exact rational-distribution formulation above.

Result and conventions

For every fixed rational \(\alpha\in[0,1]\), the stated problem is \(\mathrm{NP}\)-complete. The finite-voter hardness result transfers by a polynomial-time normalization of voter multiplicities into probabilities.

I use the standard Copeland convention: \(x\) defeats \(y\) when \(\mu[x\succ y]>\tfrac12\), loses when \(\mu[x\succ y]<\tfrac12\), and ties when equality holds. Thus “otherwise they tie” means neither candidate defeats the other. Reading it as declaring a tie whenever \(x\) fails to defeat \(y\) would conflict with the stated loss rule.

The winner condition is nonunique: \(p\) need only attain the maximum score.

Finite-voter hardness theorem

We use the following established result: for every fixed rational \(\alpha\in[0,1]\), constructive control by adding at most \(k\) candidates for Copeland\(_\alpha\) is \(\mathrm{NP}\)-hard for explicitly listed voters with strict complete rankings, in the nonunique-winner model. This is Theorem 4.9 of Faliszewski, Hemaspaandra, Hemaspaandra, and Rothe, [*Llull and Copeland Voting Computationally Resist Bribery and Control*](https://arxiv.org/pdf/0809.4484#page=44).

Its input consists of disjoint candidate sets \(C,D\), rankings over \(C\cup D\), a designated candidate \(p\in C\), and a budget \(k\). These are precisely the combinatorial data required here.

Polynomial-time reduction

Fix such an \(\alpha\). Let a finite-voter instance have voter list \((R_1,\ldots,R_n)\), with \(n>0\). For each distinct ranking \(R\) appearing in the list, let \(m_R\) be its multiplicity. Construct the explicitly listed distribution

\(\mu(R)=m_R/n.\)

Keep \(C,D,p,k\) unchanged.

This is a valid rational probability distribution because all multiplicities are positive and

\(\sum_R\mu(R)=\frac{1}{n}\sum_Rm_R=1.\)

There are at most \(n\) support rankings. Each numerator and denominator has \(O(\log(n+1))\) bits. Grouping identical rankings and writing their probabilities therefore takes polynomial time and produces polynomial output length.

If the source formulation permits an empty voter list, handle it separately: replace it by two mutually reversed rankings, each with probability \(\tfrac12\). Every pair then ties, just as with zero voters, including after any candidate restriction.

Preservation of every candidate restriction

Let \(E\subseteq D\) be arbitrary and put \(S=C\cup E\). For distinct \(x,y\in S\), deleting other candidates from a strict ranking preserves the relative order of \(x,y\). Consequently,

\(\mu[x\succ y]=\sum_{R:\,x\succ_R y}\frac{m_R}{n}=\frac{|\{i:x\succ_{R_i}y\}|}{n}.\)

Writing \(N_{xy}=|\{i:x\succ_{R_i}y\}|\), strict completeness gives \(N_{yx}=n-N_{xy}\). Hence

\(\mu[x\succ y]>\tfrac12\quad\Longleftrightarrow\quad N_{xy}>N_{yx},\)

and

\(\mu[x\succ y]=\tfrac12\quad\Longleftrightarrow\quad N_{xy}=N_{yx}.\)

Thus every pairwise victory, loss, and tie in \(S\) agrees between the source election and the constructed distribution. Each candidate receives exactly the same Copeland\(_\alpha\) score in both instances, so their winner sets coincide.

Because the candidate sets and budget are unchanged, this proves

\(\exists E\subseteq D,\ |E|\le k:\ p\text{ wins in the source instance}\)

if and only if

\(\exists E\subseteq D,\ |E|\le k:\ p\text{ wins under }\mu.\)

This polynomial-time many-one reduction establishes \(\mathrm{NP}\)-hardness.

Membership in \(\mathrm{NP}\)

A certificate is a subset \(E\subseteq D\), represented by a bit vector of length \(|D|\). Check \(|E|\le k\), then compute scores on \(S=C\cup E\).

For completeness, exact rational arithmetic remains polynomial even when probabilities have large binary denominators. Write the listed probabilities as \(a_i/b_i\), with \(b_i>0\), and let

\(B=\prod_i b_i.\)

The bit length of \(B\) is at most the sum of the denominator bit lengths, up to an additive constant, and is therefore polynomial in the input length. For each distinct \(x,y\in S\), compute the integer

\(A_{xy}=\sum_{i:\,x\succ_{R_i}y}a_i(B/b_i).\)

Then \(\mu[x\succ y]=A_{xy}/B\). Comparing \(2A_{xy}\) with \(B\) determines the pairwise outcome exactly. There are at most \(|C\cup D|^2\) ordered pairs, and all these computations use integers of polynomial bit length.

Finally, write \(\alpha=u/v\), where \(u,v\) are integers and \(v>0\). If candidate \(x\) has \(w_x\) victories and \(t_x\) ties, its score is

\(s_\alpha(x)=w_x+\frac{u}{v}t_x.\)

Compare the integer scores \(vw_x+ut_x\). Accept exactly when \(p\)'s score is at least every other candidate's score. This is a polynomial-time verifier.

Therefore the problem is \(\mathrm{NP}\)-complete for every fixed rational \(\alpha\in[0,1]\). The same conclusion holds if rational \(\alpha\in[0,1]\) is supplied as part of the input: the verifier remains polynomial, and hardness already holds for any fixed allowed value.

⟨structured verdict parsed — rendered above⟩

Assessment: proved under the explicitly stated standard Copeland convention. The cited hardness theorem applies, the reduction preserves every permitted candidate addition, and the membership argument uses polynomial-time exact arithmetic. No mathematical repair is required.

• Interpretation of the task. The prover correctly uses the nonunique-winner condition: \(p\) must attain the maximum score, but need not be the sole winner.

The task’s phrase “otherwise they tie” is ambiguous because failure of \(x\) to defeat \(y\) includes a victory for \(y\). The prover explicitly resolves this using the standard victory/loss/tie convention, consistent with the task’s separate loss rule. The conclusion is verified under that convention; the literal conflicting reading does not define a consistent pairwise outcome rule. This is an ambiguity in the task, not an undisclosed assumption in the proof.

• Cited hardness theorem. Theorem 4.9 of the cited paper does establish resistance to constructive control by adding candidates for every rational \(0\leq\alpha\leq1\), including the nonunique-winner model and strict complete voter rankings. The paper’s bounded addition problem uses an input budget \(k\); it distinguishes this from unlimited addition. Its ordinary voter representation lists ballots individually. Thus the theorem supplies precisely the source hardness required here. [Verified source](https://arxiv.org/pdf/0809.4484#page=44).

All relevant hypotheses match: fixed rational \(\alpha\), disjoint initial and additional candidate sets, complete rankings over their union, a designated initial candidate, and addition of at most \(k\) candidates.

• Construction and encoding size. For \(n>0\), assigning probability \(m_R/n\) to each distinct ranking is valid: the masses are positive and sum to \(1\). There are at most \(n\) support entries, and both numerator and denominator require \(O(\log(n+1))\) bits. Grouping identical explicitly listed rankings is polynomial-time. Neither the construction nor its size bound assumes that binary-encoded multiplicities have been expanded.

• Empty voter list. The proposed pair of reversed rankings produces equal probability in both directions for every distinct candidate pair, including after restriction. This preserves the all-tie source election.

If the full candidate set contains only \(p\), the reversed rankings coincide. They represent a single ranking of total mass \(1\); this harmless representation degeneracy does not affect the construction’s correctness.

• Preservation under restriction. The proof fixes an arbitrary \(E\subseteq D\), so its argument covers every feasible choice, rather than just one selected subset. Removing other candidates preserves the relative order of any retained pair. Consequently, the displayed identity

\(\mu[x\succ y]=N_{xy}/n\)
is correct.

Strict completeness gives \(N_{yx}=n-N_{xy}\). The stated strict-majority and equality equivalences follow exactly, and losses are preserved as well. Therefore all pairwise point contributions, candidate scores, and winner sets coincide.

• Reduction equivalence. Since \(C,D,p,k\) are unchanged, precisely the same subsets satisfy the budget in both instances. Winner preservation for every such subset establishes both directions of the existential equivalence. This is a polynomial-time many-one reduction and proves the claimed hardness.

• Membership in \(\mathrm{NP}\). The proposed certificate has polynomial length. The common denominator \(B=\prod_i b_i\) has polynomial bit length because denominator bit lengths are part of the input.

Each division \(B/b_i\) is exact. On valid probability-distribution inputs, the integers \(A_{xy}\) and their partial sums lie between \(0\) and \(B\), so the claimed polynomial bit bounds hold. There are polynomially many candidate pairs and support entries. Comparing \(2A_{xy}\) with \(B\) determines every outcome exactly.

Multiplying scores by the positive denominator \(v\) preserves their ordering. The acceptance condition therefore verifies precisely that \(p\) is a winner.

• Parameters and edge cases. The reasoning includes \(\alpha=0\), \(\alpha=1\), no additional candidates, an empty addition set, and budgets exceeding \(|D|\). With only one retained candidate, all scores are zero and the verifier correctly accepts. If rational \(\alpha\) is part of the input, its numerator and denominator contribute to input length, so score comparisons remain polynomial; restricting to a fixed value establishes hardness.

Feedback to the prover: No missing lemma, unjustified theorem application, or substantive gap was found. Retain the explicit convention paragraph, since it identifies the task’s only definitional ambiguity.

⟨structured verdict parsed — rendered above⟩