Answer: A polynomial-time algorithm computes rational static prices and caps guaranteeing welfare at least \(\mathrm{OPT}_{\mu}/2\), and therefore at least \(\mathrm{OPT}_{\mu}/4\), for every measurable arrival order and every measurable utility-maximizing tie resolution.
Corollary 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWe can compute in poly-time a price vector ⃗p∗and supply vector ⃗k∗such that for any arrival order, the expected welfare of the posted price mechanism with these prices is at least one-fourth of the optimum social welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(M\) goods, \(\tau\) buyer types with rational masses \(\mu_t\) summing to one, XoS demand and valuation oracles, and rational piecewise-linear convex per-capita cost curves \(C_i\), can a polynomial-time algorithm in \(M,\tau,L\) compute item prices \(p_i\) and mass supply caps \(q_i\in[0,1]\) such that an on-the-fly posted-price mechanism achieves at least \(\mathrm{OPT}_{\mu}/4\) for every measurable arrival order with type frequencies \(\mu\)? Each infinitesimal buyer chooses a utility-maximizing integral bundle from the available goods, and \(\mathrm{OPT}_{\mu}\) maximizes \(\sum_{t,S}x_{t,S}v_t(S)-\sum_i C_i(y_i)\), where \(\sum_S x_{t,S}=\mu_t\) and \(y_i=\sum_{t,S\ni i}x_{t,S}\).
Let \(I\) be a set of \(M\geq1\) goods. A society is given by its support: the list of its \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) denotes support size, not the number of possible types.
Each type has a normalized, monotone XoS valuation \(v_t:2^I\to\mathbb{Q}_{\geq0}\), with \(v_t(\varnothing)=0\). Access consists of valuation and demand oracles, and an XoS oracle returning an additive supporting clause attaining \(v_t(S)\) on a queried bundle \(S\); demand queries may restrict the available goods.
Each explicitly encoded cost \(C_i:[0,1]\to\mathbb{Q}_{\geq0}\) is finite, continuous, nondecreasing, convex and piecewise linear with rational breakpoints and coefficients, and \(C_i(0)=0\). Costs and welfare are measured per unit of total population. Let \(L\) count explicit input bits and bound rational oracle-answer lengths; running time counts bit operations and oracle queries.
Define \(\mathrm{OPT}_{\mu}=\max_{x\geq0}\{\sum_{t,S\subseteq I}x_{t,S}v_t(S)-\sum_i C_i(y_i):\sum_{S\subseteq I}x_{t,S}=\mu_t,\ y_i=\sum_{t,S\ni i}x_{t,S}\}\).
A static on-the-fly mechanism specifies rational prices \(p_i\geq0\) and caps \(q_i\in[0,1]\). An arrival order is a measurable map \(a:[0,1]\to\{1,\ldots,\tau\}\) with \(\lambda(a^{-1}(t))=\mu_t\), where \(\lambda\) is Lebesgue measure.
For a measurable bundle choice \(B(s)\), put \(z_i(s)=\int_0^s\mathbf{1}_{\{i\in B(u)\}}\,du\). Almost everywhere, \(B(s)\) maximizes \(v_{a(s)}(S)-\sum_{i\in S}p_i\) over \(S\subseteq\{i:z_i(s)<q_i\}\); each buyer receives an integral bundle, including possibly the empty bundle, and ties may be resolved arbitrarily. Welfare is \(\int_0^1v_{a(s)}(B(s))\,ds-\sum_i C_i(z_i(1))\), charging only actual production.
Can an algorithm using \(\operatorname{poly}(M,\tau,L)\) time and oracle queries compute static prices and caps guaranteeing welfare at least \(\mathrm{OPT}_{\mu}/4\) for every measurable arrival order and every measurable utility-maximizing tie resolution, or can this polynomial-time approximation guarantee be ruled out?
For finite independent Bayesian XoS buyers and convex production costs, polynomial-time computation of static prices and supply caps guarantees one-fourth of expected optimal welfare for every arrival order, using demand and XoS oracles; exact distribution processing depends on the support of the product distribution ([Sekar, 2017](https://www.ijcai.org/proceedings/2017/0055.pdf)).
No result settling this precise atomless, fixed-frequency, every-order formulation was identified in the literature search.
Yes. Under the stated oracle and encoding assumptions, a polynomial-time algorithm computes rational static prices and caps guaranteeing welfare at least \(\mathrm{OPT}_{\mu}/2\), hence at least \(\mathrm{OPT}_{\mu}/4\), for every measurable arrival order and every measurable utility-maximizing tie resolution.
The proof uses an optimal fractional allocation directly. Splitting a type’s mass between bundles is allowed by the benchmark and does not require giving any individual buyer a fractional bundle.
For each good \(i\), write its piecewise-linear convex cost as
\(\displaystyle C_i(y)=\max_{1\leq k\leq K_i}\{c_{ik}y+b_{ik}\},\qquad 0\leq y\leq1.\)
Here the affine functions are the extensions of its linear pieces. Convexity makes each extension a supporting line, so this representation is exact. Nondecreasing costs give \(c_{ik}\geq0\). All coefficients have polynomial encoding length, and \(K=\sum_iK_i\) is bounded by the explicit input size.
Introduce unrestricted epigraph variables \(w_i\). The welfare problem becomes the rational linear program
\(\displaystyle \max\left\{\sum_{t,S}v_t(S)x_{t,S}-\sum_iw_i\right\},\)
subject to
\(\displaystyle \sum_Sx_{t,S}=\mu_t\quad\text{for every }t,\qquad x_{t,S}\geq0,\)
and
\(\displaystyle w_i\geq c_{ik}\sum_{t,S:\,i\in S}x_{t,S}+b_{ik}\quad\text{for every }i,k.\)
Every feasible allocation has total mass one, so its good quantities belong to \([0,1]\). Consequently, minimizing each epigraph variable produces exactly the prescribed production cost. This LP therefore has optimal value \(\mathrm{OPT}_{\mu}\). It is feasible by assigning everybody the empty bundle, and its optimum is finite and attained.
Its dual has variables \(\alpha_t\), unrestricted, and \(\theta_{ik}\geq0\). Define
\(\displaystyle \pi_i=\sum_k c_{ik}\theta_{ik}.\)
The dual minimizes
\(\displaystyle \sum_t\mu_t\alpha_t-\sum_{i,k}b_{ik}\theta_{ik},\)
subject to
\(\displaystyle \sum_k\theta_{ik}=1\quad\text{for every }i,\)
and
\(\displaystyle \alpha_t+\sum_{i\in S}\pi_i\geq v_t(S)\quad\text{for every }t,S.\)
The equality constraints arise because each \(w_i\) is unrestricted.
Separation. First check the explicit constraints on \(\theta\). If they hold, every \(\pi_i\) is nonnegative. For each type \(t\), a demand query at prices \(\pi\) returns a bundle maximizing
\(\displaystyle v_t(S)-\sum_{i\in S}\pi_i.\)
A valuation query on that bundle determines whether the corresponding dual constraint is violated. Thus a strong separation call needs at most one demand query and one valuation query per type, together with polynomial-time rational arithmetic. Arbitrary oracle tie-breaking causes no difficulty: every returned maximizer has the same objective value.
We use the standard exact rational oracle-LP theorem with primal recovery: a feasible LP with polynomially many rows, bounded coefficient encoding lengths, and a bounded optimum admits polynomial-time exact solution with polynomial-size primal support when its dual has a strong separation oracle returning violated original constraints. Primal recovery retains polynomially many columns and solves the resulting explicit LP; this is the standard [ellipsoid and column-recovery construction](https://www.cs.cmu.edu/~15850/hws/h4.pdf).
All hypotheses hold here. There are \(\tau+K\) primal rows, all coefficients have encoding length polynomial in \(M,\tau,L\), and the separation oracle above returns an actual bundle constraint. For completeness, the dual also has a bounded optimal representative: each \(\theta_i\) lies in a simplex, and, for fixed \(\theta\), one can choose
\(\displaystyle \alpha_t=\max_S\left\{v_t(S)-\sum_{i\in S}\pi_i\right\}\in[0,v_t(I)].\)
It follows that we can compute an exact optimal allocation \(x^*\), represented by polynomially many positive variables, in \(\operatorname{poly}(M,\tau,L)\) bit operations and oracle queries. Its rational coordinates have polynomial encoding length by the usual determinant bounds for basic LP solutions.
For every pair \((t,S)\) with \(x^*_{t,S}>0\), query the XoS oracle for a supporting additive clause \(a_{t,S}\). Its defining properties are
\(\displaystyle \sum_{i\in T}a_{t,S}(i)\leq v_t(T)\quad\text{for every }T\subseteq I,\)
and
\(\displaystyle \sum_{i\in S}a_{t,S}(i)=v_t(S).\)
Define benchmark quantities and additive value contributions by
\(\displaystyle q_i=\sum_{t,S:\,i\in S}x^*_{t,S},\qquad V_i=\sum_{t,S:\,i\in S}x^*_{t,S}a_{t,S}(i).\)
Then
\(\displaystyle \sum_iV_i=\sum_{t,S}x^*_{t,S}v_t(S),\qquad \mathrm{OPT}_{\mu}=\sum_i\bigl(V_i-C_i(q_i)\bigr).\)
We next prove the crucial itemwise inequality
\(\displaystyle V_i\geq C_i(q_i).\)
Delete good \(i\) from every benchmark bundle, merging masses when bundles coincide. This remains a feasible allocation with the same type masses. Quantities of other goods remain unchanged, while the quantity of \(i\) becomes zero. The supporting-clause inequality gives
\(\displaystyle v_t(S\setminus\{i\})\geq v_t(S)-a_{t,S}(i)\qquad(i\in S).\)
Thus total valuation decreases by at most \(V_i\), and production cost decreases by exactly \(C_i(q_i)\). The modified allocation has welfare at least
\(\displaystyle \mathrm{OPT}_{\mu}-V_i+C_i(q_i).\)
Optimality of \(x^*\) implies the claimed inequality.
Write
\(\displaystyle W_i=V_i-C_i(q_i)\geq0.\)
If \(q_i=0\), its definition implies \(V_i=0\), hence \(W_i=0\).
Use the benchmark quantities \(q_i\) as caps. Set
\(\displaystyle p_i=\frac{V_i+C_i(q_i)}{2q_i}\quad\text{when }q_i>0,\)
and set \(p_i=0\) when \(q_i=0\).
These prices are nonnegative rationals of polynomial encoding length. For each positive cap,
\(\displaystyle p_iq_i-C_i(q_i)=\frac{W_i}{2},\qquad V_i-p_iq_i=\frac{W_i}{2}.\)
Furthermore, convexity and \(C_i(0)=0\) imply, for \(0\leq r\leq q_i\),
\(\displaystyle C_i(r)\leq\frac{r}{q_i}C_i(q_i).\)
Since \(V_i\geq C_i(q_i)\), we have \(p_i\geq C_i(q_i)/q_i\). Consequently,
\(\displaystyle p_ir-C_i(r)\geq0\qquad(0\leq r\leq q_i).\)
Thus every good produces nonnegative seller profit at every permitted final production quantity; selling its entire cap produces profit \(W_i/2\).
Fix any admissible measurable arrival map \(a\) and any measurable maximizing bundle choice \(B\). Let
\(\displaystyle r_i=z_i(1),\qquad u(s)=v_{a(s)}(B(s))-\sum_{i\in B(s)}p_i,\qquad U=\int_0^1u(s)\,ds.\)
First, actual production respects every cap: \(r_i\leq q_i\). Indeed, \(z_i\) is continuous and nondecreasing. If it reaches \(q_i\), feasibility makes its derivative zero almost everywhere thereafter, because the good is unavailable whenever \(z_i(s)\geq q_i\). It therefore cannot exceed the cap. This argument also covers \(q_i=0\).
Partition positive-cap goods into
\(\displaystyle E=\{i:q_i>0,\ r_i=q_i\},\qquad F=\{i:q_i>0,\ r_i<q_i\}.\)
Every good in \(F\) remains available throughout the execution, since
\(\displaystyle z_i(s)\leq r_i<q_i\quad\text{for every }s\in[0,1].\)
Consider almost any arrival \(s\) of type \(t\). For every benchmark bundle \(S\) of that type, \(S\cap F\) is available. Utility maximization and the supporting clause imply
\(\displaystyle u(s)\geq v_t(S\cap F)-\sum_{i\in S\cap F}p_i\geq\sum_{i\in S\cap F}\bigl(a_{t,S}(i)-p_i\bigr).\)
Average these inequalities with weights \(x^*_{t,S}/\mu_t\), which sum to one because \(\mu_t>0\). We obtain
\(\displaystyle u(s)\geq\frac{1}{\mu_t}\sum_Sx^*_{t,S}\sum_{i\in S\cap F}\bigl(a_{t,S}(i)-p_i\bigr).\)
Integrating over the type-\(t\) arrivals multiplies the right-hand side by exactly \(\mu_t\). Summing over types therefore yields
\(\displaystyle U\geq\sum_{i\in F}(V_i-p_iq_i)=\frac12\sum_{i\in F}W_i.\)
This averaging is solely a comparison of utilities against feasible integral bundles. It imposes no fractional-bundle requirement on buyers.
For every good, the preceding convexity bound gives nonnegative profit. For \(i\in E\), the entire cap is sold, so its profit equals \(W_i/2\). Hence
\(\displaystyle \sum_i\bigl(p_ir_i-C_i(r_i)\bigr)\geq\frac12\sum_{i\in E}W_i.\)
By the definition of \(r_i\), integrated payments equal \(\sum_i p_ir_i\). Welfare therefore decomposes exactly as
\(\displaystyle \mathrm{Welfare}=U+\sum_i\bigl(p_ir_i-C_i(r_i)\bigr).\)
The utility and profit bounds give
\(\displaystyle \mathrm{Welfare}\geq\frac12\sum_{i\in F}W_i+\frac12\sum_{i\in E}W_i=\frac12\sum_iW_i=\frac{\mathrm{OPT}_{\mu}}2.\)
The penultimate equality uses \(W_i=0\) for zero-cap goods. Every inequality used only measurability, the prescribed type masses, feasibility, and utility maximization. Thus the bound holds for every arrival order and every measurable maximizing tie resolution.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes a polynomial-time construction guaranteeing welfare at least \(\mathrm{OPT}_{\mu}/2\), which exceeds the requested guarantee. I found no major or minor mathematical issues requiring repair.
The output addresses the specified atomless, fixed-frequency problem directly. Its benchmark allocation respects each type’s mass, and its welfare analysis fixes an arbitrary admissible measurable arrival map and an arbitrary measurable maximizing bundle choice.
The proof does not replace fixed frequencies with independent draws or an expectation. Splitting benchmark mass across bundles is permitted by the definition of \(\mathrm{OPT}_{\mu}\); the mechanism’s buyers still choose integral bundles.
Assessment: Correct and aligned with the assignment.
The representation
\[
C_i(y)=\max_k\{c_{ik}y+b_{ik}\}
\]
is correct on the specified domain: the affine extensions of the pieces of a continuous convex piecewise-linear function lie below that function and attain it on their respective pieces. Nondecreasingness implies nonnegative piece slopes.
The type-mass constraints imply that every production quantity belongs to \([0,1]\). Thus the epigraph constraints use the cost representation only within its valid domain.
The LP objective subtracts each epigraph variable with coefficient one, so an optimum sets it equal to the corresponding cost. The LP therefore represents the benchmark exactly. The empty allocation establishes feasibility. Finiteness and attainment follow from the finite bundle domain, bounded allocation quantities, and continuous costs.
Assessment: Correct.
The dual signs and constraints are correct:
After checking the explicit constraints, \(\pi_i=\sum_k c_{ik}\theta_{ik}\) is nonnegative. Demand queries therefore use permitted prices.
A maximizing demand bundle detects a violated bundle constraint whenever one exists. A valuation query gives the exact objective value needed for that comparison. Oracle tie-breaking does not affect the test.
Assessment: Correct.
The invoked rational oracle-LP result is applicable. The relevant hypotheses are checked in the output:
The bound \(\alpha_t\in[0,v_t(I)]\) is valid: the empty bundle gives the lower bound, while monotonicity and nonnegative prices give the upper bound.
The cited [column-recovery source](https://www.cs.cmu.edu/~15850/hws/h4.pdf) describes retaining polynomially many dual constraints and solving the corresponding restricted primal. Exact rational optimization and certificate recovery are standard under the bounded rational-data assumptions used here; this is also discussed in the primary research source [On finding exact solutions of linear programs in the oracle model](https://personal.lse.ac.uk/veghl/papers/Dadush-Vegh-Zambelli-SODA-2022.pdf).
The polynomial-size recovered allocation and determinant bounds justify polynomial encoding lengths. Subsequent XoS queries and arithmetic therefore remain polynomial in the stated parameters.
Assessment: Correct. The computational claim requires exact LP recovery, and the output explicitly invokes that result.
The two stated supporting-clause properties are exactly those required by the argument. Summing clause attainment over supported benchmark bundles gives the stated decomposition of benchmark value.
The deletion comparison is valid. Removing one good preserves type masses and every other good’s quantity. The supporting-clause inequality bounds the resulting valuation loss by \(V_i\), while the cost saving is exactly \(C_i(q_i)\), using \(C_i(0)=0\).
Optimality consequently gives \(V_i\geq C_i(q_i)\). This establishes nonnegative itemwise welfare contributions without assuming that optimality automatically decomposes itemwise.
When \(q_i=0\), no positive benchmark allocation contains that good, so \(V_i=W_i=0\).
Assessment: Correct.
For positive caps, the price formula gives both identities claimed:
\[
p_iq_i-C_i(q_i)=V_i-p_iq_i=\frac{W_i}{2}.
\]
Convexity and the zero initial cost give the stated chord bound for every \(r\in[0,q_i]\). Together with \(V_i\geq C_i(q_i)\), this implies nonnegative profit at every permitted production quantity.
Zero-cap goods have zero production and zero cost, so they also satisfy the nonnegative-profit statement.
The construction uses rational operations on polynomially encoded quantities. Division by a positive rational cap preserves polynomial encoding length.
Assessment: Correct, including the zero-cap case.
Each cumulative production function is absolutely continuous, continuous, and nondecreasing because it is an integral of a measurable indicator.
Once it reaches its cap, availability excludes further purchases almost everywhere. Absolute continuity therefore prevents production from exceeding the cap. This also handles caps equal to zero.
If \(r_i<q_i\), then \(z_i(s)\leq r_i<q_i\) throughout the execution. Consequently, every good in \(F\) is available at every arrival.
A good reaching its cap only at the endpoint still belongs to \(E\) and supplies the required full-cap profit. The argument does not require earlier exhaustion.
Assessment: Correct.
For every supported benchmark bundle of an arriving type, its intersection with \(F\) is a feasible integral alternative. Utility maximization and the supporting-clause inequality give the stated utility lower bound.
The weights \(x^*_{t,S}/\mu_t\) are well-defined and sum to one because all type masses are positive. Averaging these inequalities is valid even when individual clause-minus-price terms are negative.
The comparison’s right-hand side depends only on the type. Integrating over that type’s arrivals multiplies it by exactly \(\mu_t\), irrespective of their ordering or interleaving. Summing over types gives
\[
U\geq\frac12\sum_{i\in F}W_i.
\]
Assessment: Correct. This is the step that uses fixed frequencies to obtain an every-order guarantee.
Integrated payments equal \(\sum_i p_ir_i\), so the utility-plus-profit decomposition is exact.
Nonnegative profit from all goods and full-cap profit from \(E\) give the complementary lower bound. Since \(E\) and \(F\) partition positive-cap goods and zero-cap goods have zero contribution, combining the bounds yields
\[
\mathrm{Welfare}\geq\frac{\mathrm{OPT}_{\mu}}2.
\]
The argument covers zero valuations, zero costs, zero optimum, partially sold caps, endpoint exhaustion, and arbitrary admissible measurable tie resolutions.
Assessment: Correct. No repair or additional lemma is needed.
⟨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.