betaFeedback

WorksComputer Science

The Optimal Competitive Ratio for Subadditive Online Combinatorial Auctions is Less Than 1/2

Abstract

We construct a four-buyer online combinatorial auction with independent subadditive valuations and a fixed, known arrival order in which every online rule earns strictly less than 1/21/2 of the expected offline optimum. A common partition, revealed at the third arrival, gives the first three buyers one unit of welfare per item. If the rule uses three distinct partitions, either an item allocated early contributes zero or the fourth buyer's expected value for the remaining bundle is one less than its size. We compute the optimal online and offline welfare exactly and show that a 1/21/2 guarantee always holds with at most three buyers.

Introduction

Let MM be a finite set of indivisible items. Buyers arrive in a fixed, known order with valuations vi:2M→R≥0v_i : 2^M \to\mathbb{R}_{\ge0} drawn independently from known distributions. On buyer ii’s arrival, the rule sees viv_i and irrevocably allocates a bundle SiS_i of remaining items. Its welfare is ALG=∑ivi(Si)\mathrm{ALG} = \sum_i v_i(S_i). The prophet knows all valuations and maximizes welfare over disjoint bundles, obtaining OPT\mathrm{OPT}. Valuations are monotone and satisfy v(∅)=0v(\varnothing) = 0. Subadditivity means v(S∪T)≤v(S)+v(T)v(S \cup T) \le v(S) + v(T) for all S,T⊆MS,T \subseteq M.

For one item, the prophet inequality of Krengel, Sucheston, and Garling [3, 4] guarantees 1/21/2 of the expected maximum. Samuel-Cahn [7] showed that a single threshold achieves this guarantee. Feldman, Gravin, and Lucier [2] extended the 1/21/2 guarantee to XOS valuations using static item prices. An XOS valuation is a maximum of finitely many nonnegative additive valuations.

For subadditive valuations, Correa and Cristi [1] proved a 1/61/6 guarantee. For any ε>0\varepsilon> 0, MacRury et al. [6] gave a demand-query algorithm with guarantee 1/(6+ε)1/(6+\varepsilon), improved to 1/(60/11+ε)1/(60/11+\varepsilon) for i.i.d. valuations. Its expected running time is polynomial in the number of buyers and items, total support size, and 1/ε1/\varepsilon. For valuations with finite support, Kroll et al. [5 Theorem 1.1] gave an expected-polynomial-time demand-query algorithm with guarantee 1/4−ε1/4 - \varepsilon for every ε>0\varepsilon> 0 against the stronger ex-ante configuration LP benchmark. Taking ε↓0\varepsilon\downarrow0 gives a 1/41/4 guarantee for the optimal online rule. We show that 1/21/2 can fail even against the expected offline optimum.

Theorem 1. For some constant ε>0\varepsilon> 0, there is a four-buyer instance with independent, monotone, subadditive valuations and a fixed, known arrival order in which every online allocation rule satisfies

E[ALG]E[OPT]≤12−ε.\frac{\mathbb{E}[\mathrm{ALG}]}{\mathbb{E}[\mathrm{OPT}]} \le\frac{1}{2} - \varepsilon.

§ 4 gives an online rule that obtains at least 1/21/2 of the expected offline optimum with at most three buyers. Thus four is the smallest number of buyers for which a 1/21/2 guarantee can fail.

A stronger upper bound. A construction with a growing number of buyers gives an upper bound of approximately 0.444211, strictly below 4/94/9. The proof and Lean formalization are available in the GitHub repository.

The instance

For integers a,b≥2a,b \ge2, let C={1,…,a}×{1,…,b}C = \{1,\ldots,a\} \times\{1,\ldots,b\} be an a×ba \times b grid. An item is a labeling x:C→{1,2,3}x : C \to\{1,2,3\} that uses a label other than 1 in at most two cells. Let MM be the set of all such labelings. Counting zero, one, and two cells with labels other than 1 gives

