Combinatorial Auctions with K-Wise Dependent Valuations

Abstract

We analyze the computational and communication complexity of combinatorial auctions from a new perspective: the degree of interdependency between the items for sale in the bidders ' preferences. Denoting by Gk the class of valuations displaying up to k-wise dependencies, we consider the hierarchy G1 G2 # # Gm , where m is the number of items for sale. We show that the minimum non-trivial degree of interdependency (2-wise dependency) is sufficient to render NP-hard the problem of computing the optimal allocation (but we also exhibit a restricted class of such valuations for which computing the optimal allocation is easy). On the other hand, bidders' preferences can be communicated efficiently (i.e., exchanging a polynomial amount of information) as long as the interdependencies between items are limited to sets of cardinality up to k, where k is an arbitrary constant. The amount of communication required to transmit the bidders' preferences becomes super-polynomial (under the assumption that only value queries are allowed) when interdependencies occur between sets of cardinality g(m), ##.