Problem ID: D44-127 Model: GPT 6 Astra Ultra Version: 1
Constant prophet bounds for subadditive bidders: corrected target
Status. Unresolved for all subadditive valuations. We prove a static-price guarantee under a quantified additive-envelope condition, and show precisely why that condition does not resolve the catalogue's general target.
Short problem and subclass
There are $m$ items and independent random bidders in a fixed arrival order. Each bidder purchases a utility-maximizing available bundle at prices fixed before values are drawn. The question asks for an absolute welfare approximation for normalized monotone subadditive values. The unrestricted online allocation theorem does not settle this mechanism restriction.
For this attempt, each bidder's valuation $v_i$ comes with nonnegative measurable random weights $(w_{ig})_{g=1}^m$, depending only on that bidder's type, such that almost surely \[
a_i(S):=\sum_{g\in S}w_{ig}\ \leq\ v_i(S)\ \leq\beta a_i(S)
\quad\text{for every }S\subseteq[m], \tag{1}
\] where $1\leq\beta<\infty$ is common. Correlation among weights of a single bidder is unrestricted; independence across bidders is maintained. Assume ${\mathbb{E}}\max_i w_{ig}<\infty$. The weights are used to define prices; bidders still maximize their actual $v_i$, not their envelopes. Arbitrary utility-maximizing tie-breaking is allowed, provided it uses only the realized arrival history and current type, not future types.
Lemma (An itemwise utility lower bound): Fix prices $p_g\geq0$. Let $q_{ig}$ be the probability item $g$ remains available immediately before bidder $i$, and let $q_g$ be the probability it is never sold. Let $U_i$ be bidder $i$'s realized utility. Under the lower inequality in (1), \[
{\mathbb{E}} U_i\geq\sum_g q_{ig}{\mathbb{E}}(w_{ig}-p_g)_+,
\qquad q_{ig}\geq q_g.
\]
Proof: For a realized available set $R_i$, bidder $i$ can buy $T_i=\{g\in R_i:w_{ig}>p_g\}$. Its utility is at least $a_i(T_i)-p(T_i)=\sum_{g\in R_i}(w_{ig}-p_g)_+$. An actual maximizing bundle gives at least that utility. Availability before this bidder depends only on previous independent types and the mechanism's exogenous randomness. It is therefore independent of the current vector $w_i$. Taking expectations proves the first inequality. The event that $g$ is never sold is contained in the event that it is available before $i$, proving the second. ∎
Theorem (Static prices for additive envelopes): Define $V_g={\mathbb{E}}\max_i w_{ig}$ and post the deterministic prices $p_g=V_g/2$. Then expected welfare obeys \[
{\mathbb{E}}\sum_i v_i(S_i)\ \geq\frac12\sum_g V_g
\ \geq\frac1{2\beta}{\mathbb{E}}{\operatorname{OPT}}(v).
\] This holds under arbitrary within-bidder correlation and history-measurable maximizing tie-breaking. The theorem remains true for valuations outside the subadditive class if they satisfy (1).
Proof: For every realization of the weights and every item, \[
\sum_i(w_{ig}-p_g)_+\geq(\max_i w_{ig}-p_g)_+
\geq\max_i w_{ig}-p_g.
\] Sum the lemma over bidders and use $q_{ig}\geq q_g$ to obtain \[
{\mathbb{E}}\sum_iU_i\geq\sum_g q_g(V_g-p_g).
\] Expected revenue is exactly $\sum_g p_g(1-q_g)$. Welfare equals utility plus revenue, even if some items remain unsold. Since $p_g=V_g-p_g=V_g/2$, the sum is at least $\sum_g V_g/2$. For any feasible allocation $(T_i)$, the upper inequality in (1) gives \[
\sum_i v_i(T_i)\leq\beta\sum_i\sum_{g\in T_i}w_{ig}
\leq\beta\sum_g\max_iw_{ig}.
\] Maximize over allocations and take expectations. All expressions are integrable by this same upper bound. If the optimal expectation is zero, the inequality is interpreted directly, without dividing by it. ∎
Corollary (Heterogeneous envelope losses): Suppose (1) holds with bidder-specific constants $\beta_i\leq\bar\beta$. The same prices guarantee $1/(2\bar\beta)$ of expected optimum. More generally the first welfare bound in the theorem needs only the lower envelopes; any separately proved upper bound ${\mathbb{E}}{\operatorname{OPT}}(v)\leq K\sum_gV_g$ yields approximation $1/(2K)$.
Proof: Use $\bar\beta$ in the allocation inequality. For the more general assertion combine the first bound in the theorem with the stated comparison. No comparison between individual purchased bundles and an offline bundle is needed. ∎
A quantitative limitation of the route
Proposition (Subadditivity does not supply a constant envelope): For the normalized monotone subadditive valuation $v(S)={\mathbf 1}\{S\ne\varnothing\}$ on $m$ items, any additive function $a(S)=\sum_{g\in S}w_g$, $w_g\geq0$, satisfying $a(S)\leq v(S)\leq\beta a(S)$ for every $S$ must have $\beta\geq m$.
Proof: The singleton upper inequalities give $w_g\geq1/\beta$ for all $g$. The lower inequality on the full set gives $\sum_gw_g\leq1$. Hence $m/\beta\leq1$. ∎
This obstruction occurs even for unit-demand values, a tractable economic subclass. It is a limitation of requiring one additive envelope valid for every bundle, not a lower bound on posted-price welfare. An additive support chosen only for an offline allocated bundle can evade it, but that support then depends on other bidders. The independence step in the utility lemma must be re-established for such a construction. Subadditivity alone does not justify making that substitution.
The theorem is existential: expectations of the surrogate maxima define prices, and we make no oracle-complexity claim for discovering a good surrogate or computing those expectations. The unresolved target is a constant independent of $m$ without condition (1), using static item prices under the original information and demand rules.
Reference and source scope
José Correa and Andrés Cristi (2023),
A Constant Factor Prophet Inequality for Online Combinatorial Auctions, STOC, pp. 686--697; author manuscript, introduction and "Posted Prices," printed pp. 14--16.
https://www.dii.uchile.cl/~jcorrea/papers/Manuscripts/2023CC.pdf. Their unrestricted $1/6$ prophet result and discussion of item prices were inspected. Our argument is an elementary restricted posted-price calculation; it is not a claim that their unrestricted algorithm is implementable by these prices.
Completion Estimate
20%