Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

Sepehr Assadi (Rutgers)

Location:  CoRE 301
Date & time: Wednesday, 11 September 2019 at 11:00AM - 12:00PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.