Answer: Polynomial-time solvable (\(\mathrm P\)); exact optimization is also polynomial-time solvable.
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe split point with the highest value of in- formation will occur at one of the intersection points.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a decision tree \(D\), outcomes \(O\), and a finite set \(T\) of complete utility profiles \(u^t\in[0,1]^O\) with rational masses \(\mu_t\), choose an outcome \(o\) and threshold \(s\) for one common question. For each answer group \(A_-=\{t:u_o^t<s\}\) and \(A_+=\{t:u_o^t>s\}\), choose a strategy maximizing that group's total expected utility, and maximize the resulting value \(W_1(o,s)-W_0\), where \(W_1(o,s)=\sum_{a\in\{-,+\}}\max_{\pi\in\Pi}\sum_{t\in A_a}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t\) and \(W_0=\max_{\pi\in\Pi}\sum_{t\in T}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t\).
Input: an explicitly represented finite decision tree \(D\) with \(n\) nodes, decision nodes, chance nodes whose outgoing probabilities are nonnegative binary rationals summing to \(1\), and leaves labelled by outcomes in \(O\), where \(m=|O|\geq2\). A strategy \(\pi\in\Pi\) selects one outgoing edge at every decision node; \(P_D(z\mid\pi)\) is its induced outcome probability.
A society is given by its support: the list \(T\) of \(\tau\geq1\) distinct complete utility profiles \(u^t\in([0,1]\cap\mathbb Q)^O\), each with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types. All profiles use common best and worst reference outcomes with utilities \(1\) and \(0\); these references need not occur among the leaves. No independence of utility coordinates is assumed. Let \(L\) be the total input bit length.
One common, cost-free standard-gamble question chooses \(o\in O\) and rational \(s\in(0,1)\) with \(s\ne u_o^t\) for every \(t\). Its answer groups are \(A_- =\{t:u_o^t<s\}\) and \(A_+=\{t:u_o^t>s\}\). Each group receives its own strategy, common to all its types; an empty group contributes \(0\).
Define \(V(A)=\max_{\pi\in\Pi}\sum_{t\in A}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t\), \(W_0=V(T)\), and \(W_1(o,s)=V(A_-)+V(A_+)\). The optimization problem is to maximize \(W_1(o,s)-W_0\); its decision version additionally takes a binary-rational threshold \(b\).
Is deciding whether some admissible \((o,s)\) satisfies \(W_1(o,s)-W_0\geq b\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,n,L\).
The verified anchor is an intersection-point characterization for independent utility coordinates under a continuous density, rather than a discrete complexity classification: a highest-value split can be chosen at an intersection of viable strategies' expected-utility functions. [Chajewska, Koller and Parr (2000)](https://cdn.aaai.org/AAAI/2000/AAAI00-056.pdf).
No result settling exactly the finite-support problem above was identified in the literature search.
The decision problem is in \(\mathrm P\). The optimization problem can also be solved exactly in polynomial time, including recovery of an optimal admissible question and its two strategies.
An explicit bit-operation bound is
\[
O\!\left(\left[m\tau\log(\tau+1)+m^2\tau+mn(\tau+1)\right]L^2\right).
\]
The proof uses the explicitly represented tree and support; it requires no independence of utility coordinates.
For any group \(A\subseteq T\), define its aggregate utility vector by
\[
g_A(z)=\sum_{t\in A}\mu_tu_z^t,\qquad z\in O.
\]
For every strategy \(\pi\), rearranging the finite sums gives
\[
\sum_{t\in A}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t
=\sum_{z\in O}P_D(z\mid\pi)g_A(z).
\]
Thus \(V(A)\) is the optimal expected utility in the same tree with leaf utilities \(g_A\). This aggregation preserves the requirement that all types in \(A\) receive one common strategy.
Let \(F_A(v)\) denote the optimal value in the subtree rooted at node \(v\). Compute it from the leaves upward:
These recurrences follow by induction on subtree height. At a decision node, the strategy chooses one child and then an optimal strategy in that child’s subtree. At a chance node, every child strategy contributes with a nonnegative coefficient. Because the child subtrees have disjoint decision nodes, their maximizing strategies can be combined into a single strategy attaining the displayed sum.
Consequently, if \(r\) is the root, then \(F_A(r)=V(A)\). The tree has \(n-1\) edges, so this calculation takes \(O(n)\) arithmetic operations. Recording maximizing children recovers an optimal strategy. The same recurrence gives \(V(\varnothing)=0\).
Fix an outcome \(o\). Sort and deduplicate
\[
S_o=\{0,1\}\cup\{u_o^t:t\in T\}
\]
to obtain \(a_0<a_1<\cdots<a_k\), where \(a_0=0\) and \(a_k=1\).
Every admissible threshold belongs to exactly one interval \((a_i,a_{i+1})\). Throughout that interval, its answer groups are
\[
A_-=\{t:u_o^t\leq a_i\},
\qquad
A_+=T\setminus A_-.
\]
Indeed, no supported coordinate value lies strictly between the two adjacent boundaries. Therefore \(W_1(o,s)\) is constant on each interval.
Choose the representative
\[
s_i=\frac{a_i+a_{i+1}}2.
\]
It is rational, lies strictly between \(0\) and \(1\), and differs from every \(u_o^t\). Its encoding has \(O(L)\) bits.
There are at most \(\tau+2\) distinct boundaries and hence at most \(\tau+1\) representatives for each outcome. Thus at most \(m(\tau+1)\) questions suffice to attain the optimum. This also handles coordinates taking only endpoint values and questions with an empty answer group.
First compute all weighted utility entries \(\mu_tu_z^t\), their totals \(g_T(z)\), and the baseline \(W_0=V(T)\).
For each outcome \(o\):
Keep a representative attaining the largest value. Every admissible question induces a partition examined by the algorithm, and every examined representative is admissible. Hence the retained value is exactly the requested optimum.
All outcomes are examined, including outcomes absent from the leaves: their utility coordinates can still usefully separate types with different utilities for leaf outcomes.
Sorting costs \(O(m\tau\log(\tau+1))\) comparisons. During one outcome’s sweep, each type moves at most once, updating \(m\) utility coordinates. All sweeps therefore use \(O(m^2\tau)\) updates. The tree calculations use \(O(mn(\tau+1))\) arithmetic operations.
To justify exact computation, let \(Q\) be the product of the positive denominators of all input rational occurrences, including the threshold \(b\) for the decision version. Denominators are counted separately for each encoded occurrence. Their total binary length is at most \(L\), so \(Q\) has \(O(L)\) bits.
For a fixed strategy in any subtree, its group value is a sum of terms of the form
\[
\mu_tu_z^t\prod_{e\text{ on a subtree path}}p_e.
\]
Each term uses one mass occurrence, one utility occurrence, and each path edge at most once. Its denominator therefore divides \(Q\). The sum’s denominator divides \(Q\) as well. Since there are finitely many strategies, every maximizing subtree value is attained by some strategy and also has denominator dividing \(Q\).
We can consequently store every group utility and subtree value multiplied by \(Q\), as an integer.
At a chance edge with probability \(a_e/d_e\), the scaled contribution is computed as \(a_eH(c)/d_e\), where \(H(c)=QF_A(c)\). This division is exact: the denominator of \(F_A(c)\) divides the product of the mass and utility denominators and the chance-edge denominators inside the child subtree. That product excludes the parent-edge occurrence \(d_e\), so it divides \(Q/d_e\).
Every unscaled group value lies between \(0\) and \(\sum_{t\in A}\mu_t\leq1\). Thus stored values lie between \(0\) and \(Q\). Intermediate multiplication results, sorting cross-products, and the scaled threshold \(Qb\) also have \(O(L)\) bits.
Elementary integer multiplication and division on these operands take \(O(L^2)\) bit operations. Constructing \(Q\) takes \(O(L^2)\) bit operations as well: successive schoolbook multiplications have total cost bounded by the square of the sum of the factors’ bit lengths. Combining this with Section 3 gives
\[
O\!\left(\left[m\tau\log(\tau+1)+m^2\tau+mn(\tau+1)\right]L^2\right).
\]
Finally, compare the maximum scaled gain with the integer \(Qb\). This decides the question exactly.
The cited paper describes bottom-up expectimax for explicit decision trees. [Chajewska, Koller and Parr (2000)](https://cdn.aaai.org/AAAI/2000/AAAI00-056.pdf). The finite-support classification proved here follows from enumerating coordinate-induced partitions and computing each group’s aggregate utility vector; it does not require a continuous density or independent coordinates.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the stated finite-support problem is in \(\mathrm P\), and the exact optimization algorithm and bit-operation bound are justified. No major or minor mathematical issues were found.
The definition
\[
g_A(z)=\sum_{t\in A}\mu_tu_z^t
\]
correctly preserves the requirement that every type in an answer group receives the same strategy. The displayed interchange of sums is valid because both sums are finite. Maximization remains outside the sum over types, so the argument does not inadvertently allow type-specific strategies.
The bottom-up recurrence correctly computes \(V(A)\):
The last property depends on the input being a tree and on strategies having an independent choice at every decision node. Both are explicit hypotheses of the task.
There are \(n-1\) edges, so the claimed \(O(n)\) arithmetic-operation count holds even with unbounded node degree. Recording a maximizing child at every decision node produces a complete optimal strategy, including choices at nodes that are ultimately unreachable. For \(A=\varnothing\), every leaf value and consequently every subtree value is zero.
Finding: Correct and sufficiently justified.
Adding \(0\) and \(1\) to the supported coordinate values handles both endpoints correctly. Because admissible thresholds exclude every supported coordinate value and must lie strictly between \(0\) and \(1\), each belongs to exactly one open interval between consecutive distinct boundaries.
Within such an interval, the asserted partition
\[
A_-=\{t:u_o^t\leq a_i\},\qquad A_+=T\setminus A_-
\]
is correct. In particular, types equal to the lower boundary belong to the lower answer group; ties are never divided.
Every midpoint representative is rational, strictly inside its interval, and therefore admissible. Computing a midpoint from two input rationals increases its encoding length by at most a constant factor, so the claimed \(O(L)\) length holds.
The count of at most \(\tau+1\) intervals per outcome follows from at most \(\tau+2\) distinct boundaries. The argument covers coordinates constant at \(0\), constant at \(1\), constant at an interior value, and coordinates taking only endpoint values. Empty answer groups cause no difficulty.
Finding: The finite enumeration is exhaustive and contains only admissible questions.
The sweep maintains precisely the aggregate utilities required by the recurrence. Moving an entire tied block at its boundary produces the partition for the interval immediately above that boundary. The complementary vector is correctly obtained by subtraction from \(g_T\).
The baseline \(W_0\) is independent of the question, so maximizing the computed gains selects an optimal question. The finite enumeration is nonempty, ensuring that a maximizing representative exists.
The strategy-recovery claim is supported by Section 1: the two maximizing strategies can be retained when the best candidate is updated. This does not change the stated asymptotic bound.
Examining outcomes absent from the leaves is necessary and correctly included. Such coordinates can distinguish utility profiles even though they contribute no direct leaf utility.
Finding: The algorithm resolves both the decision and optimization assignments.
The component counts are correct:
Initial weighted-entry computation, aggregation, baseline evaluation, candidate comparison, and representative construction are absorbed by these terms under \(m\geq2\), \(\tau\geq1\), and \(n\geq1\).
Finding: The operation count is valid.
The common-denominator argument is sound. Counting denominators separately for every encoded occurrence ensures that repeated numerical denominators still supply the multiplicity needed for products.
For a fixed strategy, each term uses one mass occurrence, one utility occurrence, and distinct chance-edge occurrences along a tree path. Its denominator therefore divides \(Q\). Adding such terms preserves this divisibility, and taking a maximum selects an attained strategy value rather than creating a new denominator.
The exact-division claim at a chance edge is also justified. The denominator product sufficient for the child value excludes that parent-edge occurrence, so it divides \(Q/d_e\). Consequently, the scaled child value is divisible by \(d_e\), making the specified division exact.
The bounds on operand lengths hold:
The stated construction cost for \(Q\) and the \(O(L^2)\) schoolbook arithmetic bound are valid. Thus the overall bound
\[
O\!\left(\left[m\tau\log(\tau+1)+m^2\tau+mn(\tau+1)\right]L^2\right)
\]
is justified and polynomial in the explicit input length.
Finding: No denominator-growth or exact-arithmetic gap remains.
The attribution concerning bottom-up expectimax is accurate: the cited paper explicitly describes maximization at decision nodes and expectation at chance nodes. [Chajewska, Koller and Parr (2000)](https://cdn.aaai.org/AAAI/2000/AAAI00-056.pdf).
The proof is self-contained and does not invoke the paper’s intersection-point characterization. Its classification applies to the explicit tree and explicit finite support in the task; it makes no unsupported extension to arbitrary continuous distributions or succinct representations.
No repair or additional clarification 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.