Answer: \(\Sigma_2^P\)-complete with unrestricted party sizes; \(\mathrm{NP}\)-complete under every fixed positive upper bound on party size, including singleton parties.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatedistrict candidacy is Σp 2-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given districts \(D\), parties with named candidate sets, a fixed tie-breaking order, and for each district either an empty electorate or a finite-support rational distribution over complete rankings of the candidates with total mass \(1\), does there exist a nomination profile in which each candidate is nominated in at most one district and no party can increase its number of elected candidates by unilaterally changing its nominations? Each nonempty district elects the plurality winner under its ranking distribution and the fixed tie-break.
Let \(D\) be a nonempty set of \(d\) districts and \(C\) a set of \(m\ge d\) named candidates, partitioned into nonempty parties. A fixed strict order on \(C\) breaks all electoral ties; party sizes are unrestricted.
Each district has either an empty electorate or a distribution of total mass \(1\) over strict complete rankings of \(C\). A society is given by its support: the list of types with positive mass, each mass a binary rational. Write \(\tau_D\) for a district's support size and \(\tau=\sum_{D}\tau_D\); these count listed types, not possible rankings. Let \(L\) be the total input bit length.
A party may nominate any subset of its candidates in each district, including several candidates or none, provided each candidate is nominated in at most one district; candidates may remain unnominated. A unilateral deviation may replace the party's entire nomination strategy.
Each district with nominees elects one plurality winner using the ranking masses and the fixed tie-break. An empty electorate gives every nominee score \(0\), so the tie-break selects its winner; a district without nominees elects nobody. Each party's utility is its number of elected candidates.
Is deciding whether such a game admits a pure Nash equilibrium in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L,d\), and the number of parties.
For explicitly listed finite electorates, equilibrium existence is \(\Sigma_2^P\)-complete with unrestricted party sizes and \(\mathrm{NP}\)-complete with any fixed bound on party size, including singleton parties ([Harrenstein and Turrini, 2022](https://wrap.warwick.ac.uk/id/eprint/162392/1/WRAP-computing-Nash-equilibria-district-based-nominations-Turrini-2022.pdf)). No result specifically treating the rational-distribution formulation was located in the literature search.
Equilibrium existence is \(\Sigma_2^P\)-complete, hence \(\mathrm{NP}\)-hard. If every party has at most \(\,k\) candidates for any fixed positive constant \(\,k\), it is \(\mathrm{NP}\)-complete, including when every party is a singleton.
Here, binary rationals mean fractions whose numerators and denominators are encoded in binary. The proof transfers the stated finite-electorate hardness results and establishes polynomial-time exact outcome computation for the rational formulation.
The boundary case \(\,m=d\) always admits an equilibrium: nominate each candidate in a different district. Every candidate is elected, so each party attains its maximum possible utility. The hardness concerns the general case permitting \(\,m>d\).
Let \(\,p\) be the number of parties, let their sizes be \(\,s_1,\ldots,s_p\), and put \(\,k=\max_i s_i\).
Label the districts by \(\,1,\ldots,d\). A nomination profile is exactly a function
\(x:C\longrightarrow\{0,1,\ldots,d\}\),
where \(\,x(c)=0\) means that candidate \(\,c\) remains unnominated. This representation allows several candidates from one party in a district and ensures that each candidate is nominated in at most one district.
Consequently, there are exactly \(\,(d+1)^m\) profiles, and party \(\,i\) has exactly \(\,(d+1)^{s_i}\) strategies.
We first show that a profile’s outcome can be computed exactly in polynomial time.
For a nonempty district \(\,D\), write its listed masses as \(\,a_{D,j}/b_{D,j}\), and define
\(Q_D=\prod_{j=1}^{\tau_D}b_{D,j}\)
and
\(w_{D,j}=a_{D,j}(Q_D/b_{D,j})\).
These are integers, and the total-mass assumption gives
\(\sum_j w_{D,j}=Q_D\).
The bit length of \(\,Q_D\) is at most the sum of the bit lengths of its input denominators, hence is \(\,O(L)\). Every weight and every accumulated score also has \(\,O(L)\) bits. Using ordinary integer multiplication and division, all these weights can be precomputed in \(\,O(L^3)\) bit operations.
Given a profile, scan each listed ranking until reaching its highest-ranked nominee. Add that type’s integer weight to the nominee’s score. Integer scores are precisely the rational scores multiplied by the positive constant \(\,Q_D\), so they preserve all comparisons and equalities. Apply the given tie-break among maximum-score nominees.
For an empty electorate, all nominee scores are zero, as required. For a district without nominees, record no winner.
A conservative bound for evaluating a profile, including all party utilities, is
\(T=O\bigl((m\tau+dm+m+p+1)L^2\bigr)\)
bit operations after preprocessing. Here \(\,m\tau\) counts scanned ranking entries; no enumeration of unlisted rankings is involved.
We use the following stated finite-electorate result: with one plurality winner per district, a fixed candidate tie-break, the specified nomination strategies, and utilities counting elected party members, equilibrium existence is \(\Sigma_2^P\)-complete; its singleton-party restriction is \(\mathrm{NP}\)-complete. These are Theorem 2 and Corollary 1 of [Harrenstein and Turrini (2022)](https://wrap.warwick.ac.uk/id/eprint/162392/1/WRAP-computing-Nash-equilibria-district-based-nominations-Turrini-2022.pdf).
Take an instance of that finite-electorate problem. Keep its candidates, parties, districts, and tie-break unchanged. In a district containing \(\,n_D>0\) voters, group identical rankings. If ranking \(\,\rho\) occurs \(\,n_{D,\rho}>0\) times, list it with mass
\(\mu_D(\rho)=n_{D,\rho}/n_D\).
Represent an empty electorate by an empty support.
These masses are positive binary-encoded rationals summing to one. If the original instance has \(\,n\) voters altogether, the output has \(\,\tau\leq n\) listed types, and each numerator and denominator uses \(\,O(\log(n+1))\) bits. Grouping explicitly listed rankings and computing these fractions therefore takes polynomial time and produces polynomial output length.
Fix any nomination profile \(\,x\), any nonempty district \(\,D\), and any nominee \(\,c\). Its new score is exactly
\(\operatorname{score}_{\mathrm{new},D}(c;x)=\operatorname{score}_{\mathrm{old},D}(c;x)/n_D\).
Division by the same positive number preserves every plurality comparison and every tie. Because the tie-break is unchanged, the elected candidate is unchanged. Empty electorates and districts without nominees also behave identically.
Thus every profile has exactly the same party utilities in both games. The strategy spaces are identical, so this equality also holds after every unilateral deviation. A profile is therefore an equilibrium in the finite instance if and only if it is an equilibrium in the rational instance.
The reduction preserves party sizes and the condition \(\,m\geq d\). It proves \(\Sigma_2^P\)-hardness in general and \(\mathrm{NP}\)-hardness for singleton parties. Singleton instances also satisfy every fixed positive upper bound on party size.
A profile requires \(\,O(m\log(d+1))\) bits. A deviation consists of a party index and a replacement assignment for its candidates, also requiring polynomially many bits.
By Section 1, whether that deviation strictly increases the party’s utility is decidable in polynomial time. Equilibrium existence consequently has the form
\(\exists x\;\forall(i,y)\;[u_i(x)\geq u_i(x_{-i},y)]\),
with polynomial-length quantified strings and a polynomial-time predicate. Invalid universal encodings can simply satisfy the predicate automatically. This proves membership in \(\Sigma_2^P\), and therefore \(\Sigma_2^P\)-completeness.
If \(\,s_i\leq k\) for a fixed constant \(\,k\), a proposed profile can instead be checked by enumerating every party’s replacement strategies. There are at most
\(\sum_{i=1}^p(d+1)^{s_i}\leq p(d+1)^k\)
such checks. Since \(\,d\leq m\) and the candidates are explicitly listed, this is polynomial in input length for fixed \(\,k\). Guessing and checking a profile proves membership in \(\mathrm{NP}\). Together with singleton hardness, this establishes the bounded-size completeness claim.
Let
\(S=\sum_{i=1}^p(d+1)^{s_i}\),
and use the evaluation bound \(\,T\) from Section 1.
After the one-time \(\,O(L^3)\) preprocessing:
| Task | Running time in bit operations |
|---|---|
| Evaluate one profile | \(\,O(T)\) |
| Verify one proposed equilibrium by enumerating deviations | \(\,O((1+S)T)\) |
| Decide existence by enumerating profiles and deviations | \(\,O((d+1)^m(1+S)T)\) |
These algorithms are exhaustive: the verifier checks every legal replacement strategy, and the existence algorithm checks every legal nomination profile.
Using \(\,S\leq p(d+1)^k\), the total deterministic existence bound simplifies to
\(O\bigl(L^3+p(d+1)^{m+k}T\bigr)\).
For unrestricted party sizes, \(\,k\leq m\), giving
\(O\bigl(L^3+p(d+1)^{2m}T\bigr)\).
For fixed \(\,k\), certificate verification takes
\(O\bigl(L^3+p(d+1)^kT\bigr)\),
which is polynomial. This is a verification bound, not a polynomial-time existence algorithm.
Thus the rational support encoding preserves the hardness while allowing polynomial-time exact utility evaluation. A polynomial-time existence algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The rational-distribution problem is \(\Sigma_2^P\)-complete with unrestricted party sizes and \(\mathrm{NP}\)-complete under every fixed positive upper bound on party size. I found no major or minor mathematical issues requiring repair.
The function \(x:C\to\{0,1,\ldots,d\}\) exactly represents the permitted nominations. Each candidate is either unnominated or assigned to one district. Independent assignments allow multiple candidates from the same party in one district.
Therefore, the counts \((d+1)^m\) for profiles and \((d+1)^{s_i}\) for party \(i\)'s strategies are correct. Replacement assignments represent entire unilateral deviations, as required.
For every nonempty district, the denominators are positive integers, so \(Q_D=\prod_j b_{D,j}\) is positive and each quotient \(Q_D/b_{D,j}\) is integral. Consequently, the weights \(w_{D,j}\) are positive integers. The mass normalization gives \(\sum_jw_{D,j}=Q_D\).
The product's bit length is bounded by the sum of the input denominator bit lengths. Since each weight and each accumulated score is at most \(Q_D\), their bit lengths are also \(O(L)\). Unreduced input fractions do not invalidate these statements.
The preprocessing bound \(O(L^3)\) is valid and conservative: there are \(O(L)\) listed masses, and ordinary multiplication and exact division on integers of \(O(L)\) bits cost at most \(O(L^2)\) per operation.
Scanning a strict complete ranking until its first nominee correctly identifies that type's plurality vote. Multiplying all scores in a district by the same positive integer preserves comparisons and ties, so the integer computation produces precisely the prescribed winner.
Both exceptional cases are handled correctly: empty electorates assign every nominee score zero, and districts without nominees elect nobody. In a district without nominees, scanning its rankings can simply be skipped.
The stated bound
\(T=O((m\tau+dm+m+p+1)L^2)\)
covers ranking scans, score initialization and winner selection, candidate assignments, and utility accumulation. It counts listed types rather than possible rankings and requires no expansion of rational masses into voters.
The citation matches the claimed source results. The paper's model permits arbitrary subsets of party candidates in each district, prohibits nominating a candidate twice, uses a fixed candidate tie-break, and assumes at least as many candidates as seats. Its complexity section fixes one winner per district and plurality, with parties maximizing their elected membership. Theorem 2 and Corollary 1 give the claimed unrestricted and bounded-size classifications, including singleton parties. The hardness constructions use complete candidate rankings. These hypotheses match the reduction's source problem. [Harrenstein and Turrini (2022), Sections 3 and 5](https://wrap.warwick.ac.uk/id/eprint/162392/1/WRAP-computing-Nash-equilibria-district-based-nominations-Turrini-2022.pdf).
Allowing empty electorates in the target causes no difficulty: hardness can be transferred from source instances with nonempty electorates.
Grouping identical explicitly listed rankings is polynomial-time processing. Each positive frequency \(n_{D,\rho}\) and district size \(n_D\) is at most the total number \(n\) of voters, so the claimed \(O(\log(n+1))\) encoding bound is correct. There are at most \(n\) output types.
For every profile and nominee in a nonempty district, the new score equals the old score divided by \(n_D\). This identity holds uniformly over all nomination profiles, including every unilateral deviation. Thus winners, party utilities, and profitable-deviation relations are preserved.
The strategy spaces, party sizes, and condition \(m\ge d\) remain unchanged. The reduction therefore establishes unrestricted \(\Sigma_2^P\)-hardness and singleton \(\mathrm{NP}\)-hardness. Singleton instances lie within every fixed positive party-size upper bound, so the latter hardness claim follows for each such bound.
Profiles and replacement strategies have polynomial-length encodings. Exact outcome computation makes the comparison of original and deviating utilities a polynomial-time predicate.
The existential profile quantifier followed by universal quantification over parties and legal replacement strategies expresses equilibrium existence correctly. Invalid universal encodings may satisfy the predicate automatically because they represent no legal deviation. This establishes membership in \(\Sigma_2^P\).
For fixed \(k\), enumerating all replacements requires at most \(p(d+1)^k\) evaluations. Since \(d\le m\) and candidates are explicitly represented, this is polynomial in input length. Guessing a profile and performing these checks establishes membership in \(\mathrm{NP}\).
With \(S=\sum_i(d+1)^{s_i}\), verification requires one baseline evaluation and at most \(S\) deviation evaluations. The bound \(O((1+S)T)\) after preprocessing is correct.
Enumerating every profile gives \(O((d+1)^m(1+S)T)\). The simplifications using \(S\le p(d+1)^k\) are valid because \(p\ge1\), \(d\ge1\), and \(k\ge1\). All total bounds correctly include the one-time \(O(L^3)\) preprocessing cost.
When \(m=d\), assigning each candidate to a distinct district elects every candidate, including in empty electorates. Each party then achieves utility \(s_i\), its absolute maximum, so no profitable deviation exists.
This boundary case is consistent with hardness over the general input family. The final statement that a polynomial-time existence algorithm would imply \(\mathrm{P}=\mathrm{NP}\) follows from the established \(\mathrm{NP}\)-hardness.
No additional clarification or missing lemma is needed.
⟨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.