@booklet {shahardobzinski-trmfca2005,
	title = {Truthful Randomized Mechanisms for Combinatorial Auctions},
	howpublished = {Discussion Papers},
	year = {2005},
	month = {11},
	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({\textquoteright}{\textasciicircum}\v sm)-approximation of the optimal social welfare for arbitrary bidder valuations {\textendash} 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({\textquoteright}{\textasciicircum}\v sm)-approximation.},
	url = {/files/dp408.pdf},
	author = {Shahar Dobzinski, Noam Nisan and Schapira, Michael}
}
