Answer: Polynomial-time solvable
Proposition 9 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor Copeland, for any number of candidates and an odd number of voters, every candidacy game has an NE.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(X\), strict candidate preference rankings with each candidate ranked first in their own ranking, a fixed tie-breaking priority, and a rational distribution \(\mu\) over supported complete voter rankings with no tied pairwise masses, find a nonempty running slate \(Y\subseteq X\) that is a pure Nash equilibrium. For each slate, restrict rankings to \(Y\), elect the Copeland winner under strict pairwise majority and the fixed priority, and treat the empty slate as a no-election outcome ranked below every candidate. A slate is an equilibrium if no running candidate benefits by withdrawing and no nonrunning candidate benefits by joining.
Let \(X\) be a candidate set with \(m\geq 1\). Each candidate has a strict ranking of \(X\), placing themselves first, and cares only about the elected candidate. A fixed strict priority order on \(X\) breaks winner ties on every slate by restriction.
A society is given by its support: a list of \(\tau\) distinct strict complete voter rankings of \(X\), each with positive binary rational mass \(\mu_t\), with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
Assume \(\sum_{t:a\succ_t b}\mu_t\neq 1/2\) for every distinct \(a,b\in X\). On each nonempty slate \(Y\subseteq X\), voters retain their masses and restrict their rankings to \(Y\); elect the Copeland winner using strict pairwise majority and the fixed priority.
The empty slate elects a no-election outcome that every candidate ranks below every member of \(X\). A nonempty slate is a pure Nash equilibrium if no member strictly benefits by withdrawing and no excluded candidate strictly benefits by joining.
Can a nonempty pure Nash equilibrium always be found in time polynomial in \(m,\tau,L\), or is this search problem NP-hard?
For finite electorates with an odd number of voters, Copeland candidacy games always admit a pure Nash equilibrium; the guarantee also holds for even electorates without pairwise majority ties. [Discrete existence result](https://arxiv.org/pdf/1306.1849v2).
A later result guarantees an equilibrium electing the full-slate winner under the same discrete assumptions. [Published extension](https://www.lamsade.dauphine.fr/~lang/papers/LMPC25.pdf). No result explicitly addressing the rational-distribution search problem was located.
A nonempty pure Nash equilibrium can always be found in time polynomial in \(m,\tau,L\). Indeed, an equilibrium electing the full-slate winner can be constructed without consulting candidates’ preferences beyond their self-first assumption.
The construction appears in [Proposition 9 of the discrete existence paper](https://arxiv.org/pdf/1306.1849v2) and [Proposition 13 of the published extension](https://www.lamsade.dauphine.fr/~lang/papers/LMPC25.pdf). Below is a self-contained proof, including the bit-complexity argument for rational masses.
Write \(a\to b\) when
\( \sum_{t:a\succ_t b}\mu_t>1/2 \).
Because voter rankings are strict and complete, the masses preferring \(a\) to \(b\) and \(b\) to \(a\) sum to \(1\). The no-ties assumption therefore ensures that exactly one of \(a\to b\) and \(b\to a\) holds.
Restricting rankings to a slate containing both candidates preserves their comparison. Thus every slate uses the corresponding induced subgraph of this fixed majority tournament.
For a nonempty slate \(Z\) and \(x\in Z\), define its Copeland score by
\( d_Z(x)=|\{y\in Z\setminus\{x\}:x\to y\}| \).
Let \(c\) be the full-slate winner and put
\( q=d_X(c) \).
Consequently, every \(x\in X\) satisfies \(d_X(x)\leq q\), and \(c\) has priority over every other candidate whose full-slate score equals \(q\).
Output the slate
\( Y=\{c\}\cup\{y\in X:c\to y\} \).
In particular, \(Y\) is nonempty and \(|Y|=q+1\).
First observe that every slate \(Z\) satisfying \(Y\subseteq Z\subseteq X\) elects \(c\).
Indeed, \(Y\) already contains every candidate that \(c\) defeats. Hence \(d_Z(c)=q\). For every \(x\in Z\setminus\{c\}\), restriction cannot increase its number of victories, so
\( d_Z(x)\leq d_X(x)\leq q \).
If \(d_Z(x)<q\), then \(x\) loses to \(c\) by score. If \(d_Z(x)=q\), these inequalities force \(d_X(x)=q\), so the fixed priority favors \(c\) over \(x\). This proves the observation.
We now check every possible unilateral deviation.
All deviations are covered, so \(Y\) is a pure Nash equilibrium. The argument also covers \(m=1\), when \(Y=\{c\}\).
Write each input mass as \(\mu_t=a_t/b_t\), with positive binary integers \(a_t,b_t\). Define
\( D=\prod_{t=1}^{\tau}b_t \)
and
\( w_t=a_t(D/b_t) \).
Then \(\mu_t=w_t/D\) and \(\sum_t w_t=D\). Consequently, each majority comparison can be performed exactly using
\( a\to b\quad\Longleftrightarrow\quad 2\sum_{t:a\succ_t b}w_t>D \).
Although the numerical value of \(D\) can be exponential, its bit length is at most one plus the sum of the input denominators’ bit lengths, hence is \(O(L)\). Each \(w_t\) and each subset sum also has \(O(L)\) bits, since the weights are positive and sum to \(D\).
Precomputing positions in the voter rankings permits each pairwise comparison to use \(\tau\) ranking comparisons and additions of \(O(L)\)-bit integers. There are \(\binom m2\) pairs. Computing \(D\) and the weights uses polynomially many exact multiplications and divisions on polynomial-bit integers.
Finally, computing the full-slate scores, selecting \(c\) by priority, and constructing \(Y\) require only polynomial additional work. No expansion into individual voters is needed. Therefore the entire search runs in time polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The construction produces a nonempty pure Nash equilibrium electing the full-slate Copeland winner, and its implementation runs in time polynomial in \(m,\tau,L\). No major or minor mathematical issues were found.
For distinct \(a,b\), strict complete voter rankings place exactly one above the other. Since the masses sum to \(1\), the two directional comparison masses sum to \(1\). The no-ties hypothesis therefore implies that exactly one direction has mass greater than \(1/2\).
Thus the majority relation is a tournament. Restricting a ranking to a slate containing both candidates preserves their relative order, and masses remain unchanged. Consequently, the majority tournament on any slate is exactly the induced tournament. Both claims are justified under the stated assumptions.
The defined score \(d_Z(x)\) counts pairwise victories, as required for Copeland without pairwise ties.
Since \(c\) is the full-slate winner and \(q=d_X(c)\), every candidate has full-slate score at most \(q\). Among candidates with score \(q\), the fixed priority favors \(c\). These assertions follow directly from the winner rule.
The output
\[
Y=\{c\}\cup\{y\in X:c\to y\}
\]
contains \(c\) and exactly its \(q\) defeated opponents. Therefore \(Y\) is nonempty and has size \(q+1\).
For any \(Y\subseteq Z\subseteq X\), every opponent defeated by \(c\) is present in \(Z\). No added opponent is defeated by \(c\), by the definition of \(Y\). Hence \(d_Z(c)=q\).
For every other \(x\in Z\), the induced-tournament property gives
\[
d_Z(x)\leq d_X(x)\leq q.
\]
If \(d_Z(x)=q\), both inequalities force \(d_X(x)=q\). The full-slate priority comparison therefore favors \(c\), and the same comparison applies on \(Z\) because priority is fixed and restricted to each slate.
This proves the stated superset claim, including all score-tie cases.
The three deviation classes exhaust the available unilateral changes.
The empty-slate convention is used correctly. In particular, when \(m=1\), the output is the singleton containing \(c\), and its withdrawal cannot improve its outcome.
The proof therefore establishes equilibrium for every admissible candidate preference profile, without inspecting preferences below the self-first position.
The common-denominator construction is exact:
\[
D=\prod_{t=1}^{\tau}b_t,\qquad
w_t=a_t(D/b_t).
\]
Each division is integral, and normalization yields \(\sum_t w_t=D\). The majority test
\[
2\sum_{t:a\succ_t b}w_t>D
\]
is consequently equivalent to the original rational comparison.
The bit length of \(D\) is \(O(L)\), since the logarithm of the product is the sum of the denominator logarithms. Positivity and \(\sum_t w_t=D\) imply that each weight and every subset sum is at most \(D\); doubling a subset sum adds at most one bit.
There are \(\binom{m}{2}\) pairwise comparisons, each using at most \(\tau\) ranking comparisons and additions on \(O(L)\)-bit integers. Precomputed ranking positions, exact multiplication and division, score computation, priority selection, and output construction all require polynomial time. The exponentially large numerical denominator does not imply exponentially large binary arithmetic.
The same slate construction appears in [Proposition 9 of the discrete paper](https://arxiv.org/pdf/1306.1849v2) and [Proposition 13 of the published extension](https://www.lamsade.dauphine.fr/~lang/papers/LMPC25.pdf). Their discrete statements assume an odd electorate; the extension also discusses even electorates without pairwise ties.
The prover supplies a self-contained argument directly for rational masses, so it does not rely on an unstated transfer from discrete existence to polynomial-time computation.
None required. The proof addresses the intended rational-distribution search problem and verifies all relevant deviations, tie-breaking conditions, and arithmetic bounds.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.