Approximating Revenue Maximizing Combinatorial Auctions Anton Likhodedov and Tuomas Sandholm Carnegie Mellon University Computer Science Department 5000 Forbes Avenue Pittsburgh PA 15213 likh sandholm cs cmu edu Abstract Designing revenue maximizing combinatorial auctions CAs is a recognized open problem in mechanism design It is unsolved even for two bidders and two items for sale Rather than attempting to characterize the optimal auction we focus on designing approximations suboptimal auction mechanisms which yield high revenue Our approximations belong to the family of virtual valuations combinatorial auctions VVCA VVCA is a Vickrey ClarkeGroves VCG mechanism run on virtual valuations that are linear transformations of the bidders real valuations We pursue two approaches to constructing approximately optimal CAs The first is to construct a VVCA with worst case and average case performance guarantees We give a logarithmic approximation auction for basic important special cases of the problem 1 limited supply of items on sale with additive valuations and 2 unlimited supply The second approach is to search the parameter space of VVCAs in order to obtain high revenue mechanisms for the general problem We introduce a series of increasingly sophisticated algorithms that use economic insights to guide the search and thus reduce the computational complexity Our experiments demonstrate that in many cases these algorithms perform almost as well as the optimal VVCA yield a substantial increase in revenue over the VCG mechanism and drastically outperform the straightforward algorithms in run time 1 Introduction Combinatorial auctions CAs where agents can bid on bundles of items are popular autonomy preserving ways of allocating items goods tasks resources services etc They are relatively efficient both in terms of process and outcome and are extensively used in a variety of allocation problems in economics and computer science One of the main open problems in CAs and the whole field of mechanism design is designing optimal auctions that is auctions that maximize the seller s expected revenue A major advance on the problem was the full characterization of 1 item auctions Myerson 1981 later extended to the case of selling multiple units of the same item However the characterization of multi item auctions has been obtained only for very specialized models two Copyright c 2005 American Association for Artificial Intelligence www aaai org All rights reserved items two agents drawing valuations for the items from the same binary distribution Avery Hendershott 2000 Armstrong 2000 Rather than attempting to characterize the optimal CA we focus on designing approximations suboptimal auction mechanisms which yield high revenue Our approximations belong to the family of virtual valuations combinatorial auctions VVCA Likhodedov Sandholm 2004 VVCA is a Vickrey Clarke Groves VCG mechanism run on virtual valuations that are linear transformations of the bidders real valuations The coefficients of these linear transformations parameterize the family of VVCAs The restriction to linear transformations is motivated by incentive compatibility In this paper we use the VVCA concept to design the mechanisms which yield high revenue In Section 3 we design a randomized mechanism based on VVCAs that yields a logarithmic worst case approximation and deterministic VVCAs that yield a logarithmic average case approximation to the optimal auction for the basic settings of 1 items in limited supply and additive valuations no complementary or substitutable items and 2 items in unlimited supply and general valuations In Section 4 we pursue the approach of designing the high revenue auctions automatically We present increasingly sophisticated algorithms for searching the parametric families of VVCAs and a more general family of affine maximizer auctions AMA for good parameters for the specific setting seller s prior over the bidders valuations The algorithms use economic insights to navigate the search space efficiently in order to enhance computational speed The experiments show that they yield significantly higher revenue than the VCG that they scale much better than the previous automated design algorithms for this problem Conitzer Sandholm 2003 Likhodedov Sandholm 2004 and that the more sophisticated methods indeed drastically outperform the more obvious ones in both absolute run time and anytime performance 2 Notation and framework We study a setting with one seller index 0 refers to the seller a set N of n bidders and a set G g1 gm of heterogeneous items on sale In an auction the bidders submit bids for the bundles of items and the auction rules determine the allocation a and the payments t where ai is the bundle of goods that bidder i receives and ti is the payment by bidder i 2 1 Valuations and mechanism design principles We make the standard assumption that each bidder i has a quasi linear utility function ui vi a ti where vi a is the valuation of bidder i for allocation a Each bidder s true valuations are private information Thus a bidder might strategically misrepresent her valuations in order to gain higher utility As is standard in the computer science mechanism design literature we focus on ex post incentive compatible IC mechanisms that is mechanisms where each bidder maximizes her utility by bidding truthfully regardless of what valuations the other bidders reveal Such mechanisms are also called dominant strategy mechanisms They are robust in the sense that the bidders do not benefit from counterspeculating each others valuations and rationality Limiting the scope to truthful mechanisms is without loss of generality the well known revelation principle shows that anything that can be accomplished with an arbitrary mechanism can also be accomplished with a truth promoting mechanism Mas Colell Whinston Green 1995 As usual we also require that the mechanism be ex post individually rational IR each bidder is no worse off by participating than not participating for all possible valuation revelations of the other bidders 2 2 An important family of auctions that satisfies the above conditions is the affine maximizer auction AMA Definition 2 1 Affine maximizer auction AMA Each bidder i submits her valuations vi The allocation a is computed so as to maximize1 n X i vi a a 2 1 i 0 Here i are positive numbers and a is an arbitrary function of allocation Both and are chosen by the auction designer and they are common