Improving the Computational Efficiency of Combinatorial Auction Algorithms
Abstract
This paper introduces two algorithms (both actually are variants of a
single algorithm)—the First price Upper Bound, FUB, and SEcond price
Lower Bound, SeLB, algorithms—aimed at serving as subroutines in
computationally efficient algorithms for combinatorial auctions. The type
of combinatorial auctions treated in the paper are the once where bids
are placed on one unit of one or more items at a certain valuation of
the combinatoin. Thus, he problem is to find a combination of bids that
maximizes the total surplus, while the combination is feasible (i.e. at
most one unit per commodity can be requested in the combination). Consequently,
this problem is equivalent to weighted k-set packing. The FUB algorithm
gives an upper bound on the total surplus. The SeLB algorithm gives 1)
an approximate solution (and hence a lower bound) and 2) a ranking of
bids, named the SEcond Price Surplus (SePS) rank.
Empirical studies suggests that these algorithms are at least one to
two orders of magnitudes faster than current algorithms for optimal winner
determination, for example the algorithms by Sandholm and Fujishima et
al. The studies also show that the approximate solution often is of very
high quality (often within 5% from the optimal solution). The ranking
tends to rank bids such that bids with a high probability have a high
rank—often less than 1% of the search space needs to be considered
in order to find the optimal solution, and combinations with high surplus
are found very early. The main implication of this is that it seems that
FUB and SeLB algorithms can be run before the current algorithms in order
to drastically improve the anytime performance (i.e. very rapidly come
up with a high quality solution) and significantly reduce the time required
for finding the optimal solution.
Novel algorithms for winner determination based on repeated usage of
FUB and SeLB are currently under evaluation.
| |
