Answer: \(\mathrm{NP}\text{-complete}\), even for \(\delta=1\) and strict pairwise majorities.
Theorem 3 — class: hardness
Given candidates \(C\), a finite support of complete rankings \(t\) with binary-rational masses \(\mu_t\ge 0\) summing to \(1\), a target \(c^\star\), and a rational threshold \(\delta\), define \(P^\mu_{ab}=1\) if \(a\) has greater pairwise majority mass than \(b\), \(P^\mu_{ab}=0\) if it has less, and \(P^\mu_{ab}=\tfrac12\) on a tie. Is there a balanced binary agenda and seeding for which the paper's tournament-winning probability \(q(c^\star,KT;P^\mu)\ge\delta\)?
Let \(C\) contain \(m=2^h\) candidates, with \(h\ge1\), and let \(c^\star\in C\) and \(\delta\in[0,1]\cap\mathbb Q\).
A society is given by its support: a list of \(\tau\) distinct strict complete rankings of \(C\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For distinct \(a,b\in C\), put \(M_{ab}=\sum_{t:a\succ_t b}\mu_t\), and set \(P^\mu_{ab}=1\), \(0\), or \(\tfrac12\) according as \(M_{ab}>\tfrac12\), \(M_{ab}<\tfrac12\), or \(M_{ab}=\tfrac12\).
An agenda \(KT\) is a full binary tree whose \(m\) leaves all have depth \(h\), together with a bijection from candidates to leaves. At each internal node, the winners of its two child subtrees compete, and candidate \(a\) defeats candidate \(b\) with probability \(P^\mu_{ab}\); tied comparisons use independent fair coins. Let \(q(c^\star,KT;P^\mu)\) be the probability that \(c^\star\) reaches the root.
Is deciding whether some agenda \(KT\) satisfies \(q(c^\star,KT;P^\mu)\ge\delta\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Vu, Altman, and Shoham established NP-completeness for balanced schedule control with an explicitly supplied pairwise probability matrix taking values in \(\{0,\tfrac12,1\}\). [Source](https://www.ifaamas.org/Proceedings/aamas09/pdf/01_Full%20Papers/04_23_FP_0767.pdf)
Aziz et al. established NP-completeness even for explicitly supplied deterministic pairwise outcomes. [Source](https://ojs.aaai.org/index.php/AAAI/article/view/8805) No result explicitly treating this exact rational-support society formulation was located.
The problem is \(\mathrm{NP}\)-complete, even when \(\delta=1\) and every pairwise majority is strict. The reduction uses only polynomially many distinct rankings with positive dyadic masses.
For \(\delta=0\), every instance is trivially a yes-instance. The hardness result concerns the general input family, with an unbounded number of candidates.
We use the following established theorem.
Deterministic balanced tournament fixing is \(\mathrm{NP}\)-complete. An instance consists of a candidate set \(C\), with \(|C|=2^h\), a distinguished candidate \(c^\star\), and deterministic pairwise outcomes \(D_{ab}\in\{0,1\}\), satisfying \(D_{ab}+D_{ba}=1\) for distinct candidates. The question is whether some assignment of candidates to a complete balanced knockout tree makes \(c^\star\) its winner.
This is Theorem 1 of [Aziz et al., *Fixing a Balanced Knockout Tournament*](https://ojs.aaai.org/index.php/AAAI/article/view/8805/8664). Their definition explicitly requires a power-of-two candidate count and permits arbitrary assignments to the leaves. Thus its agendas have exactly the shape required here.
The missing step is to realize an arbitrary deterministic outcome matrix by a society whose rational-support encoding has polynomial size. We prove that step directly.
Lemma. Let \(C\) have \(m\ge2\) candidates, and let \(D\) specify deterministic outcomes for every distinct pair. One can construct, in polynomial time, a society of distinct strict complete rankings with positive dyadic masses such that \(P^\mu_{ab}=D_{ab}\) for all distinct \(a,b\). Its support size is \(O(m^2)\), and its total encoding length is \(O(m^3\log m)\), using candidate labels of \(O(\log m)\) bits.
Proof. For each unordered pair, write its desired orientation as \(a\to b\), meaning \(D_{ab}=1\). Choose any ordering \(r_1,\ldots,r_{m-2}\) of \(C\setminus\{a,b\}\), and introduce the two rankings
\[ a\succ b\succ r_1\succ\cdots\succ r_{m-2}, \]
\[ r_{m-2}\succ\cdots\succ r_1\succ a\succ b. \]
Here and below, an empty list is simply omitted.
For a multiset \(\mathcal V\) of rankings, define its count margin by
\[ \Delta_{\mathcal V}(x,y) = \#\{R\in\mathcal V:x\succ_R y\} - \#\{R\in\mathcal V:y\succ_R x\}. \]
The displayed pair contributes \(2\) to \(\Delta_{\mathcal V}(a,b)\) and zero to every other unordered-pair margin:
Introduce such a pair of rankings for every unordered candidate pair. The resulting multiset has
\[ B=2\binom m2=m(m-1) \]
rankings, counting multiplicities. Each desired orientation \(a\to b\) has margin exactly \(2\): its own pair contributes \(2\), and every other pair contributes zero.
To ensure dyadic masses, let
\[ N=2^{\lceil\log_2 B\rceil}. \]
Both \(B\) and \(N\) are even. Consequently, \((N-B)/2\) is a nonnegative integer. Choose a fixed complete ranking \(R\), and add \((N-B)/2\) copies of the pair consisting of \(R\) and its reversal. Each such pair contributes zero to every margin. We now have exactly \(N\) rankings, still with margin \(2\) for every desired orientation.
Merge repeated rankings. If distinct ranking \(R_t\) occurs \(k_t\) times, give it mass
\[ \mu_t=\frac{k_t}{N}. \]
These masses are positive dyadic rationals, and
\[ \sum_t\mu_t=\frac{\sum_t k_t}{N}=1. \]
For every desired orientation \(a\to b\), the normalized margin is
\[ M_{ab}-M_{ba}=\frac{2}{N}. \]
Because the rankings are strict and complete, \(M_{ab}+M_{ba}=1\). Solving these two equations gives
\[ M_{ab}=\frac12+\frac1N>\frac12. \]
Thus \(P^\mu_{ab}=1=D_{ab}\), and the reverse comparison has probability zero.
Finally, \(B\le N<2B\), so the number of generated rankings and the final support size are \(O(m^2)\). Each ranking requires \(O(m\log m)\) bits. Each numerator \(k_t\) and the denominator \(N\) require \(O(\log m)\) bits. Hence the total encoding length is \(O(m^3\log m)\). Generating, padding, and merging these polynomially many rankings all take polynomial time. This proves the lemma.
Take an instance \((C,D,c^\star)\) of deterministic balanced tournament fixing. Apply the lemma to produce its society, retain \(C\) and \(c^\star\), and set \(\delta=1\).
All hypotheses of the target problem hold:
For any agenda, the two instances therefore have the same winner. Formally, their winners agree at each leaf; if they agree at both children of an internal node, the identical deterministic comparison gives the same winner at that node. Induction up the tree proves agreement at the root.
In particular,
\[ q(c^\star,KT;P^\mu) = \begin{cases} 1,&\text{if }c^\star\text{ wins }KT\text{ under }D,\\ 0,&\text{otherwise}. \end{cases} \]
It follows that
\[ \exists KT:\ c^\star\text{ wins under }D \quad\Longleftrightarrow\quad \exists KT:\ q(c^\star,KT;P^\mu)\ge1. \]
This is a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness.
The same reduction works for any fixed rational threshold \(\delta\in(0,1]\), since these constructed instances have winning probabilities only in \(\{0,1\}\).
We show that a proposed agenda can be verified in polynomial bit complexity, including when majority comparisons tie.
Precompute each candidate’s position in each ranking. For every distinct pair, sum the masses of rankings placing the first candidate above the second, and compare that sum exactly with \(\tfrac12\).
There are \(O(\tau m^2)\) summand inspections. Under the ordinary binary encoding of rational numerators and denominators, these calculations have polynomial bit complexity in \(L\): the product of all input denominators is a common denominator whose bit length is at most the sum of their bit lengths. Thus every entry of \(P^\mu\) can be computed exactly in polynomial time.
A full binary tree whose leaves all have depth \(h\) must be the perfect binary tree of depth \(h\): every node at smaller depth must have two children, and no node at depth \(h\) can have children.
Consequently, a certificate is just a permutation assigning the \(m\) candidates to the leaves of one canonical perfect tree. Its length is \(O(m\log m)\).
For a tree node \(v\), let \(C_v\) be its descendant candidates, let \(s_v=|C_v|\), and let \(Q_v(a)\) denote the probability that \(a\in C_v\) wins its subtree.
A subtree with \(s_v\) leaves has \(s_v-1\) matches. Preassign an independent fair bit to each internal node, using that bit if its comparison ties and otherwise ignoring it. These bits reproduce the stipulated independent tie-breaking. Therefore
\[ Q_v(a)=\frac{A_v(a)}{2^{s_v-1}} \]
for an integer \(A_v(a)\) satisfying \(0\le A_v(a)\le2^{s_v-1}\).
We compute these numerators directly. At a leaf occupied by \(a\), set \(A_v(a)=1\). At an internal node with children \(u,w\), define \(r_{ab}=2P^\mu_{ab}\in\{0,1,2\}\). For \(a\in C_u\), independence of the two child subtrees and the current comparison gives
\[ Q_v(a) = Q_u(a)\sum_{b\in C_w}Q_w(b)P^\mu_{ab}. \]
Since \(s_v=s_u+s_w\), substituting the common-denominator representations yields
\[ A_v(a) = A_u(a)\sum_{b\in C_w}A_w(b)r_{ab}. \]
For \(a\in C_w\), use the same formula with the children interchanged.
Every stored numerator has at most \(m\) bits. At each internal node the computation uses \(O(|C_u||C_w|)\) arithmetic operations. Each unordered candidate pair lies in opposite children at exactly one node, its lowest common ancestor. Hence the total number of arithmetic operations is \(O(m^2)\), all on polynomially bounded integers.
Finally, write \(\delta=d/e\) with \(e>0\). At the root \(\rho\), verify the threshold by the exact integer comparison
\[ eA_\rho(c^\star)\ge d\,2^{m-1}. \]
This comparison also has polynomial bit complexity in \(m+L\). The decision problem therefore belongs to \(\mathrm{NP}\).
The rational-support formulation is \(\mathrm{NP}\)-complete. The explicit majority realization transfers the deterministic hardness theorem without increasing the input size superpolynomially, and exact agenda verification establishes membership in \(\mathrm{NP}\). Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output proves the claimed result: the rational-support problem is \(\mathrm{NP}\)-complete, even with \(\delta=1\) and strict majority comparisons. I found no major or minor mathematical issues.
Theorem 1 of [Aziz et al., *Fixing a Balanced Knockout Tournament*](https://ojs.aaai.org/index.php/AAAI/article/view/8805/8664) establishes \(\mathrm{NP}\)-completeness of deterministic tournament fixing. Its definitions require a power-of-two player count, complementary deterministic pairwise outcomes, and arbitrary assignments to a balanced knockout tree. The paper explicitly identifies existence of a winning draw with existence of a winning seeding.
These are the hypotheses stated in Section 1. The restriction \(h\ge1\) causes no difficulty: the cited hardness construction uses more than one player. The source theorem therefore applies to the source instances used here.
For the designated pair \(a\to b\), both rankings place \(a\) above \(b\), so their combined contribution to its count margin is \(2\).
For a comparison involving one designated candidate and one remaining candidate, the two rankings have opposite orientations, so their contributions cancel. Comparisons between two remaining candidates also cancel because their ordering is reversed.
This covers every comparison other than the designated pair. Consequently, adding the construction for every unordered pair produces margin \(2\) in each desired orientation. Contributions from gadgets for other pairs are zero.
The lemma uses the complementary deterministic-outcome hypothesis stated in Section 1; that hypothesis ensures each unordered pair has exactly one desired orientation.
The initial number of rankings is correctly computed as \(B=m(m-1)\). For \(m\ge2\), \(B\) is positive and even. The chosen \(N=2^{\lceil\log_2 B\rceil}\) is also even, so \((N-B)/2\) is a nonnegative integer.
A ranking and its reversal cancel on every comparison. Thus padding to exactly \(N\) rankings preserves all margins.
Merging duplicate rankings and assigning mass \(k_t/N\) preserves the multiset’s normalized comparison counts. Every resulting mass is positive and dyadic, the rankings are distinct, and their masses sum to one.
The normalized equations
\[
M_{ab}-M_{ba}=\frac{2}{N},
\qquad
M_{ab}+M_{ba}=1
\]
correctly yield \(M_{ab}=\frac12+\frac1N\). Hence every required majority is strict and realizes the desired deterministic outcome.
The edge case \(m=2\) is covered: the remaining list is empty, \(B=N=2\), and merging the two identical rankings gives a single ranking of mass \(1\).
The bound \(B\le N<2B\) is correct, including when \(B\) is already a power of two. Therefore the number of generated rankings and the final support size are both \(O(m^2)\).
Each explicit ranking requires \(O(m\log m)\) bits under the stated candidate labeling. The multiplicities and denominator require \(O(\log m)\) bits each. The resulting total bound \(O(m^3\log m)\) is valid.
Generating the rankings, adding padding, and merging duplicates all operate on polynomially many strings of polynomial length. The claimed polynomial construction time follows.
The reduction retains the candidate set, distinguished candidate, and allowable agendas, and sets \(\delta=1\). The constructed comparison matrix equals the source deterministic matrix entry by entry.
The stated induction over the agenda correctly proves equality of the winner at every node. Therefore the target winning probability is \(1\) exactly when the source distinguished candidate wins, and otherwise it is \(0\).
The displayed equivalence establishes a polynomial-time many-one reduction. It proves hardness on instances with strict majorities and \(\delta=1\).
The extension to any fixed rational \(\delta\in(0,1]\) is also correct because the constructed probabilities belong to \(\{0,1\}\). The separate statement that \(\delta=0\) always gives a yes-instance is valid.
Precomputed ranking positions permit the claimed \(O(\tau m^2)\) summand inspections. Under the explicitly stated ordinary binary numerator-denominator encoding, a product of input denominators has polynomial bit length in \(L\). Exact mass sums and comparisons with \(\frac12\) therefore have polynomial bit complexity.
A full binary tree with all leaves at depth \(h\) is necessarily perfect. Thus assigning candidates to the leaves of a canonical perfect tree represents every permissible agenda, and a permutation certificate has length \(O(m\log m)\).
Preassigning independent fair bits to internal nodes reproduces the specified tie-breaking distribution. A subtree with \(s_v\) leaves has \(s_v-1\) internal nodes, so each subtree winning probability has the stated representation with denominator \(2^{s_v-1}\).
The child subtrees use disjoint independent bits. The probability recurrence therefore applies. Its denominator calculation is correct:
\[
(s_u-1)+(s_w-1)+1=s_v-1.
\]
Consequently, the displayed recurrence for \(A_v(a)\) contains no missing factor.
Since \(0\le A_v(a)\le2^{s_v-1}\), each stored numerator needs at most \(s_v\le m\) bits. The sums and products in the recurrence also have polynomial bit length.
Every unordered candidate pair occurs across the two children of exactly its lowest common ancestor. Counting both candidate directions changes only a constant factor, so the total arithmetic-operation count is \(O(m^2)\).
Finally, with \(e>0\), the threshold comparison \(eA_\rho(c^\star)\ge d\,2^{m-1}\) is exactly equivalent to the desired probability inequality and has polynomial bit complexity.
The reduction and verification algorithm together establish the claimed \(\mathrm{NP}\)-completeness. No additional clarification or repair is required.
⟨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.