Truthful Randomized Mechanisms for Combinatorial Auctions

Shahar Dobzinski, Noam Nisan and Michael Schapira

We design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. Both mechanisms are randomized, and are incentive-compatible in the universal sense. This is in contrast to recent previous work that only addresses the weaker notion of incentive compatibility in expectation. The first mechanism obtains an O(√m)-approximation of the optimal social welfare for arbitrary bidder valuations -- this is the best approximation possible in polynomial time. The second one obtains an O(log2 m)-approximation for a subclass of bidder valuations that includes all submodular bidders. This improves over the best previously obtained incentive-compatible mechanism for this class which only provides an O(√m)-approximation.

November, 2005
Published in: