Vidal's library
Title: Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches
Author: Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham
Book Tittle: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence
Pages: 548--553
Publisher: Morgan Kaufmann Publishers Inc.
Year: 1999
Abstract: In combinatorial auctions, multiple goods are sold simultaneously and bidders may bid for arbitrary combinations of goods. Determining the outcome of such an auction is an optimization problem that is NP-complete in the general case. We propose two methods of overcoming this apparent intractability. The first method, which is guaranteed to be optimal, reduces running time by structuring the search space so that a modified depth-first search usually avoids even considering allocations that contain conflicting bids. Caching and pruning are also used to speed searching. Our second method is a heuristic, market-based approach. It sets up a virtual multi-round auction in which a virtual agent represents each original bid bundle and places bids, according to a fixed strategy, for each good in that bundle. We show through experiments on synthetic data that (a) our first method finds optimal allocations quickly and offers good anytime performance, and (b) in many cases our second method, despite lacking guarantees regarding optimality or running time, quickly reaches solutions that are nearly optimal.

Cited by 236  -  Google Scholar

@InProceedings{fujishima99a,
  author =	 {Yuzo Fujishima and Kevin Leyton-Brown and Yoav
                  Shoham},
  title =	 {Taming the Computational Complexity of Combinatorial
                  Auctions: Optimal and Approximate Approaches},
  googleid =	 {5ef8b4HHSAEJ:scholar.google.com/},
  booktitle =	 {Proceedings of the Sixteenth International Joint
                  Conference on Artificial Intelligence},
  year =	 1999,
  pages =	 {548--553},
  publisher =	 {Morgan Kaufmann Publishers Inc.},
  abstract =	 {In combinatorial auctions, multiple goods are sold
                  simultaneously and bidders may bid for arbitrary
                  combinations of goods. Determining the outcome of
                  such an auction is an optimization problem that is
                  NP-complete in the general case. We propose two
                  methods of overcoming this apparent
                  intractability. The first method, which is
                  guaranteed to be optimal, reduces running time by
                  structuring the search space so that a modified
                  depth-first search usually avoids even considering
                  allocations that contain conflicting bids. Caching
                  and pruning are also used to speed searching. Our
                  second method is a heuristic, market-based
                  approach. It sets up a virtual multi-round auction
                  in which a virtual agent represents each original
                  bid bundle and places bids, according to a fixed
                  strategy, for each good in that bundle. We show
                  through experiments on synthetic data that (a) our
                  first method finds optimal allocations quickly and
                  offers good anytime performance, and (b) in many
                  cases our second method, despite lacking guarantees
                  regarding optimality or running time, quickly
                  reaches solutions that are nearly optimal.},
  keywords =     {combinatorial auctions},
  url =		 {http://jmvidal.cse.sc.edu/library/fujishima99a.pdf},
  cluster = 	 {92543151104649189}
}
Last modified: Wed Mar 9 10:14:43 EST 2011