An Algorithm for Optimal Winner Determination in Combinatorial Auctions

Tuomas Sandholm

Abstract

Combinatorial auctions, i.e. auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auctions in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP complete. We present a search algorithm for optimal winner determination. Experiments are shown on several bid distributions. The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is necessarily sparsely populated in practice. We do this via provably sufficient selective generation of children in the search and by using a method for fast child generation, heuristics that are accurate and optimized for speed, and four methods for preprocessing the search space.

Introduction

In traditional sequential auctions, bidding on complementary items—such as a left and right shoe or adjacent radio spectrum bands—presents a significant risk. Bidders must estimate the value of current items based on uncertain future wins. Combinatorial auctions mitigate this by allowing agents to bid directly on bundles of items.

However, this flexibility introduces a major computational challenge for the auctioneer. Finding the revenue-maximizing combination of bids is equivalent to the "weighted set packing" problem, which is NP-complete. While dynamic programming approaches explore the entire theoretical space of $2^m - 1$ item combinations, they typically fail beyond 25 items. This paper introduces a highly optimized search algorithm that scales by focusing exclusively on the space of actually submitted bids, leveraging the inherent sparsity of real-world auction data.

Methodology: Optimized Search and the Bidtree

The winner determination problem is framed as a tree search where each path represents a sequence of disjoint bids. To navigate this space efficiently, the authors introduce several novel mechanisms.

The Bidtree and Stopmask

A central innovation is the Bidtree data structure, which facilitates rapid identification of valid child nodes. This is paired with a Stopmask that allows the algorithm to prune branches in-place. By using the Stopmask, the algorithm can instantly skip bids containing items that have already been allocated in the current path, maintaining linear space complexity.

The Bidtree and Stopmask mechanism for efficient child generation and pruning.

Search Strategy and Preprocessing

The algorithm employs Iterative Deepening A (IDA) search with an admissible heuristic based on the maximum bid price per item. This ensures aggressive pruning of suboptimal paths. To further reduce the search space, four preprocessing steps (PRE1-PRE4) are applied:

  1. Retaining only the highest bid for identical bundles.
  2. Pruning "noncompetitive" bids that are dominated by combinations of smaller bids.
  3. Decomposing the auction into independent sub-graphs if bid sets do not overlap.
  4. Pre-calculating mutually exclusive bid pairs to streamline conflict checks.

Experimental Evaluation

Due to the lack of real-world combinatorial auction data, the algorithm was tested on four synthetic distributions: Random, Weighted Random, Uniform (fixed number of items per bid), and Decay (probabilistic item addition).

Key Results

The IDA* strategy demonstrated performance two orders of magnitude faster than standard Depth-First Search. On "Random" distributions, the algorithm successfully scaled to 400 items and 2,000 bids. While the heuristic calculations are computationally intensive, the resulting search tree is so well-pruned that overall solving time remains low.

Search time for the uniform distribution showing scaling with items per bid.

A notable finding is that the algorithm performs better as the number of items per bid increases. In the "Uniform" distribution, auctions with longer bids are solved faster because they consume items more quickly, leading to a shallower search tree.

Conclusion and Future Directions

The proposed algorithm demonstrates that sparsity in the bid space is the key to scaling optimal winner determination. By constructively building allocations from submitted bids rather than exploring the entire power set of items, the algorithm moves beyond the limitations of previous dynamic programming methods.

Future work includes extending the protocol to handle XOR-bids, allowing bidders to express subadditivity (e.g., "I want A or B, but not both"). The authors also suggest adaptations for multi-unit auctions and combinatorial double auctions, where multiple buyers and sellers participate simultaneously.

Summary updated

Abstract

Combinatorial auctions, i.e. auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auctions in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP complete. We present a search algorithm for optimal winner determination. Experiments are shown on several bid distributions. The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is necessarily sparsely populated in practice. We do this via provably sufficient selective generation of children in the search and by using a method for fast child generation, heuristics that are accurate and optimized for speed, and four methods for preprocessing the search space.
BibTeX
@inproceedings{sandholm1999algorithm,
  author = {Tuomas Sandholm},
  title = {{An Algorithm for Optimal Winner Determination in Combinatorial Auctions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure