Online Combinatorial Auctions with Few Samples

In online combinatorial auctions, $n$ bidders sequentially arrive, each with a combinatorial valuation (such as submodular/XOS) over $m$ indivisible items. The aim is to immediately allocate a subset of the remaining items to maximize the total \emph{welfare}, defined as the sum of bidder valuations. % A long line of work has studied this problem when the bidder valuations come from known distributions. In particular, 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 at these prices. However, these studies assume that the distributions are given to the algorithm as input. This paper explores the possibility of $O(1)$-competitive algorithms when only a handful of samples from the underlying distributions are provided. 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 polynomial number of samples suffice to yield an $O(1)$-competitive online truthful mechanism for submodular/XOS valuations. 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. Based on a joint work with Paul Dutting, Thomas Kesselheim, Brendan Lucier, and Rebecca Reiffenhauser.