Search

We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a nontrivial approximation ratio of O(log²m) [STOC'06, ACM, New York, 2006, pp. 644-652], where m is the number of items. This approximation ratio was subsequently improved to O(logmlog logm) [S. Dobzinski, APPROX'07, Springer, Berlin, 2007, pp. 89-103] and then to O(logm) [P. Krysta and B. Vöcking, ICALP'12, Springer, Heidelberg, 2012, pp. 636-647]. In this paper we develop the first mechanism that breaks the logarithmic barrier. Specifically, the mechanism provides an approximation ratio of O(√logm). Similarly to previous constructions, our mechanism uses polynomially many value and demand queries and, in fact, provides the same approximation ratio for the larger class of XOS (also known as fractionally subadditive) valuations. We also develop a computationally efficient implementation of the mechanism for combinatorial auctions with budget additive bidders. Although, in general, computing a demand query is NP-hard for budget additive valuations, we observe that the specific form of demand queries that our mechanism uses can be efficiently computed when bidders are budget additive. [ABSTRACT FROM AUTHOR]