Answer: Deterministic polynomial-time solvable in \(m,\tau,L\).
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet G = (V, E) be a tournament graph. Let A ∈V such that for all v ∈Nin(A), degout(v) ≤ degout(A). Then one can construct in polynomial time a binomial spanning arborescence of G rooted at A.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(2^r\) candidates, a target \(c^\star\), a fixed tie-breaking order, and a rational distribution \(\mu\) over strict rankings, orient each candidate pair toward its majority-preferred candidate, resolving ties by the order. If every candidate that defeats \(c^\star\) has outdegree at most \(c^\star\)’s outdegree, construct a balanced single-elimination bracket in which \(c^\star\) wins.
Let \(C\) be a candidate set of size \(m=2^r\), where \(r\) is a nonnegative integer, with designated candidate \(c^\star\) and a fixed strict total tie-breaking order.
A society is given by its support: the list of \(\tau\) distinct strict rankings with positive binary-rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For distinct candidates \(a,b\), write \(a\to b\) when the mass ranking \(a\) above \(b\) exceeds \(1/2\), or equals \(1/2\) and the tie-breaking order favors \(a\). Define \(d^+(a)=|\{b\in C\setminus\{a\}:a\to b\}|\).
Promise that \(d^+(b)\le d^+(c^\star)\) whenever \(b\to c^\star\). A bracket assigns each candidate exactly once to the leaves of a perfect binary tree of depth \(r\); each match uses \(\to\), and every candidate pair may be matched. The required output is a bracket won by \(c^\star\).
Is this promised bracket-construction problem solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Known discrete result: for any tournament graph satisfying this same outdegree promise, a winning balanced bracket can be constructed in polynomial time. [Verified source](https://theory.stanford.edu/~virgi/tournament3.pdf).
The promised bracket-construction problem is solvable in deterministic polynomial time in \(m,\tau,L\). The support representation allows us to compute the entire majority tournament exactly in polynomial time, after which the given discrete theorem applies.
Write the input rankings as \(\pi_1,\ldots,\pi_\tau\), with masses \(w_1,\ldots,w_\tau\). For distinct candidates \(a,b\), define
\(s(a,b)=\sum_{i:\,\pi_i\text{ ranks }a\text{ above }b}w_i\).
Because each ranking is strict and the masses sum to \(1\), we have \(s(a,b)+s(b,a)=1\). Consequently:
Thus \(G=(C,E)\), where \(E=\{(a,b):a\to b\}\), is a tournament graph. Its edge directions specify exactly the match outcomes in the original problem.
Use the standard binary encoding of rational numbers, writing \(w_i=p_i/q_i\), with positive integers \(p_i,q_i\) given in binary. Define
\(D=\prod_{i=1}^{\tau}q_i\) and \(W_i=p_i(D/q_i)\).
These are integers, and \(\sum_i W_i=D\). Moreover,
\(\log_2 D=\sum_i\log_2 q_i\le L\).
Hence \(D\), every \(W_i\), and every partial sum of the \(W_i\) have \(O(L)\) bits. Computing them requires only polynomially many bit operations, using ordinary integer multiplication and exact division.
For each ranking, record the position of every candidate. For each unordered candidate pair \(\{a,b\}\), compute
\(S(a,b)=\sum_{i:\,\pi_i\text{ ranks }a\text{ above }b}W_i\).
Determine the edge direction by comparing \(2S(a,b)\) with \(D\), applying the tie-breaking order when they are equal.
There are \(\binom m2\) pairs, and each requires at most \(\tau\) additions of \(O(L)\)-bit integers, together with position comparisons. Thus the complete tournament can be constructed in polynomial time in \(m,\tau,L\). This procedure iterates only over the supplied support; it never enumerates all \(m!\) possible rankings.
Once the edges are known, counting outgoing edges computes every \(d^+(a)\) in polynomial time.
The discrete theorem supplied in the question states: for a tournament on a power-of-two number of vertices, if a designated vertex has outdegree at least that of every vertex beating it, a balanced winning bracket can be constructed in polynomial time. This is the bracket formulation of Theorem 3 in [Vassilevska Williams, *Fixing a Tournament*](https://theory.stanford.edu/~virgi/tournament3.pdf).
All hypotheses hold here:
Apply that construction to obtain a perfect balanced bracket won by \(c^\star\). Since its graph edges are precisely the society’s match outcomes, the same bracket is valid for the original society.
For \(m=1\), return the single leaf labeled \(c^\star\).
The algorithm consists of exact polynomial-time tournament construction followed by the polynomial-time discrete bracket construction. The tournament has \(m\) vertices and \(\binom m2\) edges, so the second stage also has input size polynomial in \(m\). The output bracket has \(m\) leaves and \(m-1\) internal nodes.
Therefore the required bracket always exists on promised inputs and can be produced in deterministic polynomial time in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the promised bracket can be constructed in deterministic polynomial time in \(m,\tau,L\). I found no mathematical errors or gaps requiring clarification.
For every distinct pair \(a,b\), each strict ranking contributes its mass to exactly one of \(s(a,b)\) and \(s(b,a)\). Therefore \(s(a,b)+s(b,a)=1\). The prover correctly checks all three cases relative to \(1/2\). At equality, the fixed strict total order selects exactly one winner. Thus every unordered pair has exactly one directed edge, and that edge agrees with the original match rule.
Each \(q_i\) divides \(D=\prod_i q_i\), so \(W_i=p_i(D/q_i)\) is an integer. Normalization gives \(\sum_i W_i=D\).
The bound \(\log_2 D\le L\) is valid because the input contains the binary encodings of all denominators. The bit length of \(D\) is consequently at most \(L+1\). Positivity and normalization ensure that each \(W_i\), and each partial sum over distinct support entries, is at most \(D\). Hence the claimed \(O(L)\) bit bound is correct. Multiplication and exact division on these integers require polynomially many bit operations.
No reduction to lowest terms or least common denominator is necessary. The argument also covers dyadic masses as a special case.
The integer sum satisfies \(S(a,b)=D\,s(a,b)\). Since \(D>0\), comparing \(2S(a,b)\) with \(D\) gives precisely the comparison of \(s(a,b)\) with \(1/2\). Doubling increases bit length by at most one, and equality is handled by the stipulated tie-breaking order.
Position tables correctly support comparisons within each supplied ranking. There are \(\binom m2\) pairs, with at most \(\tau\) support contributions per pair. The resulting arithmetic and position comparisons take polynomial time in \(m,\tau,L\). The prover correctly distinguishes the supplied support size from the number of possible rankings. Counting outgoing edges then computes the promised degrees exactly.
I checked [Vassilevska Williams, *Fixing a Tournament*](https://theory.stanford.edu/~virgi/tournament3.pdf). Theorem 3 gives a polynomial-time construction of a binomial spanning arborescence rooted at a designated vertex whose outdegree is at least that of every vertex beating it. The paper defines these arborescences recursively and identifies them with balanced single-elimination brackets.
The prover’s bracket formulation is therefore faithful to the cited result on the power-of-two instances in this task. All applicable hypotheses are explicitly checked: the graph is a tournament, its size is \(m=2^r\), its designated vertex is \(c^\star\), and the degree inequality holds for every vertex beating \(c^\star\). No additional hypothesis that \(c^\star\) has globally maximum outdegree is required.
The graph and society have identical outcomes for every possible match. Consequently, the winning balanced bracket returned by the discrete construction remains winning under the society’s match rule. The theorem supplies a construction, rather than merely an existence statement, so its invocation meets the required output specification.
The case \(m=1\) is explicitly handled: the single leaf is the required depth-zero bracket.
The explicitly constructed tournament has polynomial size in \(m\), so composing its construction with the discrete polynomial-time algorithm preserves polynomial running time in \(m,\tau,L\). The bracket has \(m\) leaves and \(m-1\) internal nodes, consistent with polynomial output size.
No repair feedback is needed. The proof establishes the polynomial-time alternative for all promised inputs.
⟨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.