Combinatorial Auctions with k-wise Dependent Valuations

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), where g(m) is an arbitrary function such that g(m) → ∞ as m → ∞. We also consider approximate elicitation, in which the auctioneer learns, asking polynomially many value queries, an approximation of the bidders’ actual preferences.

Authors

• Vincent Conitzer Carnegie Mellon University

Keywords

No keywords are indexed for this paper.