Vidal's library
Title: Partial-revelation VCG mechanism for combinatorial auctions
Author: Wolfram Conen and Tuomas Sandholm
Book Tittle: Proceedings of the National Conference on Artificial Intelligence
Pages: 367--372
Year: 2002
Abstract: Winner determination in combinatorial auctions has received significant interest in the AI community in the last 3 years. Another difficult problem in combinatorial auctions is that of eliciting the bidders' preferences. We introduce a progressive, partial-revelation mechanism that determines an efficient allocation and the Vickrey payments. The mechanism is based on a family of algorithms that explore the natural lattice structure of the bidders' combined preferences. The mechanism elicits utilities in a natural sequence, and aims at keeping the amount of elicited information and the effort to compute the information minimal. We present analytical results on the amount of elicitation. We show that no valuequerying algorithm that is constrained to querying feasible bundles can save more elicitation than one of our algorithms. We also show that one of our algorithms can determine the Vickrey payments as a costless by-product of determining an optimal allocation.

Cited by 47  -  Google Scholar

@InProceedings{conen02a,
  author =	 {Wolfram Conen and Tuomas Sandholm},
  title =	 {Partial-revelation {VCG} mechanism for combinatorial
                  auctions},
  booktitle =	 {Proceedings of the National Conference on Artificial
                  Intelligence},
  pages =	 {367--372},
  year =	 2002,
  abstract =	 {Winner determination in combinatorial auctions has
                  received significant interest in the AI community in
                  the last 3 years. Another difficult problem in
                  combinatorial auctions is that of eliciting the
                  bidders' preferences. We introduce a progressive,
                  partial-revelation mechanism that determines an
                  efficient allocation and the Vickrey payments. The
                  mechanism is based on a family of algorithms that
                  explore the natural lattice structure of the
                  bidders' combined preferences. The mechanism elicits
                  utilities in a natural sequence, and aims at keeping
                  the amount of elicited information and the effort to
                  compute the information minimal. We present
                  analytical results on the amount of elicitation. We
                  show that no valuequerying algorithm that is
                  constrained to querying feasible bundles can save
                  more elicitation than one of our algorithms. We also
                  show that one of our algorithms can determine the
                  Vickrey payments as a costless by-product of
                  determining an optimal allocation.},
  url = 	 {http://jmvidal.cse.sc.edu/library/conen02a.pdf},
  keywords = 	 {auctions},
  cluster = 	 {17961555476411548930}
}
Last modified: Wed Mar 9 10:15:39 EST 2011