Improved Combinatorial Auctions with and without Samples

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their values from independent distributions. We give a universally truthful, polynomial-time $(2+\text{eps})$-approximation mechanism using $O(\log \text{\hspace{0.17em}⁣}\log m)$ samples from each distribution. The approximation factor is tight even for a single item and without the incentive constraints, due to the classic prophet inequality. Compared to the previous state-of-the-art with the same guarantees [Dütting–Kesselheim–Lucier–Reiffenhäuser–Singla (FOCS 2024)], our running time is exponentially faster, and our sample complexity is doubly-exponentially lower, resolving two explicit open problems by Dütting et al. * Using the same techniques, we also obtain improved mechanisms in the secretary and offline versions, where the values are worst-case, and buyers are processed in either random order (secretary) or without any timing restrictions (offline). After a long line of works, the state of the art in both models is an $O((\log \text{\hspace{0.17em}⁣}\log m{)}^2)$-approximation due to [Assadi–Kesselheim–Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log \text{\hspace{0.17em}⁣}\log m)$. We indeed obtain an $O(\log \text{\hspace{0.17em}⁣}\log m)$-approximate universally truthful mechanism for the secretary and offline models.