Answer: Computing the exact optimal value is \(\mathrm{NP}\)-hard, even for \(k=2\). An optimal executable stopping rule is computable in polynomial time.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 is finite and upon termination re- turns the optimal strategy of the representative agent given a set of known opportunities.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite offer set \(X\) with rational probabilities \(p_x\), buyer types \(T\) with rational masses \(\mu_t\) summing to \(1\), total population mass \(M>0\), and per-search cost \(\kappa(M)>0\), compute an optimal policy and its expected net utility from an initial set of known offers. A state records each type’s best known offer \(r_t\in X\); stopping yields \(M\sum_{t\in T}\mu_t U_t(r_t)\), while continuing pays \(\kappa(M)\), draws an offer according to \(p\), and updates each type’s record if its utility improves. In B2C, each offer can serve all mass of every type.
Given a nonempty offer set \(X\subseteq\mathbb{Q}^k\), let \(m=|X|\); supply binary-rational probabilities \(p_x\geq0\) with \(\sum_{x\in X}p_x=1\).
A society is given by its support: the list of \(\tau\) buyer types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. Supply total mass \(M\in\mathbb{Q}_{>0}\), the per-search cost \(c=\kappa(M)\in\mathbb{Q}_{>0}\), and explicit utility tables \(U_t:X\to\mathbb{Q}\). Attributes are oriented so that \(x\leq y\) coordinatewise implies \(U_t(x)\leq U_t(y)\) for every type.
Initially a nonempty set \(K\subseteq X\) is known at no further cost, and each record \(r_t\) maximizes \(U_t\) over \(K\). Every known offer remains available and can serve all mass of every type.
At each stage, stop and obtain \(G(r)=M\sum_t\mu_tU_t(r_t)\), or pay \(c\), draw one offer independently from \(p\), and replace every record whose utility strictly improves. Retain the old record on utility ties; use a fixed ordering for initial ties. There is no outside option, discounting, or finite horizon.
A policy assigns stop or continue to each reachable record state. Its objective is \(\mathbb{E}[G(r_{\mathrm{stop}})-cH]\), where \(H\) counts additional searches; policies with infinite expected search count have value \(-\infty\). An optimal policy may be represented by an executable stopping rule rather than an exhaustive state table. Let \(L\) be the total binary input length.
Can the exact optimal expected net utility and an optimal policy be computed in time polynomial in \(m,\tau,k,L\), or is computing the optimal value NP-hard?
For finite lists of buyers, a terminating algorithm returning an optimal B2C search strategy is established, without a polynomial-time guarantee. [Sarne–Kraus](https://cdn.aaai.org/AAAI/2005/AAAI05-026.pdf)
A later parallel-search algorithm has a running-time bound polynomial in the explicitly enumerated state count and a bound on simultaneous searches; this does not establish polynomial time in the support input above. [Manisterski–Sarne–Kraus](https://u.cs.biu.ac.il/~sarned/pub/manisterskietaljair08.pdf)
No result settling this exact rational-mass problem was located.
Computing the exact optimal value is \(\mathrm{NP}\)-hard, even with two attributes, utilities in \(\{0,1\}\), dyadic probabilities and masses, and a singleton initially known set.
However, an optimal policy always has a polynomial-time executable stopping rule. Thus the difficulty lies in computing its exact expected payoff.
We prove both statements.
For a record state \(r\), define its expected one-search utility gain by
\(\displaystyle d(r)=M\sum_{t=1}^{\tau}\mu_t\sum_{x\in X}p_x\max\{U_t(x)-U_t(r_t),0\}.\)
Proposition. The following policy is optimal:
\(\displaystyle \text{continue if }d(r)>c,\qquad \text{stop if }d(r)\leq c.\)
Fix an infinite sequence of independent draws from \(p\). Let \(r_h\) denote the records after processing the first \(h\) draws, whether or not a particular policy would already have stopped. Put \(G_h=G(r_h)\), and let \(\mathcal F_h\) denote the information from those draws.
Every record utility is nondecreasing. Consequently, for every draw sequence,
\(\displaystyle d(r_{h+1})\leq d(r_h).\)
Indeed, increasing \(U_t(r_t)\) can only decrease each term \(\max\{U_t(x)-U_t(r_t),0\}\), and all its weights are nonnegative.
Define
\(\displaystyle S=\inf\{h\geq0:d(r_h)\leq c\}.\)
First, \(S\) has finite expectation. Let \(X_+=\{x\in X:p_x>0\}\), and let \(T_x\) be the first occurrence time of \(x\). After every offer in \(X_+\) has appeared, no subsequent draw can improve any record, so \(d=0\). Hence
\(\displaystyle S\leq\max_{x\in X_+}T_x,\qquad \mathbb E[S]\leq\sum_{x\in X_+}\mathbb E[T_x] =\sum_{x\in X_+}\frac1{p_x}<\infty.\)
Now consider any competing policy whose search count \(H\) has finite expectation. Its objective is \(J(H)=\mathbb E[G_H-cH]\). Conditional on \(\mathcal F_h\), the expected increment \(G_{h+1}-G_h\) is \(d(r_h)\). Therefore,
\(\displaystyle J(H)=G_0+\sum_{h=0}^{\infty} \mathbb E\!\left[\mathbf1_{\{H>h\}}\bigl(d(r_h)-c\bigr)\right]. \)
To justify this identity, telescope the utility increments and use that \(\{H>h\}\) is \(\mathcal F_h\)-measurable. All record utilities, and thus all \(d(r_h)\), are bounded because the tables are finite. The series is absolutely integrable since \(\mathbb E[H]<\infty\).
The same identity holds for \(S\). For each \(h\), pointwise,
\(\displaystyle \bigl(\mathbf1_{\{S>h\}}-\mathbf1_{\{H>h\}}\bigr) \bigl(d(r_h)-c\bigr)\geq0. \)
There are two cases:
Taking expectations and summing yields \(J(S)\geq J(H)\). Policies with infinite expected search count have value \(-\infty\) by the problem’s convention, so they cannot improve on \(S\). This proves the proposition.
Evaluating \(d(r)\) uses \(O(m\tau)\) rational arithmetic operations. Each term uses input rationals and record utilities taken directly from the input tables; exact summation and comparison have polynomial bit complexity in \(L\).
Thus an executable optimal policy can be constructed in polynomial time, and each stop/continue decision can be evaluated in polynomial time. This does not compute its exact expected payoff.
We reduce from the standard \(\mathrm{NP}\)-complete Set Cover problem. ([Karp, 1972](https://doi.org/10.1007/978-1-4684-2001-2_9))
An instance consists of a nonempty universe \(E=\{e_1,\ldots,e_u\}\), sets \(S_1,\ldots,S_n\subseteq E\), and a budget \(b\), asking whether at most \(b\) sets cover \(E\). We restrict to \(n\geq1\) and \(1\leq b\leq n\). These restrictions preserve hardness: the excluded cases are immediately decidable and can be mapped to fixed yes or no instances satisfying the restrictions.
We construct a search instance and a rational threshold \(\theta\) such that
\(\displaystyle E\text{ has a cover using at most }b\text{ sets} \quad\Longleftrightarrow\quad V^*\geq\theta, \)
where \(V^*\) is the optimal expected net utility.
Let
\(\displaystyle q=2^{\lceil\log_2u\rceil}.\)
For each element \(e_t\), introduce a type with weight
\(\displaystyle w_t= \begin{cases} 1,&t<u,\\ q-u+1,&t=u, \end{cases} \qquad \mu_t=\frac{w_t}{q}. \)
Every mass is positive and dyadic, and \(\sum_t\mu_t=1\). Set \(M=q\) and \(c=\frac12\). Consequently, type \(t\)’s contribution to total utility is \(w_tU_t(r_t)\).
Introduce the following offers:
Take \(K=\{x_0\}\). All utilities belong to \(\{0,1\}\). When every element is covered, total utility equals \(\sum_tw_t=q\).
There are \(m=n+2\) offers. Index them by \(i=0,\ldots,n+1\), with \(x_\star=x_{n+1}\), and assign
\(\displaystyle x_i=(i,n+1-i)\in\mathbb Q^2.\)
Distinct offers are coordinatewise incomparable: their first coordinates increase while their second coordinates decrease. Thus the utility tables satisfy the required coordinatewise monotonicity.
They also extend to coordinatewise nondecreasing functions on all of \(\mathbb Q^2\), by defining
\(\displaystyle \widetilde U_t(z)= \max\bigl(\{0\}\cup\{U_t(x):x\in X,\ x\leq z\}\bigr). \)
At an offer \(x_i\), the only offer coordinatewise below it is \(x_i\) itself, so this extension agrees with the table.
Define
\(\displaystyle \ell=\lceil\log_2(n+1)\rceil,\qquad B=2^{\,2+(b+1)\ell},\qquad \varepsilon=B^{-1}. \)
Set
\(\displaystyle p_{x_0}=0,\qquad p_{x_i}=\varepsilon\quad(1\leq i\leq n),\qquad p_{x_\star}=1-n\varepsilon. \)
These probabilities are dyadic and sum to one. Moreover,
\(\displaystyle B>4n^{b+1},\qquad n\varepsilon<\frac14,\qquad p_{x_\star}>\frac34.\)
A type’s record utility equals one precisely when its element has been covered by a drawn set offer, or the universal offer has appeared.
If some element remains uncovered, its type has weight at least one. Drawing \(x_\star\) improves that type’s contribution by at least one. Hence
\(\displaystyle d(r)\geq p_{x_\star}>\frac34>c.\)
If every element is covered, every record utility is already maximal, so \(d(r)=0\).
By the proposition, the optimal policy therefore continues until every element is covered, then stops. Let \(H^*\) be its search count. The universal offer guarantees
\(\displaystyle \mathbb E[H^*]\leq\frac1{p_{x_\star}}<\frac43.\)
Its terminal utility is always \(q\), giving
\(\displaystyle V^*=q-\frac12\mathbb E[H^*].\)
Thus the hardness holds even though the optimal policy has bounded expected search count.
For each \(j\geq0\), let \(C_j\) count the ordered tuples
\(\displaystyle (i_1,\ldots,i_j)\in\{1,\ldots,n\}^j\)
whose associated sets cover \(E\). Put \(A_j=n^j-C_j\). Because \(E\) is nonempty, \(C_0=0\) and \(A_0=1\).
The event \(H^*>j\) occurs exactly when the first \(j\) draws are set offers whose union fails to cover \(E\). Each specified tuple of set offers has probability \(\varepsilon^j\). Therefore,
\(\displaystyle \Pr(H^*>j)=A_j\varepsilon^j.\)
The tail-sum identity for a nonnegative integer-valued random variable gives
\(\displaystyle \mathbb E[H^*] =\sum_{j=0}^{\infty}A_j\varepsilon^j. \)
Since \(n\varepsilon<1\), define
\(\displaystyle D=\frac1{1-n\varepsilon}-\mathbb E[H^*] =\sum_{j=0}^{\infty}C_j\varepsilon^j. \)
The series converge absolutely, because \(0\leq C_j\leq n^j\).
If a cover uses \(r\leq b\) sets, then \(r\geq1\). Order those sets and repeat one of them until obtaining a covering tuple of length \(b\). Thus \(C_b\geq1\), implying
\(\displaystyle D\geq\varepsilon^b.\)
If no cover uses at most \(b\) sets, then \(C_j=0\) for every \(j\leq b\). Indeed, a covering tuple of length \(j\) would give a cover consisting of at most \(j\) distinct sets.
Consequently,
\(\displaystyle D\leq \sum_{j=b+1}^{\infty}n^j\varepsilon^j =\frac{(n\varepsilon)^{b+1}}{1-n\varepsilon}. \)
Using \(n\varepsilon<\frac14\) and \(B>4n^{b+1}\), we obtain
\(\displaystyle D< \frac43\frac{n^{b+1}}{B^{b+1}} < \frac13\,B^{-b} = \frac13\,\varepsilon^b. \)
In particular, no instances satisfy \(D<\varepsilon^b\).
Define the rational number
\(\displaystyle \theta= q-\frac1{2(1-n\varepsilon)}+\frac{\varepsilon^b}{2}. \)
Since
\(\displaystyle V^*= q-\frac1{2(1-n\varepsilon)}+\frac D2, \)
the two cases prove exactly
\(\displaystyle V^*\geq\theta \quad\Longleftrightarrow\quad E\text{ has a cover using at most }b\text{ sets}. \)
The construction has \(m=n+2\), \(\tau=u\), and \(k=2\). Its utility tables, coordinates, masses, and total mass have polynomial encoding length.
Also,
\(\displaystyle \log_2B=2+(b+1)\ell=O(b\log(n+1)).\)
Thus the probabilities have polynomial binary length. The threshold involves \(B^b\) and \(B-n\), so its binary length is \(O(b^2\log(n+1)+\log u)\), also polynomial because \(b\leq n\). The entire reduction is computable in polynomial time.
For completeness, the constructed optimal value is rational. If \(T(A)\) is the expected remaining search count when the covered elements are \(A\subseteq E\), then \(T(E)=0\), and for \(A\neq E\),
\(\displaystyle T(A)= \frac{ 1+\varepsilon\sum_{i:S_i\not\subseteq A}T(A\cup S_i) }{ 1-\varepsilon|\{i:S_i\subseteq A\}| }. \)
This follows by conditioning on the next draw and moving self-loop terms to the left. Every successor in the numerator strictly contains \(A\), and the denominator is at least \(1-n\varepsilon>0\). Backward induction over subsets therefore gives rational \(T(A)\), and hence rational \(V^*\).
We have proved that deciding whether \(V^*\) is at least a supplied rational threshold is \(\mathrm{NP}\)-hard. A polynomial-time algorithm returning the exact value as a binary rational would solve this decision problem by rational comparison. Therefore exact value computation is \(\mathrm{NP}\)-hard, while constructing an optimal executable policy is polynomial-time solvable.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the task: exact optimal-value computation is \(\mathrm{NP}\)-hard, even under the stated restrictions, while an optimal executable stopping rule can be constructed in polynomial time. I found no major or minor mathematical issues.
1. Optimal stopping rule
The definition of \(d(r)\) correctly accounts for every type’s improvement from the same draw. Linearity of expectation applies despite the correlation between types’ improvements.
The pathwise inequality \(d(r_{h+1})\leq d(r_h)\) is valid: record utilities never decrease, each positive-part expression decreases as its record utility increases, and all weights are nonnegative. Utility ties leave these quantities unchanged.
The stopping time \(S\) has finite expectation. The positive-probability support is nonempty, each \(T_x\) has geometric mean \(1/p_x\), and observing every positive-probability offer leaves no possible improvement from subsequent draws. Zero-probability offers do not affect this argument.
For every competing policy with finite expected search count, \(H\) is a stopping time for the draw filtration, so \(\{H>h\}\) is measurable before draw \(h+1\). The conditional expected utility increment is therefore exactly \(d(r_h)\).
The infinite-series identity for \(J(H)\) is justified as written. Finite utility tables uniformly bound all increments and all \(d(r_h)\); multiplying this bound by \(\mathbb E[H]<\infty\) establishes absolute integrability. This also covers negative utility entries and the case \(H=0\).
The pointwise comparison is correct in both cases:
Consequently, summation gives \(J(S)\geq J(H)\). Policies with infinite expected search count are handled by the task’s explicit convention. Stopping when \(d(r)=c\) is therefore optimal as claimed; uniqueness is neither needed nor asserted.
2. Polynomial-time policy representation
Evaluating \(d(r)\) requires \(O(m\tau)\) rational arithmetic operations. Every record utility is an input-table entry, so repeated searches do not increase the bit length of stored utilities. Products, sums, and the comparison with \(c\) have polynomial bit complexity.
The conclusion concerns constructing the executable rule and evaluating each decision. It does not assert a polynomial bound on the number of searches. This is exactly the policy representation permitted by USER_TASK.
3. Reduction source and admissibility
The cited source establishes the \(\mathrm{NP}\)-completeness of finite Set Cover. The prover states the relevant decision problem precisely, and the restrictions to a nonempty universe, \(n\geq1\), and \(1\leq b\leq n\) preserve hardness. The excluded cases are polynomially decidable, as claimed. [Karp’s paper, reproduced](https://www.scribd.com/document/889712245/Karp-Paper-1972)
All constructed inputs satisfy the task:
Distinct offer coordinates are incomparable, so the required monotonicity holds. The optional extension to all of \(\mathbb Q^2\) is also valid: its defining maximum is nondecreasing under coordinatewise increases and agrees with every table entry.
Neither duplicate set contents nor empty sets cause a problem: offers remain distinct through their coordinates.
4. Probability bounds
Since \(2^\ell\geq n+1>n\), the displayed definition gives
\(B=4(2^\ell)^{b+1}>4n^{b+1}\).
Thus every probability is nonnegative, all probabilities are dyadic, and they sum to one.
The bounds \(n\varepsilon<1/4\) and \(p_{x_\star}>3/4\) follow. They remain valid when \(n=1\) and \(b=1\).
5. Optimal behavior in the constructed instance
Whenever an element remains uncovered, its type has contribution weight at least one. The universal offer therefore produces expected aggregate gain at least \(p_{x_\star}>c\). Once all elements are covered, every utility is maximal and \(d(r)=0\).
The proposition consequently identifies the optimal stopping time as the first complete coverage time. That time is bounded by the first universal-offer occurrence, giving the stated finite expectation bound.
Terminal aggregate utility is always \(q\), so
\(V^*=q-\frac12\mathbb E[H^*]\)
is correct.
6. Tail probabilities and separation
For every \(j\geq0\), the event \(H^*>j\) is exactly the event that the first \(j\) draws are set offers whose union does not cover the universe. Coverage is persistent, so this description correctly includes all earlier stopping conditions.
Each ordered tuple has probability \(\varepsilon^j\), yielding
\(\Pr(H^*>j)=A_j\varepsilon^j\).
The base case is correct because the universe is nonempty: \(C_0=0\) and \(A_0=1\).
The tail-sum identity applies to this nonnegative integer-valued stopping time. Both subsequent series converge absolutely because \(n\varepsilon<1\), so their subtraction is justified.
For a yes instance, any nonempty cover of size at most \(b\) can be padded by repetitions to length \(b\). Therefore \(C_b\geq1\) and \(D\geq\varepsilon^b\).
For a no instance, a covering tuple of length at most \(b\) would supply a cover of at most \(b\) distinct sets. Hence the claimed coefficients vanish. The geometric-tail calculation and both strict inequalities are correct:
\(D<\frac43 n^{b+1}B^{-(b+1)}<\frac13 B^{-b}\).
The threshold substitution preserves the inequality direction. Yes instances satisfy \(V^*\geq\theta\), while no instances satisfy \(V^*<\theta\). Equality at the threshold causes no ambiguity.
7. Encoding size and exact-value conclusion
The construction uses explicitly listed types and utility tables of polynomial size. Coordinate lengths, masses, and total mass also have polynomial encoding length.
The probability denominator has bit length \(O(b\log(n+1))\), and \(B^b\) has bit length \(O(b^2\log(n+1))\). Since \(b\leq n\), the threshold and the entire reduction have polynomial binary length. The separation does not depend on an exponentially long input encoding.
The recurrence for \(T(A)\) correctly includes the cost of the next search, removes self-loops, and omits the universal successor because its remaining search count is zero. Its denominator is positive, and every numerator successor strictly enlarges \(A\). The rationality conclusion follows from the stated finite backward induction.
Finally, a polynomial-time algorithm outputting the exact value as a binary rational would permit polynomial-time comparison with the constructed threshold. The reduction therefore establishes the claimed hardness of exact-value computation. No claim of membership in \(\mathrm{NP}\) or \(\mathrm{NP}\)-completeness is made.
Repair feedback: none required. The argument establishes both claimed results under the task’s supplied-cost and explicit-support input model.
⟨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.