Answer: \(\mathrm P\): every valid instance admits a successful policy, with polynomial-time construction and exact rational evaluation.
Theorem 1.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateEvery market with up to 3 buyers, each with a multi-demand valuation function, admits an optimal dynamic pricing. Moreover, the prices can be computed in polynomial (in the number of items m) time, using value queries4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) item categories, three multi-demand types with rational masses \(\mu_t\) summing to one, rational per-capita supplies \(q_j\), and rational values and caps, does there exist a state-based nonnegative pricing policy, computable from residual type masses and supplies, such that every measurable arrival order and every utility-maximizing tie choice by infinitesimal mass yields terminal welfare equal to the configuration-LP optimum? If so, can such a policy be constructed and evaluated in time polynomial in \(m\), \(\tau=3\), and input bit length \(L\)?
A society is given by its support: the list of the \(\tau=3\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m\geq1\) categories, binary-rational supplies \(q_j\geq0\), binary-rational values \(w_{tj}\geq0\), and integer demand caps \(1\leq k_t\leq m\). Let \(L\) be the total input bit length.
A configuration is any subset \(S\subseteq[m]\), containing at most one unit of each category. Its multi-demand value \(v_t(S)\) is the sum of its \(\min\{k_t,|S|\}\) largest item values. Configurations larger than the cap remain permissible; the cap limits value, not purchases. Mass \(d\alpha\) receiving \(S\) consumes \(d\alpha\) of every category in \(S\) and contributes \(v_t(S)d\alpha\) to welfare.
Define \(\mathrm{OPT}=\max\{\sum_{t,S}v_t(S)x_{tS}:x_{tS}\geq0,\ \sum_Sx_{tS}=\mu_t,\ \sum_{t,S:j\in S}x_{tS}\leq q_j\}\), including the empty configuration. Unsold supply is allowed; impose no equality between aggregate demand and supply.
A policy is a finitely described measurable map \(P(r,Q)\in\mathbb R_{\geq0}^m\), depending on the input and residual masses and supplies, chosen before the next arriving type is revealed. At state \((r,Q)\), type \(t\) may choose any configuration maximizing \(v_t(S)-\sum_{j\in S}P_j(r,Q)\) among \(S\subseteq\{j:Q_j>0\}\), with arbitrary ties.
An arrival order is a measurable map \(a:[0,1]\to[3]\) with \(\lambda(a^{-1}(t))=\mu_t\), where \(\lambda\) is Lebesgue measure. An execution is a measurable configuration choice \(S(s)\) and nonnegative absolutely continuous residual state starting at \((\mu,q)\), satisfying \(\dot r_t(s)=-\mathbf1_{\{a(s)=t\}}\), \(\dot Q_j(s)=-\mathbf1_{\{j\in S(s)\}}\), and the demand condition almost everywhere.
A policy must admit an execution through time \(1\) for every arrival order. It is successful if every such execution, under every measurable demanded configuration choice, has welfare \(\int_0^1v_{a(s)}(S(s))\,ds=\mathrm{OPT}\). Its description must define it on real residual states; computational evaluation means exact rational prices at rational states, whose encoding length is denoted \(B\).
Is deciding whether a successful policy exists in \(\mathrm P\), or is it NP-hard?
In the polynomial-time case, can a successful policy on every yes-instance be constructed in time polynomial in \(m,\tau,L\), and evaluated in time polynomial in \(m,\tau,L,B\)?
For finite markets with at most three multi-demand buyers, optimal dynamic prices exist and can be computed in polynomial time, guaranteeing optimal welfare for every arrival order and tie choice ([Berger–Eden–Feldman](https://arxiv.org/abs/2002.06863)).
Efficient optimal dynamic pricing is also known for arbitrarily many finite bi-demand buyers ([Bérczi–Bérczi-Kovács–Szögi](https://arxiv.org/abs/2107.05131)). No result settling the continuum policy problem defined here was located.
Every valid instance admits a successful policy. Thus the decision problem belongs to \(\mathrm P\). A successful policy can be constructed in time polynomial in \(m,\tau,L\) and evaluated exactly at rational residual states in time polynomial in \(m,\tau,L,B\).
The proof actually works for every finite support size \(\tau\), including the stipulated \(\tau=3\).
The main idea is to select prices from the relative interior of an optimal dual face. Every demanded configuration then has the correct welfare derivative for every dual solution in that face. We prove both welfare optimality of all executions and existence of an execution for each measurable arrival order.
For any nonnegative real residual state \(z=(r,Q)\), let \(F(z)\) denote the configuration-LP optimum with masses \(r\) and supplies \(Q\). In particular, \(F(\mu,q)=\mathrm{OPT}\).
This LP is feasible, since all residual mass can receive the empty configuration. Its feasible set is compact: every variable satisfies \(0\le x_{tS}\le r_t\). Consequently, its optimum is attained.
By finite-dimensional LP duality,
\(F(r,Q)=\min\left\{\sum_t r_tu_t+\sum_jQ_jp_j:\ p_j\ge0,\quad u_t+\sum_{j\in S}p_j\ge v_t(S)\ \text{for every }t,S\right\}.\)
The constraint for the empty configuration implies \(u_t\ge0\). Define
\(D_t(p)=\max_{S\subseteq[m]}\left(v_t(S)-\sum_{j\in S}p_j\right).\)
Thus the dual constraints are precisely \(p\ge0\) and \(u_t\ge D_t(p)\).
Because prices are nonnegative, the maximum defining \(D_t(p)\) can be attained by a configuration of size at most \(k_t\). Indeed, from any configuration \(S\), retain its \(\min\{k_t,|S|\}\) highest-valued items, obtaining \(T\). Then
\(v_t(T)=v_t(S),\qquad \sum_{j\in T}p_j\le\sum_{j\in S}p_j.\)
Therefore,
\(D_t(p)=\max_{\substack{T\subseteq[m]\\ |T|\le k_t}}\sum_{j\in T}(w_{tj}-p_j).\)
For any \(\eta\ge0\) and any such \(T\),
\(\sum_{j\in T}(w_{tj}-p_j)\le k_t\eta+\sum_j(w_{tj}-p_j-\eta)_+,\)
where \(x_+=\max\{x,0\}\).
Equality is attained by taking \(\eta\) to be the \(k_t\)-th largest member of the list \((w_{tj}-p_j)_+\). To verify this, write the list in decreasing order as \(\gamma_{(1)},\ldots,\gamma_{(m)}\) and set \(\eta=\gamma_{(k_t)}\). Then
\(k_t\eta+\sum_j(\gamma_j-\eta)_+=\sum_{\ell=1}^{k_t}\gamma_{(\ell)}.\)
Hence
\(D_t(p)=\min_{\eta\ge0}\left(k_t\eta+\sum_j(w_{tj}-p_j-\eta)_+\right).\)
This identity concerns the maximum utility. Oversized configurations remain permissible, and the subsequent proof applies to every demanded configuration, including oversized ones.
Set
\(V=\max_t\sum_jw_{tj},\qquad M=V+1.\)
For every \(p\ge0\), we have \(0\le D_t(p)\le V\).
An optimal configuration-dual solution can be chosen with \(0\le p_j,u_t\le M\). To see this, start with an optimal dual solution and replace each \(p_j>M\) by \(M\). Since \(w_{tj}<M\) for every type, the corresponding adjusted item value remains negative. The formula above shows that this replacement leaves every \(D_t(p)\) unchanged. Next replace each \(u_t>M\) by \(M\); feasibility is preserved because \(D_t(p)\le V<M\). Both replacements weakly decrease the objective, whose coefficients are nonnegative. Optimality therefore remains intact.
Introduce auxiliary variables \(\eta_t,\xi_{tj}\), and let \(H\) be the fixed rational polytope consisting of \(h=(p,u,\eta,\xi)\) satisfying:
Its projection onto \((p,u)\) is exactly
\(\left\{(p,u)\in[0,M]^{m+\tau}:u_t\ge D_t(p)\ \text{for every }t\right\}.\)
One inclusion follows from the demand-utility formula. For the other, choose the threshold \(\eta_t\) described above and set \(\xi_{tj}=(w_{tj}-p_j-\eta_t)_+\). These auxiliary variables are at most \(V\), and their expression equals \(D_t(p)\).
For \(h\in H\), define
\(\ell_h(r,Q)=\sum_t r_tu_t+\sum_jQ_jp_j.\)
We have proved
\(F(z)=\min_{h\in H}\ell_h(z).\)
The polytope \(H\) has \(n=m+2\tau+\tau m\) variables and polynomially many inequalities, all with encoding length polynomial in the input size.
Since \(H\) is compact, \(F\) is the minimum of finitely many linear functions, one for each vertex of \(H\). Moreover,
\(|F(z)-F(z')|\le M\|z-z'\|_1.\)
Thus \(F\) is Lipschitz on the nonnegative residual-state space.
For each residual state, define its optimal dual face
\(G(z)=\{h\in H:\ell_h(z)=F(z)\}.\)
We select a point in the relative interior of this face using a construction that depends only on the face itself.
Write all defining inequalities of \(H\) as \(g_i(h)\ge0\), for \(i=1,\ldots,R\), with each \(g_i\) affine. Fix a coordinate order for lexicographic minimization.
For a nonempty face \(G\) of \(H\), let:
Define
\(\bar h(G)=\frac{h_0(G)+\sum_{i=1}^R h_i(G)}{R+1}.\)
All these points exist and are unique because the relevant sets are nonempty compact polytopes.
If \(g_i\) vanishes everywhere on \(G\), it also vanishes at \(\bar h(G)\). Otherwise its maximum on \(G\) is positive, so \(g_i(\bar h(G))>0\). Consequently, every inequality not identically tight on \(G\) is strict at \(\bar h(G)\). A sufficiently small relative neighborhood of this point in the affine hull of \(G\) therefore lies in \(G\). This proves
\(\bar h(G)\in\operatorname{relint}G.\)
Define the policy by taking its price coordinates:
\(P(r,Q)=p\bigl(\bar h(G(r,Q))\bigr).\)
This definition uses only the residual state and the input.
The polytope \(H\) has finitely many faces. For each face, the states at which it is exactly the optimal face are described by finitely many linear equalities and strict inequalities comparing vertex objectives.
These state sets are Borel. The selector is constant on each such set, so the policy is a finitely described Borel measurable map on real residual states.
We will use the following elementary fact.
Lemma. If an affine function \(\phi\) is nonnegative on a convex set \(G\), and \(\phi(\bar h)=0\) at a point \(\bar h\in\operatorname{relint}G\), then \(\phi\) vanishes everywhere on \(G\).
Proof. If \(\phi(h_1)>0\) at some \(h_1\in G\), relative interior implies that, for sufficiently small \(\varepsilon>0\),
\(h_2=\bar h+\varepsilon(\bar h-h_1)\in G.\)
But then \(\phi(h_2)=-\varepsilon\phi(h_1)<0\), a contradiction. ∎
Lemma. Let \(z=(r,Q)\), suppose \(r_t>0\), and let \(S\) be any configuration demanded by type \(t\) at prices \(P(z)\), among the available categories. Then, for every \(h=(p,u,\eta,\xi)\in G(z)\),
\(u_t+\sum_{j\in S}p_j=v_t(S).\)
Proof. Write \(\bar h=\bar h(G(z))\), and let \(x\) be an optimal residual configuration allocation. Its primal-dual gap with \(\bar h\) is
\(\ell_{\bar h}(z)-F(z)=\sum_{t,T}x_{tT}\left(\bar u_t+\sum_{j\in T}\bar p_j-v_t(T)\right)+\sum_j\bar p_j\left(Q_j-\sum_{t,T:j\in T}x_{tT}\right)=0.\)
Every summand is nonnegative.
Since \(r_t>0\), some \(T\) has \(x_{tT}>0\). Such a configuration uses only available categories: if \(Q_j=0\), feasibility forces every allocation containing \(j\) to have zero mass. The gap identity implies
\(v_t(T)-\sum_{j\in T}\bar p_j=\bar u_t.\)
Every configuration has utility at most \(\bar u_t\) by dual feasibility. Therefore the maximum utility among available configurations equals \(\bar u_t\), and the demanded configuration \(S\) satisfies
\(\bar u_t+\sum_{j\in S}\bar p_j-v_t(S)=0.\)
The affine function
\(\phi(h)=u_t+\sum_{j\in S}p_j-v_t(S)\)
is nonnegative throughout \(H\), and hence throughout \(G(z)\). Applying the relative-interior lemma proves the claim. ∎
This lemma is the central property of the policy. It holds for every demanded tie choice.
Consider any execution through time \(1\), with any admissible measurable arrival order and configuration choices. Write its residual state as \(z(s)=(r(s),Q(s))\).
At almost every interior time, the execution equations hold and the residual state is differentiable. At such a time, the arriving type \(t=a(s)\) has \(r_t(s)>0\). Indeed, a differentiable nonnegative function has derivative zero wherever it equals zero at an interior point, whereas the execution equation gives \(\dot r_t(s)=-1\).
Let \(S=S(s)\). The preceding lemma yields, for every \(h\in G(z(s))\),
\(\frac{d}{ds}\ell_h(z(s))=-u_t-\sum_{j\in S}p_j=-v_t(S).\)
Recall that \(F\) is the minimum of the finitely many vertex objectives. At a point where \(z\) is differentiable, each active vertex objective has the same first-order change, namely \(-v_t(S)\). Inactive vertices have strictly positive objective gaps and cannot affect the first-order minimum. Consequently,
\(\frac{d}{ds}F(z(s))=-v_{a(s)}(S(s))\)
almost everywhere.
Because \(F\) is Lipschitz and \(z\) is absolutely continuous, \(F\circ z\) is absolutely continuous. Integrating gives
\(\int_0^1v_{a(s)}(S(s))\,ds=F(z(0))-F(z(1)).\)
The arrival-order constraints imply \(r(1)=0\). With no residual mass, the residual welfare optimum is zero regardless of unsold supply, so \(F(z(1))=0\). Therefore
\(\int_0^1v_{a(s)}(S(s))\,ds=F(\mu,q)=\mathrm{OPT}.\)
This proves the required welfare guarantee for every execution. It remains to establish execution existence.
Fix an arbitrary measurable arrival order \(a\) with the prescribed type masses. We construct an execution in finitely many phases.
Suppose a phase starts at time \(s_0<1\) in a nonnegative state \(z_0=(r_0,Q_0)\) consistent with the preceding execution. Set \(G=G(z_0)\).
For each type with \(r_{0t}>0\), choose one demanded configuration \(S_t\) at prices \(P(z_0)\), using available categories. These configurations exist because the choice set is finite and includes the empty configuration.
For a type with \(r_{0t}=0\), its remaining arrival set has measure zero: consistency gives
\(r_{0t}=\mu_t-\lambda\{s<s_0:a(s)=t\}.\)
For such a type, set \(S_t=\varnothing\); this choice cannot affect the execution on a set of positive measure.
Define the cumulative arrivals during this phase by
\(c_t(s)=\int_{s_0}^{s}\mathbf1_{\{a(u)=t\}}\,du.\)
The tentative state trajectory is
\(r_t(s)=r_{0t}-c_t(s),\qquad Q_j(s)=Q_{0j}-\sum_{t:j\in S_t}c_t(s).\)
These functions are absolutely continuous. Coordinates initially equal to zero remain zero: exhausted types have no remaining arrival mass, and the selected configurations avoid exhausted categories.
By the lemma in Section 4, for every \(h\in G\),
\(\ell_h(z(s))=F(z_0)-\sum_t c_t(s)v_t(S_t).\)
Here types with zero residual mass contribute nothing. Thus all members of \(G\) retain the same objective along the tentative trajectory.
Choose any \(h^\ast\in G\). For every vertex \(h\) of \(H\) outside \(G\), define its gap
\(\Delta_h(s)=\ell_h(z(s))-\ell_{h^\ast}(z(s)).\)
Each gap is continuous and strictly positive at \(s_0\).
End the phase at the first of the following events:
Unless \(s_0=1\), the phase has positive duration. There are finitely many initially positive coordinates and finitely many initially positive vertex gaps, all continuous.
Before the endpoint, the state is nonnegative, its positive-coordinate pattern is unchanged, and every outside vertex gap remains positive. Hence its optimal face is exactly \(G\). The policy therefore keeps the same prices throughout the phase, and the configurations \(S_t\) remain demanded.
At the endpoint, all gaps and coordinates are nonnegative. Thus the new optimal face contains \(G\). If an outside vertex gap has reached zero, this containment is proper.
Now start the next phase using the new state.
There are two kinds of nonterminal events:
Once a residual coordinate becomes zero, it remains zero. Therefore there are at most \(m+\tau\) events of the first kind.
The optimal faces form a nested chain. Each proper inclusion of faces increases affine dimension, and \(H\) has dimension at most \(n\). Therefore there are at most \(n\) events of the second kind.
Every nonterminal phase ends with at least one of these events. Consequently, the construction reaches time \(1\) after at most \(n+m+\tau+1\) phases.
The resulting configuration choice is measurable: on each phase it is a fixed function of the measurable arriving type. The residual trajectory is nonnegative and absolutely continuous, with the required derivatives. Demand holds throughout phase interiors; the finitely many endpoints are irrelevant to the almost-everywhere condition.
We have therefore constructed an execution through time \(1\) for the arbitrary arrival order \(a\).
Together with Section 5, this proves that the policy is successful.
The policy description consists of the rational polytope \(H\), the fixed coordinate order, and the selector algorithm of Section 3. Its size and construction time are polynomial in \(m,\tau,L\).
At a rational residual state of encoding length \(B\), evaluate the policy as follows:
Lexicographic minimization requires at most \(n\) ordinary LP optimizations, fixing one coordinate after another. Hence the total number of LP calls is polynomial.
We invoke the standard exact rational-LP theorem: an LP with rational, finitely encoded data can be optimized in polynomial bit time, with a rational optimizer of polynomial encoding length. Its hypotheses hold here: the number of variables and constraints is polynomial, the coefficient encoding length is polynomial in \(m,\tau,L,B\), and all optimization sets are nonempty compact polytopes.
The average therefore gives exact rational prices, with polynomial encoding length, in time polynomial in \(m,\tau,L,B\). No enumeration of faces or vertices is needed by the evaluator; those finite sets were used only in the proof.
The finite-market results cited in the question concern indivisible buyers: [Berger–Eden–Feldman](https://arxiv.org/abs/2002.06863) and [Bérczi–Bérczi-Kovács–Szögi](https://arxiv.org/abs/2107.05131). The argument above establishes the continuum guarantee directly through the residual configuration LP and absolute continuity, while permitting unsold supply and arbitrary demanded ties.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and resolves the stated continuum problem, subject to one minor omission in the bit-complexity justification. I found no false central step, missing mathematical lemma, or failure involving oversized configurations, arbitrary ties, zero supplies, or measurable arrival orders.
The conclusion applies to the task’s intended model: purchases may exceed demand caps, supply may remain unsold, and prices must be selected before observing the arriving type.
The residual configuration LP is feasible because the empty configuration is allowed. There are finitely many variables, and each satisfies \(0\le x_{tS}\le r_t\), so its feasible set is compact.
The displayed dual has the correct signs and constraints: the supply inequalities produce \(p_j\ge0\), while the mass equalities initially produce unrestricted \(u_t\). The empty-configuration constraint then gives \(u_t\ge0\). Finite-dimensional LP duality applies because the primal is feasible and has a finite attained optimum.
Removing items beyond the highest-valued \(k_t\) preserves configuration value and weakly decreases expenditure because prices are nonnegative. This establishes the formula for maximum utility without excluding oversized configurations from subsequent demand choices.
The threshold computation is correct, including ties, zero adjusted values, and \(k_t=m\). Taking the \(k_t\)-th largest nonnegative adjusted value gives exactly the sum of the largest \(k_t\) such values.
The bound \(M=V+1\) works also when all values are zero. Since \(w_{tj}<M\), truncating a price above \(M\) leaves its adjusted item value negative and therefore leaves every \(D_t(p)\) unchanged. Truncating \(u_t\) preserves feasibility. Nonnegative residual coefficients ensure that these operations cannot increase the dual objective.
Both inclusions in the claimed projection of \(H\) are justified. The chosen auxiliary variables obey their bounds, and \(H\) is a nonempty compact rational polytope. Thus the representation of \(F\) as a minimum over \(H\), its finite vertex representation, and its stated Lipschitz bound are valid.
Lexicographic minimization on each nonempty compact optimization set gives a unique point. Averaging the selected slack maximizers makes every defining inequality that is not identically tight on the face strictly satisfied.
The neighborhood argument is valid within the affine hull of the face: the inequalities identically tight on the face remain equalities there, and the remaining inequalities have positive slack.
The optimal face has only finitely many possibilities. Comparing the finitely many vertex objectives describes each corresponding state region by linear equalities and strict inequalities. Consequently, the policy is Borel measurable.
Its finite description is the polytope and selector rule; the proof does not require an explicit list of all faces. This addresses real residual states as requested.
The primal-dual gap identity has the correct terms and signs. All summands are nonnegative.
When \(r_t>0\), an optimal allocation assigns positive mass to at least one configuration of type \(t\). Such a configuration cannot contain a category with zero residual supply. Its complementary-slackness equality establishes that the maximum utility over available configurations equals the selected \(\bar u_t\).
Therefore every demanded configuration, including an oversized tied choice, has zero dual slack at the selected point. The supplied relative-interior lemma correctly extends this equality to every member of the optimal face.
The hypothesis \(r_t>0\) is essential and is appropriately retained.
At an interior differentiability point, a nonnegative residual mass cannot equal zero while having derivative \(-1\). Hence the arriving type has positive residual mass almost everywhere where the execution equations hold.
Every active vertex objective consequently has the same derivative, namely \(-v_{a(s)}(S(s))\). There are finitely many inactive vertices, each with positive objective gap at the point under consideration, so they cannot change the first-order minimum. This justifies the derivative asserted for \(F\circ z\).
The composition is absolutely continuous because \(F\) is Lipschitz and \(z\) is absolutely continuous. Integration is therefore justified.
The prescribed arrival masses imply \(r(1)=0\), and residual welfare with zero masses is zero regardless of remaining supply. The resulting welfare identity is exactly the required guarantee for every execution and every admissible demanded tie choice.
The cumulative-arrival functions are absolutely continuous for arbitrary measurable arrival orders. Consistency implies that an exhausted type has no remaining arrival mass, so setting its phase configuration to the empty set causes no almost-everywhere demand violation.
The selected configurations avoid initially exhausted categories. Until a stopping event, positive coordinates remain positive, all outside vertex gaps remain positive, and all members of the initial optimal face retain equal objectives. Thus the optimal face, selected prices, availability set, and demand status remain unchanged throughout the phase interior.
Each phase has positive duration: there are finitely many initially positive coordinates and vertex gaps, and all are continuous. At its endpoint, nonnegativity is preserved and the new optimal face contains the previous face.
The termination argument is valid. A coordinate can become exhausted only once, and a proper inclusion of faces increases affine dimension. Every nonterminal phase produces at least one of these events. The stated bound on the number of phases follows.
Concatenating finitely many phases gives the required measurable configuration choice and nonnegative absolutely continuous residual trajectory. The finitely many endpoints do not affect the almost-everywhere requirements.
The polytope has the stated number of variables and polynomially many inequalities of polynomial encoding length. Its description and the selector algorithm can be constructed in polynomial time.
The number of LP calls needed for evaluation is polynomial. Each optimization set is a nonempty compact rational polytope, so exact rational LP optimization applies.
Minor issue: the write-up asserts, without separately justifying, that coefficient encoding lengths remain polynomial through all sequential coordinate-fixing LP calls. A polynomial number of LP calls alone does not establish polynomial total bit complexity if newly inserted exact values could grow substantially.
This is an expositional omission, not a substantive obstacle. The minimum requested clarification is a uniform polynomial bound on the encoding lengths of the values introduced during lexicographic optimization. A precise invocation of the standard rational-vertex bit-length bound for the fixed polytope \(H\), explaining its applicability to these selected points, suffices. The final averaging operation should be covered by the same bit-length accounting.
The proof establishes both parts of the task: every valid instance is a yes-instance, and the proposed policy has a polynomial-size construction and polynomial-time exact rational evaluation. The finite-market results are not used as premises, so no transfer of their hypotheses to the continuum model requires verification.
⟨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.