Answer: Polynomial-time solvable in the stated comparison-oracle model, with linearly many queries and exact optimality over the final consistent set.
Proposition 11 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 3 has a time complexity of O(poly(nT , 1/δ)) and uses only O(poly(nT , 1/δ)) queries, where nT is the number of nodes in tree T.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an explicit decision tree \(T\) with rational chance probabilities, \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), and for each type a rational polytope \(B_t\) of feasible coefficients for a normalized utility \(u_t(x)=\sum_{j=1}^{q} b_{tj}I_j(x)\) in a shared I-spline basis, design an adaptive elicitation algorithm. Each query asks a society-level oracle to compare lotteries by their mass-weighted expected utility \(W(\ell)=\sum_t\mu_t\sum_x p_\ell(x)u_t(x)\). The algorithm must output one contingent policy \(\pi\) whose worst-case regret, over all utility profiles consistent with the polytopes and observed answers, is at most \(\delta\); determine its query and time complexity in \(n_T,\tau,q,L,\) and \(1/\delta\).
Given an explicit rooted decision tree \(T\) with \(n_T\) nodes, a decision-node root, nonempty action sets, and rational chance probabilities summing to \(1\) at each chance node, let \(X\subseteq[0,1]\) be its rational leaf outcomes together with \(0,1\), and let \(m=|X|\). A contingent policy deterministically selects one action at each relevant decision node and induces a lottery \(\ell_\pi\).
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The shared basis consists of \(q\) normalized order-three I-splines on a uniform subdivision of \([0,1]\), with \(I_j(0)=0\) and \(I_j(1)=1\). Each type has an explicitly inequality-described, nonempty rational polytope \(B_t\subseteq\{b\in\mathbb R^q:b_j\geq0,\ \sum_j b_j=1\}\), defining \(u_t(x)=\sum_j b_{tj}I_j(x)\). Thus utilities are nondecreasing and normalized at the endpoints.
An unknown fixed profile \(b^*\in\prod_t B_t\) answers queries comparing any two rational lotteries on \(X\), by their values \(W_b(\ell)=\sum_t\mu_t\sum_{x\in X}p_\ell(x)u_t(x)\). The oracle returns a weakly preferred lottery; either answer is allowed at equality. Queries need not be induced by policies. Each answer retains precisely the profiles satisfying its weak comparison inequality.
For the final consistent set \(\mathcal B\), the required output is one policy \(\pi\) satisfying \(\max_{b\in\mathcal B}\max_{\pi'}[W_b(\ell_{\pi'})-W_b(\ell_\pi)]\leq\delta\), where \(\delta\in(0,1)\) is rational. Let \(L\) be the total binary input length, including the polytopes, basis data, and tolerance; count oracle calls separately from bit computation, including query construction.
Does this adaptive elicitation problem admit polynomially many queries and polynomial bit time in \(m,n_T,\tau,q,L,1/\delta\), or is it NP-hard in this comparison-oracle model? Determine its query and time complexity in these parameters.
For one decision maker with normalized monotone utility and polyhedral utility uncertainty, interactive backward induction has polynomial time and query bounds in \(n_T,1/\delta\), with at most \(n_T\lceil\log_2(2n_T/\delta)\rceil\) queries under polynomial-time linear-programming subroutines ([published result](https://www.ijcai.org/proceedings/2017/0637.pdf)). The same source states that additive multi-agent extensions are possible, but gives no support-and-bit-complexity theorem for the mass formulation above; no separate result settling this exact formulation was located.
The problem is polynomial-time solvable in the stated comparison-oracle model. In fact, there is an algorithm returning a policy with final maximum regret exactly \(0\), using at most
\(Q=\sum_{v\text{ decision node}}(\deg(v)-1)\leq n_T-1\)
oracle calls and polynomial bit computation.
This bound is independent of \(1/\delta\). The essential hypothesis is that the oracle permits comparisons between arbitrary rational lotteries on \(X\), including lotteries induced by policies within subtrees.
For a profile \(b=(b_1,\ldots,b_\tau)\), define its aggregate utility by
\(U_b(x)=\sum_{t=1}^{\tau}\mu_t\sum_{j=1}^{q}b_{tj}I_j(x)\).
Then
\(W_b(\ell)=\sum_{x\in X}p_\ell(x)U_b(x)\).
Consequently, for any lotteries \(\ell_1,\ldots,\ell_k\) and nonnegative rational weights \(p_i\) summing to \(1\),
\(W_b(\sum_i p_i\ell_i)=\sum_i p_iW_b(\ell_i)\).
This identity holds for every admissible profile. It allows backward induction using the same functional at every node. We do not need to identify individual types’ utilities or explicitly construct the set of aggregate utilities.
Process every node after all its children. At each node \(v\), store a rational lottery \(\ell_v\) and deterministic choices describing a policy within its subtree.
\(\ell_v=\sum_{i=1}^{k}p_i\ell_{c_i}\).
Retain the previously selected policies in all child subtrees.
Output the policy specified by these choices, restricted to relevant decision nodes.
Every query is legal: subtree lotteries are rational probability distributions on \(X\), even when they are not induced by a policy starting at the root.
Let \(\mathcal B\) be precisely the original profile set intersected with the weak inequalities supplied by this transcript. No additional profile restrictions are imposed. The true profile \(b^*\) satisfies every answer, so \(\mathcal B\) is nonempty.
Fix an arbitrary \(b\in\mathcal B\). Every answer in the transcript is a valid weak comparison under this same profile.
First, a sequential tournament returns a child lottery maximizing \(W_b\) among all children. Indeed, after processing any initial segment, the incumbent weakly dominates every lottery in that segment. For the next comparison:
This establishes the invariant by induction. It applies simultaneously to every \(b\in\mathcal B\), including profiles for which some comparisons are ties.
Now define \(V_v(b)\) as the maximum expected utility achievable by a deterministic policy within the subtree rooted at \(v\). These maxima exist because the tree is finite and action sets are nonempty. We prove, by induction from leaves toward the root, that
\(W_b(\ell_v)=V_v(b)\).
Leaf. There is only its prescribed outcome, so the assertion holds.
Chance node. Child subtrees are disjoint because the input is a tree. Thus their policies can be chosen independently. Nonnegative chance probabilities imply
\(V_v(b)=\sum_i p_iV_{c_i}(b)\):
every collection of child policies is bounded above by this sum, and choosing an optimal policy in each child attains it. Using linearity and the induction hypothesis gives
\(W_b(\ell_v)=\sum_i p_iW_b(\ell_{c_i})=\sum_i p_iV_{c_i}(b)=V_v(b)\).
Zero-probability branches cause no difficulty.
Decision node. Its optimal value is
\(V_v(b)=\max_i V_{c_i}(b)\).
By the induction hypothesis, these values equal \(W_b(\ell_{c_i})\). The tournament selects a maximizing child, proving the assertion.
At the root \(r\), therefore, the output policy \(\pi\) satisfies
\(W_b(\ell_\pi)=V_r(b)=\max_{\pi'}W_b(\ell_{\pi'})\)
for every \(b\in\mathcal B\). Hence its required regret is exactly
\(\max_{b\in\mathcal B}\max_{\pi'}[W_b(\ell_{\pi'})-W_b(\ell_\pi)]=0\),
which is at most \(\delta\).
A decision node with \(k\) children uses exactly \(k-1\) queries. Consequently,
\(Q=\sum_{v\text{ decision node}}(\deg(v)-1)\).
Let \(s\) be the number of leaves. Every internal node has at least one child, and a rooted tree has \(n_T-1\) edges. Thus
\(\sum_{v\text{ internal node}}(\deg(v)-1)=s-1\).
All terms are nonnegative, giving
\(Q\leq s-1\leq n_T-1\).
These are upper bounds; prior utility information can permit fewer queries.
It remains to establish that the stored lotteries have polynomial-length rational descriptions.
Write each chance-edge probability as \(a_e/d_e\), where \(a_e\) and \(d_e\) are integers with \(0\leq a_e\leq d_e\) and \(d_e\geq1\). For each node \(v\), let \(D_v\) be the product of all chance-edge denominators within its subtree, with empty product \(1\).
Because the denominator encodings are part of the input, every \(D_v\) has at most \(L+1\) bits.
Represent \(\ell_v\) by integer numerators \(N_{v,x}\), using the common denominator \(D_v\). We verify that this representation can be maintained exactly.
\(N_{v,x}=N_{c,x}(D_v/D_c)\).
\(N_{v,x}=\sum_c a_{vc}N_{c,x}\bigl(D_v/(d_{vc}D_c)\bigr)\).
The chance-node formula is exactly the numerator of
\(\sum_c(a_{vc}/d_{vc})\ell_c\).
Thus all divisions are exact, and each stored lottery remains a probability distribution. In particular,
\(0\leq N_{v,x}\leq D_v\).
Therefore every probability in every query has an \(O(L)\)-bit representation. A dense query containing two lotteries has \(O(m(L+1))\) bits, including the probabilities and outcome descriptions.
There are \(O(mn_T)\) integer arithmetic operations for the denominator and lottery computations, on integers of \(O(L)\) bits. Sorting and indexing the rational outcomes requires \(O(n_T\log(n_T+1))\) rational comparisons. With elementary integer arithmetic, a sufficient total bit-time bound, including writing all queries and the output policy, is
\(O\bigl(L+n_T(m+\log(n_T+1))(L+1)^2\bigr)\).
No spline evaluation, linear programming, or polytope projection is required. The dependence on \(\tau\), \(q\), and the tolerance is covered by reading their input descriptions within \(L\). In particular, the algorithm is polynomial in all the requested parameters, and requires no numerical dependence on \(1/\delta\).
Section 3 of the [published paper](https://www.ijcai.org/proceedings/2017/0637.pdf) explains that its algorithm uses comparisons between a sure outcome and an endpoint lottery because direct comparisons of subtree lotteries can be cognitively difficult. The oracle specified here explicitly permits those direct comparisons. This permission yields the exact tournament algorithm above.
Thus the stated elicitation problem admits polynomial bit computation with linearly many oracle calls. The proof settles the support-and-mass formulation directly.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes exact optimality over the final consistent set, with at most \(n_T-1\) oracle calls and polynomial bit computation. I found no major or minor issues requiring repair.
The definition
\[
U_b(x)=\sum_{t=1}^{\tau}\mu_t\sum_{j=1}^{q}b_{tj}I_j(x)
\]
gives precisely the welfare functional specified in the task. For each fixed profile, welfare is linear in lottery probabilities. The stated mixture identity follows by rearranging finite sums.
This supplies the common expected-utility functional needed throughout the tree. The algorithm does not need to identify utility coefficients, evaluate splines, or optimize over the uncertainty polytopes.
Leaf lotteries are rational point masses. Chance-node mixtures preserve rationality, nonnegativity, and total probability \(1\). Decision nodes retain one already constructed child lottery. Consequently, every queried object is a rational lottery on \(X\).
The task expressly permits lotteries that are not induced by root policies, so comparisons of subtree lotteries are legal. The selected actions and retained child policies describe a deterministic contingent policy. Restricting these choices to relevant decision nodes preserves its induced lottery.
Processing all nodes, including subtrees ultimately excluded by an ancestor’s selected action, is permitted and is included in the query and computation bounds.
Every answer retains the profiles satisfying the returned weak comparison. The true profile satisfies every such inequality, including when the oracle chooses either answer at equality. Thus the final set \(\mathcal B\) is nonempty.
Fixing an arbitrary \(b\in\mathcal B\) makes every comparison in the completed transcript valid under that same profile. Although the queried lotteries were chosen adaptively, their identities are fixed once the transcript is fixed. This justifies using all transcript inequalities together.
For the fixed profile, the incumbent initially maximizes welfare over the one-element processed set. If it wins the next comparison, it dominates the new child as well. If the new child wins, its welfare is at least the previous incumbent’s welfare, which was at least that of every earlier child.
This proves the invariant for weak comparisons, including ties. Because the reasoning applies to every \(b\in\mathcal B\), the final selected child maximizes welfare simultaneously over the final consistent set.
Subtree policy sets are finite and nonempty, so the maxima defining \(V_v(b)\) exist.
At leaves, the stored lottery has the unique available value. At chance nodes, disjoint child subtrees permit independent policy choices, and nonnegative probabilities justify both the upper bound and its attainment:
\[
V_v(b)=\sum_i p_iV_{c_i}(b).
\]
Zero-probability branches do not invalidate this identity.
At decision nodes, choosing an action gives
\[
V_v(b)=\max_iV_{c_i}(b).
\]
The induction hypothesis and tournament invariant therefore establish the stored lottery’s optimality.
The output policy is fixed by the transcript, while \(b\) was arbitrary. Hence the proof establishes one policy optimal for every final consistent profile, rather than merely a potentially different optimal policy for each profile. Every regret expression is consequently zero, and the required maximum regret is exactly zero.
A decision node with \(k\) children uses \(k-1\) comparisons. For a rooted tree with \(s\) leaves,
\[
\sum_{v\text{ internal}}(\deg(v)-1)=s-1.
\]
All summands are nonnegative. Thus the claimed bounds
\[
Q=\sum_{v\text{ decision}}(\deg(v)-1)\leq s-1\leq n_T-1
\]
hold, including unary internal nodes. These are valid upper bounds; no matching lower bound is claimed.
Each \(D_v\) multiplies denominators from a subset of the explicitly encoded chance edges. The sum of their binary lengths is bounded by \(L\), giving the claimed \(L+1\) bit bound.
The divisibility assertions hold because child subtrees are disjoint. Both numerator-update formulas represent the prescribed lotteries exactly. Nonnegative summands and normalization imply
\[
0\leq N_{v,x}\leq D_v.
\]
Products and partial sums in these updates also have \(O(L)\) bits.
Summing child counts over the tree gives \(O(mn_T)\) arithmetic operations. Elementary arithmetic on these integers, rational-outcome sorting, query serialization, and policy output fit the displayed polynomial bit-time bound. Dense queries have the claimed \(O(m(L+1))\) description size. No numerical dependence on \(1/\delta\) is required because the algorithm achieves zero regret.
Section 3 explains that direct comparisons of subtree lotteries can be cognitively difficult and proposes comparisons between sure outcomes and endpoint lotteries. This supports the prover’s description. [Published paper, Section 3](https://www.ijcai.org/proceedings/2017/0637.pdf)
The present correctness and complexity claims are established directly; they do not depend on importing an unstated multi-agent theorem.
Actionable feedback: No additional clarification or mathematical repair is necessary.
⟨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.