Answer: NP-complete. The candidate statistic suffices. Tight uniform worst-case history memory is \(\Theta(\log s)\) with an external round counter, and \(\Theta(\log s+\log k)\) when execution position must also be retained.
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateWith correlated valuations, the allocation matrix along with the agents who have not yet re- ceived an offer is sufficient to determine an optimal policy, whatever the design objective. Moreover, there exists a unit-demand setting with correlated valuations where optimal policies must use information of size Ω(min{n, m} log (max{n, m})). For sufficiency, the allocation matrix and remaining agents always suffices to recover the entire history of observations of any (deterministic) policy.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) indivisible item types, a finite support \(T\) of unit-demand valuation types, per-capita supplies \(q_j\), and a finite rational prior over latent states \(\omega\) specifying type masses \(\mu^\omega_{g,t}\) in each of finitely many public cohorts \(g\), find an expected-welfare-maximizing sequential cohort pricing policy. Each round visits an unvisited cohort, posts item prices, allocates each buyer an integral utility-maximizing bundle subject to remaining supply, and observes only aggregate bundle masses. Determine whether the posterior over \(\omega\), aggregate allocations, remaining cohort masses, and supplies suffice for optimal continuation, and give tight policy-state bounds in \(m\), \(\tau=|T|\), the number of cohorts, the number of latent states, and input bit length \(L\).
There are \(m\geq1\) indivisible item types, \(k\geq1\) public cohort labels, and \(s\geq1\) latent states. The input gives nonnegative rational unit-demand value vectors \(v_t\), supplies \(q_j\), a positive rational prior \(\pi_\omega\), and nonnegative rational masses \(\mu^\omega_{g,t}\), with \(\sum_\omega\pi_\omega=1\) and \(\sum_{g,t}\mu^\omega_{g,t}=1\) for every \(\omega\).
A society is given by its support: the list of its types with positive mass, each mass a binary rational. Here \(T\) is the union of the conditional supports and \(\tau=|T|\) is the support size, not the number of possible types; zero entries in the conditional mass table denote absence. All numerical input is binary rational, and \(L\) is the total input bit length.
Nature draws one unobserved \(\omega\). Each round selects an unvisited cohort and posts nonnegative rational item prices, fixed throughout that round; every cohort is visited once. Buyers maximize quasilinear utility over available bundles, paying the sum of item prices. Ties favor smaller bundles, then lexicographic item order, so each buyer receives either nothing or one integral item.
Within a selected cohort, use proportional serial service: as \(u\) runs from \(0\) to \(1\), serve mass \(\mu^\omega_{g,t}\,du\) of each type. Remove an item when its supply reaches zero and recompute choices for subsequent buyers. Thus individual allocations are integral although allocation masses may be fractional.
Only the cohort's final masses receiving each item or nothing are observed; types, within-round exhaustion times, and realized welfare are hidden. Policies know their previous actions and these observations. Welfare is the integral of allocated value, averaged over the prior.
The candidate continuation statistic consists of the posterior on \(\omega\), the cohort-indexed aggregate allocation matrix, remaining supplies, and the conditional remaining cohort masses for each \(\omega\) (the input masses for unvisited cohorts, zero for visited cohorts), together with the unvisited cohort labels.
For a rational threshold \(B\), is deciding whether some policy achieves expected welfare at least \(B\) in P or NP-hard?
Does the candidate statistic suffice for optimal continuation, and what are the tight worst-case bounds on the minimum history-memory bits needed by an optimal deterministic policy?
State running times and memory bounds in \(m,\tau,k,s,L\); history memory excludes the read-only input and fixed policy description.
For finite agents with correlated valuations, allocation information and unvisited agent identities support an optimal policy; some unit-demand instances require \(\Omega(\min\{n,m\}\log(\max\{n,m\}))\) history-information bits, where \(n\) is the number of agents. [Brero et al.](https://arxiv.org/html/2010.01180v2)
No result settling this exact continuum cohort problem was located in the literature search.
The welfare-threshold problem is NP-complete, already with \(m=s=1\) and \(\tau=2\).
The candidate statistic suffices for optimal continuation. In fact, the posterior, remaining supplies, and unvisited cohort labels suffice.
For history memory, I count all persistent history-dependent controller state, including a history-dependent program counter. The read-only input and fixed policy description are excluded. Under this convention:
These are sharp uniform worst-case bounds: the dependence on \(s\) is necessary already for \(m=1,\tau=3,k=3\), and the dependence on \(k\) is necessary without an external round counter. They are worst-case statements, not lower bounds for every parameter tuple; for example, with an external round counter, \(s=1\) requires no history memory.
Let \(V=\max_{t,j}v_{t,j}\). Replacing every price exceeding \(V+1\) by \(V+1\) preserves all choices: such an item has strictly negative utility for every type and is never purchased.
We may therefore restrict prices to the rational cube \([0,V+1]^m\).
For each type \(t\), consider the comparisons
\(v_{t,j}-p_j=0\),
and
\((v_{t,j}-p_j)-(v_{t,\ell}-p_\ell)=0\), for \(j<\ell\).
There are
\(H=\tau m+\tau\binom m2=\tau m(m+1)/2\)
such hyperplanes. A sign pattern specifies which item utilities are positive and their complete weak ordering. Together with the prescribed tie-breaking rule, it determines the chosen alternative for every subset of available items.
Consequently, prices sharing a sign pattern induce identical within-round behavior, including after item exhaustion.
For every feasible sign pattern, choose one rational representative. This gives a menu \(\mathcal P\) with
\(|\mathcal P|\le A:=3^H\).
The representatives have polynomial bit length. To see this explicitly, impose the required equalities and replace each strict inequality \(f(p)>0\) by \(f(p)\ge\delta\), with \(0\le\delta\le1\). Maximize \(\delta\) over the bounded price cube. A pattern containing strict inequalities is feasible precisely when the optimum is positive. Rational linear programming supplies a rational optimal vertex whose encoding length is polynomial in \(m,\tau,L\). Patterns containing only equalities are handled by ordinary rational feasibility.
Thus \(\mathcal P\) can be constructed in time
\(3^{\tau m(m+1)/2}\operatorname{poly}(m,\tau,L)\).
This menu works simultaneously for every cohort, latent state, and residual inventory.
Fix a cohort, state, inventory, and menu price vector. During a phase with unchanged availability, every type has a fixed choice. The consumption rate of item \(j\) is
\(a_j=\sum_{t:\,t\text{ chooses }j}\mu^\omega_{g,t}\).
If \(r_j\) is its current supply, the next phase lasts
\(\Delta=\min\bigl(\{1-u\}\cup\{r_j/a_j:a_j>0\}\bigr)\).
After this interval, update allocations and supplies and remove every exhausted item. Every phase ending before \(u=1\) exhausts at least one item. Hence a round has at most \(m+1\) phases.
The arithmetic remains polynomial in the input length, despite fractional exhaustion times. Here is a denominator bound.
Let \(D\) be the product of all numerical input denominators. Its binary length is \(O(L)\), and all input rationals have denominator dividing \(D\). Write phase rates as \(a_j=A_j/D\), where \(0\le A_j\le D\).
Suppose current supplies and \(u\) share denominator \(E\), with \(r_j=R_j/E\) and \(u=U/E\). If item \(j\) determines the next exhaustion event, then
\(\Delta=DR_j/(EA_j)\).
The updated supply of item \(\ell\) and updated service time are
\(r'_\ell=(A_jR_\ell-A_\ell R_j)/(EA_j)\),
\(u'=(A_jU+DR_j)/(EA_j)\).
Allocated type masses also have denominator dividing \(EA_j\). Thus the common denominator need only be multiplied by \(A_j\le D\).
For a phase ending at \(u=1\), multiplication by \(D\) suffices. Across \(k\) rounds there are at most \(k(m+1)\) such multiplications. Therefore supplies, observations, and allocation masses have bit length
\(O((k(m+1)+1)L)\).
Multiplying by values and summing welfare adds only polynomially many bits. Summing the \(s\) state-specific welfare values with their rational prior weights is also polynomial-time exact arithmetic.
A complete execution in one state uses at most
\(O(k(m+1)\tau m)\)
rational operations for choices and phase updates. Simulating all states, checking history consistency, and comparing expected welfare with \(B\) takes \(\operatorname{poly}(m,\tau,k,s,L)\) bit operations.
For a fixed deterministic policy, each latent state produces one deterministic execution. At a fixed depth, there are therefore at most \(s\) reachable histories. A policy has at most \(1+ks\) reachable history nodes.
A polynomial-size certificate can specify a cohort and a polynomial-length rational price vector at each such node. Equivalently, it can specify \(ks\) actions indexed by latent state and round.
The verifier:
The consistency check is essential: actions may depend on observable history, but not directly on the hidden state. Once this check passes, the simulated actions define a legitimate deterministic policy on all reachable histories.
The finite menu also proves that an optimal deterministic policy exists. Backward induction maximizes over finitely many cohort-price actions; randomizing among actions cannot improve their maximum expected continuation value.
Hence the decision problem belongs to NP.
One explicit exact algorithm enumerates all state-by-round action tables over the \(k|\mathcal P|\) possible actions and performs the preceding verification. Its running time is bounded by
\(\bigl(k\,3^{\tau m(m+1)/2}\bigr)^{ks}\operatorname{poly}(m,\tau,k,s,L)\).
This is an upper bound, not a claim of optimal running time.
Reduce from SUBSET SUM with positive integer weights \(a_1,\ldots,a_n\) and target \(b\), restricted to \(0<b<\sum_i a_i\). The excluded cases can be decided directly.
Let \(C=\sum_i a_i\). Construct \(k=n\) cohorts, one item, and one latent state. There are exactly two types, valued \(2\) and \(1\).
In cohort \(i\), give the value-\(2\) type mass
\(h_i=1/(2n)\),
and the value-\(1\) type mass
\(\ell_i=a_i/(2C)\).
The total mass is \(1\), since \(\sum_i h_i=\sum_i\ell_i=1/2\).
Set supply and threshold to
\(q=1/2+b/(2C)\),
\(B=1+b/(2C)\).
The construction has polynomial binary encoding length.
Let \(x_H\) and \(x_L\) denote the total allocated high- and low-value masses. Feasibility gives
\(x_H\le1/2\), and \(x_H+x_L\le q\).
Consequently,
\(W=2x_H+x_L=x_H+(x_H+x_L)\le1/2+q=B\).
Equality holds precisely when
\(x_H=1/2\), and \(x_H+x_L=q\).
Thus attaining \(B\) requires serving all high-value mass and allocating low-value mass exactly \(b/(2C)\).
For the single item, prices have three possible effects:
Every cohort has positive high-value mass. Therefore, attaining \(B\) rules out \(p\ge2\) in any cohort.
It also rules out exhaustion at any time \(u<1\) within a cohort: such exhaustion leaves the positive high-value mass \(h_i(1-u)\) unserved. Likewise, exhaustion cannot occur before any later cohort containing high-value buyers.
Hence, under a policy attaining \(B\), every cohort completes its service without premature exhaustion. Its low-value allocation is therefore either its whole mass \(\ell_i\), when \(p<1\), or zero, when \(1\le p<2\).
For \(I=\{i:p_i<1\}\), equality consequently implies
\(\sum_{i\in I}\ell_i=b/(2C)\),
or equivalently,
\(\sum_{i\in I}a_i=b\).
Conversely, suppose \(\sum_{i\in I}a_i=b\). Post price \(0\) in cohorts in \(I\), and price \(1\) in all other cohorts, visiting them in any order.
The total purchasing mass is exactly
\(\sum_i h_i+\sum_{i\in I}\ell_i=q\).
Before the last cohort finishes, the purchasing mass still to be served is positive, because every unvisited cohort contains positive high-value mass. Thus no premature exhaustion occurs. All high-value mass and exactly the prescribed low-value mass are allocated, attaining \(B\).
The threshold is attainable if and only if the SUBSET SUM instance is positive. Together with NP membership, this proves NP-completeness.
Let a reachable history have posterior \(\beta\), remaining inventory \(r\), and unvisited labels \(U\).
Conditional on a latent state \(\omega\), an action \((g,p)\) has a deterministic:
These depend only on \(\omega,r,g,p\) and the input masses. In particular, conditional remaining masses are the input masses for labels in \(U\).
If the observation is \(o\), the posterior update is
\(\beta'_\omega= \frac{\beta_\omega\,\mathbf 1\{O(\omega,r,g,p)=o\}} {\sum_\nu\beta_\nu\,\mathbf 1\{O(\nu,r,g,p)=o\}}\).
The inventory update subtracts the observed item-allocation masses, and \(U'=U\setminus\{g\}\).
Therefore two histories with the same \((\beta,r,U)\) have identical immediate expected rewards and identical distributions of successor states under every action. Backward induction gives identical optimal continuation values and permits the same optimal continuation action.
Past welfare need not be included: welfare is additive, so its conditional expectation is a constant when optimizing the continuation.
The candidate statistic contains \((\beta,r,U)\), so it suffices. Its cohort-indexed allocation matrix and conditional remaining-mass table are redundant once these three components are available.
Moreover, if \(S\) is the set of states consistent with a history, then
\(\beta_\omega=\pi_\omega/\sum_{\nu\in S}\pi_\nu\) for \(\omega\in S\),
and \(\beta_\omega=0\) otherwise. Thus posterior weights do not require arbitrary precision beyond the rational input and the consistent-state set.
Fix an optimal deterministic policy. At depth \(d\), its reachable histories partition the latent states into at most \(s\) nonempty sets: every state follows exactly one history.
Store the current node’s index in this depth-specific list. The fixed policy description contains the action and observation-transition tables. With \(d\) externally available, this needs at most
\(\lceil\log_2 s\rceil\)
persistent history bits.
Without an external round counter, index nodes across the entire tree. There are at most \(1+ks\), giving
\(\lceil\log_2(1+ks)\rceil\)
bits.
These bounds concern retained history information. Exact simulation and observation processing can additionally use polynomial arithmetic workspace, as established in Section 2.
Fix an integer \(r\ge2\). Use \(s=r^2\) equally likely states, indexed by \((i,j)\in\{1,\ldots,r\}^2\), one item of supply \(q=1/8\), and three cohorts \(D_1,D_2,C\).
There are three types, with values \(0,1,4\).
Define distinct rational numbers
\(d_i=1/8+i/(16(r+1))\).
In state \((i,j)\):
All masses are nonnegative and sum to \(1\). Also,
\(5/8<M_{ij}<3/4\),
so \(M_{ij}>q>a_{ij}\).
The diagnostic cohorts never purchase at nonnegative prices. Their observations reveal \(i\) and \(j\), respectively, through their masses receiving nothing, without changing inventory.
In \(C\), the possible welfare values are:
\(W_{\mathrm{both}}=q(1+3a_{ij}/M_{ij})\).
\(W_{\mathrm{high}}=4a_{ij}\).
When \(i=j\),
\(W_{\mathrm{high}}=1/4\),
whereas
\(W_{\mathrm{both}}< (1/8)(1+(3/16)/(5/8))=13/80<1/4\).
When \(i\ne j\),
\(W_{\mathrm{high}}=1/16\),
whereas \(W_{\mathrm{both}}>1/8>1/16\).
Thus the uniquely optimal price class is high-only exactly when \(i=j\).
Visiting both diagnostics first attains the statewise maximum in every state. Therefore its expected welfare is optimal.
Every optimal policy must visit both diagnostics before \(C\). After seeing fewer than both, both equality and inequality remain possible with positive conditional probability. No single price class attains both statewise maxima; taking \(C\) then produces a strict expected loss.
Now consider the retained controller states after its first diagnostic. If two distinct indices \(i\ne i'\) produced the same controller state, give the second diagnostic index \(i\). The second observation would then be identical in states \((i,i)\) and \((i',i)\), and inventory and unvisited labels would also be identical. A deterministic controller starting from the same retained state must make the same final price-class choice. But optimality requires high-only in the first state and both-types in the second—a contradiction.
There must consequently be at least \(r\) distinguishable retained states, requiring
\(\lceil\log_2 r\rceil=\Omega(\log s)\)
history bits. This remains a lower bound even when current observations, inventory, and unvisited labels are externally readable: before the second diagnostic, those physical states do not encode the first index.
The family has fixed \(m=1,\tau=3,k=3\), and polynomial input length in \(r\). Non-square values of \(s\) can be accommodated by duplicating latent states and splitting their prior weights; taking \(r=\lfloor\sqrt s\rfloor\) preserves the asymptotic lower bound.
Without an external round counter or other externally supplied history state, the controller must also distinguish enough execution positions to output \(k\) different cohort labels. If two pre-action controller states were identical, their deterministic next actions would select the same label, violating the requirement to visit each cohort exactly once.
Hence at least \(k\) controller states, or \(\lceil\log_2 k\rceil\) bits, are necessary.
Adding empty cohorts to the preceding construction preserves its information lower bound and permits arbitrary \(k\ge3\). The combined requirement is
\(\Omega(\max\{\log s,\log k\})=\Omega(\log s+\log k)\),
matching the upper bound up to constants.
The cited [finite-agent result](https://arxiv.org/html/2010.01180v2) is compatible with these bounds: a large allocation-history lower bound can coexist with a logarithmic bound in the number of explicitly supported latent profiles.
⟨structured verdict parsed — rendered above⟩
The NP-completeness claim and sufficiency of the candidate statistic are correct. The memory bounds are supported under the stated convention that all persistent controller state is counted, with minor clarification needed about externally readable observations and the meaning of “sharp.”
1. Finite price menu
The price truncation is valid. An item priced above \(V+1\) has strictly negative utility for every type, and changing its price to \(V+1\) preserves that property.
The listed comparisons determine every type’s utility ordering, including ties with the empty bundle. Consequently, they determine choices from every available-item subset. This is sufficient to preserve behavior after exhaustion, not merely initial choices.
The count \(H=\tau m(m+1)/2\) is correct, and \(3^H\) is a valid upper bound on feasible sign patterns; independence of the hyperplanes is unnecessary.
The rational-representative argument is sound:
Thus the finite-menu construction and its stated exponential running-time bound are justified.
2. Exact simulation and arithmetic
The phase simulation correctly implements proportional serial service. During a phase, fixed choices give constant consumption rates. The next event is either completion of service or exhaustion of an item. Simultaneous exhaustions are handled by removing every exhausted item.
There are at most \(m\) exhaustion events and one final service-completion phase per round. Initially empty items must be treated as unavailable, consistently with the task’s definition.
The denominator calculation checks out. For an exhaustion determined by item \(j\),
\(\Delta=DR_j/(EA_j)\),
and the displayed updates for supplies and service time are algebraically correct. Multiplication by a type mass with denominator dividing \(D\) cancels the additional factor \(D\) in this expression.
For a phase ending at \(u=1\), multiplying the common denominator by \(D\) suffices. Since \(A_j\le D\), the accumulated denominator has the claimed polynomial bit length. Numerators also remain polynomial in length: allocations are bounded by total mass, service time lies in \([0,1]\), and residual supplies are bounded by input supplies.
The polynomial bit-complexity claim for exact simulation and expected-welfare comparison is therefore justified.
3. NP membership and deterministic optimality
For a fixed deterministic policy, each latent state generates exactly one execution. Hence each depth has at most \(s\) reachable histories, and the reachable policy tree has at most \(1+ks\) nodes.
The proposed certificate is polynomial in size under the input’s explicit conditional-mass-table representation. Polynomial-length menu representatives suffice for its prices.
The consistency check correctly prevents state-indexed certificates from exploiting hidden information. Comparing complete observable histories, including previous actions, ensures that identical histories receive identical next actions. Together with the visit checks, this defines a legitimate policy on every reachable history.
The finite action menu and finite horizon justify backward induction and existence of an optimal deterministic policy. Randomization cannot improve the maximum continuation value.
The enumeration bound
\(\bigl(k\,3^{\tau m(m+1)/2}\bigr)^{ks}\operatorname{poly}(m,\tau,k,s,L)\)
is a valid upper bound.
4. NP-hardness reduction
The construction satisfies the task’s normalization and support requirements. Both types have positive mass, the total mass is one, and all numbers have polynomial binary encoding length.
The universal bound is correct:
\(W=2x_H+x_L=x_H+(x_H+x_L)\le 1/2+q=B\).
Equality requires both \(x_H=1/2\) and \(x_H+x_L=q\), because each corresponding deficit is nonnegative.
The price classes correctly account for tie-breaking:
Premature exhaustion leaves positive high-value mass unserved. Therefore, equality forces each cohort’s low-value allocation to be either its full mass or zero. The resulting equality is exactly the SUBSET SUM condition.
Conversely, the prescribed prices for a subset-sum solution generate total purchasing mass exactly \(q\). Positive high-value mass remains to be served until the final cohort completes, so there is no premature exhaustion.
The reduction proves NP-hardness already for \(m=s=1\) and \(\tau=2\). Combined with membership, NP-completeness follows.
5. Sufficiency of the candidate statistic
The argument establishes the stronger sufficiency claim for \((\beta,r,U)\).
Conditional on a latent state, the next allocation, observation, reward, and inventory are determined by that state, current inventory, and selected action. Conditional masses of unvisited cohorts remain the input masses.
The posterior update is correct for reachable observations, where its denominator is positive. Equal \((\beta,r,U)\) therefore yields equal immediate expected rewards and equal successor-state distributions.
Additivity of welfare makes accumulated welfare irrelevant to continuation optimization. The candidate statistic contains all three sufficient components, so its sufficiency follows.
The posterior’s normalized-prior expression is also correct: deterministic observations eliminate inconsistent states without otherwise changing their relative prior weights.
6. Memory upper bounds
The node-index construction is valid under the stated convention. The fixed policy description can contain actions and observation transitions; only the current node index needs to persist.
An externally available depth permits depth-specific indexing using at most \(\lceil\log_2 s\rceil\) bits. Indexing all reachable nodes instead gives at most \(\lceil\log_2(1+ks)\rceil\) bits.
These bounds concern persistent history information. The separate polynomial workspace qualification is appropriate.
7. Memory lower bounds
The diagnostic construction satisfies all mass and supply constraints. In particular,
\(5/8<M_{ij}<3/4\),
and \(M_{ij}>q>a_{ij}\).
The diagnostic cohorts never purchase, including at zero price, because the empty bundle wins utility ties. Their nothing-allocation observations reveal their respective indices.
The welfare calculations are correct:
\(W_{\mathrm{both}}=q(1+3a_{ij}/M_{ij})\),
and
\(W_{\mathrm{high}}=4a_{ij}\).
For diagonal states, the bound \(W_{\mathrm{both}}<13/80<1/4\) is correct. For off-diagonal states, \(W_{\mathrm{both}}>1/8>1/16\). Thus the optimal price class differs strictly between the two cases.
Both diagnostics first attain every state’s individual maximum. Taking \(C\) earlier leaves diagonal and off-diagonal states possible and incurs a strict loss in at least one positive-probability state. The necessity of observing both diagnostics follows.
Under the primary controller-state convention, the collision argument establishes at least \(r\) distinguishable states and hence \(\Omega(\log s)\) bits. Splitting prior weights among duplicate states preserves the construction’s behavior.
The execution-position argument gives the \(\Omega(\log k)\) contribution when neither a round counter nor another source of execution-position information is supplied. The combination matches the upper bound up to constants.
Two minor issues remain:
8. Relationship to the cited finite-agent result
The cited paper states the allocation-information sufficiency and finite-agent information lower bound described in the task. Those statements do not contradict a logarithmic bound in the number of explicitly supported latent states. The prover uses this only as a compatibility observation, not as a theorem establishing its continuum result. [Brero et al., Theorem 1](https://arxiv.org/html/2010.01180v2)
The output resolves the complexity and statistic questions, and supports its principal memory claims under its declared controller convention. No additional mathematical lemma is needed for those principal claims.
⟨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.