An improved approximation algorithm for combinatorial auctions with submodular bidders

Abstract

We explore the allocation problem in combinatorial auctions with submodular bidders. We provide an e/e-1 approximation algorithm for this problem. Moreover, our algorithm applies to the more general class of XOS bidders. By presenting a matching unconditional lower bound in the communication model, we prove that the upper bound is tight for the XOS class.Our algorithm improves upon the previously known 2-approximation algorithm. In fact, we also exhibit another algorithm which obtains an approximation ratio better than 2 for submodular bidders, even in the value queries model.Throughout the paper we highlight interesting connections between combinatorial auctions with XOS and submodular bidders and various other combinatorial optimization problems. In particular, we discuss coverage problems and online problems.