d4-conf-aaai-2026-4206 (d4-conf-aaai-2026-4206)

Given a balanced bracket with \(N=2^h\) leaves, a finite set of entrant types with a complete deterministic match-outcome relation, rational masses \(\mu_t\) summing to \(1\), and a target type \(f\) with \(\mu_f\ge 1/N\), decide whether the masses can be assigned to leaf slots of size \(1/N\) and paired at each match so that the entire root mass has type \(f\). Parameterize by \(\lambda=|\{t\ne f:\ f\text{ beats }t\}|\), the number of supported opponent types the target type beats.

A society is given by its support: a list \(T\) of \(\tau\) entrant types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Input also includes a complete balanced binary bracket with \(N=2^h\) leaves, \(h\ge1\), an outcome table specifying exactly one winner for each pair of distinct types, and \(f\in T\) with \(\mu_f\ge1/N\). A match between two copies of the same type produces that type.
Assign divisible mass to leaves, each receiving total mass \(1/N\), while preserving each type's total initial mass.
At each internal node, choose any nonnegative real coupling \(q_{st}\) between its two children's surviving type masses: row sums equal the left child's masses and column sums equal the right child's masses. Each paired amount \(q_{st}\) contributes that amount of the winning type to the parent; the losing amount is eliminated. Thus every node has total surviving mass \(1/N\).
Feasibility means that the root has mass \(1/N\) of type \(f\) and zero mass of every other type. Set \(\lambda=|\{t\in T\setminus\{f\}:f\text{ beats }t\}|\).
The bracket is represented explicitly. Let \(m=\tau\) denote the outcome-table dimension and \(L\) the total input bit length; state running times in \(m,\tau,N,L\) and \(\lambda\).

Is this continuous tournament-fixing feasibility problem in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard?

