Efficient Algorithms for Online Subadditive Combinatorial Allocations

We give a polynomial-time algorithm for online combinatorial auctions with subadditive valuations whose expected social welfare is at least a $1/(6+\varepsilon)$ fraction of the optimal offline welfare, and, as a consequence of the same techniques, a $(2+\varepsilon)$-approximation for the offline problem. The online bound improves on the previous best polynomial-time guarantee of $O(\log\log m)$, due to Dütting, Kesselheim, and Lucier, and it attains the constant $6$ that Correa and Cristi had reached only in exponential time; the offline bound matches the best ratio known for the problem. All these results rest on a family of bid profiles we call mutually mirroring strategies. In the auction where agents bid on individual items and each item goes to its highest bidder, we show that any mutually mirroring profile induces an allocation within $2+\varepsilon$ of optimal. Run inside the online auction format of Correa and Cristi, the same profiles degrade only to $6+\varepsilon$. Finally, they can be sampled in polynomial time, which converts both structural guarantees into algorithms.