Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders

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 ISTOC'061 who gave an 0(10g2 m) -approximation where m is number of items. This problem has been studied extensively since, culminating in an 0 (A/log m) -approximation mechanism by Dobzinski ISTOC'161. We present a computationally-efficient truthful mechanism with approximation ratio that improves upon the state-of-theart by an exponential factor. In particular, our mechanism achieves an 0 ((log log m) 3)-approximation in expectation, uses only 0(n) demand queries, and has universal truthfulness guarantee. This settles an open question of Dobzinski on whether O(\/log m) is the best approximation ratio in this setting in negative.