An Algorithm for Multi-Unit Combinatorial Auctions

Kevin Leyton-Brown, Yoav Shoham, Moshe TennenholtzAAAI 2000 · OpenReview

Abstract

We present CAMUS (Combinatorial Auction Multi-Unit Search), a novel algorithm for computing optimal winning bids in multi-unit combinatorial auctions (CAs). While previous research primarily addressed single-unit CAs, our approach handles the more general case where multiple units of each good are available and bids can specify arbitrary quantities. By combining a branch-and-bound search with specialized dynamic programming and caching, CAMUS achieves efficient performance on complex allocation problems.

Introduction

Combinatorial auctions allow bidders to place bids on bundles of items, capturing the synergies between different goods. However, determining the optimal allocation—the Winner Determination Problem (WDP)—is NP-complete. Prior to this work, algorithms were largely restricted to single-unit auctions. In real-world scenarios, sellers often possess multiple identical units of various goods. Treating each unit as a unique item leads to a combinatorial explosion that renders single-unit algorithms impractical. CAMUS addresses this gap by directly modeling multi-unit availability.

The CAMUS Algorithm

The core of CAMUS is a depth-first branch-and-bound search. To manage the complexity of multi-unit allocations, the algorithm incorporates several key optimizations:

Dynamic Programming for Singletons

Bids requesting only a single type of good (singletons) are common and can significantly increase the search space. CAMUS employs a preprocessing step using dynamic programming to find the optimal way to satisfy singleton bids for every possible quantity. These pre-calculated results are then treated as atomic bids during the main search, drastically reducing the branching factor.

Pruning and Caching

To prune the search tree, CAMUS uses a computationally inexpensive relaxation. It calculates an upper bound on potential revenue by assuming remaining goods can be sold at the best average price per unit found in the remaining bids. If the current revenue plus this upper bound is less than the best solution found so far, the branch is pruned. Additionally, a hash-based caching mechanism stores results of sub-searches, allowing the algorithm to bypass redundant calculations when encountering previously explored states.

Experimental Results

The algorithm was evaluated using synthetic datasets designed to simulate realistic bidding patterns, where the number of goods and units per good follow a decay distribution.

Scalability and Performance

Experiments demonstrated that CAMUS scales effectively with both the number of bids and the number of goods. As shown in the figure below, while the search time grows with the number of bids, the growth is sub-exponential, making it feasible for large-scale auctions even with 40 units across 16 goods.

Scaling of search time with the number of bids across different problem sizes.

Anytime Utility and Near-Optimality

One of the most significant features of CAMUS is its "anytime" nature. It quickly identifies high-quality solutions and then spends the remaining time proving their optimality. Data illustrates that finding a 99% optimal solution is roughly an order of magnitude faster than finding and proving the 100% optimal allocation.

Time required to reach different levels of optimality as a function of the number of bids.

Conclusion

CAMUS represents a significant step forward in combinatorial auction research by providing a robust solution for the multi-unit WDP. The integration of dynamic programming with branch-and-bound search allows for efficient handling of large bid sets. Future work will focus on refining heuristics and exploring the algorithm's performance on real-world bidding data.

Summary updated

Abstract

We present a novel algorithm for computing the optimal winning bids in a combinatorial auction (CA), that is, an auction in which bidders bid for bundles of goods. All previously published algorithms are limited to single-unit CAs, already a hard computational problem. In contrast, here we address the more general problem in which each good may have multiple units, and each bid speci€es an unrestricted number of units desired from each good. We prove the correctness of our branch-and-bound algorithm, which incorporates a specialized dynamic programming procedure. We then provide very encouraging initial experimental results from an implemented version of the algorithm.
BibTeX
@inproceedings{leytonbrown2000algorithm,
  author = {Kevin Leyton-Brown and Yoav Shoham and Moshe Tennenholtz},
  title = {{An Algorithm for Multi-Unit Combinatorial Auctions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
  url = {https://openreview.net/forum?id=BkZZy0euWH},
}
Figure