Seminar Details
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
- Start Date: September 11, 2019
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Sepehr Assadi - Princeton University
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Presentation Type: Stand Alone Presentation
- Abstract:
A longstanding open problem in Algorithmic Mechanism Design is to design computationally-efficient truthful mechanisms for (approximately) maximizing welfare in combinatorial auctions with submodular bidders. The first such mechanism was obtained by Dobzinski, Nisan, and Schapira [STOC’06] who gave an O(log^2 m)-approximation where m is number of items. This problem has been studied extensively since, culminating in an O(sqrt{log m})-approximation mechanism by Dobzinski [STOC’16].
In this talk, we present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an O((log log m)^3)-approximation in expectation, uses only O(n) demand queries, and has universal truthfulness guarantee.
Based on joint work with Sahil Singla; to appear in FOCS 19.