The Complexity of Optimal Mechanism Design

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

TL;DR

This paper proves that finding the optimal auction for selling multiple items is computationally intractable, even in the simplest scenarios. This is a significant result because it demonstrates that approximation algorithms are likely necessary for practical revenue maximization in these settings, and it introduces a novel technique for proving hardness in mechanism design.

What Problem Does This Paper Address?

The field of mechanism design, particularly in economics and computer science, seeks to design optimal "rules of the game" (like auctions) to achieve certain goals, such as maximizing revenue for a seller. While the problem of designing an optimal auction for a single item is well-understood and computationally tractable (thanks to Myerson's seminal work), the problem of selling multiple items has remained a major open challenge. Existing solutions for multi-item auctions often fall short of characterizing the computational complexity, leaving it unclear whether these problems can be solved efficiently. This paper tackles this gap by proving that, contrary to what might be hoped, finding an optimal multi-item auction is fundamentally hard, even under very simple assumptions about bidders' preferences and the items themselves.

Methods

The authors employ a sophisticated approach that involves constructing a family of carefully designed mechanism design instances. They start with a known, but exponentially large, linear program (LP) for revenue maximization. They then create a relaxed version of this LP and show that for their specific instances, optimal solutions to the relaxed LP correspond to optimal solutions of the original LP. This allows them to analyze the structure of these optimal solutions. The core of their hardness proof comes from reducing a known #P-hard problem (the lexicographic rank problem) to the problem of computing the optimal mechanism for these specific instances. This reduction leverages the structure of the LP solutions and a clever construction of item values and probabilities.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and constructs specific problem instances for its proofs, rather than using empirical datasets.

Key Insights and Ideas

  • Fundamental Hardness: The paper establishes that optimal revenue maximization in multi-item auctions is not just difficult to implement efficiently, but is computationally hard to even compute the optimal mechanism, unless P = P#P. This means we likely can't do better than approximation algorithms in many cases.
  • No Structure to Exploit (Initially): A key challenge was that optimal mechanisms for simple multi-item settings don't exhibit obvious structural properties that could be exploited for efficient computation. The authors' approach creates this structure through LP relaxations.
  • LP Relaxation as a Tool for Hardness: The paper demonstrates a powerful technique: using LP relaxations to transform a problem with seemingly no exploitable structure into one where the structure of the relaxed solution can be used to embed a #P-hard problem.
  • General Applicability: The hardness result applies to a very broad class of mechanisms, not just direct or deterministic ones, and holds even for simple additive bidders with independent values.

Key Results

The paper proves that computing an optimal mechanism for selling multiple items to a single additive bidder with independent values is #P-hard, unless ZPP = P#P. This means that finding such an auction is computationally intractable. This result holds even for very simple settings where bidders' values for items are independently distributed on two rational numbers with rational probabilities.

Limitations and Future Work

The authors acknowledge that their results do not preclude the existence of a fully polynomial-time approximation scheme (FPTAS) for the mechanism design problem, and this remains an open question. They also discuss how computational power of bidders can shift the complexity burden, suggesting further avenues of research in understanding the interplay between seller and bidder computational capabilities. The paper's focus is on theoretical hardness, and practical implications for algorithm design would involve exploring approximation algorithms.

Summary updated

Abstract

Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless ZPP contains P^#P. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated. We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint.
BibTeX
@inproceedings{daskalakis2014complexity,
  author = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title = {{The Complexity of Optimal Mechanism Design}},
  booktitle = {SODA},
  year = {2014},
  url = {https://openreview.net/forum?id=uT4fTFXxxs},
}
Figure