Seminars

View all Seminars  |  Download ICal for this event

Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

Series: Theory Seminar Series

Speaker: Dr. Sahil Singla Research Instructor (postdoc) Princeton University USA

Date/Time: Nov 27 04:36:41

Location: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract:
A longstanding open problem in Algorithmic Mechanism Design is to design computationally e?cient 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]. We present a computationally-e?cient truthful mechanism with approximation ratio that improves upon the state-of-the-art by an exponential factor. In particular, our mechanism achieves an O((loglog m)^3)-approximation in expectation, uses only O(n) demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether ?(sqrt{log m}) is the best approximation ratio in this setting in negative.
This is based on a joint work with Sepehr Assadi and appeared in FOCS 2019.

Speaker Bio:
Sahil Singla is a Research Instructor (postdoc) at Princeton University and the Institute for Advanced Study. Prior to this, he was a graduate student at Carnegie Mellon University where he was advised by Prof Manuel Blum and Prof Anupam Gupta. Broadly, his research interests are in theoretical problems related to the theme `Optimization Under Uncertainty\\\'. More particularly, he has been working on discrete optimization problems using uncertainty models from areas like Online & Approximation Algorithms, Machine Learning Theory, and Algorithmic Game Theory.

Host Faculty: Dr. Arindam Khan