Answer: Deciding whether \(Q^*\le B\) is \(\mathrm{NP}\)-hard, even for \(B=1\), \(\tau=1\), and \(n=4\). The permitted adaptive strategies can improve the optimized independent HLG baseline by an unbounded factor: a family with \(L=\Theta(k)\) has \(Q^*=2\) and optimized baseline count \(2k\).
Proposition 2 — class: algorithmic
Given a finite support \(T\) with rational masses \(\mu_t\), and for each type \(t\) a feasible set \(F_t\) and uncertain GAI utility set \(U_t\), where members of that type share the same latent utility, determine the worst-case number of adaptive threshold queries needed to return recommendations \(x_t\in F_t\) such that \(\max_{(u_t)\in\prod_{t\in T}U_t}\sum_{t\in T}\mu_t[\max_{y\in F_t}u_t(y)-u_t(x_t)]\le\epsilon\). In particular, can query allocation using the masses improve on running HLG independently with per-type tolerances \(\epsilon_t\) satisfying \(\sum_t\mu_t\epsilon_t\le\epsilon\)?
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). The parameter \(\tau\) is the support size, not the number of possible types.
There are \(m\) Boolean attributes. Each nonempty feasible set \(F_t\subseteq\{0,1\}^m\) is specified by a Boolean constraint formula. Type \(t\) has a GAI utility \(u_t(x)=\sum_{k=1}^{K_t}f_{tk}(x[S_{tk}])\), with explicitly listed factor tables and scopes \(S_{tk}\). Initially, every table entry lies independently in a finite interval \([a_{tkz},b_{tkz}]\) with signed binary-rational endpoints; these intervals define \(U_t\). Utilities use a common cardinal scale. Let \(n\) be the total number of table entries and \(L\) the total input bit length.
Each type has one fixed latent parameter vector shared by its entire mass; vectors of different types are independent. A unit-cost query selects a type, a table entry \(p\), and a rational threshold \(q\), and receives the truthful answer to \(p\le q\). Queries may depend on previous answers. Let \(U_t^h\) be the closure of the parameter vectors consistent with transcript \(h\).
For binary-rational \(\epsilon>0\), a deterministic strategy must terminate on every consistent answer sequence with one recommendation \(x_t\in F_t\) per type satisfying \(\max_{(u_t)\in\prod_tU_t^h}\sum_t\mu_t[\max_{y\in F_t}u_t(y)-u_t(x_t)]\le\epsilon\). Let \(Q^*\) be the minimum possible worst-case total number of queries. The decision input additionally contains a binary-encoded integer \(B\ge0\).
The independent HLG baseline fixes positive tolerances \(\epsilon_t\) with \(\sum_t\mu_t\epsilon_t\le\epsilon\), then separately queries each type's widest parameter interval at its midpoint until that type admits a recommendation of maximum regret at most \(\epsilon_t\). Optimize this baseline over the tolerances; fix arbitrary deterministic tie-breaking.
Is deciding whether \(Q^*\le B\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Can mass-aware adaptive strategies improve the optimized independent HLG baseline's worst-case query count? State running times in \(m,\tau,n,L\) and the budget encoding length.
For one decision maker with \(n_0\) parameters, HLG guarantees regret at most \(\epsilon\) after \(n_0\lceil\log_2(M/\epsilon)\rceil\) queries when \(M>\epsilon\), where \(M=\sum_k\max_z(b_{kz}-a_{kz})\); this is a query bound, not a polynomial-time planning theorem. [Verified source](https://www.cs.toronto.edu/~cebly/Papers/BPPS-aij06.pdf).
No result settling this exact mass-weighted adaptive query-budget problem was located in the literature search.
The decision problem is \(\mathrm{NP}\)-hard, even with \(\tau=1\), \(n=4\), and the fixed positive budget \(B=1\). Thus a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The permitted adaptive strategies can improve the optimized independent HLG baseline by an unbounded factor. Below, a family with \(m=1\), \(\tau=2\), and \(n=4\) has \(Q^*=2\), while the optimized baseline requires exactly \(2k\) queries, with input length \(L=\Theta(k)\).
These conclusions do not require assuming that minimax regret or optimal query planning is polynomial-time computable.
For a consistent transcript \(h\), write the closed parameter interval of entry \(z\) in factor \(k\) of type \(t\) as \([a^h_{tkz},b^h_{tkz}]\). Coordinate threshold queries preserve the product structure of the uncertainty sets.
For feasible recommendations \(x,y\in F_t\), define
\[ D^h_{tk}(x,y)= \begin{cases} 0,&x[S_{tk}]=y[S_{tk}],\\ b^h_{tk,y[S_{tk}]}-a^h_{tk,x[S_{tk}]},& x[S_{tk}]\ne y[S_{tk}]. \end{cases} \]
Here and below, the displayed mathematics uses the equivalent notation \(D^h_{tk}(x,y)\) when referenced in prose.
If the two local assignments coincide, their utility contributions cancel. Otherwise, the two table entries are independent, so their difference is maximized by putting the entry used by \(y\) at its upper endpoint and the entry used by \(x\) at its lower endpoint. Independence between all entries therefore gives
\[ R_t^h(x):=\max_{u_t\in U_t^h} \left[\max_{y\in F_t}u_t(y)-u_t(x)\right] =\max_{y\in F_t}\sum_k D^h_{tk}(x,y). \]
Define \(r_t(h)=\min_{x\in F_t}R_t^h(x)\).
For fixed recommendations, independence between types implies
\[ \max_{(u_t)\in\prod_tU_t^h} \sum_t\mu_t\left[\max_{y\in F_t}u_t(y)-u_t(x_t)\right] =\sum_t\mu_tR_t^h(x_t). \]
Indeed, the left side is at most the right side, and equality follows by choosing, independently for every type, a parameter vector attaining its maximum. Such maxima exist because the closed uncertainty boxes are compact and the feasible sets are finite.
Recommendations can also be chosen independently. Consequently, a transcript admits valid recommendations exactly when
\[ \sum_t\mu_t r_t(h)\le\epsilon. \]
This is a stopping criterion, not an efficient planning theorem.
We give a polynomial-time many-one reduction from Boolean satisfiability.
Let \(\Phi(z_1,\ldots,z_d)\) be the input formula. Construct one type with mass \(1\). Its attributes are \(z_1,\ldots,z_d\) and two selector bits \(s\). Set
\[ F=\left\{(z,s): \bigl(s\ne 11\ \land\ z=0^d\bigr) \ \lor\ \bigl(s=11\ \land\ \Phi(z)\bigr)\right\}. \]
This set is always nonempty: it contains the three fallback outcomes with selectors \(00,01,10\).
Use one factor, with scope consisting of the selector bits:
| Selector | Utility-table interval |
|---|---|
| \(00\) | \([0,2]\) |
| \(01\) | \([0,2]\) |
| \(10\) | \([0,2]\) |
| \(11\) | \([2,2]\) |
The three uncertain entries are independent. Set \(\epsilon=1\) and \(B=1\).
A feasible outcome with selector \(11\) has utility \(2\) for every parameter vector. Every other feasible outcome has utility at most \(2\). Recommending any satisfying outcome therefore has regret zero without queries.
Thus \(Q^*=0\).
Only the three fallback outcomes are feasible.
Consider any strategy using at most one query. Follow the answer consistent with all three uncertain entries being zero. At least two uncertain entries remain unqueried.
Whatever fallback outcome the strategy recommends, there is a different fallback outcome whose entry remains unqueried. Keep the recommended outcome’s entry at zero and set that other entry to \(2\). This parameter vector remains consistent with the transcript: the changed entry was not queried, and every queried entry retains its value.
The recommendation therefore has maximum regret at least \(2\), exceeding \(\epsilon\). Hence \(Q^*>1\).
In fact, \(Q^*=2\). Query the first fallback entry at threshold \(1\). If the answer is \(p>1\), recommend that outcome. Its closed posterior lower bound is \(1\), so its maximum regret is at most \(1\). Otherwise, query the second entry at threshold \(1\). If it exceeds \(1\), recommend it; otherwise, recommend the third outcome. In the last case, both competing utilities are at most \(1\), while the recommended utility is at least zero.
Thus the reduction has
\[ \Phi\text{ satisfiable}\quad\Longleftrightarrow\quad Q^*\le 1. \]
The construction has \(m=d+2\), \(\tau=1\), \(n=4\), constant-length numerical data, and a constant-length budget encoding. Its construction time is polynomial in the formula size. This proves \(\mathrm{NP}\)-hardness even for the fixed positive budget \(B=1\).
Fix an integer \(k\ge2\), and let \(c=2^{-k}\).
There are two types, with masses
\[ \mu_1=\frac14,\qquad \mu_2=\frac34. \]
Each type has one Boolean attribute, both outcomes feasible, and one utility table:
| Outcome | Type \(t\)'s utility |
|---|---|
| \(0\) | The known value \(c\) |
| \(1\) | An independent parameter \(p_t\in[0,1]\) |
Set \(\epsilon=c/8\). The two parameters belong to different types and are independent.
For an unqueried type, recommending outcome \(1\) has maximum regret \(c\): its utility might be zero. Recommending outcome \(0\) has maximum regret \(1-c\). Since \(c\le1/4\), its minimax regret is exactly \(c\).
After at most one query, some type remains entirely unqueried. By the decomposition above, every recommendation then has social maximum regret at least
\[ \min(\mu_1,\mu_2)c=\frac c4>\frac c8=\epsilon. \]
Thus \(Q^*\ge2\).
For the matching upper bound, query each \(p_t\) at threshold \(c\). If \(p_t\le c\), recommend outcome \(0\); otherwise, recommend outcome \(1\). Each recommendation has regret zero throughout the corresponding closed posterior interval.
Therefore \(Q^*=2\).
Let \(\epsilon_1,\epsilon_2>0\) satisfy the baseline’s tolerance constraint
\[ \frac14\epsilon_1+\frac34\epsilon_2\le\frac c8. \]
It follows that \(\epsilon_1\le c/2<c\) and \(\epsilon_2\le c/6<c\).
For either type, the only positive-width interval is the interval for \(p_t\). HLG therefore repeatedly bisects that interval.
Consider the consistent parameter value \(p_t=0\). After \(j\) queries, the closed interval is \([0,2^{-j}]\). Its minimax regret is
\[ \min\left(c,\max(0,2^{-j}-c)\right). \]
For \(j<k\), we have \(2^{-j}\ge2c\), so this regret equals \(c\). Since the allocated tolerance is strictly smaller than \(c\), HLG cannot stop before query \(k\).
Conversely, HLG always stops within \(k\) queries. Its successive thresholds along the all-yes branch are \(2^{-1},\ldots,2^{-k}=c\). A no answer at any of these thresholds gives a posterior lower bound at least \(c\), making outcome \(1\) optimal. If all answers are yes, the final upper bound is \(c\), making outcome \(0\) optimal.
Thus each type has worst-case HLG count exactly \(k\), for every admissible tolerance allocation. The simultaneous parameter vector \(p_1=p_2=0\) realizes both worst cases. Consequently,
\[ Q_{\mathrm{HLG,opt}}=2k,\qquad Q^*=2. \]
The improvement factor is \(k\), which is unbounded. This already holds for a fixed query order; adaptation of subsequent query choices is unnecessary for the separation.
Here \(m=1\), \(\tau=2\), \(n=4\), and \(L=\Theta(k)\). The two-query strategy takes \(O(L)\) bit operations to read and emit its thresholds. A direct exact implementation of HLG takes \(O(k^2+L)\) bit operations on this family.
Let \(s\) be the budget encoding length, and let \(n_t\) be type \(t\)'s number of table entries. Define
\[ M_t=\sum_k\max_z(b_{tkz}-a_{tkz}) \]
and let \(H_t=0\) when \(M_t\le\epsilon\), and otherwise \(H_t=n_t\lceil\log_2(M_t/\epsilon)\rceil\). Put \(H=\sum_tH_t\).
Choosing \(\epsilon_t=\epsilon\) for every type is admissible because the masses sum to one. The HLG guarantee stipulated in the question therefore yields \(Q^*\le H\). This uses the query guarantee associated with [Propositions 1–2 of Boutilier et al.](https://www.cs.toronto.edu/~cebly/Papers/BPPS-aij06.pdf).
Binary-rational encoding gives \(M_t/\epsilon\le n\,2^{O(L)}\), so
\[ H=O\bigl(n(L+\log(n+1))\bigr). \]
Thus polynomially many queries always suffice, although computing an optimal strategy is \(\mathrm{NP}\)-hard.
At a specified transcript, enumerate all Boolean assignments, test feasibility, and evaluate every feasible recommendation–competitor pair using Section 1. If posterior endpoints have bit length at most \(\lambda\), this takes
\[ O\left(\tau\,4^m\operatorname{poly}(m,n,L+\lambda)\right). \]
HLG midpoint queries produce endpoints of bit length \(O(L+H)\). Hence an exact implementation of the independent baseline with tolerances \(\epsilon_t=\epsilon\) has running time
\[ O\left((H+\tau)\,4^m \operatorname{poly}(m,\tau,n,L+H)\right). \]
This implements one admissible baseline; it does not assert polynomial-time optimization over tolerances.
For completeness, arbitrary rational thresholds do not prevent a finite exact search. A deliberately coarse upper bound is
\[ \operatorname{poly}(m,\tau,n,L+s) + 2^{\,2^{\,O(H+m\tau+n+\log(L+2))}}. \]
Here is a justification.
First, if \(B\ge H\), answer yes. Otherwise put \(b=B<H\). Enumerate full binary trees of depth \(b\), label every internal node by a queried entry, and label every leaf by a feasible recommendation for each type. Early termination can be padded with extra queries while retaining the recommendation, because additional information cannot increase maximum regret.
For any fixed labeling, introduce one threshold variable for each internal node. For each leaf and each feasible tuple of competing outcomes, a violating parameter vector is described by:
These are rational linear inequalities in the \(n\) latent parameters and the threshold variables. Requiring no such violating vector is equivalent to validity on the transcript closure: if a continuous loss exceeds \(\epsilon\) at a point in the closure, it also exceeds \(\epsilon\) at a sufficiently nearby consistent point.
Eliminate the \(n\) latent parameters by Fourier–Motzkin elimination, retaining strict inequalities. Each violating set projects to a conjunction of rational linear inequalities in the thresholds. Starting with at most \(2n+b+1\) inequalities, elimination produces at most
\[ (2n+b+2)^{2^{n+1}} \]
inequalities, with coefficient bit lengths bounded by \(2^{O(n)}\operatorname{poly}(L+b)\).
There are at most \(2^{b+m\tau}\) projected violating sets. To avoid all of them, enumerate a choice of one violated defining inequality from each set. Each choice gives a rational linear feasibility problem in the threshold variables.
Strict feasibility is decidable by adding a common positive slack variable and solving a rational linear program. A feasible choice has rational thresholds: a nonempty rational polyhedron has a rational point, and positive slack preserves all strict inequalities.
There are at most \(2^b-1\) threshold variables. Counting tree labelings, elimination output, and inequality choices yields the stated doubly exponential bound. Since \(b<H\), the numerical value of a very large binary-encoded budget never needs to be expanded into a tree.
Both target questions are settled: deciding \(Q^*\le B\) is \(\mathrm{NP}\)-hard, and the optimized independent HLG baseline can be worse by an unbounded factor. The exact complexity class and a tight general running-time bound are not determined by these proofs.
⟨structured verdict parsed — rendered above⟩
The two principal claims are correct: the reduction establishes $\mathrm{NP}$-hardness, and the example establishes an unbounded separation from the optimized independent HLG baseline. The general decision algorithm is also sound in substance. I found two minor omissions in its supporting computational discussion, and no major issue.
A consistent transcript imposes only coordinatewise restrictions. Taking its closure therefore gives a nonempty product of closed intervals, including possibly singleton intervals.
For fixed feasible outcomes $x,y$, an entry used by both outcomes cancels. When their local assignments differ, independence permits the competitor’s entry to attain its upper endpoint and the recommendation’s entry to attain its lower endpoint simultaneously. Independence across factors justifies summing these contributions.
Interchanging maximization over parameters with maximization over feasible competitors is valid because the feasible set is finite. Compactness of the closed parameter box ensures attainment.
Independence between types likewise justifies the weighted sum of individual maximum regrets. Finally, choosing recommendations independently gives exactly the stated stopping condition:
$$\sum_t\mu_t r_t(h)\le\epsilon.$$
These statements use the required model of one shared parameter vector per type. They do not replace that vector with independently varying utilities within a type’s mass.
The feasibility formula has polynomial size and always admits the three fallback outcomes. The utility table has exactly four entries, and all numerical data satisfy the input restrictions.
If $\Phi$ is satisfiable, a feasible outcome with selector $11$ has utility $2$ throughout the uncertainty set. Every other outcome has utility at most $2$, so a zero-query recommendation exists.
If $\Phi$ is unsatisfiable, follow the transcript generated by setting all three uncertain entries to zero. A strategy making at most one query leaves at least two of those entries unqueried. Regardless of its recommendation, one different fallback outcome has an unqueried entry. Raising that entry to $2$ while retaining all other entries at zero preserves the transcript and produces regret $2$.
This reasoning also covers a query to the known entry, a threshold outside the initial interval, and termination without any query.
The proposed two-query strategy is valid in every branch. In a branch answering $p>1$, the posterior closure has lower endpoint $1$, which still gives regret at most $1$. In the final all-yes branch, both competitors have utility at most $1$.
Thus the equivalence
$$\Phi\text{ satisfiable}\quad\Longleftrightarrow\quad Q^*\le1$$
is established. The conclusion is $\mathrm{NP}$-hardness; no membership claim is made.
For an unqueried type, the two recommendations have maximum regrets $c$ and $1-c$, respectively. Since $k\ge2$, the minimax regret is $c$.
After at most one query, at least one type retains this regret. Its weighted contribution is at least $c/4$, exceeding $\epsilon=c/8$. Hence $Q^*\ge2$.
Querying each parameter at $c$ achieves zero regret. Both closed posterior intervals include the boundary $p_t=c$, where the outcomes tie, so closure introduces no problem. Therefore $Q^*=2$.
Every admissible positive tolerance allocation forces both tolerances below $c$. On the consistent parameter value $p_t=0$, midpoint queries leave the interval $[0,2^{-j}]$. The displayed minimax-regret calculation is correct, and for every $j<k$ it equals $c$. Thus neither type can stop before its $k$th query.
Conversely, any no answer among the first $k$ midpoint thresholds makes outcome $1$ optimal throughout the posterior closure. An all-yes sequence reaches upper endpoint $c$, making outcome $0$ optimal. Each type therefore has worst-case count exactly $k$, and the simultaneous vector $p_1=p_2=0$ realizes both counts.
Consequently, optimizing tolerances does not change the baseline count $2k$. The ratio to $Q^*$ is $k$.
This proves an advantage for the permitted strategy class. As the output itself notes, the example does not require adaptive query selection; it also does not isolate mass awareness as the cause of the advantage. That limitation does not invalidate the requested comparison.
Under ordinary explicit binary-rational encoding, $L=\Theta(k)$. The stated $O(L)$ strategy time and coarse $O(k^2+L)$ direct HLG implementation time are consistent with the threshold lengths and query counts.
Choosing every tolerance equal to $\epsilon$ is admissible because the masses sum to one. For $M_t>\epsilon$, the supplied HLG guarantee applies to each type’s independent table-entry intervals and midpoint queries.
Minor issue: the zero-query case $M_t\le\epsilon$ additionally uses the bound $r_t\le M_t$. This is Proposition 1 of the cited source, but the output does not state it explicitly. The source does state that minimax regret is bounded by maxspan; its definition matches the displayed $M_t$. [Boutilier et al., Propositions 1–2](https://www.cs.toronto.edu/~cebly/Papers/BPPS-aij06.pdf)
Minimum clarification: explicitly state that theorem and identify $M_t$ with its maxspan quantity. This supplies the justification for defining $H_t=0$.
The bound $M_t/\epsilon\le n\,2^{O(L)}$ is compatible with explicit binary-rational input lengths. Summing the resulting bounds gives the stated polynomial query bound.
Enumerating recommendation–competitor pairs requires at most $4^m$ pairs per type. Feasibility testing, factor evaluation, and exact rational arithmetic fit the indicated polynomial overhead. Midpoint endpoint lengths grow at most linearly with the number of queries, so the baseline implementation bound follows.
The preliminary comparison with $H$ correctly avoids expanding a large binary-encoded budget.
A strategy of worst-case depth at most $b$ has a finite binary-tree representation. Padding early termination preserves validity because additional information cannot increase maximum regret.
For fixed tree labels, transcript comparisons and weighted utility losses are rational linear inequalities in the latent parameters and threshold variables. Enumerating competitor tuples represents the social maximum correctly.
The closure argument is valid: a strict loss violation at a closure point persists at sufficiently nearby consistent points by continuity. An inconsistent leaf imposes no requirement because its consistent set and closure are empty.
Fourier–Motzkin elimination applies to these finite systems with weak and strict inequalities. The stated inequality-count and coefficient-length bounds are sufficiently coarse. Complementing each projected conjunction by choosing a violated inequality correctly represents avoidance of all violating sets.
Minor issue: “adding a common positive slack variable and solving a rational linear program” leaves the strict-feasibility acceptance test implicit. Merely allowing nonnegative slack would not suffice.
Minimum clarification: specify the LP objective and the acceptance condition that requires strictly positive achievable slack, including how an unbounded objective is handled. This is a routine implementation detail, not missing new mathematics.
The rational-threshold conclusion is sound once positive slack is enforced. The counts of tree labels, projected systems, inequality choices, variables, and coefficient lengths fit the claimed coarse doubly exponential bound.
The output therefore resolves both target questions. Neither minor omission affects the hardness reduction or the baseline separation.
⟨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.