Online Combinatorial Auctions

We study combinatorial auctions in online environments with the goal of maximizing social welfare. In this problem, new items become available on each day and must be sold before their respective expiration dates. We design online auctions for the widely studied classes of submodular and XOS valuations, and show the following results: – For submodular valuations, we give an O(log m)-competitive mechanism for adversarial valuations and an O(1)-competitive mechanism for Bayesian valuations, where m is the total number of items. Both these mechanisms are computationally efficient and universally truthful for myopic agents, i.e., agents with no knowledge of the future. – For XOS valuations, we show that there is no online mechanism that can achieve a competitive ratio of o ((m/ log m)1/3) even in a Bayesian setting. Our lower bound holds even if we do not require truthfulness and/or computational efficiency of the mechanism. This establishes a sharp separation between XOS valuations and its subclass of submodular valuations for online combinatorial auctions. In contrast, no such separation exists for offline auctions, where the best bounds for both submodular and XOS valuations are O((log log m)3) for adversarial settings (Assadi and Singla, FOCS 2019) and O(1) for Bayesian settings (Dütting et al., FOCS 2017). In contrast to the above, if items do not expire and only need to be sold before the market closes, then we give a reduction from offline to online mechanisms that preserves the competitive ratio for all subadditive valuations (that includes XOS and submodular valuations), thereby achieving the same bounds as the respective best offline mechanisms.

• Algorithms and Theory

• Economics and Electronic Commerce