Truthful randomized mechanisms for combinatorial auctions

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(log 2 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.

Authors

• Shahar Dobzinski
• Noam Nisan
• Michael Schapira

Keywords

• combinatorial auctions
• incentive compatibility