@Article{sandholm02b,
  author =	 {Tuomas Sandholm},
  title =	 {An Algorithm for Winner Determination in
                  Combinatorial Auctions},
  googleid =	 {4QiRpWWVWlsJ:scholar.google.com/},
  journal =	 {Artificial Intelligence},
  year =	 2002,
  volume =	 135,
  number =	 {1-2},
  pages =	 {1--54},
  month =	 {February},
  abstract =	 {Combinatorial auctions, that is, auctions where
                  bidders can bid on combinations of items, tend to
                  lead to more efficient allocations than traditional
                  auction mechanisms in multi-item auctions where the
                  agents valuations of the items are not
                  additive. However, determining the winners so as to
                  maximize revenue isNP-complete. First, we analyze
                  existing approaches for tackling this problem:
                  exhaustive enumeration, dynamic programming, and
                  restricting the allowable combinations. Second, we
                  study the possibility of approximate winner
                  determination, proving inapproximability in the
                  general case, and discussing approximation
                  algorithms for special cases. We then present our
                  search algorithm for optimal winner
                  determination. Experiments are shown on several bid
                  distributions which we introduce. The algorithm
                  allows combinatorial auctions to scale up to
                  significantly larger numbers of items and bids than
                  prior approaches to optimal winner determination by
                  capitalizing on the fact that the space of bids is
                  sparsely populated in practice. The algorithm does
                  this by provably sufficient selective generation of
                  children in the search tree, by using a secondary
                  search for fast child generation, by using
                  heuristics that are admissible and optimized for
                  speed, and by preprocessing the search space in four
                  ways. Incremental winner determination and quote
                  computation techniques are presented. We show that
                  basic combinatorial auctions only allow bidders to
                  express complementarity of items.We then introduce
                  two fully expressive bidding languages, called
                  XOR-bids and OR-of-XORs, with which bidders can
                  express general preferences (both complementarity
                  and substitutability). The latter language is more
                  concise.We show how these languages enable the use
                  of the Vickrey Clarke Groves mechanism to construct
                  a combinatorial auction where each bidder s dominant
                  strategy is to bid truthfully. Finally, we extend
                  our search algorithm and preprocessors to handle
                  these languages },
  keywords =     {multiagent combinatorial auctions},
  url =		 {http://jmvidal.cse.sc.edu/library/sandholm02b.pdf},
  citeseer =	 {533603.html},
  doi =		 {10.1016/S0004-3702(01)00159-X},
  cluster = 	 {6582738069157382369}
}