Discrete balanced tournament fixing is [NP-complete](https://ojs.aaai.org/index.php/AAAI/article/view/8805). With \(n\) players and favorite out-degree \(\ell\), it admits time \(2^{2^\ell}n^{O(1)}\), but ETH excludes time \(2^{2^{\ell/c}}n^{O(1)}\) for every constant \(c>1\) ([source](https://arxiv.org/html/2601.08530v1)).
No result settling exactly the divisible-mass problem defined above was located.

Result. The problem as defined is in \(\mathsf{P}\). It admits an exact rational linear programming formulation of polynomial size, with running time \((L+Nm\tau)^{O(1)}=(L+N\tau^2)^{O(1)}\), uniformly for every value of \(\lambda\).

Linear programming formulation. Let \(V\) be the bracket’s node set, \(A\) its leaf set, \(I\) its internal-node set, and \(\rho\) its root. Thus \(|A|=N\), \(|I|=N-1\), and \(|V|=2N-1\). For each \(v\in I\), designate its children by \(a(v)\) and \(b(v)\).

Define the fixed winner function \(w:T\times T\to T\) using the outcome table, with \(w(t,t)=t\).

Introduce nonnegative real variables:

• \(x_{v,t}\) for each \(v\in V\) and \(t\in T\), representing type \(t\)’s surviving mass at node \(v\);
• \(q_{v,s,t}\) for each \(v\in I\) and \(s,t\in T\), representing the amount paired between left-child type \(s\) and right-child type \(t\).

Impose the following linear equalities.

• Each leaf receives its prescribed total mass:

\(\displaystyle \sum_{t\in T}x_{a,t}=\frac1N \qquad(a\in A).\)

• Leaf assignments preserve each type’s initial mass:

\(\displaystyle \sum_{a\in A}x_{a,t}=\mu_t \qquad(t\in T).\)

• Each coupling has the required child marginals:

\(\displaystyle \sum_{t\in T}q_{v,s,t}=x_{a(v),s}\qquad(v\in I,\ s\in T),\)

\(\displaystyle \sum_{s\in T}q_{v,s,t}=x_{b(v),t}\qquad(v\in I,\ t\in T).\)

• Each paired amount contributes exactly its winner’s mass:

\(\displaystyle x_{v,r}=\sum_{\substack{s,t\in T\\w(s,t)=r}}q_{v,s,t}\qquad(v\in I,\ r\in T).\)

• The root consists entirely of the favorite:

\(\displaystyle x_{\rho,f}=\frac1N,\qquad x_{\rho,t}=0\qquad(t\in T\setminus\{f\}).\)

The winner function is input data. Consequently, the sums in constraint 4 have fixed index sets: they introduce no nonlinear conditions.

Proof of exact equivalence. First suppose a feasible tournament execution exists. Assign \(x_{v,t}\) its actual surviving masses and \(q_{v,s,t}\) its actual chosen couplings. Leaf capacities and initial-mass preservation give constraints 1 and 2. The coupling rules give constraint 3. The prescribed match outcomes give constraint 4, including diagonal pairings between copies of the same type. The successful root gives constraint 5. Hence the linear program is feasible.

Conversely, suppose the linear program has a feasible real solution. Assign mass \(x_{a,t}\) of type \(t\) to leaf \(a\). Constraints 1 and 2 make this a valid initial assignment.

Process internal nodes from the leaves toward the root. Inductively, suppose the children of \(v\) have surviving masses \(x_{a(v),s}\) and \(x_{b(v),t}\). Nonnegativity and constraint 3 make \(q_v\) an admissible coupling of these two mass vectors. Apply that coupling. Constraint 4 says that the resulting surviving mass of every type \(r\) is exactly \(x_{v,r}\), establishing the induction step.

For completeness, every internal node also has the required total surviving mass. Since every ordered pair has exactly one winner, constraint 4 and the row-marginal equations imply

\(\displaystyle \sum_{r\in T}x_{v,r}=\sum_{s,t\in T}q_{v,s,t}=\sum_{s\in T}x_{a(v),s}.\)

Starting with constraint 1, induction therefore gives total mass \(1/N\) at every node. Finally, constraint 5 makes the execution successful.

Thus the linear program is feasible if and only if the instance is feasible under the stated divisible-mass rules.

Size and exact running time. The formulation has

\(\displaystyle D=(2N-1)\tau+(N-1)\tau^2=O(N\tau^2)\)

variables and, excluding nonnegativity constraints,

\(\displaystyle E=N+\tau+2(N-1)\tau+(N-1)\tau+\tau=N+(3N-1)\tau=O(N\tau)\)

equalities. It has \(O(N\tau^2)\) nonzero coefficients: each coupling variable appears in its row equation, its column equation, and exactly one winner equation.

All matrix coefficients belong to \(\{-1,0,1\}\). Right-hand sides are input masses, zero, or \(1/N\). A sparse encoding therefore has bit length

\(\displaystyle B=O\!\left(L+N\tau^2\log(N\tau+2)\right).\)

Apply the standard polynomial-time theorem for rational linear programming: feasibility of a finite system of rational linear equalities and inequalities can be decided exactly in time polynomial in its encoding length. Its hypotheses hold here because every coefficient and right-hand side is rational and explicitly encoded. This theorem handles feasible sets contained in proper affine subspaces; no strict-feasibility assumption is needed.

The resulting bit running time is

\(\displaystyle B^{O(1)}=(L+N\tau^2)^{O(1)}=(L+Nm\tau)^{O(1)},\)

where the last equality uses \(m=\tau\). Because the bracket is explicit, its node count is polynomially bounded by \(L\), so this is polynomial in the total input length. There is no additional dependence on \(\lambda\).

Relation to the discrete problem. The cited [discrete NP-completeness result](https://ojs.aaai.org/index.php/AAAI/article/view/8805) concerns draws assigning individual players to leaves. Here, divisible leaf assignments and freely chosen couplings are precisely the continuous variables above. No integrality or product constraint is part of the stated model, so discrete hardness does not settle this continuous problem. The exact linear formulation does.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly. The linear program exactly captures the stated divisible-mass rules, and its encoding has polynomial size. I found no major or minor issues requiring repair.

• Definitions and variables.

The node counts \(N\), \(N-1\), and \(2N-1\) are correct for the given complete binary bracket. The variables cover every node’s surviving type masses and every internal node’s ordered child-type pairings.

The winner function is fixed by the input, including \(w(t,t)=t\). Thus the winner-indexed sums use fixed sets of variables and are linear. There is no optimization over match outcomes.

• Leaf constraints.

Constraint 1 enforces exactly the required mass \(1/N\) at every leaf. Constraint 2 preserves each supported type’s initial mass across all leaves. Together with nonnegativity, these constraints express precisely the allowed divisible initial assignment.

No integrality condition is required or introduced.

• Coupling and winner constraints.

Constraint 3 gives exactly the prescribed row and column marginals, with the left and right children correctly distinguished.

Constraint 4 assigns each paired amount to exactly one winning type. It counts each coupling entry once, including diagonal entries. Consequently, it correctly models elimination of the losing amount without doubling the surviving amount.

These constraints contain no product or independence assumption. This matches the task’s permission to choose arbitrary couplings.

• Execution implies LP feasibility.

Every variable is assigned its corresponding mass or coupling from the execution. Each of constraints 1–5 then follows directly from the corresponding rule in the task. This direction is complete.

• LP feasibility implies an execution.

The leaf assignment is valid by constraints 1 and 2. At each internal node, the induction hypothesis identifies its children’s actual surviving masses with the corresponding variables. Nonnegativity and constraint 3 therefore make the specified coupling admissible. Constraint 4 then gives exactly the declared parent masses.

The induction is valid because the bracket is a tree: each child’s surviving mass is used by its unique parent. The task imposes no further consistency requirement between couplings at different nodes.

The separate total-mass calculation is also correct. Every ordered pair has exactly one winner, so summing the winner equations counts every coupling entry once. The row equations identify this sum with the left child’s total mass. Induction from the leaf capacities establishes mass \(1/N\) at every node. Constraint 5 then establishes the required root outcome.

• Size calculations.

The variable count
\(D=(2N-1)\tau+(N-1)\tau^2\)
is correct.

The equality count is also correct:
\(E=N+\tau+2(N-1)\tau+(N-1)\tau+\tau=N+(3N-1)\tau\).

Each coupling variable occurs in exactly three equalities. The occurrences of the mass variables contribute only \(O(N\tau)\) additional entries. Including nonnegativity still gives \(O(N\tau^2)\) nonzero coefficients overall.

• Encoding and polynomial-time theorem.

All matrix coefficients are indeed in \(\{-1,0,1\}\). The right-hand sides are explicitly encoded rational input masses, zero, or \(1/N\).

The bound
\(B=O(L+N\tau^2\log(N\tau+2))\)
accounts for sparse indices, coefficients, and right-hand sides. Repeated leaf right-hand sides require \(O(N\log N)\) bits, which this bound covers even when \(\tau=1\).

The prover states the applicable theorem precisely enough: exact feasibility of explicitly encoded finite rational linear systems is decidable in polynomial bit time. Its hypotheses hold here, and affine degeneracy does not invalidate the theorem. The distinction between preliminary full-dimensional ellipsoid arguments and general polynomial-time LP feasibility is addressed in the [MIT lecture notes](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).

Absorbing the logarithmic factor into an unspecified polynomial exponent is legitimate. Using \(m=\tau\), the claimed bound \((L+Nm\tau)^{O(1)}=(L+N\tau^2)^{O(1)}\) follows. Explicit bracket representation ensures that \(N\) is polynomially bounded by \(L\).

• Scope, parameters, and edge cases.

The argument applies to every permitted support size, including \(\tau=1\), and to \(N=2\). Diagonal pairings are explicitly handled. It does not require strict positivity of intermediate masses.

The promise \(\mu_f\ge1/N\) need not be used separately: the equivalence proof already applies to all promised inputs. No additional dependence on \(\lambda\) appears.

The distinction from discrete tournament fixing is valid. The [cited discrete result](https://ojs.aaai.org/index.php/AAAI/article/view/8805) concerns a different feasibility model; the prover establishes the continuous classification through its own exact formulation.

Required clarification or repair: None.

⟨structured verdict parsed — rendered above⟩