On the Complexity of Computing an Equilibrium in Combinatorial Auctions

Shahar Dobzinski, Hu Fu, Robert Kleinberg

Abstract

In the study of algorithmic game theory, combinatorial auctions represent a critical challenge for mechanism design. While simultaneous second-price auctions are known to achieve high social welfare at equilibrium—demonstrated by a low Price of Anarchy—the computational feasibility of reaching such an equilibrium remains a significant hurdle. This paper investigates the complexity of finding pure Nash equilibria across various bidder valuation classes. We demonstrate that while equilibria can be computed efficiently for submodular valuations, the problem becomes exponentially difficult for more complex classes, such as XOS and subadditive valuations, requiring either exponential communication or an exponential number of oracle queries.

Introduction

Combinatorial auctions, where multiple items are sold to bidders with diverse preferences over sets of items, are a cornerstone of modern market design. A central question in this field is whether simple, non-centralized auction formats can achieve efficient outcomes. Simultaneous second-price auctions (SISPAs) are particularly attractive due to their simplicity: every item is sold separately but concurrently.

Previous research has established that the Price of Anarchy in these games is often small (e.g., a factor of 2), suggesting that if players reach a Nash equilibrium, the resulting social welfare is near-optimal. However, this theoretical guarantee is only meaningful if the equilibrium is computationally reachable. This research bridges the gap between the existence of good equilibria and the practical ability of agents to find them, mapping the computational boundaries of equilibrium computation.

The Computational Landscape of Valuations

The difficulty of finding an equilibrium is intrinsically tied to the complexity of the bidders' valuation functions. The paper focuses on three primary classes:

  1. Submodular Valuations: Characterized by "diminishing returns," where the marginal value of an item decreases as the bidder acquires more items.
  2. XOS (Fractionally Subadditive) Valuations: A broader class where valuations are represented as the maximum of several linear functions.
  3. Subadditive Valuations: The most general class considered, where the value of a union of sets is no greater than the sum of the values of the individual sets.

Methodology

The authors utilize a multi-faceted approach combining algorithmic design with complexity theory:

1. Iterative Stealing Procedure

For submodular bidders, the authors introduce an "Iterative Stealing" algorithm. In this process, bidders are allowed to "steal" items from one another if their marginal value for an item exceeds the current bid placed by another player. The research proves that for specific subclasses, such as budget-additive bidders or a constant number of players, this local improvement process converges to a pure Nash equilibrium in polynomial time.

2. Welfare-Preserving Reductions

The authors develop black-box reductions that take standard approximation algorithms (which typically ignore incentives) and transform their outputs into valid Nash equilibria. This ensures that the equilibrium found maintains the same welfare guarantees as the original approximation.

3. Communication and Query Complexity

To establish lower bounds, the researchers employ communication complexity—measuring the minimum information exchange required between players—and query complexity, which counts the number of calls to a valuation "oracle." They construct specific, "pathological" valuation instances to prove that certain equilibria cannot be found efficiently.

Key Results and Findings

Efficiency in Submodular Settings

The research finds that the greedy nature of submodular valuations facilitates equilibrium discovery. For a constant number of bidders, a pure Nash equilibrium can be found in polynomial time. For the general submodular case, the authors provide a pseudo-polynomial time algorithm, where the runtime depends on the magnitude of the item values.

The Hardness of Subadditivity

A primary contribution of the paper is proving the "Subadditive Impossibility." Even with only two players, finding a pure Nash equilibrium with subadditive valuations requires exponential communication. This suggests that for these bidders, the "simple" auction format is not actually simple to navigate.

The Oracle Trap for XOS

For XOS valuations, the authors demonstrate a gap in traditional algorithmic approaches. They prove that any deterministic algorithm relying on standard demand and XOS oracles requires an exponential number of queries to find a "traditional" equilibrium (one where bids are tied to specific oracle prices), even if such an equilibrium is known to exist.

Discussion and Future Work

This work clarifies the boundary between tractable and intractable equilibrium computation. It shows that while submodularity allows for efficient market clearing, even slight increases in valuation complexity (to XOS or subadditive) lead to exponential computational barriers.

One remaining open question is the existence of "non-traditional" algorithms for XOS valuations that might bypass the oracle query limits established here. Furthermore, while the submodular results are promising, the transition from pseudo-polynomial to strictly polynomial-time algorithms for an arbitrary number of bidders remains a significant challenge for future research in combinatorial auction theory.

Summary updated

BibTeX
@inproceedings{dobzinski2015complexity,
  author = {Shahar Dobzinski and Hu Fu and Robert Kleinberg},
  title = {{On the Complexity of Computing an Equilibrium in Combinatorial Auctions}},
  booktitle = {SODA},
  year = {2015},
  doi = {10.1137/1.9781611973730.9},
}
Figure