Economics Faculty Database
Economics
Arts & Sciences
Duke University

 HOME > Arts & Sciences > Economics > Faculty    Search Help Login pdf version printable version 

Publications [#236217] of Vincent Conitzer

Journal articles or Book chapters PUBLISHED

  1. Conitzer, V; Sandholm, T; Santi, P, Combinatorial auctions with k-wise dependent valuations, Proceedings of the National Conference on Artificial Intelligence, vol. 1 (December, 2005), pp. 248-254
    (last updated on 2024/03/29)

    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 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.


Duke University * Arts & Sciences * Economics * Faculty * Research * Staff * Master's * Ph.D. * Reload * Login