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.
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.
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