Answer: \(\mathrm{NP}\)-complete
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a complete oriented and weighted major- ity graph G and a candidate A, it is NP-complete to check whether A is a fair possible winner for G.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(|C|=2^k\), a finite support \(S\) of complete rankings over \(C\), positive binary-rational masses \(\mu_t\) summing to \(1\), with a strict majority for one candidate in every pair, and a target \(A\), decide whether there is a balanced binary voting tree with one leaf per candidate in which \(A\) wins under the majority relation induced by \(\mu\).
Let \(C\) be a candidate set with \(m=|C|=2^k\), where \(k\) is a nonnegative integer, and let \(A\in C\).
A society is given by its support \(S\): the list of \(\tau\) distinct strict complete rankings with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau=|S|\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For distinct candidates, define \(x\succ_\mu y\) iff \(\sum_{t\in S:\,x\succ_t y}\mu_t>1/2\). Promise that exactly one direction holds for every pair.
A voting tree has exactly two children at each internal node and exactly one leaf per candidate. It is balanced when its maximum and minimum leaf depths differ by at most \(1\). Each internal node returns the majority winner between its children's returned candidates; the root returns the overall winner.
Is deciding whether some balanced voting tree returns \(A\) solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
The discrete weighted-majority-graph formulation was asserted to be \(\mathrm{NP}\)-complete by [Lang et al.](https://www.ijcai.org/Proceedings/07/Papers/221.pdf).
For deterministic tournament-graph input with a power-of-two number of players, balanced tournament fixing is \(\mathrm{NP}\)-complete ([Aziz et al.](https://cgi.cse.unsw.edu.au/~haziz/ko_journal.pdf)); this result uses graph input rather than a rational-support society.
The problem is \(\mathrm{NP}\)-complete, even when every mass is a dyadic rational and the support size satisfies \(\tau\leq m(m-1)+2\).
The essential step is a polynomial-size construction representing any tournament as the strict majority relation of such a society.
We first verify that the question’s definition of balance yields precisely the usual complete knockout bracket.
Let \(d\) be the minimum leaf depth, with the root at depth \(0\). Every leaf has depth \(d\) or \(d+1\). Because every internal node has exactly two children and there are no leaves before depth \(d\), there are exactly \(2^d\) nodes at depth \(d\).
Let \(a\) of those nodes be leaves. By the definition of minimum depth, \(1\leq a\leq 2^d\). Every remaining node has two leaf children: a deeper descendant would violate balance. Consequently,
\(m=a+2(2^d-a)=2^{d+1}-a\),
and therefore \(2^d\leq m<2^{d+1}\).
Since \(m=2^k\), these inequalities force \(d=k\). Substituting gives \(a=2^k\), so every leaf has depth \(k\).
Thus every admissible balanced tree is a perfect binary tree, and choosing such a tree amounts to assigning the candidates bijectively to the leaves of a fixed perfect bracket. Ordering its two children at any node does not affect its winner.
For \(m=1\), the answer is trivially yes. Hardness concerns the unbounded family of larger instances.
Let \(T\) be an arbitrary tournament on \(C\), where \(m\geq 2\). Write \(u\to v\) when \(u\) beats \(v\) in \(T\).
We construct a multiset of rankings first, then merge duplicates to obtain the required distinct support.
For each edge \(u\to v\), list the other candidates in any order as \(r_1,\ldots,r_{m-2}\), and introduce these two rankings:
\(P_{uv}: u\succ v\succ r_1\succ\cdots\succ r_{m-2}\),
\(Q_{uv}: r_{m-2}\succ\cdots\succ r_1\succ u\succ v\).
The contribution of a ranking multiset to the margin of \(x\) over \(y\) means the number of rankings placing \(x\) above \(y\), minus the number placing \(y\) above \(x\).
This pair of rankings contributes margin \(2\) for \(u\) over \(v\), and margin \(0\) for every other unordered pair. Indeed:
There are \(\binom{m}{2}\) edges, so the resulting multiset contains \(N=2\binom{m}{2}=m(m-1)\) rankings. Each edge’s own gadget contributes margin \(2\) in its prescribed direction; every other gadget contributes zero to that pair. Thus the multiset realizes every edge of \(T\) with margin \(2\).
To ensure dyadic masses, let \(D\) be the smallest power of two satisfying \(D\geq N\). Then \(N\leq D<2N\).
Both \(D\) and \(N\) are even, so \(h=(D-N)/2\) is a nonnegative integer. Choose any ranking \(\rho\), and add \(h\) copies of \(\rho\) and \(h\) copies of its complete reversal. These additions cancel on every pairwise margin. There are now exactly \(D\) rankings.
For each distinct ranking \(t\) appearing in this multiset, let \(b_t\) be its multiplicity and set \(\mu_t=b_t/D\). This produces a society with distinct support, positive dyadic masses, and total mass \(1\).
For every edge \(u\to v\), aggregation preserves the margin, giving
\(\sum_{t:\,u\succ_t v}\mu_t-\sum_{t:\,v\succ_t u}\mu_t=2/D\).
Because every ranking is strict and complete, these two sums add to \(1\). Hence
\(\sum_{t:\,u\succ_t v}\mu_t=1/2+1/D>1/2\).
Therefore the society satisfies the no-ties promise and has majority tournament exactly \(T\).
Before aggregation there are at most \(N+2\) distinct rankings, so \(\tau\leq m(m-1)+2\). Each ranking requires \(O(m\log m)\) bits, and each mass requires \(O(\log m)\) bits, since \(b_t\leq D<2m(m-1)\). Thus the total output length is \(O(m^3\log m)\). Constructing the rankings, padding them, and merging duplicates all take polynomial time.
We use the following established result: given a complete deterministic tournament on a power-of-two number of players and a distinguished player, deciding whether some assignment to a perfect knockout bracket makes that player win is \(\mathrm{NP}\)-complete. This is Theorem 1 of [Aziz et al., *Fixing Balanced Knockout and Double Elimination Tournaments*](https://cgi.cse.unsw.edu.au/~haziz/ko_journal.pdf). Their model explicitly assumes a power-of-two player count, and their hardness construction preserves that condition.
Take an instance \((T,A)\) of this problem. Keep its candidate set and distinguished candidate, and construct the society from Section 2.
All relevant hypotheses are preserved:
For any fixed leaf assignment, evaluation in the society and evaluation in \(T\) return the same candidate at every node. This follows by induction from the leaves: if the two child winners agree between evaluations, their pairwise winner also agrees because the majority tournament is exactly \(T\).
By Section 1, the admissible balanced voting trees are precisely the brackets used in the source problem. Consequently,
\(A\text{ wins some bracket in }T\quad\Longleftrightarrow\quad A\text{ wins some balanced voting tree in the constructed society}.\)
The construction is polynomial, so this proves \(\mathrm{NP}\)-hardness for rational-support society input. It does not require relying on the earlier weighted-majority-graph assertion.
A certificate is a permutation of the candidates specifying their positions in a fixed perfect bracket. Its length is \(O(m\log m)\).
From the input society, compute each pairwise majority by summing the corresponding rational masses exactly and comparing the sum with \(1/2\). Exact rational addition and comparison take polynomial time in the total input bit length: even using products of input denominators, their bit lengths are bounded by the sum of the denominator bit lengths, which is at most \(L\).
Then evaluate the bracket using its \(m-1\) internal comparisons and accept exactly when its root returns \(A\). Verification is polynomial in \(m,\tau,L\).
Together with the reduction, this establishes \(\mathrm{NP}\)-completeness. A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly. The construction preserves every tournament edge, uses polynomially many bits, and produces distinct support with positive dyadic masses. The cited hardness theorem applies to the precise bracket model required here. I found no mathematical gaps or false statements.
Let \(d\) be the minimum leaf depth. Balance implies that all leaves lie at depths \(d\) and \(d+1\). Since every node at depth less than \(d\) is internal and has exactly two children, there are exactly \(2^d\) nodes at depth \(d\).
If \(a\) of these are leaves, then \(1\leq a\leq 2^d\). Every remaining node must have two leaf children: an internal child would produce a leaf deeper than \(d+1\). Therefore the count
\[
m=a+2(2^d-a)=2^{d+1}-a
\]
is correct, as are the resulting inequalities \(2^d\leq m<2^{d+1}\).
For \(m=2^k\), these inequalities force \(d=k\), and substitution forces \(a=2^k\). Thus the admissible trees are exactly perfect binary brackets. Assigning candidates bijectively to a fixed bracket captures all possibilities; exchanging children does not change a pairwise winner.
The case \(m=1\), including \(k=0\), is explicitly and correctly handled.
Both displayed rankings are strict complete rankings, including when \(m=2\), where the list of remaining candidates is empty.
For the designated pair \(u,v\), both rankings place \(u\) above \(v\), producing margin \(2\). For a pair involving exactly one remaining candidate, the rankings give opposite comparisons. For a pair of remaining candidates, the reversed list also gives opposite comparisons. These cases exhaust all other unordered pairs.
Consequently, each gadget changes only its designated pair’s margin. Summing the gadgets over all \(\binom{m}{2}\) tournament edges gives exactly \(N=m(m-1)\) rankings and margin \(2\) in every prescribed direction. No transitivity of the tournament is assumed or needed.
For \(m\geq2\), \(N\geq2\) and \(N\) is even. The least power of two \(D\geq N\) satisfies \(N\leq D<2N\) and is also even. Hence \(h=(D-N)/2\) is a nonnegative integer.
A ranking and its complete reversal contribute opposite margins for every pair. Adding \(h\) copies of each therefore preserves all margins and increases the total multiplicity to \(D\). This also covers \(D=N\), when no padding is added.
Merging duplicate rankings preserves their total contribution. Every retained multiplicity \(b_t\) is positive, so the masses \(b_t/D\) are positive dyadic rationals and sum to \(1\).
The normalized margin is correctly computed as \(2/D\). Strict completeness makes the two opposing comparison masses sum to \(1\), so the designated winning mass is \(1/2+1/D>1/2\). Thus the construction satisfies the promise for every pair.
The original \(N\) ranking occurrences yield at most \(N\) distinct rankings; padding introduces at most two additional rankings. Therefore \(\tau\leq m(m-1)+2\) holds.
With candidates indexed by integers, a ranking uses \(O(m\log m)\) bits. Both numerator and denominator of each constructed mass use \(O(\log m)\) bits because \(b_t\leq D<2m(m-1)\). The stated total length \(O(m^3\log m)\) follows.
Explicitly creating the padded multiset remains polynomial because \(D=O(m^2)\). Comparing rankings and merging duplicates also require only polynomial time. There is no hidden exponential representation cost.
The cited source defines tournament fixing using deterministic pairwise outcomes, unrestricted draws, and a power-of-two player count. Its Theorem 1 states NP-completeness, and its reduction explicitly chooses the player count to be a power of two. These match the theorem statement used by the prover. [Aziz et al., *Fixing Balanced Knockout and Double Elimination Tournaments*](https://cgi.cse.unsw.edu.au/~haziz/ko_journal.pdf)
The reduction retains the candidates and distinguished candidate and realizes the source tournament exactly. Every listed target hypothesis is therefore satisfied. Reliance on the earlier weighted-majority-graph assertion is unnecessary.
For any fixed leaf assignment, the two evaluations agree at the leaves. If they agree on both child winners, they agree at the parent because the constructed majority relation equals the source tournament. The stated induction therefore establishes agreement at every node.
Combined with the verified characterization of balanced trees, this proves both directions of the winning-instance equivalence. The polynomial construction is a valid many-one reduction and establishes NP-hardness.
A leaf permutation has polynomial certificate length. Pairwise majority comparisons can be computed exactly in polynomial time: multiplying the input denominators produces a common denominator whose bit length is bounded by their total encoded bit length, and the corresponding numerator arithmetic also remains polynomial.
Evaluating the resulting bracket uses \(m-1\) comparisons. The singleton case remains trivial. Thus verification is polynomial in \(m,\tau,L\).
NP membership and the reduction establish the claimed NP-completeness, including the stated restricted family of dyadic societies. The implication that a polynomial-time algorithm would yield \(\mathrm{P}=\mathrm{NP}\) is valid.
No additional clarification or repair 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.