On the Complexity of Computing an Equilibrium in Combinatorial Auctions

Shahar Dobzinski, Hu Fu, Robert D. Kleinberg

TL;DR

This paper investigates the computational complexity of finding a "good" equilibrium in combinatorial auctions, specifically focusing on simultaneous second-price auctions. The authors show that for certain types of bidder valuations (submodular), finding an equilibrium with near-optimal social welfare is computationally feasible, often by leveraging existing approximation algorithms. However, for more complex valuations (subadditive and XOS), finding such equilibria can be computationally intractable, requiring exponential communication or queries.

What Problem Does This Paper Address?

Combinatorial auctions are a powerful mechanism for selling multiple items where bidders can express complex preferences over bundles of items. A key question in this field is whether the outcomes of these auctions, particularly when bidders act strategically to reach an equilibrium, are efficient in terms of social welfare (maximizing the total value to all bidders). While much research focuses on designing algorithms to find high-welfare allocations (ignoring strategic behavior) or analyzing the price of anarchy (the ratio of optimal welfare to equilibrium welfare), this paper bridges the gap by asking: can we efficiently compute an equilibrium that achieves good social welfare? They focus on the simultaneous second-price auction setting and explore the computational cost of finding pure Nash equilibria with welfare close to the optimal.

Methods

The paper employs a combination of algorithmic techniques and complexity theory.

  • Reductions: For submodular valuations, they use black-box reductions. This means they show that if an efficient algorithm exists for a related problem (like finding an approximate allocation), they can use it as a subroutine to efficiently find a good equilibrium.
  • Iterative Stealing Procedure: A core algorithmic component is the "iterative stealing procedure." This process starts with an arbitrary allocation and iteratively allows bidders to "steal" items from each other if it improves their utility, mimicking a best-response dynamic. They analyze how this procedure terminates and what properties the resulting equilibrium has.
  • Communication Complexity: For subadditive valuations, they use communication complexity to prove impossibility. This involves constructing scenarios where bidders must exchange a large amount of information to determine if an equilibrium exists, demonstrating that no efficient algorithm can exist.
  • XOS Oracle Analysis: For XOS valuations, they analyze the complexity of algorithms that rely on "XOS oracles" (which provide specific information about a bidder's valuation). They show that even with these oracles, finding traditional equilibria can require an exponential number of queries.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and algorithmic complexity rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Submodularity is Key for Tractability: The paper highlights that the "submodular" property of bidder valuations is crucial for making the problem of finding good equilibria computationally tractable. This property implies a certain "niceness" in how valuations change with added items.
  • Equilibria Can Be "Close" to Optimal Allocations: For submodular bidders, they demonstrate that if you can find an allocation with a certain welfare guarantee (e.g., an α-approximation), you can also find an equilibrium with at least that same guarantee, often with only a modest increase in computational cost.
  • Subadditivity and XOS Lead to Intractability: In contrast, subadditive and XOS valuations, which are more general and less structured than submodular ones, lead to significant computational hurdles. This suggests that the structure of bidder preferences is a critical factor in the complexity of finding efficient equilibria.
  • The Role of XOS Oracles: The paper reveals that even with specialized "XOS oracles" designed to help understand XOS valuations, finding equilibria can still be exponentially hard. This implies that the inherent complexity lies not just in querying valuations but in the combinatorial nature of the problem.
  • Local Maxima vs. Nash Equilibria: For submodular bidders, they show that finding a "local maximum" (an allocation where no single item can be moved to improve welfare) is PLS-complete (a class of computationally hard problems). Interestingly, finding a Nash equilibrium is easier in this context, suggesting that the set of equilibria is strictly larger than the set of local maxima.

Key Results

  • Submodular Bidders: For submodular bidders, they provide algorithms that can find a no-overbidding equilibrium with at least the same approximation guarantee as an existing approximation algorithm for finding allocations. This holds for constant numbers of bidders or budget-additive bidders.
  • Subadditive Bidders: For subadditive bidders, they prove an exponential communication lower bound for finding a pure Nash equilibrium, even if one is guaranteed to exist. This is the first such computational impossibility result for pure equilibria in this setting.
  • XOS Valuations: They show that any deterministic algorithm finding a "traditional" equilibrium for XOS valuations, using only demand, value, and XOS oracle queries, requires an exponential number of queries in the worst case.

Limitations and Future Work

  • XOS Valuations - Open Questions: While they show an impossibility result for finding traditional equilibria in XOS auctions, they acknowledge that they are unable to extend their algorithms for submodular bidders to XOS bidders in general, nor can they prove that finding an equilibrium with XOS bidders always requires exponential communication. This suggests further research into the specific structure of XOS valuations and their implications for equilibrium computation.
  • Exponential Convergence: The paper demonstrates that the natural dynamic for XOS auctions proposed in prior work can take exponentially many steps to converge, even for submodular bidders. This raises questions about whether more efficient dynamics exist or if this exponential convergence is inherent for certain XOS oracle implementations.
  • Generalizing Impossibility Results: The impossibility results for subadditive and XOS valuations are primarily shown for two players. While they mention that these results can be extended to more players by adding dummy bidders, further exploration of the complexity with a larger number of players might be warranted.

Summary updated

Abstract

We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game a pure Nash equilibrium with social welfare close to the optimal one. We show that when the valuations of the bidders are submodular, in many interesting settings (e.g., constant number of bidders, budget additive bidders) computing an equilibrium with good welfare is essentially as easy as computing, completely ignoring incentives issues, an allocation with good welfare. On the other hand, for subadditive valuations, we show that computing an equilibrium requires exponential communication. Finally, for XOS (a.k.a. fractionally subadditive) valuations, we show that if there exists an efficient algorithm that finds an equilibrium, it must use techniques that are very different from our current ones.
BibTeX
@inproceedings{dobzinski2015complexity,
  author = {Shahar Dobzinski and Hu Fu and Robert D. Kleinberg},
  title = {{On the Complexity of Computing an Equilibrium in Combinatorial Auctions}},
  booktitle = {SODA},
  year = {2015},
  doi = {10.1137/1.9781611973730.9},
}
Figure