arXiv preprint ·
Improved Combinatorial Auctions with and without Samples
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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+\eps)$-approximation mechanism using $O(\log\!\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\!\log m)^2)$-approximation due to [Assadi--Kesselheim--Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log\!\log m)$. We indeed obtain an $O(\log\!\log m)$-approximate universally truthful mechanism for the secretary and offline models.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Exact Cut Complexity of Equal-Length Proportional Cake Cutting
A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm
Optimal Online Stochastic Matching
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.