m=∣M∣=1+2ab+4(ab2)=1+2(ab)2.m = |M| = 1 + 2ab + 4\binom{ab}{2} = 1 + 2(ab)^2.

Each cell cc partitions MM into Ai(c)={x∈M:x(c)=i}A_i(c) = \{x \in M : x(c) = i\} for i=1,2,3i = 1,2,3.

The first three buyers. Buyer 1 may use any cell. Buyer 2 may use any cell in a uniformly random row II. Buyer 3 may use any cell in an independently and uniformly drawn column JJ. If CiC_i is the set of cells available to buyer ii, her valuation is

vi(S)=max⁡c∈Ci∣S∩Ai(c)∣.v_i(S) = \max_{c \in C_i} |S \cap A_i(c)|.

Each of these valuations is XOS. All three buyers can use (I,J)(I,J), so allocating Ai(I,J)A_i(I,J) to each buyer ii earns welfare mm.

The fourth buyer. For an ordered triple e=(e1,e2,e3)e = (e_1,e_2,e_3) of distinct cells, call B(e)={x∈M:x(ei)≠i for i=1,2,3}B(e) = \{x \in M : x(e_i) \ne i \text{ for } i = 1,2,3\} a block. The fourth buyer’s expected valuation is

g(S)=∣S∣−d(S),d(S)=1{S contains a block}.g(S) = |S| - d(S), \qquad d(S) = 1\{S \text{ contains a block}\}.

Fix 0<q<1/m0 < q < 1/m. Independently of the first three buyers, buyer 4 has valuation g/qg/q with probability qq and valuation zero otherwise.

Lemma 2. Every two blocks intersect, the function gg is monotone and subadditive, and g(∅)=0g(\varnothing) = 0.

Proof. The all-1 labeling can violate the constraints of two blocks only at the first cells of their triples. At each such cell at most two labels are forbidden. Choose an allowed label there and leave all other labels equal to 1. This item belongs to both blocks, even if they coincide.

Thus every block is nonempty and g(∅)=0g(\varnothing) = 0. Adding an item increases dd by at most one, so gg is monotone. For disjoint S,TS,T at most one contains a block, giving d(S)+d(T)≤d(S∪T)d(S) + d(T) \le d(S \cup T) and hence g(S∪T)≤g(S)+g(T)g(S \cup T) \le g(S) + g(T). For arbitrary S,TS,T, the disjoint case and monotonicity give g(S∪T)≤g(S)+g(T∖S)≤g(S)+g(T)g(S \cup T) \le g(S) + g(T \setminus S) \le g(S) + g(T). □

The optimal offline and online welfare

The prophet. When buyer 4 has zero valuation, the common cell (I,J)(I,J) yields welfare mm, which is optimal since each item contributes at most one. When her valuation is g/qg/q, giving her MM yields welfare (m−1)/q(m - 1)/q. This allocation is optimal because removing any one item xx from MM leaves a block. Indeed, choose a cell e1e_1 where x(e1)=1x(e_1) = 1 and complete it to a triple ee of distinct cells. Then x∉B(e)x \notin B(e), so g(M∖{x})=m−2g(M \setminus\{x\}) = m - 2. By monotonicity, giving buyer 4 any proper subset lowers her value by at least 1/q>m1/q > m, while the first three buyers can gain at most mm. Averaging over buyer 4’s valuation gives

E[OPT]=(1−q)m+(m−1)=2m−1−qm.(1)\mathbb{E}[\mathrm{OPT}] = (1-q)m + (m-1) = 2m - 1 - qm. \tag*{(1)}

The online upper bound. After the rule assigns SiS_i to buyer i≤3i \le3, choose ci∈Cic_i \in C_i with vi(Si)=∣Si∩Ai(ci)∣v_i(S_i) = |S_i \cap A_i(c_i)|, breaking ties by a fixed order. Let RR be the items remaining after buyer 3. Conditional on the history through buyer 3, including the rule’s random choices, buyer 4 has expected value g(R)g(R) for RR. By monotonicity, conditional expected welfare is at most

