# Truthful Randomized Mechanisms for Combinatorial Auctions

Shahar Dobzinski (), Noam Nisan and Michael Schapira ()

Abstract: 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(\sqrt{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(\sqrt m)$-approximation.

New Economics Papers: this item is included in nep-gth
Date: 2005-11
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2) Track citations by RSS feed

http://ratio.huji.ac.il/sites/default/files/publications/dp408.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text