The Complexity of Optimal Mechanism Design

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

TL;DR

This paper proves that finding a revenue-optimal auction for multiple items is computationally intractable (#P-hard), even in the simplest possible setting: a single bidder with independent values for each item. This result provides a definitive theoretical justification for why researchers have shifted toward approximation algorithms, as finding the "perfect" mechanism is likely impossible for any modern computer.

What Problem Does This Paper Address?

In 1981, Roger Myerson (who later won a Nobel Prize) solved the problem of how to design an auction that maximizes revenue for a single item. His solution was elegant, efficient, and changed the face of economics. However, for over 30 years, the "multi-item" version of this problem remained the "Holy Grail" of mechanism design.

The challenge is that when a bidder wants multiple items, their values for different combinations can interact in complex ways. While researchers found ways to solve this if the number of possible "types" of bidders was small, they struggled with the "succinct" case—where a bidder’s preferences are described by independent distributions for each item. If you have $n$ items and each has two possible values, there are $2^n$ possible bidder types. Can we find the optimal auction in time polynomial to $n$, rather than $2^n$? This paper finally answers with a resounding "No."

Methods

The authors employ a sophisticated blend of linear programming (LP) and complexity theory. Their approach follows these steps:

  1. LP Relaxation: They start with a "folklore" linear program for revenue optimization (LP1) which is exponentially large. They then create a relaxed version (LP2) that is easier to analyze.
  2. Dual Flow Interpretation: They take the dual of this relaxed program (LP3) and interpret its solutions as a minimum-cost flow problem on a lattice. This allows them to use geometric and combinatorial tools to characterize what an optimal solution looks like.
  3. The Reduction: To prove hardness, they reduce a known #P-hard problem—#SubsetSum—to a new problem they define called LexRank (Lexicographic Rank). They then show that an algorithm capable of finding an optimal auction could be used to solve LexRank.
  4. Characterizing Uniqueness: By carefully choosing the parameters of the bidder's distribution, they ensure that the optimal auction is unique and has a structure that directly encodes the solution to the hard counting problem.

Datasets

As a theoretical paper in algorithmic game theory, no empirical datasets were used. The "data" consists of mathematical instances of auction problems defined by rational numbers representing values and probabilities.

Key Insights and Ideas

  • Complexity is Inherent: The most striking insight is that complexity doesn't arise from "messy" features like correlated item values or complex combinatorial preferences. Hardness exists even when item values are independent and the bidder is additive (the value of a bundle is just the sum of the values of the items).
  • Randomization Doesn't Help: The hardness result applies even to randomized mechanisms. Often, allowing randomization makes optimization easier; here, it remains intractable.
  • The Flow Paradigm: Mapping the dual of the revenue-maximization LP to a flow problem on a lattice is a novel technique. It reveals a hidden combinatorial structure in optimal auctions that can be exploited for reductions.
  • Approximation is Mandatory: This paper provides the "stop sign" for researchers. It proves that the community's focus on finding Constant-Factor Approximations or FPTAS (Fully Polynomial-Time Approximation Schemes) is the only mathematically sound path forward for multi-item auctions.

Key Results

  • Theorem 1: There is no expected polynomial-time solution to the optimal mechanism design problem unless $ZPP \supseteq P^{\#P}$ (a highly unlikely collapse in complexity classes).
  • Hardness of Specifics: It is #P-hard to determine if an optimal mechanism assigns a specific item to a specific bidder type with probability 0 or 1, even under a promise that one of those two cases is true.
  • Minimal Settings: These results hold even for a single bidder whose values for items are independently distributed on just two rational numbers.
  • Budget Constraints: The authors also show (Theorem 2) that the problem is NP-hard for "budget-additive" bidders, where the bidder has a hard cap on what they can spend, even if their values for items are known with certainty.

Limitations and Future Work

  • The Approximation Gap: While the paper proves that exact optimization is hard, it does not rule out the existence of a Fully Polynomial-Time Approximation Scheme (FPTAS) for the single additive bidder case. Determining the exact boundary where approximation becomes hard is a remaining open question.
  • Beyond Single Bidders: While the paper focuses on the single-bidder case to show how "easy" the problem can be while remaining hard, extending these specific flow-based techniques to multi-bidder settings with more complex constraints remains a fertile ground for future research.
  • Practicality of Indirect Mechanisms: The authors note that while some "indirect" mechanisms might be easy for a seller to describe, they might be NP-hard for a bidder to actually play optimally. This highlights the need for "computationally efficient" definitions that consider both the seller and the buyer.

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