∑i=13∣Si∩Ai(ci)∣+g(R)≤m.\sum_{i=1}^{3} |S_i \cap A_i(c_i)| + g(R) \le m.

If c1,c2,c3c_1, c_2, c_3 are distinct, consider the block B(c1,c2,c3)B(c_1,c_2,c_3). An item of this block assigned to buyer i≤3i \le3 lies outside Ai(ci)A_i(c_i) and contributes zero to the sum. If none of the block’s items is assigned, the whole block remains and g(R)=∣R∣−1g(R) = |R| - 1. In either case, conditional expected welfare is at most m−1m - 1.

Buyer 2’s row avoids c1c_1 with probability 1−1/a1 - 1/a. Given the history through buyer 2 on that event, buyer 3’s independent column avoids both cells with probability at least 1−2/b1 - 2/b. Thus all three cells are distinct with probability at least pa,b=(1−1/a)(1−2/b)p_{a,b} = (1 - 1/a)(1 - 2/b), giving E[ALG]≤m−pa,b\mathbb{E}[\mathrm{ALG}] \le m - p_{a,b}.

A matching online rule. Buyer 1 uses (1,1)(1,1). Buyer 2 uses (1,1)(1,1) if I=1I = 1 and (I,2)(I,2) otherwise. Buyer 3 reuses an earlier cell in her column if possible, and chooses any cell in her column otherwise. Buyer ii receives every remaining item in Ai(ci)A_i(c_i), earning one per item. The final bundle RR consists of the items with x(ci)≠ix(c_i) \ne i for all three buyers.

If the cells are distinct, RR is a block. If buyers i,ji,j share a cell uu, then every block B(e)B(e) contains an item outside RR. To construct one, choose a label in {i,j}\{i,j\} at uu allowed by B(e)B(e), which forbids at most one label there. Put 2 at e1e_1 if e1≠ue_1 \ne u, and put 1 at all remaining cells. Thus d(R)=1d(R) = 1 exactly when the cells are distinct.

Giving RR to buyer 4 yields conditional expected welfare m−d(R)m - d(R). The cells are distinct exactly when I≠1I \ne1 and J∉{1,2}J \notin\{1,2\}, which has probability pa,bp_{a,b}. The rule therefore attains m−pa,bm - p_{a,b}, and (1) gives the optimal online ratio ra,b(q)=(m−pa,b)/(2m−1−qm)r_{a,b}(q) = (m - p_{a,b})/(2m - 1 - qm).

Choosing the grid dimensions. For a fixed grid, ra,b(q)r_{a,b}(q) increases with qq, so its infimum is

lim⁡q↓0ra,b(q)=12−pa,b−1/21+4(ab)2.\lim_{q \downarrow0} r_{a,b}(q) = \frac{1}{2} - \frac{p_{a,b} - 1/2}{1 + 4(ab)^2}.

Maximizing the subtracted term over integers a,b≥2a,b \ge2 gives the largest limiting gap. The choice a=4a = 4, b=9b = 9 yields m=2,593m = 2{,}593 and p4,9=7/12p_{4,9} = 7/12, for a limiting ratio of 1/2−1/62,2201/2 - 1/62{,}220. Taking q=1/(54m)q = 1/(54m) gives the exact ratio

r4,9(154m)=279,981559,978=12−4279,989.r_{4,9}\left(\frac{1}{54m}\right) = \frac{279{,}981}{559{,}978} = \frac{1}{2} - \frac{4}{279{,}989}.

This proves theorem 1 with ε=4/279,989\varepsilon= 4/279{,}989.

At most three buyers

Theorem 3. With at most three buyers whose valuations are independent, monotone, and subadditive, there is an online allocation rule satisfying E[ALG]≥12E[OPT]\mathbb{E}[\mathrm{ALG}] \ge\frac{1}{2}\mathbb{E}[\mathrm{OPT}].

