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 G k the class of valuations displaying up to k-wise dependencies, we consider the hierarchy G 1 ⊂ G 2 ⊂ ⋯ ⊂ G m, 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. Copyright © 2005, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
