@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}
}