Vidal's library
Title: Bidding and Allocation in Combinatorial Auctions
Author: Noam Nisan
Book Tittle: Proceedings of the ACM Conference on Electronic Commerce
Pages: 1--12
Year: 2000
Abstract: When an auction of multiple items is performed it is often desirable to allow bids on combinations of items as opposed to only on single items. Such an auction is often called combinatorial and the exponential number of possible combinations results in computational intractability of many aspects regarding such an auction. This paper considers two of these aspects: the bidding language and the allocation algorithm. First we consider which kinds of bids on combinations are allowed and how i.e., in what language they are specied. The basic tradeoff is the expressibility of the language versus its simplicity. We consider and formalize several bidding languages and compare their strengths. We prove exponential separations between the expressive power of different languages and show that one language OR bids with phantom items can polynomially simulate the others. We then consider the problem of determining the best allocation---a problem known to be computationally intractable. We suggest an approach based on Linear Programming LP and motivate it. We prove that the LP approach finds an optimal allocation if and only if prices can be attached to single items in the auction. We pinpoint several classes of auctions where this is the case and suggest greedy and branch and bound heuristics based on LP for other cases.

Cited by 237  -  Google Scholar

@InProceedings{nisan00a,
  author =	 {Noam Nisan},
  title =	 {Bidding and Allocation in Combinatorial Auctions},
  googleid =	 {EFLYQOrZgaMJ:scholar.google.com/},
  booktitle =	 {Proceedings of the {ACM} Conference on Electronic
                  Commerce},
  pages =	 {1--12},
  year =	 2000,
  abstract =	 {When an auction of multiple items is performed it is
                  often desirable to allow bids on combinations of
                  items as opposed to only on single items. Such an
                  auction is often called combinatorial and the
                  exponential number of possible combinations results
                  in computational intractability of many aspects
                  regarding such an auction. This paper considers two
                  of these aspects: the bidding language and the
                  allocation algorithm. First we consider which kinds
                  of bids on combinations are allowed and how i.e., in
                  what language they are specied. The basic tradeoff is
                  the expressibility of the language versus its
                  simplicity. We consider and formalize several bidding
                  languages and compare their strengths. We prove
                  exponential separations between the expressive power
                  of different languages and show that one language OR
                  bids with phantom items can polynomially simulate
                  the others. We then consider the problem of
                  determining the best allocation---a problem known to
                  be computationally intractable. We suggest an
                  approach based on Linear Programming LP and motivate
                  it. We prove that the LP approach finds an optimal
                  allocation if and only if prices can be attached to
                  single items in the auction. We pinpoint several
                  classes of auctions where this is the case and
                  suggest greedy and branch and bound heuristics based
                  on LP for other cases. },
  keywords =     {combinatorial auctions},
  url =		 {http://jmvidal.cse.sc.edu/library/nisan00a.pdf},
  cluster = 	 {11781937700311421456}
}
Last modified: Wed Mar 9 10:14:57 EST 2011