An Algorithm for Optimal Winner Determination in Combinatorial Auctions

TL;DR

This paper introduces a novel search algorithm for finding the optimal allocation of items in combinatorial auctions, a complex problem that is NP-complete. By cleverly exploiting the sparseness of bids in practice, their algorithm significantly scales beyond previous methods, making truly efficient combinatorial auctions more feasible.

What Problem Does This Paper Address?

Traditional auctions often struggle when multiple items are involved. If items are auctioned sequentially, bidders face the difficult task of guessing future bids to value items, leading to inefficient allocations. Parallel auctions mitigate this but don't fully solve the problem. Combinatorial auctions allow bidders to bid on bundles of items, enabling them to express complementarities (e.g., "I want item A and item B together"). This is much more efficient but creates a new challenge: determining the "winner" (i.e., the allocation that maximizes the auctioneer's revenue) becomes computationally intractable, specifically an NP-complete problem. This paper tackles the problem of efficiently finding this optimal allocation in combinatorial auctions.

Methods

The core of the paper is a new search algorithm designed to find the optimal winner determination. Instead of exhaustively enumerating all possible allocations, which is computationally prohibitive, their approach builds a search tree. Key innovations include:

  • Selective Child Generation: The algorithm intelligently prunes the search space by only exploring branches that correspond to actual bids. This is achieved by a rule that dictates children of a node must include the item with the smallest index among those not yet allocated.
  • Bidtree Data Structure: A specialized binary tree (Bidtree) is used to store bids, allowing for efficient searching and pruning.
  • Stopmask: A mechanism within the Bidtree that uses "BLOCKED" and "MUST" states to prune branches based on item allocation rules, preventing redundant exploration.
  • Preprocessing Steps (PRE1-PRE4): Several preprocessing steps are introduced to reduce the complexity of the search:
  • PRE1: Keeps only the highest bid for any given combination.
  • PRE2: Removes "provably noncompetitive" bids (bids that are more expensive than a combination of other disjoint bids).
  • PRE3: Decomposes bids into disjoint sets, allowing independent searches within each set.
  • PRE4: Marks noncompetitive tuples of disjoint bids to avoid considering them together on the same path.
  • Iterative Deepening A (IDA) Search: The main search is implemented using IDA* with custom heuristics that never underestimate revenue, ensuring optimality.

Datasets

Not discussed in the paper. The experiments were conducted using synthetically generated bid distributions (Random, Weighted Random, Uniform, Decay) to evaluate the algorithm's performance under various conditions.

Key Insights and Ideas

  • Exploiting Bid Sparseness: The most crucial insight is that in practice, the space of possible bids is extremely sparse. The algorithm's efficiency hinges on capitalizing on this sparseness, unlike dynamic programming which explores the entire allocation space regardless of bids.
  • Structure of Optimal Allocations: The paper demonstrates that by focusing on the smallest unallocated item, a structured search tree can be built that guarantees each optimal allocation is explored exactly once.
  • Preprocessing for Efficiency: The suite of preprocessing steps (PRE1-PRE4) significantly reduces the search space before the main algorithm even begins, acting as powerful filters.
  • Anytime Algorithm: The depth-first nature of the search allows it to be an "anytime" algorithm, meaning it can be stopped at any point and will return the best feasible solution found so far, with solutions improving monotonically over time.

Key Results

  • The algorithm allows combinatorial auctions to scale to significantly larger numbers of items and bids compared to prior optimal winner determination approaches.
  • Experiments showed that the algorithm could generate 35,000 nodes per second on smaller instances (25 items, short bids).
  • While performance degraded with more items and longer bids, the heuristic and search path length often compensated, making it efficient even for complex scenarios. For instance, with 400 items and 2000 bids, it solved cases easily due to short search paths.
  • The decay distribution was found to be particularly hard, but the algorithm still performed well, especially when bids became longer.
  • The paper also notes that the algorithm can be applied to other problems like weighted set packing, independent set, and maximum clique.

Limitations and Future Work

  • Worst-Case Complexity: The worst-case complexity of the main search is still exponential in the number of bids, though this is mitigated by the sparseness of actual bids.
  • Preprocessing Time: While PRE2 and PRE4 are generally effective, they can be computationally intensive for bids with a large number of items. The paper mentions partial execution of these steps to balance preprocessing time and main search time.
  • Future Work: The authors are developing winner determination algorithms for combinatorial double auctions (involving multiple buyers and sellers) and exploring extensions for XOR-bids (where only one of a set of bids can be accepted) and multi-unit items. They also suggest that PRE2 and PRE4 could be made into anytime or approximate preprocessors.

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{1999algorithm,
  title = {{An Algorithm for Optimal Winner Determination in Combinatorial Auctions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure