Answer: \(\mathrm{NP}\text{-complete}\), even with one candidate in party \(2\), positive masses for every candidate, and dyadic rational masses.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSEATS(2,2) is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two disjoint candidate sets \(C_1,C_2\) and binary-rational masses \(\mu_c\) over candidate-favorite voter types, with \(\sum_c \mu_c=1\), each party partitions its candidates into lists. A list \(\ell\) has mass \(\mu(\ell)=\sum_{c\in\ell}\mu_c\); using quota \(1/2\), it receives \(\min\{|\ell|,\lfloor 2\mu(\ell)\rfloor\}\) first-round seats, and remaining seats are allocated by the paper’s largest-remainder rule with ties split by lottery. Does there exist a pair of list partitions that is a pure Nash equilibrium and gives party 1 expected payoff \(2\)?
Let \(C_1,C_2\) be disjoint nonempty finite candidate sets, with \(m=|C_1|+|C_2|\), and fix two seats. Each voter type has one favorite candidate and votes for the list containing that candidate.
The society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational, summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Candidates absent from the support have mass \(0\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A strategy for party \(i\) is a partition of \(C_i\) into nonempty lists; candidates are indivisible. For each list \(\ell\), set \(\mu(\ell)=\sum_{c\in\ell}\mu_c\) and award \(a_\ell=\min\{|\ell|,\lfloor2\mu(\ell)\rfloor\}\) first-round seats, using quota \(1/2\).
Set \(R=2-\sum_\ell a_\ell\). Only lists with \(|\ell|>a_\ell\) remain eligible. Rank these by \(r_\ell=\mu(\ell)-a_\ell/2\), and award one additional seat to each of the highest-ranked \(\min\{R,\text{number of eligible lists}\}\) lists. At a cutoff tie, choose uniformly among subsets of the tied lists of the required size. Any unfillable seats remain vacant.
Each party's payoff is its expected number of seats. The decision problem asks whether some pure Nash equilibrium gives party \(1\) payoff exactly \(2\).
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For integer vote counts, the corresponding two-seat equilibrium decision problem is NP-complete; that formulation uses quota \(\lfloor V/2\rfloor\), where \(V\) is the total vote count. [Ding and Lin (2014)](https://ojs.aaai.org/index.php/AAAI/article/download/8888/8747)
No result settling the exact normalized rational-mass formulation above was identified in the literature search.
Result. The decision problem is \(\mathrm{NP}\)-complete, even when party \(2\) has exactly one candidate, every candidate has positive mass, and every mass is a dyadic rational. Consequently, it has no algorithm polynomial in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).
The proof below applies directly to the stipulated quota \(1/2\). It uses PARTITION, also used in [Ding and Lin’s integer-model proof, Theorem 2](https://cdn.aaai.org/ojs/8888/8888-13-12416-1-2-20201228.pdf).
1. A polynomially verifiable equilibrium certificate
Write \(p=\mu(C_1)\) and \(q=\mu(C_2)=1-p\). Denote partitions by \(\Pi_1,\Pi_2\), and let \(U_2=\{C_2\}\) be party \(2\)’s unified partition.
First, every outcome allocates at most two seats. Indeed,
\(\displaystyle \sum_\ell a_\ell\leq \sum_\ell 2\mu(\ell)=2,\)
and the second round allocates at most the remaining number of seats. Thus both payoffs are nonnegative and at most \(2\).
Lemma 1. There exists a pure Nash equilibrium giving party \(1\) payoff \(2\) if and only if there exists a partition \(\Pi_1\) giving party \(1\) payoff \(2\) against \(U_2\).
*Proof.* Fix \(\Pi_1\), and write
\(\displaystyle F=\sum_{\ell\in\Pi_1}a_\ell,\qquad E=\{\ell\in\Pi_1:|\ell|>a_\ell\}.\)
Suppose first that \(q<1/2\). Under every partition of party \(2\), its lists receive no first-round seats, remain eligible, and have remainders at most \(q\). Consequently the number of second-round seats is \(R=2-F\).
Against \(U_2\), party \(2\)’s sole list has remainder exactly \(q\). It receives zero expected seats precisely when
\[\displaystyle \bigl|\{\ell\in E:r_\ell>q\}\bigr|\geq R. \tag{1}\]
To justify necessity, suppose fewer than \(R\) eligible party \(1\) lists have remainder strictly greater than \(q\). If fewer than \(R\) lists in total are eligible, party \(2\)’s list is selected. Otherwise the cutoff remainder is at most \(q\). A cutoff below \(q\) selects party \(2\)’s list certainly; a cutoff equal to \(q\) selects it with positive probability under the stipulated uniform rule. In either case its expected payoff is positive. Sufficiency follows because the \(R\) strictly higher party \(1\) lists fill every remaining seat.
Moreover, condition (1) guarantees party \(1\) both seats against every opposing partition: every opposing remainder is at most \(q\).
Now suppose \((\Pi_1,\Pi_2)\) is an equilibrium with party \(1\)’s payoff \(2\). Party \(2\)’s payoff is therefore zero, so its deviation to \(U_2\) must also give zero. Necessarily \(q<1/2\), since otherwise \(U_2\) receives at least one first-round seat. Condition (1) then holds, and party \(1\) receives both seats against \(U_2\).
Conversely, suppose \(\Pi_1\) gives party \(1\) payoff \(2\) against \(U_2\). Again \(q<1/2\), and condition (1) holds. Party \(2\) therefore receives zero against every deviation. Party \(1\), already receiving the maximum possible payoff, cannot improve. Hence \((\Pi_1,U_2)\) is an equilibrium. \(\square\)
A certificate consists solely of the list label assigned to each candidate in \(C_1\), using \(O(m\log(m+1))\) bits. The verifier computes \(q,F\), eligibility, and the count in (1).
For an explicit bit-complexity bound, put
\(\displaystyle B=L+m\lceil\log_2(m+1)\rceil+1.\)
The product of the input rational denominators has \(O(L)\) bits. Using this common denominator, schoolbook integer arithmetic verifies the certificate in
\(\displaystyle O\bigl((m+\tau)B^2\bigr)\)
bit operations. Candidates absent from the support receive mass zero. This proves membership in \(\mathrm{NP}\), with no enumeration of opposing strategies or possible voter types.
2. The critical subset-sum interval
Lemma 2. Suppose \(2/3<p\leq3/4\). A desired equilibrium exists if and only if some subset \(S\subseteq C_1\) satisfies
\[\displaystyle q<\mu(S)<p-q. \tag{2}\]
*Proof.* By Lemma 1, it suffices to consider play against \(U_2\).
For any party \(1\) partition,
\(\displaystyle F\leq2p\leq3/2.\)
Since \(F\) is an integer, it is either zero or one.
If \(F=1\), the sum of the remainders of all party \(1\) lists, including ineligible ones, is
\(\displaystyle \sum_{\ell\in\Pi_1}r_\ell=p-\frac12\leq1-p=q.\)
Every remainder is nonnegative, because \(a_\ell\leq2\mu(\ell)\). Therefore no eligible party \(1\) list has remainder strictly greater than \(q\). Condition (1) fails, so party \(1\) cannot receive both seats.
Thus a successful partition must have \(F=0\). Condition (1) then requires two distinct party \(1\) lists with masses \(x>q\) and \(y>q\). Since \(x+y\leq p\),
\(\displaystyle q<x\leq p-y<p-q.\)
Taking either list as \(S\) proves necessity of (2).
Conversely, suppose (2) holds. The two lists \(S\) and \(C_1\setminus S\) both have mass greater than \(q\), so both are nonempty. Their masses are also strictly less than
\(\displaystyle p-q=2p-1\leq1/2.\)
Hence neither receives a first-round seat. Both are eligible and strictly outrank party \(2\)’s unified list, so each receives one second-round seat. Lemma 1 yields the desired equilibrium. \(\square\)
3. A reduction using only dyadic masses
We reduce from the standard \(\mathrm{NP}\)-complete PARTITION problem: given positive binary integers \(a_1,\ldots,a_n\), decide whether some index subset has sum \(W/2\), where
\(\displaystyle W=\sum_{i=1}^{n}a_i.\)
Choose \(D\) to be the smallest power of two satisfying \(D\geq16W^2\), and define
\(\displaystyle K=\left\lceil\frac{2D}{3W}\right\rceil,\qquad t=3KW-2D.\)
These quantities satisfy
\[\displaystyle 0<t<3W<K. \tag{3}\]
Indeed, the ceiling gives \(0\leq t<3W\). Equality \(t=0\) would imply \(3KW=2D\), impossible because \(2D\) is a power of two. Finally,
\(\displaystyle K\geq\frac{2D}{3W}\geq\frac{32W}{3}>3W.\)
Construct the election with
\(\displaystyle C_1=\{c_1,\ldots,c_n\},\qquad C_2=\{d\},\)
and masses
\(\displaystyle \mu_{c_i}=\frac{Ka_i}{D},\qquad \mu_d=\frac{D-KW}{D}.\)
Give each candidate one supported voter type favoring that candidate. Thus \(\tau=m=n+1\).
Party \(1\)’s total mass is \(p=KW/D\). By (3) and the definition of the ceiling,
\(\displaystyle \frac23<p<\frac23+\frac WD\leq\frac23+\frac1{16W}\leq\frac{35}{48}<\frac34.\)
Consequently all constructed masses are positive, sum exactly to one, and are dyadic. Lemma 2 applies.
For a subset \(S\subseteq C_1\), let \(s=\sum_{c_i\in S}a_i\). Its mass is \(Ks/D\). The interval condition (2) becomes
\(\displaystyle D-KW<Ks<2KW-D.\)
Subtracting the midpoint and doubling gives the equivalent condition
\(\displaystyle |2Ks-KW|<3KW-2D=t,\)
or
\[\displaystyle K|2s-W|<t. \tag{4}\]
Since \(2s-W\) is an integer and \(0<t<K\), condition (4) holds exactly when \(2s=W\). Therefore
\(\displaystyle \text{the PARTITION instance is yes}\quad\Longleftrightarrow\quad\text{the constructed election has the requested equilibrium}.\)
This proves \(\mathrm{NP}\)-hardness. In particular, the construction respects indivisibility of candidates and the exact quota \(1/2\); it does not replace either by an approximation.
4. Encoding size and conclusion
Minimality of \(D\) gives \(16W^2\leq D<32W^2\). Hence \(D,K\), and every mass numerator have \(O(\log(W+1))\) bits. The output length is
\(\displaystyle L_{\mathrm{out}}=O\bigl((n+1)(\log(W+1)+\log(n+1))\bigr).\)
The construction takes \(O((n+1)(\log(W+1))^2)\) bit operations using schoolbook arithmetic, and therefore is polynomial in the PARTITION input length.
Together with the verifier from Section 1, this establishes \(\mathrm{NP}\)-completeness for the stated support representation. Hardness already holds with \(\tau=m\), so it does not depend on implicitly encoding additional voter types.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes \(\mathrm{NP}\)-completeness for the exact normalized rational-mass problem in USER_TASK, including the claimed restriction to positive dyadic masses and one candidate for party \(2\). I found no major or minor issues requiring repair.
The inequality
\[
\sum_\ell a_\ell\leq\sum_\ell 2\mu(\ell)=2
\]
is correct: each first-round allocation is bounded by twice its list’s mass. The second round awards at most the remaining seats, so every realized outcome allocates at most two seats.
Consequently, party \(1\)’s expected payoff of exactly \(2\) implies that party \(2\)’s expected payoff is zero. This implication remains valid when vacant seats are allowed; it does not assume that every strategy profile fills both seats.
The characterization is correct for arbitrary valid input masses, including zero-mass candidates.
When \(q<1/2\), every party \(2\) list has mass below \(1/2\), receives no first-round seats, and remains eligible because it is nonempty. Its remainder is its mass and is at most \(q\). Thus the number of remaining seats is indeed \(R=2-F\), independently of party \(2\)’s partition.
Against \(U_2\), the sole opposing list has remainder \(q\). Condition (1) correctly characterizes its receiving zero expected seats:
The uniform cutoff rule therefore supports the strict inequality used in (1). Equality of remainders cannot guarantee exclusion of party \(2\).
Condition (1) also guarantees both seats for party \(1\) against every opposing partition, since every opposing remainder is bounded by \(q\). This step correctly accounts for both first-round seats and the remaining second-round seats.
Both equilibrium implications are valid:
The boundary cases cause no failure. For \(R=0\), condition (1) is vacuous and party \(1\) already holds both first-round seats. For \(q=0\), opposing lists remain eligible, and the same strict-remainder comparison applies.
The certificate specifies a partition of \(C_1\) by assigning a list label to each candidate. The stated certificate size, \(O(m\log(m+1))\), is sufficient.
Lemma 1 removes the need to certify or enumerate best responses. The verifier only needs exact list masses, first-round allocations, eligibility, and the comparisons in (1). It does not need to compute arbitrary tie probabilities.
The arithmetic bound is sound. The product of the rational denominators has \(O(L)\) bits, and exact mass sums and comparisons can be performed using this common denominator. With
\[
B=L+m\lceil\log_2(m+1)\rceil+1,
\]
the bound \(O((m+\tau)B^2)\) bit operations is a valid conservative bound using schoolbook arithmetic.
The treatment of absent candidates as having mass zero agrees with USER_TASK. The verifier’s complexity depends on the actual support size \(\tau\), without enumerating possible voter types.
All hypotheses and inequalities are used correctly.
For \(2/3<p\leq3/4\), the integer \(F\) satisfies
\[
0\leq F\leq2p\leq3/2,
\]
so \(F\) is either zero or one.
If \(F=1\), the total remainder of party \(1\)’s lists is \(p-1/2\). Every remainder is nonnegative, including those of ineligible lists. The comparison
\[
p-\frac12\leq1-p=q
\]
holds throughout the stated range. Thus no eligible party \(1\) list can have remainder strictly greater than \(q\), and condition (1) fails for the one remaining seat.
If \(F=0\), both seats must come from two distinct eligible party \(1\) lists whose masses exceed \(q\). The displayed chain
\[
q<x\leq p-y<p-q
\]
is valid and establishes the necessary interval condition.
Conversely, the interval condition makes both complementary list masses strictly greater than \(q\) and strictly less than \(p-q\leq1/2\). Both lists are nonempty, receive no first-round seats, remain eligible, and strictly outrank \(U_2\). Lemma 1 then applies.
The endpoint \(p=3/4\) is handled correctly: strictness in the subset interval ensures that both constructed lists still have mass strictly below \(1/2\).
The source problem is stated precisely as PARTITION on positive binary integers. The historical claim that Ding and Lin’s Theorem 2 also reduces from PARTITION is accurate. [Ding and Lin, Theorem 2](https://cdn.aaai.org/ojs/8888/8888-13-12416-1-2-20201228.pdf).
For the stated nonempty source instances, \(W\geq1\), so all constructed quantities are defined.
The ceiling calculation gives \(0\leq t<3W\). The exclusion of \(t=0\) is correct: \(3KW\) is divisible by \(3\), whereas \(2D\), a power of two, is not. The lower bound on \(K\) correctly establishes
\[
0<t<3W<K.
\]
The total party \(1\) mass satisfies the claimed bounds:
\[
\frac23<p<\frac23+\frac WD
\leq\frac23+\frac1{16W}
\leq\frac{35}{48}<\frac34.
\]
The constants and inequality directions are correct. Therefore Lemma 2 applies, all candidate masses are positive, and the masses sum exactly to one. Their common denominator is a power of two, so they are dyadic.
The algebra converting the subset interval into (4) is correct. Its endpoints have midpoint \(KW/2\), and twice its half-width is \(t\), yielding
\[
K|2s-W|<t.
\]
Because \(2s-W\) is an integer and \(0<t<K\), this condition holds exactly when \(2s=W\).
This establishes both directions of the reduction. Odd values of \(W\) are handled automatically: no integer subset sum can satisfy \(2s=W\). Candidate indivisibility is preserved because each source integer corresponds to one candidate.
Minimality of \(D\) correctly gives \(16W^2\leq D<32W^2\). The quantities \(D\), \(K\), and all mass numerators consequently have \(O(\log(W+1))\) bits.
The stated output-length bound accounts for both masses and candidate identifiers. The construction-time bound is compatible with schoolbook arithmetic; positivity of the source integers also gives \(n\leq W\), so identifier-writing costs fit that bound.
Thus the reduction is polynomial in the binary PARTITION input length. Together with the polynomial certificate verifier, it establishes \(\mathrm{NP}\)-completeness in the stipulated support representation. The restriction \(\tau=m\) is explicitly realized.
Required repair or clarification: none. The conditional conclusion that no polynomial-time algorithm exists unless \(\mathrm{P}=\mathrm{NP}\) is justified.
⟨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.