Integer Programming for Combinatorial Auction Winner Determination
Abstract
Combinatorial auctions are important as they enable bidders to place bids
on combinations of items; compared to other auction mechanisms, they often
increase the efficiency of the auction, while keeping risks for bidders
low. However, the determination of an optimal winner combination in combinatorial
auctions is a complex computational problem.
In this paper we (i) compare recent algorithms for winner determination
to traditional algorithms, (ii) present and benchmark a mixed integer
programming approach to the problem, which enables very general auctions
to be treated efficiently by standard integer programming algorithms (and
hereby also by commercially available software), and (iii) discuss the
impact of the probability distributions chosen for benchmarking.
The entire paper in PDF format.
Last edited April 25, 2000 by ygge@enersearch.se. |
|
