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 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 guarantee always holds with at most three buyers.
Introduction
Let be a finite set of indivisible items. Buyers arrive in a fixed, known order with valuations drawn independently from known distributions. On buyer ’s arrival, the rule sees and irrevocably allocates a bundle of remaining items. Its welfare is . The prophet knows all valuations and maximizes welfare over disjoint bundles, obtaining . Valuations are monotone and satisfy . Subadditivity means for all .
For one item, the prophet inequality of Krengel, Sucheston, and Garling [3, 4] guarantees of the expected maximum. Samuel-Cahn [7] showed that a single threshold achieves this guarantee. Feldman, Gravin, and Lucier [2] extended the 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 guarantee. For any , MacRury et al. [6] gave a demand-query algorithm with guarantee , improved to for i.i.d. valuations. Its expected running time is polynomial in the number of buyers and items, total support size, and . For valuations with finite support, Kroll et al. [5 Theorem 1.1] gave an expected-polynomial-time demand-query algorithm with guarantee for every against the stronger ex-ante configuration LP benchmark. Taking gives a guarantee for the optimal online rule. We show that can fail even against the expected offline optimum.
Theorem 1. For some constant , there is a four-buyer instance with independent, monotone, subadditive valuations and a fixed, known arrival order in which every online allocation rule satisfies
§ 4 gives an online rule that obtains at least of the expected offline optimum with at most three buyers. Thus four is the smallest number of buyers for which a 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 . The proof and Lean formalization are available in the GitHub repository.
The instance
For integers , let be an grid. An item is a labeling that uses a label other than 1 in at most two cells. Let be the set of all such labelings. Counting zero, one, and two cells with labels other than 1 gives
Each cell partitions into for .
The first three buyers. Buyer 1 may use any cell. Buyer 2 may use any cell in a uniformly random row . Buyer 3 may use any cell in an independently and uniformly drawn column . If is the set of cells available to buyer , her valuation is
Each of these valuations is XOS. All three buyers can use , so allocating to each buyer earns welfare .
The fourth buyer. For an ordered triple of distinct cells, call a block. The fourth buyer’s expected valuation is
Fix . Independently of the first three buyers, buyer 4 has valuation with probability and valuation zero otherwise.
Lemma 2. Every two blocks intersect, the function is monotone and subadditive, and .
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 . Adding an item increases by at most one, so is monotone. For disjoint at most one contains a block, giving and hence . For arbitrary , the disjoint case and monotonicity give . □
The optimal offline and online welfare
The prophet. When buyer 4 has zero valuation, the common cell yields welfare , which is optimal since each item contributes at most one. When her valuation is , giving her yields welfare . This allocation is optimal because removing any one item from leaves a block. Indeed, choose a cell where and complete it to a triple of distinct cells. Then , so . By monotonicity, giving buyer 4 any proper subset lowers her value by at least , while the first three buyers can gain at most . Averaging over buyer 4’s valuation gives
The online upper bound. After the rule assigns to buyer , choose with , breaking ties by a fixed order. Let 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 for . By monotonicity, conditional expected welfare is at most
If are distinct, consider the block . An item of this block assigned to buyer lies outside and contributes zero to the sum. If none of the block’s items is assigned, the whole block remains and . In either case, conditional expected welfare is at most .
Buyer 2’s row avoids with probability . Given the history through buyer 2 on that event, buyer 3’s independent column avoids both cells with probability at least . Thus all three cells are distinct with probability at least , giving .
A matching online rule. Buyer 1 uses . Buyer 2 uses if and otherwise. Buyer 3 reuses an earlier cell in her column if possible, and chooses any cell in her column otherwise. Buyer receives every remaining item in , earning one per item. The final bundle consists of the items with for all three buyers.
If the cells are distinct, is a block. If buyers share a cell , then every block contains an item outside . To construct one, choose a label in at allowed by , which forbids at most one label there. Put 2 at if , and put 1 at all remaining cells. Thus exactly when the cells are distinct.
Giving to buyer 4 yields conditional expected welfare . The cells are distinct exactly when and , which has probability . The rule therefore attains , and (1) gives the optimal online ratio .
Choosing the grid dimensions. For a fixed grid, increases with , so its infimum is
Maximizing the subtracted term over integers gives the largest limiting gap. The choice , yields and , for a limiting ratio of . Taking gives the exact ratio
This proves theorem 1 with .
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 .
Proof. With one buyer, allocating is optimal. With two buyers, by monotonicity. Allocating to the buyer with larger therefore gives a guarantee. For three buyers, let . Before any buyer arrives, select one of buyers 1 and 2 uniformly at random and skip the other. On the selected buyer ’s arrival, give her a bundle maximizing . Give the remaining items to buyer 3.
Fix and let maximize over partitions of . By independence, conditional on and the selection, buyer 3 has expected value for the remaining bundle . Each of the first two buyers is selected with probability . Comparing their chosen bundles with and , respectively, gives
where the second inequality uses subadditivity of . The prophet’s bundles for the first two buyers can be extended to a partition of without decreasing their value. By the choice of , those buyers therefore contribute at most . The third contributes at most , whose conditional expectation is by independence. Thus . Averaging over yields .
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]José Correa and Andrés Cristi. A constant factor prophet inequality for online combinatorial auctions. In STOC, pages 686–697, 2023.DOI
- [2]Michal Feldman, Nick Gravin, and Brendan Lucier. Combinatorial auctions via posted prices. In SODA, pages 123–135, 2015.
- [3]Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical Society, 83(4):745–747, 1977.DOI
- [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]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]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]Ester Samuel-Cahn. Comparison of threshold stop rules and maximum for independent nonnegative random variables. The Annals of Probability, 12(4):1213–1216, 1984.