Istituto di Informatica e Telematica     
Conitzer V., Sandholm T., Santi P. Combinatorial Auctions with k-wise Dependent Valuations. In: The Twentieth National Conference on Artificial Intelligence (Pittsburgh, Pennsylvania, 2005). Proceedings, pp. 248 - 254. AAAI Press, 2005.
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.
Subject combinatorial auctions
G.2.1 Combinatorics

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional