Answer: \(\mathrm{NP}\text{-complete}\), even with positive dyadic masses and \(\tau=O(m^2)\).
Proposition 20 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing [BP] is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(A\), a rational distribution \(\mu\) over complete ranking types, and a designated candidate \(x\), form the majority weak tournament \(W_\mu\); decide whether some orientation \(T\in[W_\mu]\) satisfies \(x\in BP(T)\).
Let \(A\) be a nonempty candidate set with \(m=|A|\), and let \(x\in A\). A society is given by its support: a list of \(\tau\) distinct strict complete ranking types \(r\), each with positive binary rational mass \(\mu_r\), with \(\sum_r\mu_r=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
For distinct \(a,b\in A\), put \(a\succeq_\mu b\) exactly when \(\sum_{r:a\succ_r b}\mu_r\geq 1/2\); include all reflexive pairs. This defines the majority weak tournament \(W_\mu\).
An orientation \(T\in[W_\mu]\) preserves every strict majority edge and independently replaces each majority tie by exactly one directed edge.
For a tournament \(T\), its tournament game is the two-player zero-sum game with row payoff \(G_T(a,b)=1\) if \(a\) beats \(b\), \(G_T(a,b)=-1\) if \(b\) beats \(a\), and \(G_T(a,a)=0\). The bipartisan set \(BP(T)\) is the support of its unique equilibrium mixed strategy.
Is deciding whether there exists \(T\in[W_\mu]\) with \(x\in BP(T)\) solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For an explicitly supplied weak tournament, deciding whether a designated candidate belongs to the bipartisan set of some orientation is NP-complete ([Brill, Freeman, and Conitzer, 2016](https://www.cs.cmu.edu/~conitzer/possibleAAAI16.pdf)).
No result for exactly the rational ranking-distribution input problem stated here was located in the search.
The stated ranking-distribution problem is \(\mathrm{NP}\text{-complete}\), even when every mass is dyadic and the support size satisfies \(\tau=O(m^2)\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) exists only if \(\mathrm{P}=\mathrm{NP}\).
For \(m=1\), the answer is trivially yes. The classification concerns unbounded \(m\).
We use the following supplied result: given a candidate set with some pairwise directions fixed and all remaining pairs independently orientable, deciding whether some resulting tournament has a designated candidate in its bipartisan set is \(\mathrm{NP}\text{-complete}\). This is Theorem 5 of [Brill, Freeman, and Conitzer (2016)](https://www.cs.cmu.edu/~conitzer/possibleAAAI16.pdf).
An unspecified pair in that problem corresponds to a majority tie in the present problem: either direction may be chosen, and the completed object must be a tournament.
The essential step is therefore to represent any such instance by a polynomial-size rational ranking distribution, preserving fixed directions and ties exactly.
Lemma. Let \(W\) specify, for each unordered pair of distinct candidates, either one fixed direction or a tie. There is a polynomial-time construction of a distribution over distinct strict complete rankings whose majority weak tournament is exactly \(W\). The distribution has positive dyadic masses and support size \(O(m^2)\).
Proof. Let \(E\) be the set of fixed directed edges and put \(k=|E|\).
For each edge \(a\to b\) in \(E\), list the remaining candidates in an arbitrary order \(c_1,\ldots,c_{m-2}\), and introduce these two rankings:
\(a\succ b\succ c_1\succ\cdots\succ c_{m-2}\),
\(c_{m-2}\succ\cdots\succ c_1\succ a\succ b\).
When \(m=2\), the lists of remaining candidates are empty.
For any multiset \(P\) of rankings, define its unnormalized pairwise margin by
\(M_P(u,v)=|\{r\in P:u\succ_r v\}|-|\{r\in P:v\succ_r u\}|\),
counting multiplicities.
The two rankings associated with \(a\to b\) contribute \(2\) to \(M_P(a,b)\). They contribute zero to every other unordered pair:
Thus, after adding the two rankings for every fixed edge, the resulting multiset \(P_0\), of size \(2k\), satisfies
\(M_{P_0}(u,v)=2\) if \(u\to v\in E\),
\(M_{P_0}(u,v)=-2\) if \(v\to u\in E\),
\(M_{P_0}(u,v)=0\) if \(\{u,v\}\) is tied in \(W\).
To obtain dyadic masses, let \(N\) be the least power of two satisfying \(N\geq 2(k+1)\). Then \(N\) is even and
\(2(k+1)\leq N<4(k+1)\).
Fix any complete ranking \(r_0\). Add \((N-2k)/2\) copies of the pair consisting of \(r_0\) and its reversal. Each such pair contributes zero to every pairwise margin. We now have a multiset \(P\) of exactly \(N\) rankings with the same margins as \(P_0\).
For every distinct ranking \(r\) occurring in \(P\), let \(n_r\) be its multiplicity and assign mass
\(\mu_r=n_r/N\).
These masses are positive, dyadic, and sum to one. Aggregating duplicate rankings satisfies the requirement that the input list contain distinct types.
For distinct \(u,v\), define the normalized margin
\(\Delta_\mu(u,v)=\sum_{r:u\succ_r v}\mu_r-\sum_{r:v\succ_r u}\mu_r=M_P(u,v)/N\).
Because every ranking is strict and complete, the two sums add to one. Therefore
\(\sum_{r:u\succ_r v}\mu_r=(1+\Delta_\mu(u,v))/2\).
It follows that a fixed edge \(u\to v\) has winning mass \(1/2+1/N\), its reverse has winning mass \(1/2-1/N\), and a tied pair has winning mass exactly \(1/2\). Hence \(W_\mu=W\), including its reflexive pairs.
Finally, \(\tau\leq N<4(k+1)=O(m^2)\), since \(k\leq\binom{m}{2}\). Each ranking needs \(O(m\log(m+1))\) bits after relabeling candidates by integers, and each mass needs \(O(\log(k+2))\) bits. The total output length is \(O(m^3\log(m+1))\). Generating, grouping, and encoding these rankings takes polynomial time. This proves the lemma. \(\square\)
Take an instance \((W,x)\) of the known problem and construct the distribution from the lemma, retaining the same candidate set and designated candidate.
Because \(W_\mu=W\), their allowed tournament orientations are identical:
\([W_\mu]=[W]\).
For each common orientation \(T\), the tournament game \(G_T\), and hence \(BP(T)\), is identical in the two instances. Consequently,
\(\exists T\in[W]\text{ with }x\in BP(T)\quad\Longleftrightarrow\quad\exists T\in[W_\mu]\text{ with }x\in BP(T)\).
The construction has polynomial output length and polynomial running time. It is therefore a polynomial-time many-one reduction, proving \(\mathrm{NP}\text{-hardness}\) for the exact input model in the question.
Conversely, the ranking-distribution input can be converted to its explicit majority weak tournament in polynomial time.
Write each input mass as \(\mu_r=p_r/q_r\), with positive integer denominator, and take the common denominator
\(D=\prod_r q_r\).
Its binary length is at most the sum of the binary lengths of the denominators, hence \(O(L)\). For each distinct pair \(a,b\), compute the integer
\(S_{ab}=\sum_{r:a\succ_r b}p_r(D/q_r)\).
Compare \(2S_{ab}\) with \(D\). A greater value fixes \(a\to b\), a smaller value fixes \(b\to a\), and equality identifies a tie. These are exact integer computations on numbers of polynomial bit length. Computing all comparisons takes time polynomial in \(m,\tau,L\).
The resulting instance \((W_\mu,x)\) has exactly the same answer as the original input. Since the explicit problem belongs to \(\mathrm{NP}\), its polynomial-size certificates and polynomial-time verifier also verify the ranking-distribution problem after this preprocessing.
Together with Section 3, this proves \(\mathrm{NP}\text{-completeness}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction preserves every fixed direction and every tie exactly, has polynomial output size, and satisfies the required distribution encoding. Membership in \(\mathrm{NP}\) also follows correctly. No substantive or minor mathematical gaps were found.
Section 1 states the source problem precisely: specified pairwise directions must remain fixed, and each unspecified pair independently receives one direction. The cited paper defines incomplete tournament games with unspecified off-diagonal payoffs \(\{-1,1\}\), restricts completions to symmetric games, and establishes \(\mathrm{NP}\)-completeness of possible bipartisan-set membership in Theorem 5. Thus an unspecified pair permits exactly the two orientations used in the prover’s formulation. The paper also identifies the bipartisan set with the support of the unique tournament-game equilibrium, matching the task’s definition. [Brill, Freeman, and Conitzer (2016), Sections 3.2 and 6](https://www.cs.cmu.edu/~conitzer/possibleAAAI16.pdf).
The theorem is therefore applied to the correct problem, with all relevant hypotheses satisfied.
For the gadget associated with \(a\to b\), both rankings place \(a\) above \(b\), giving margin \(2\). Every other pair falls into one of the three categories explicitly checked in the proof: two remaining candidates, \(a\) and a remaining candidate, or \(b\) and a remaining candidate. In each category the rankings give opposite comparisons, hence zero margin.
These categories exhaust all other unordered pairs. Summing the gadgets therefore gives precisely the stated margins \(2\), \(-2\), and \(0\). There is no interference between gadgets.
The choice of \(N\) satisfies
\[
2(k+1)\leq N<4(k+1).
\]
Since \(N\) and \(2k\) are even and \(N>2k\), the padding count \((N-2k)/2\) is a positive integer. A ranking and its reversal cancel on every pair, so padding leaves all margins unchanged and produces exactly \(N\) ranking occurrences.
Aggregating repeated rankings preserves the comparisons and total mass. Each resulting mass \(n_r/N\) is positive and dyadic, and the masses sum to one. Distinctness of the listed ranking types is explicitly enforced.
Strict completeness ensures that the two comparison masses for distinct \(u,v\) sum to one. Consequently the displayed identity
\[
\sum_{r:u\succ_r v}\mu_r=\frac{1+\Delta_\mu(u,v)}2
\]
is correct.
The constructed margins therefore yield winning mass \(1/2+1/N\) on a prescribed direction, \(1/2-1/N\) on its reverse, and exactly \(1/2\) for each tied pair. Under the task’s threshold convention, these are exactly the required strict edges and bidirectional ties. Reflexive pairs are included by definition.
There are at most \(N<4(k+1)\) distinct rankings, and \(k\leq\binom m2\), so \(\tau=O(m^2)\). The stated ranking and mass encoding bounds yield total output length \(O(m^3\log(m+1))\). Generating polynomially many rankings, grouping duplicates, and recording their multiplicities require polynomial time.
The edge cases also work as written. For \(k=0\), \(N=2\) and the reversal padding gives only ties. For \(m=2\), the empty remaining-candidate lists cause no difficulty. For \(m=1\), the sole ranking equals its reversal; aggregation gives one ranking of mass one, consistent with the separately stated trivial yes answer.
Exact equality \(W_\mu=W\) implies equality of the allowed orientation sets. For every such orientation, the candidate set, payoff matrix, designated candidate, and bipartisan set are unchanged. The displayed equivalence of yes instances follows directly.
Together with the verified polynomial construction, this establishes a polynomial-time many-one reduction. The dyadic-mass and support-size restrictions hold on every constructed instance.
For binary rational input, the product denominator \(D=\prod_r q_r\) has binary length \(O(L)\). The integers \(S_{ab}\) compute the comparison masses exactly, and comparing \(2S_{ab}\) with \(D\) correctly distinguishes the two strict directions from a tie. The arithmetic and the number of comparisons are polynomial in \(m,\tau,L\).
This preprocessing produces an equivalent explicit instance of polynomial size. Composing it with the source problem’s polynomial certificate verifier proves membership in \(\mathrm{NP}\); a separate equilibrium-certificate argument is unnecessary.
Actionable feedback: None is needed. The output resolves the assigned question and supports its stronger restricted-input claim.
⟨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.