Seminars
View all Seminars | Download ICal for this eventImproved 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)
Faculty Advisor:
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 ï¬rst 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-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((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