Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe possible BP winner problem (in tournament games) is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a partial tournament \(P\) on candidates \(C\) and a target \(c^\star\), does there exist a rational distribution \(\mu\) over strict rankings of \(C\) such that every specified pairwise direction in \(P\) agrees with its margin under \(\mu\), every unspecified pair has nonzero margin, and \(c^\star\in\mathrm{BP}(T_\mu)\), where \(T_\mu\) orients each pair by the sign of its margin?
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(c^\star\in C\). The input is a partial tournament \(P\): each unordered pair of distinct candidates has either one specified direction or no specified direction; missing directions are unrestricted, not ties.
A society is represented by its support: a list of \(\tau\) distinct strict rankings of \(C\) with positive binary-rational masses summing to \(1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings.
For a society \(\mu\), define \(\Delta_\mu(a,b)=\sum_{r:a\succ_r b}\mu(r)-\sum_{r:b\succ_r a}\mu(r)\). Require \(\Delta_\mu(a,b)>0\) for every specified edge \(a\to b\) and nonzero margins for all unspecified pairs. Define \(T_\mu\) by \(a\to b\) exactly when \(\Delta_\mu(a,b)>0\).
For a tournament \(T\), its tournament game is the symmetric zero-sum game with both action sets \(C\), row payoff \(1\) when the row candidate beats the column candidate, \(-1\) when it loses, and \(0\) on the diagonal. The bipartisan set \(\mathrm{BP}(T)\) comprises candidates played with positive probability in some Nash equilibrium.
The distribution is existentially chosen; neither its support nor its masses are supplied or restricted by the input. Let \(L\) denote the input bit length. State decision running times in \(m,L\), and any bounds or running times involving explicitly represented societies in \(m,\tau,L_\mu\), where \(L_\mu\) is their encoding length.
Is deciding whether such a rational society \(\mu\) exists with \(c^\star\in\mathrm{BP}(T_\mu)\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For discrete partial tournaments, deciding whether some completion has the target in its bipartisan set is \(\mathrm{NP}\)-complete ([Brill, Freeman, and Conitzer](https://arxiv.org/html/2104.14317v1)).
No result explicitly treating the rational-distribution formulation above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. Consequently, it is polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\).
The key fact is that every tournament admits a rational society with polynomial support size and encoding length. Thus the existential society formulation has exactly the same yes-instances as the discrete completion problem.
For \(\,m=1\,\), the answer is trivially yes. The construction below handles every \(\,m\geq 2\,\).
Fix a tournament \(\,T\,\) on \(\,C\,\), and write \(\,q=\binom{m}{2}\,\). Identify candidates with indices so that each ranking has encoding length \(\,O(m\log(m+1))\,\).
For each edge \(\,a\to b\,\) of \(\,T\,\), list the remaining candidates as \(\,x_1,\ldots,x_{m-2}\,\), and introduce the two rankings
\[ a\succ b\succ x_1\succ\cdots\succ x_{m-2}, \qquad x_{m-2}\succ\cdots\succ x_1\succ a\succ b. \]
Here and below, these rankings are initially a multiset; repeated rankings will be merged.
Consider their combined, unnormalized pairwise margins.
Therefore this pair of rankings contributes \(\,2\,\) precisely on the chosen edge and \(\,0\,\) on every other unordered pair.
Applying this construction to all \(\,q\,\) edges gives \(\,2q\,\) rankings. Their unnormalized margin is \(\,2\,\) on every edge of \(\,T\,\).
To obtain dyadic masses, let \(\,N\,\) be the smallest power of two satisfying \(\,N\geq 2q\,\). Both \(\,N\,\) and \(\,2q\,\) are even. Add \(\,(N-2q)/2\,\) copies of an arbitrary ranking together with the same number of copies of its reverse. Every added ranking–reverse pair contributes zero to every margin.
Give each of the resulting \(\,N\,\) ranking occurrences mass \(\,1/N\,\). Merge identical rankings: if ranking \(\,r\,\) occurs \(\,f_r\,\) times, give it mass \(\,\mu(r)=f_r/N\,\). These masses are positive dyadic rationals and sum to \(\,1\,\). Merging preserves all margins, so
\[ \Delta_\mu(a,b)=\frac{2}{N}>0 \quad\text{for every edge }a\to b\text{ of }T. \]
Hence \(\,T_\mu=T\,\), and no pair has zero margin.
The final support consists of at most the original \(\,2q\,\) rankings and two padding rankings. Thus
\[ \tau\leq 2q+2=m(m-1)+2. \]
Because \(\,2q\leq N<4q\,\), each mass needs \(\,O(\log(m+1))\,\) bits. Under the usual explicit encoding,
\[ L_\mu=O\!\left(\tau m\log(m+1)\right) =O\!\left(m^3\log(m+1)\right). \]
The construction takes polynomial time in \(\,m\,\). For example, generating the rankings, sorting their binary encodings, and merging repetitions takes \(\,O(m^3\log^2(m+1))\,\) bit operations.
This proves realizability even under the stronger interpretation that “binary-rational” requires dyadic masses.
Let \(\,\mathcal C(P)\,\) denote the tournaments extending every specified edge of \(\,P\,\). We prove
\[ \exists\mu\text{ satisfying the input constraints with } c^\star\in\mathrm{BP}(T_\mu) \quad\Longleftrightarrow\quad \exists T\in\mathcal C(P)\text{ with } c^\star\in\mathrm{BP}(T). \]
For the forward direction, antisymmetry gives \(\,\Delta_\mu(b,a)=-\Delta_\mu(a,b)\,\). Every pair has nonzero margin, so exactly one direction is selected. Every specified edge has positive margin in its specified direction. Consequently, \(\,T_\mu\in\mathcal C(P)\,\), and the assumed bipartisan membership supplies the required completion.
For the reverse direction, take a completion \(\,T\in\mathcal C(P)\,\) with \(\,c^\star\in\mathrm{BP}(T)\,\). Section 1 constructs a society with \(\,T_\mu=T\,\). Its margins satisfy every specified edge and are nonzero on every unspecified pair. It is therefore an admissible witness.
The equivalence preserves the entire input \(\,(P,c^\star)\,\).
For completeness, bipartisan membership can be checked exactly by linear programming.
Let \(\,A\,\) be the tournament payoff matrix. It satisfies \(\,A^{\mathsf T}=-A\,\). Define
\[ K=\left\{p\in\mathbb R^m: p\geq 0,\quad \mathbf 1^{\mathsf T}p=1,\quad Ap\leq 0\right\}. \]
The finite zero-sum minimax theorem applies because both action sets are finite and nonempty. The game has value zero: for every probability vector \(\,p\,\), skew-symmetry gives \(\,p^{\mathsf T}Ap=0\,\), so
\[ \max_p\min_q p^{\mathsf T}Aq\leq 0, \qquad \min_q\max_p p^{\mathsf T}Aq\geq 0. \]
Minimax equates these quantities. In particular, an optimal column strategy exists and satisfies \(\,Ap\leq 0\,\), establishing that \(\,K\,\) is nonempty.
If \(\,p,q\in K\,\), then \(\,p^{\mathsf T}A=-(Ap)^{\mathsf T}\geq 0\,\), while \(\,Aq\leq 0\,\). Therefore
\[ 0\leq p^{\mathsf T}Aq\leq 0. \]
Every row deviation against \(\,q\,\) yields payoff at most zero, and every column deviation against \(\,p\,\) yields row payoff at least zero. Thus \(\,(p,q)\,\) is a Nash equilibrium.
Conversely, suppose \(\,(p,q)\,\) is a Nash equilibrium with row payoff \(\,u\,\). The row player can deviate to \(\,q\,\), obtaining \(\,q^{\mathsf T}Aq=0\,\), so \(\,u\geq 0\,\). The column player can deviate to \(\,p\,\), giving row payoff \(\,p^{\mathsf T}Ap=0\,\), so \(\,u\leq 0\,\). Hence \(\,u=0\,\). The pure-deviation inequalities imply \(\,Aq\leq 0\,\) and \(\,p^{\mathsf T}A\geq 0\,\), the latter being equivalent to \(\,Ap\leq 0\,\). Thus both strategies lie in \(\,K\,\).
It follows that
\[ c^\star\in\mathrm{BP}(T) \quad\Longleftrightarrow\quad \max_{p\in K}p_{c^\star}>0. \]
This is a bounded rational linear program with \(\,m\,\) variables, \(\,2m\,\) inequalities, one equality, and coefficients in \(\,\{-1,0,1\}\,\). Polynomial-time exact rational linear programming therefore decides the strict positivity of its optimum in \(\,\operatorname{poly}(m)\,\) bit operations; no numerical tolerance is needed.
Theorem 8 of [Brill, Freeman, and Conitzer](https://arxiv.org/html/2104.14317v1) states that possible bipartisan membership for an incomplete tournament is \(\mathrm{NP}\)-complete. Their unspecified pairs permit either direction and exclude ties, matching the present input model.
By Section 2, the identity map \(\,(P,c^\star)\mapsto(P,c^\star)\,\) is a polynomial-time many-one reduction to the rational-society problem. This proves \(\mathrm{NP}\)-hardness.
For membership in \(\mathrm{NP}\), guess the directions of all unspecified pairs, check that the resulting tournament extends \(\,P\,\), and use Section 3 to check bipartisan membership. Verification takes \(\,\operatorname{poly}(m,L)\,\) time. Section 2 proves that this certificate is equivalent to an admissible rational society. Hence the problem is \(\mathrm{NP}\)-complete.
If \(\,k\,\) pairs are unspecified, enumerating their orientations gives a deterministic decision bound of
\[ 2^k\operatorname{poly}(m,L), \qquad k\leq\binom{m}{2}. \]
For an explicitly represented society, computing all margins requires \(\,O(\tau m^2)\,\) exact rational additions after forming the rankings’ position tables. A common denominator can be chosen as the product of the encoded denominators; its bit length is \(\,O(L_\mu)\,\). Using elementary integer arithmetic gives the conservative bit-time bound
\[ O\!\left(\tau m^2(L_\mu+1)^2\right)+\operatorname{poly}(m) \]
for computing the induced tournament and checking target membership, provided all margins are nonzero. Checking compatibility with an additional partial tournament costs \(\,O(L+m^2)\,\).
Thus evaluation of a supplied society is polynomial in its explicit size, while existential choice of the society is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes \(\mathrm{NP}\)-completeness for the rational-society formulation, including when “binary-rational” means dyadic rational. I found no major or minor issues requiring correction.
For each edge \(a\to b\), the two displayed rankings both place \(a\) above \(b\), giving unnormalized margin \(2\). Every other pair falls into one of the two cancellation cases listed by the prover: either both candidates are among the remaining candidates, or exactly one is. Their relative orders reverse between the two rankings in both cases.
Consequently, summing the gadgets over all \(q=\binom{m}{2}\) edges gives margin \(2\) in each tournament direction. No unwanted contribution remains.
This also handles \(m=2\): the list of remaining candidates is empty, the two gadget rankings coincide, and the explicitly permitted merging produces a valid support.
For \(m\geq2\), \(2q\geq2\), so the chosen power of two \(N\) is even. Thus \((N-2q)/2\) is a nonnegative integer. A ranking and its reverse cancel on every pair, so padding does not change the unnormalized margins.
After normalization and merging, every represented ranking has positive mass \(f_r/N\), the masses sum to \(1\), and they are dyadic. All tournament margins equal \(2/N>0\). The resulting support therefore consists of distinct rankings and satisfies the society definition exactly.
The singleton case is immediate under the stated definitions: there is only one ranking and one game action, and there are no pairwise constraints.
Padding introduces at most two additional distinct rankings, so \(\tau\leq2q+2=m(m-1)+2\).
The smallest-power-of-two choice gives \(2q\leq N<4q\). Both \(N\) and every multiplicity \(f_r\leq N\) consequently require \(O(\log(m+1))\) bits. Combining this with the ranking encoding gives the claimed bound \(L_\mu=O(\tau m\log(m+1))=O(m^3\log(m+1))\).
There are \(O(m^2)\) ranking occurrences, each encoded using \(O(m\log(m+1))\) bits. Generating them and sorting by comparison supports the stated conservative construction bound \(O(m^3\log^2(m+1))\).
In the forward direction, every specified pair has positive margin in its specified direction, and every unspecified pair has nonzero margin. Antisymmetry therefore selects exactly one direction for every distinct pair and produces a completion of \(P\). The assumed bipartisan membership transfers directly.
In the reverse direction, the realization construction applies to any chosen completion and preserves its entire tournament. Hence it preserves bipartisan membership and satisfies all specified and unspecified margin constraints.
Neither implication introduces an additional restriction on the input or the existentially chosen society.
The finite zero-sum minimax theorem applies to the finite, nonempty action sets. For every probability vector, skew-symmetry gives zero payoff against itself. The two displayed bounds on the maximin and minimax values are correct, and their equality establishes game value zero and nonemptiness of \(K\).
For \(p,q\in K\), the identity \(p^{\mathsf T}A=-(Ap)^{\mathsf T}\) gives the claimed nonnegative row guarantee, while \(Aq\leq0\) gives the nonpositive payoff against every row deviation. Thus the equilibrium argument is valid.
Conversely, both deviations to the opponent’s strategy are available because the action sets coincide. They force equilibrium payoff zero. The pure-deviation inequalities then put both equilibrium strategies in \(K\).
This proves the characterization for candidates played by either player in some equilibrium, as required by the task.
The feasible region \(K\) is nonempty, closed, and contained in the probability simplex, so the maximum used in the characterization exists.
The LP has the stated numbers of variables and constraints, with constant-size rational coefficients. Standard exact rational linear programming applies and decides whether the optimum is strictly positive in polynomial bit time. There is no unsupported inference from approximate numerical output to strict positivity.
Theorem 8 states that possible bipartisan-set winner determination in tournament games is \(\mathrm{NP}\)-complete. The paper’s definitions of incomplete tournament games allow the two orientations for an unspecified pair, exclude ties, and require symmetric completions. These are precisely the completion choices used here. [Brill, Freeman, and Conitzer, Sections 3.2 and 6](https://arxiv.org/html/2104.14317v1)
Therefore, the identity transformation of \((P,c^\star)\), together with the proved equivalence, is a valid polynomial-time many-one reduction.
A completion requires only one guessed direction per unspecified pair. Checking compatibility and applying the LP membership test takes \(\operatorname{poly}(m,L)\) time under the usual explicit input encoding. A certificate need not itself be a society: the established equivalence makes a completion certificate sufficient.
Enumerating all \(2^k\) completions gives the stated deterministic decision bound.
For an explicitly represented society, the margin calculation uses \(O(\tau m^2)\) rational additions. The product of the encoded denominators has bit length \(O(L_\mu)\), and elementary exact arithmetic supports the conservative bound given. The additional compatibility check is consistent with the stated explicit representation. These bounds correctly use support size \(\tau\), without treating all \(m!\) rankings as supplied input.
No additional clarification or mathematical repair is needed. The final claim of \(\mathrm{NP}\)-completeness, and its consequence concerning \(\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.