# Online Combinatorial Allocations and Auctions with Few Samples

arXiv: https://arxiv.org/abs/2409.11091 · HTML: https://mlsanity.com/paper/2409.11091/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 17 Sep 2024.

## Builds on (most cited first, 15 of 15)

- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [Prophet Inequalities with Limited Information](https://mlsanity.com/paper/1307.3736/) (2013)
- [Competitive Analysis with a Sample and the Secretary Problem](https://mlsanity.com/paper/1907.05350/) (2019)
- [Optimal Single-Choice Prophet Inequalities from Samples](https://mlsanity.com/paper/1911.07945/) (2019)
- [Single-Sample Prophet Inequalities via Greedy-Ordered Selection](https://mlsanity.com/paper/2111.03174/) (2021)
- [Combinatorial Auctions via Posted Prices](https://mlsanity.com/paper/1411.4916/) (2014)
- [Online Contention Resolution Schemes](https://mlsanity.com/paper/1508.00142/) (2015)
- [Random-Order Models](https://mlsanity.com/paper/2002.12159/) (2020)
- [Online Weighted Matching with a Sample](https://mlsanity.com/paper/2104.05771/) (2021)
- [Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs](https://mlsanity.com/paper/1612.03161/) (2016)
- [Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders](https://mlsanity.com/paper/1911.02716/) (2019)
- [Prophet Inequalities Require Only a Constant Number of Samples](https://mlsanity.com/paper/2311.09141/) (2023)
- [An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions](https://mlsanity.com/paper/2004.09784/) (2020)
- [The Two-Sided Game of Googol and Sample-Based Prophet Inequalities](https://mlsanity.com/paper/1907.06001/) (2019)
- [Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier](https://mlsanity.com/paper/2010.01420/) (2020)

## Built on by (most cited first, 3 of 3)

- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)

## Abstract (arXiv)

In online combinatorial allocations/auctions, n bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over subsets of m indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total welfare, defined as the sum of bidder valuations. A long line of work has studied this problem when the bidder valuations come from known independent distributions. In particular, for submodular/XOS valuations, we know 2-competitive algorithms/mechanisms that set a fixed price for each item and the arriving bidders take their favorite subset of the remaining items given these prices. However, these algorithms traditionally presume the availability of the underlying distributions as part of the input to the algorithm. Contrary to this assumption, practical scenarios often require the learning of distributions, a task complicated by limited sample availability. This paper investigates the feasibility of achieving O(1)-competitive algorithms under the realistic constraint of having access to only a limited number of samples from the underlying bidder distributions. Our first main contribution shows that a mere single sample from each bidder distribution is sufficient to yield an O(1)-competitive algorithm for submodular/XOS valuations. This result leverages a novel extension of the secretary-style analysis, employing the sample to have the algorithm compete against itself. Although online, this first approach does not provide an online truthful mechanism. Our second main contribution shows that a polynomial number of samples suffices to yield a (2+ε)-competitive online truthful mechanism for submodular/XOS valuations and any constant ε>0. This result is based on a generalization of the median-based algorithm for the single-item prophet inequality problem to combinatorial settings with multiple items.