Proof. With one buyer, allocating MM is optimal. With two buyers, OPT≤v1(M)+v2(M)\mathrm{OPT} \le v_1(M) + v_2(M) by monotonicity. Allocating MM to the buyer with larger E[vi(M)]\mathbb{E}[v_i(M)] therefore gives a 1/21/2 guarantee. For three buyers, let f(R)=E[v3(R)]f(R) = \mathbb{E}[v_3(R)]. Before any buyer arrives, select one of buyers 1 and 2 uniformly at random and skip the other. On the selected buyer ii’s arrival, give her a bundle B⊆MB \subseteq M maximizing vi(B)+f(M∖B)v_i(B) + f(M \setminus B). Give the remaining items to buyer 3.

Fix v1,v2v_1, v_2 and let (S,T)(S,T) maximize v1(S)+v2(T)v_1(S) + v_2(T) over partitions of MM. By independence, conditional on v1,v2v_1, v_2 and the selection, buyer 3 has expected value f(R)f(R) for the remaining bundle RR. Each of the first two buyers is selected with probability 1/21/2. Comparing their chosen bundles with SS and TT, respectively, gives

2E[ALG∣v1,v2]≥v1(S)+f(T)+v2(T)+f(S)≥v1(S)+v2(T)+f(M),\begin{aligned} 2\mathbb{E}[\mathrm{ALG} \mid v_1,v_2] \ge v_1(S) + f(T) + v_2(T) + f(S) \\ &\ge v_1(S) + v_2(T) + f(M), \end{aligned}

where the second inequality uses subadditivity of ff. The prophet’s bundles for the first two buyers can be extended to a partition of MM without decreasing their value. By the choice of (S,T)(S,T), those buyers therefore contribute at most v1(S)+v2(T)v_1(S) + v_2(T). The third contributes at most v3(M)v_3(M), whose conditional expectation is f(M)f(M) by independence. Thus 2E[ALG∣v1,v2]≥E[OPT∣v1,v2]2\mathbb{E}[\mathrm{ALG} \mid v_1,v_2] \ge\mathbb{E}[\mathrm{OPT} \mid v_1,v_2]. Averaging over v1,v2v_1,v_2 yields E[ALG]≥12E[OPT]\mathbb{E}[\mathrm{ALG}] \ge\frac{1}{2}\mathbb{E}[\mathrm{OPT}].

Use of AI. While developing the results in this note, we worked interactively with OpenAI’s GPT-5.6 Sol, GPT-6 Ultra, and GPT-6.2 Ultra. Over several rounds of discussion, we gave the models our own ideas and candidate constructions to explore. We manually verified and simplified the four-buyer construction to make its main idea easier to follow. We take full responsibility for the contents of this paper.

References

  1. [1]José Correa and Andrés Cristi. A constant factor prophet inequality for online combinatorial auctions. In STOC, pages 686–697, 2023.DOI
  2. [2]Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In SODA, pages 123–135, 2015.
  3. [3]Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83(4):745–747, 1977.DOI
  4. [4]Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. In James Kuelbs, editor, Probability in Banach Spaces, volume 4 of Advances in Probability and Related Topics, pages 197–266. Marcel Dekker, 1978.
  5. [5]Iwan Kroll, Calum MacRury, Rebecca Reiffenhäuser, and Siddharth M. Sundaram. An efficient 1/4-competitive prophet inequality for subadditive combinatorial allocations. Submitted to STOC 2027, submission no. 1456, 2026.
  6. [6]Calum MacRury, Rian Neogi, Konstantin Pashkovich, Sahil Singla, Siddharth M. Sundaram, and Chaitanya Swamy. Efficient algorithms for online subadditive combinatorial allocations. In SODA, 2027. To appear. arXiv:2610.09050.arxiv.org/abs/2610.09050
  7. [7]Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. The Annals of Probability, 12(4):1213–1216, 1984.

Paper details

vlnc:W_y6ucnzyu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents