Truthful Randomized Mechanisms for Combinatorial AuctionsShahar Dobzinski Noam Nisan Michael Schapira∗March 20, 2006AbstractWe design two computationally-efficient incentive-compatible mechanisms for combinatorialauctions 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 addressesthe weaker notion of incentive compatibility in expectation. The first mechanism obtains anO(√m)-approximation of the optimal social welfare for arbitrary bidder valuations – this isthe best approximation possible in polynomial time. The second one obtains an O(log2m)-approximation for a subclass of bidder valuations that includes all submodular bidders. Thisimproves over the best previously obtained incentive-compatible mechanism for this class whichonly provides an O(√m)-approximation.1 Introduction1.1 Bac kgroundThe field of Algorithmic Mechanism Design attempts to design efficient mechanisms for decentralizedcomputerized settings. These mechanisms must take into account both the strategic behavior ofthe different participants and the usual algorithmic efficiency considerations. Target applicationsinclude many types of protocols for Internet environment that necessitate looking at both issues –strategic and algorithmic – together. For an introduction see [20].The basic strategic notions are taken from the field of mechanism design – a subfield of economictheory (see [18, 23]), and in most of the work in computational settings, as in this one, the very robustnotion of equilibrium in dominant strategies is used. It is well known ([18], see [20]) that without lossof generality, we can limit ourselves to looking at “incentive compatible” mechanisms, also knownas “truthful” mechanisms or “strategy-proof” mechanisms. In such mechanisms participants arealways rationally motivated to correctly report their private information.The main difficulty in this field is the fact that the basic technique of mechanism design – namelyVCG mechanisms [25, 4, 11] – can only be applied in cases where the exact optimal outcome isachieved. However, in most interesting computational applications, exact optimization is NP-hard,and computationally-speaking we must settle for approximations or heuristics. As was observedin [20, 17], the VCG technique cannot be applied in such cases, and in fact [21] showed that thisinapplicability was essentially universal. Thus, the challenge is to design alternative incentive-compatible mechanisms for interesting applications.The problem of combinatorial auctions has gained the status of the paradigmatic problem ofthis field. For a thorough overview see [5]. In a combinatorial auction, m items are auctioned ton players. Each player i has a valuation function vithat describes his value vi(S) for each subset∗The School of Computer Science and Engineering, The Hebrew University of Jerusalem, {shahard, noam,mikesch}@cs.huji.ac.il.1S of items. The basic question is how to construct the auction mechanism that allocates all theitems in a way that maximizes the social welfare Σivi(Si)whereSiis the set of items allocated tobidder i. This problem indeed exhibits the basic issues of algorithmic mechanism design: findingthe exact optimum is computationally hard, even for the most interesting special cases, but severalapproximation algorithms, with varying approximation ratios, are known for the general case aswell as for various interesting special cases [16, 6, 7, 8]. However, these approximation algorithmsdo not yield incentive compatible mechanisms.In a landmark paper, Lehmann et al [17] were able to design an incentive-compatible, efficiently-computable, approximation mechanism – which achieves an approximation ratio that is as good ascomputationally possible Θ(√m) [24] – for the special case of “single-minded bidders”. This is thecase in which each bidder is only interested in a single bundle of goods. For this special case, aswell as some other single-parameter scenarios a host of incentive compatible mechanisms have beendesigned in the last few years (e.g., [19, 1, 10, 9]). However, almost nothing is known for moregeneral cases in which bidders have complex multi-dimensional preferences. Only two results areknown in multi-dimensional settings1: the first is a pair of algorithms that completely optimizeover a very restricted range of allocations and then use the usual VCG mechanism. These get abarely better than trivial approximation ratio of O(m/√log m) for the general case [12] and a weakO(√m) for the “complement-free” case [6] – both ratios being quite far from what is computationallypossible. The second result is the mechanism of [2] that applies only to the special case of auctionswith many duplicates of each good and indeed is not a VCG mechanism. Some evidence showingthat obtaining a non-VCG incentive-compatible mechanism for combinatorial auctions and relatedproblems would be difficult was given in [14].1.2 Randomized MechanismsIt was observed in [20] that randomized mechanisms can sometimes provide better approximationratios than deterministic ones. There are two possible definitions for incentive compatibility ofa randomized mechanism. The first and stronger one, defines an incentive-compatible randomizedmechanism as a probability distribution over incentive compatible deterministic mechanisms. Thus,this definition requires that for any fixed outcome of the random choices made by the mechanism,players still maximize their utility by reporting their true valuations. This definition was used in[20, 10, 9], and will be called incentive compatible in the universal sense. The weaker definitiononly requires that players maximize their expected utility, where the expectation is over the randomchoices of the mechanism (but still for every behavior of the other players). This was used in [15, 8](see below), and will be called incentive compatibility in expectation.There are two major implications of the difference between these two notions:1. Attitude towards risk: randomized mechanisms that are incentive compatible in expecta-tion only motivate risk-neutral bidders to act truthfully. Risk-averse bidders may benefit fromstrategic behavior. In contrast, the universal sense of incentive compatibility applies to anyattitude towards risk, as it applies to every possible realization of the random coins.2.