Improved algorithms for optimal winner determination in combinatorial auctions and generalizations-英文文献.pdf

Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations Tuomas Sandholm and Subhash Suri Department of Computer Science Washington University St. Louis, MO 63130-4899 fsandholm,suri g@ Abstract ing to sp eculate into an items valuation the impact of p ossibly getting other, complementary items. Combinatorial auctions can b e used to reach e- cient resource and task allo cations in multiagent Winner determination problem systems where the items are complementary. De- termining the winners is N P -complete and inap- The auctioneer has a set of items, M = f1; 2 ; : : : ; mg, proximable, but it was recently shown that op- to sell, and the buyers submit a set of bids, B = timal search algorithms do very well on average. fB ; B ; : : : ; B g. A bid is a tuple B = hS ; p i, where 1 2 n j j j This pap er presents a more sophisticated search S  M is a set of items and p is a price. Assume j j algorithm for optimal (and anytime) winner deter- for now (this is relaxed