Approximation algorithms for combinatorial auctions with complement-free bidders

Abstract We exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. The running time of these algorithms is polynomial in the number of items m and in the number of bidders n, even though the "input size " is exponential in m. The first algorithm provides an O(log m) approximation. The second algorithm provides an O(pm) approximation in the weaker model of value oracles. This algorithm is also incentive compatible. The third algorithm provides an improved 2-approximation for the more restricted case of "XOS bidders", a class which strictly contains submodular bidders. We also prove lower bounds on the possible approximations achievable for these classes of bidders. These bounds are not tight and we leave the gaps as open problems. 1 Introduction In a combinatorial auction, a set M of items, |M |=m, is sold to n bidders. Thecombinatorial character of the auction comes from the fact that each bidder values bundles of items, rather than valuing items directly. I.e., the i'th bidder'svalue for each bundle is given by a valuation function vi, where for each subset S ` M, vi(S) denotes the value (maximum willingness to pay) of the bundle S for bidder i. We assume that for each bidder i, vi is normalized (vi(;) = 0),and monotone (for eac