Answer: \(\mathrm{NP}\)-complete
Theorem 4.4 (★) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists an algorithm that solves Possible President for Maximin and runs in FPT time with parameter 𝑡.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a party partition \(\mathcal P\), distinguished party \(P^\star\), and a finite-support rational distribution \(\mu\) over complete rankings of \(C\), decide whether some nomination \(\eta(P)\in P\) makes \(p^\star=\eta(P^\star)\) the unique Maximin winner, where \(w_\mu(a,b)=\sum_{\theta:a\succ_\theta b}\mu_\theta\) and \(\operatorname{MM}_{\mu,\eta}(a)=\min_{b\ne a}w_\mu(a,b)\).
Let \(C\) be partitioned into parties \(\mathcal P\), each of size at most \(2\), with distinguished party \(P^\star\). The input gives an explicit rational distribution \(\mu\) over strict complete rankings \(t\) of \(C\). Put \(w_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t\); \(a\) defeats \(b\) iff \(w_\mu(a,b)>1/2\). For a nomination vector \(x\) with \(x_P\in P\), the Copeland score of a nominee is its number of defeated fellow nominees; it is a unique Copeland winner if its score is strictly maximal.
Target. Is it NP-hard, or solvable in polynomial time, to decide whether some nomination vector makes \(x_{P^\star}\) the unique Copeland winner?
Nearest known results. For finite elections with exactly three voters, the corresponding Possible President problem for Copeland is NP-complete even when every party has size at most \(2\). No result for the distribution-over-rankings version is assumed here.
The problem is \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard, even when the distribution has support size at most \(3\) and every probability has denominator \(3\).
A certificate specifies one nominee \(x_P\in P\) for every party \(P\in\mathcal P\). Because every party has size at most \(2\), the certificate has polynomial length.
Let the explicit support of the distribution be \(t_1,\ldots,t_s\), with rational probabilities
\[ \mu_{t_i}=\frac{p_i}{q_i}. \]
For every ordered pair of nominees \(a,b\), compute
\[ w_\mu(a,b)=\sum_{i:a\succ_{t_i}b}\frac{p_i}{q_i}. \]
This comparison can be performed exactly in polynomial time. Indeed, putting \(D=\prod_{i=1}^s q_i\), we have
\[ w_\mu(a,b)>\frac12 \quad\Longleftrightarrow\quad 2\sum_{i:a\succ_{t_i}b}p_i\frac{D}{q_i}>D. \]
Although \(D\) can be numerically large, its binary length is at most \(\sum_i\lceil\log_2 q_i\rceil\), which is bounded by the input length. Thus all required integer arithmetic has polynomial bit complexity.
After determining every pairwise defeat relation among the nominees, one computes each nominee’s Copeland score and checks whether
\[ \operatorname{score}(x_{P^\star}) > \operatorname{score}(x_P) \]
for every other nominated candidate \(x_P\). Consequently, the problem belongs to \(\mathrm{NP}\).
Use the stated \(\mathrm{NP}\)-complete Possible President problem for Copeland with exactly three voters and parties of size at most \(2\).
Consider such an instance, consisting of:
Preserve \(C\), \(\mathcal P\), and \(P^\star\). Define a distribution \(\mu\) by taking the empirical distribution of the three voters:
\[ \mu_t=\frac{|\{i\in\{1,2,3\}:t_i=t\}|}{3} \]
for every ranking \(t\) that occurs among \(t_1,t_2,t_3\). Repeated rankings are therefore aggregated. This produces an explicit rational distribution with support size at most \(3\), and the construction is polynomial-time.
Fix distinct candidates \(a,b\in C\). By construction,
\[ w_\mu(a,b) = \sum_{t:a\succ_t b}\mu_t = \frac{|\{i\in\{1,2,3\}:a\succ_{t_i}b\}|}{3}. \]
Therefore,
\[ w_\mu(a,b)>\frac12 \quad\Longleftrightarrow\quad |\{i:a\succ_{t_i}b\}|>\frac32. \]
The quantity on the right is an integer, so this is equivalent to
\[ |\{i:a\succ_{t_i}b\}|\geq 2. \]
Thus \(a\) defeats \(b\) under \(\mu\) if and only if at least two of the three original voters prefer \(a\) to \(b\). This is precisely the strict pairwise-majority relation of the original election.
Because there are three voters, no pairwise majority tie is possible.
Let \(x\) be any nomination vector. The preceding argument applies to every pair of candidates in the nominated set
\[ \{x_P:P\in\mathcal P\}. \]
Hence the pairwise-defeat digraph induced by the nominees is identical in the original three-voter election and in the constructed distributional instance. Since the Copeland score used here is the outdegree in this digraph, every nominee has exactly the same score in both instances.
In particular,
\[ x_{P^\star}\text{ is the unique Copeland winner under }\mu \]
if and only if it is the unique Copeland winner in the original three-voter election.
Thus the original instance admits a successful nomination vector if and only if the constructed distributional instance does.
The construction is a polynomial-time many-one reduction from the stated three-voter \(\mathrm{NP}\)-complete problem. Therefore the distribution-over-rankings problem is \(\mathrm{NP}\)-hard. Together with membership in \(\mathrm{NP}\), it is \(\mathrm{NP}\)-complete.
The hardness already holds for empirical distributions of three voters, so allowing arbitrary explicitly represented rational distributions does not make the problem easier.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes \(\mathrm{NP}\)-completeness by translating the assumed three-voter hardness result into an empirical distribution over those voters’ rankings. The translation preserves every pairwise majority relation and therefore preserves all Copeland scores and unique-winner outcomes for every nomination vector.
No substantive gap or false statement was found.
The proposed certificate contains one candidate from each party. Its encoding length is polynomial in the explicitly represented candidate set and partition.
The exact comparison of
\[ w_\mu(a,b)=\sum_{i:a\succ_{t_i}b}\frac{p_i}{q_i} \]
with \(1/2\) is valid. Taking \(D=\prod_i q_i\) gives an integer comparison, and
\[ \log_2 D=\sum_i\log_2 q_i, \]
so the bit length of \(D\) is polynomially bounded by the input length. Computing \(D\), the scaled summands, and their sum requires only polynomially many arithmetic operations on polynomial-length integers.
Once the pairwise defeat relation is known, computing all Copeland scores and testing strict maximality is polynomial time. Thus membership in \(\mathrm{NP}\) is rigorously established.
The reduction starts from exactly the hardness result granted in the task: Possible President for Copeland with three voters and parties of size at most \(2\).
The empirical distribution
\[ \mu_t=\frac{|\{i\in\{1,2,3\}:t_i=t\}|}{3} \]
is a valid rational probability distribution. Its support contains at most three rankings, repeated rankings are handled correctly, and all probabilities can be represented with denominator \(3\), including \(3/3\) if all rankings coincide. The construction has polynomial size and is computable in polynomial time.
For every distinct \(a,b\),
\[ w_\mu(a,b) = \frac{|\{i:a\succ_{t_i}b\}|}{3}. \]
Consequently,
\[ w_\mu(a,b)>\frac12 \]
holds exactly when at least two of the three voters rank \(a\) above \(b\). This is precisely strict majority among three voters. Since the number of voters is odd and rankings are strict, pairwise ties cannot occur.
This calculation is correct and covers every candidate pair.
For an arbitrary nomination vector, the pairwise-defeat digraph induced by its nominees is identical in the source and target instances. Under the problem’s stated Copeland convention, a nominee’s score is exactly its outdegree in this digraph.
Therefore every nominee has the same score in both instances. In particular, the distinguished party’s nominee is the unique score maximizer in one instance if and only if it is the unique score maximizer in the other. This establishes the required many-one equivalence for the existential question over nomination vectors.
The reduction proves \(\mathrm{NP}\)-hardness, and the independently established membership argument proves \(\mathrm{NP}\)-completeness. The stronger restriction to distributions supported on at most three rankings is also justified.
The prover’s concluding metadata does not follow the verifier’s requested JSON schema, but that is not a defect in the mathematical argument being audited.
⟨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.