Source-linked AI summary
The Complexity of Optimal Mechanism Design
Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos
TL;DR
The complexity of revenue-optimal multi-item auctions has remained poorly understood. Using linear-programming duality and flows, the paper proves that optimal auctions cannot be found and implemented in expected polynomial time under a standard complexity assumption, even in a simple additive-bidder setting.
Problem
The computational complexity of optimal mechanism design remained poorly understood, including for simple settings with additive valuations.
Source: §1.2 · p. 5, §7 · p. 22Method
The proof relaxes an exponentially large revenue-maximization linear program, interprets dual solutions as flows, and identifies structured instances whose optimal solutions encode a #P-hard problem.
Source: §1.2 · p. 6Results
Unless ZPP ⊇ P#P, no expected-polynomial-time solution exists, even for one additive bidder with independent values on two rational numbers with rational probabilities.
Source: §1 · p. 2, §7 · p. 22Takeaways & Limitations
The result provides a complexity-based justification for approximation beyond Myerson’s single-item setting.
Source: §1 · p. 3The results do not rule out an FPTAS, whose existence remains open even for a single additive bidder.
Source: §7 · p. 22
Abstract
from arXiv · showhide
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.
1 Introduction
The paper proves that exact revenue-optimal mechanism design is computationally hard even in a simple multi-item setting. It broadens the hardness model to arbitrary auction formats and develops a linear-programming and flow-based proof.
1 Introduction
- Unless ZPP ⊇ P#P, optimal auctions lack expected-polynomial-time solutions even for one additive bidder with independent two-point rational values, justifying approximation beyond Myerson’s setting.The item values and their probabilities are rational.Source: §1 · pp. 2–3
- It is #P-hard to determine whether every optimal mechanism assigns a specified item to a specified bidder type with probability zero or one.The result assumes one of those outcomes holds simultaneously across all optimal mechanisms.Source: §1 · p. 2
1.1 The Optimal Mechanism Design Problem
- The hardness covers any auction format or encoding, while requiring efficient computation of the auction and efficient simulation of its equilibrium allocations and prices.The model counts computation by both bidders and the auctioneer.Source: §1.1 · pp. 4–5
1.2 Techniques
- The proof relaxes an exponentially large revenue-maximization LP, interprets its dual solutions as lattice flows, and embeds a #P-hard problem in structured optimal solutions.The construction uses subset-sum ordering to characterize a subclass of dual solutions.Source: §1.2 · p. 6
1.3 Related Work
- Earlier hardness results used combinatorial valuations, correlated values, deterministic auctions, or irrational inputs, whereas this result treats independent additive values with rational supports and probabilities.Prior lower bounds did not establish intractability for this simple randomized-auction setting.Source: §1.3 · pp. 6–7
1.4 Further Results and Discussion
- In a separate result, intractability also arises for one budget-additive quasi-linear bidder with known item values and an uncertain budget.This extends the paper’s results beyond additive valuations to a simple submodular setting.Source: §1.4 · p. 7
- The hard instances for the budget-additive result have trivial indirect mechanism descriptions but require NP power for the bidder to decide what to buy.This illustrates why the paper’s efficiency framework includes bidder computation.Source: §1.4 · p. 7
2 Preliminaries
The paper studies a single additive, quasi-linear bidder with independent two-value item distributions, then uses a hard instance family to establish computational barriers for optimal mechanisms. The proof plan first targets a unique optimal direct mechanism and then extends the hardness argument to general mechanisms.
2 Preliminaries
- The instances have one additive, quasi-linear bidder whose item values are independently drawn from two values with rational parameters.For item i, the values are a_i and a_i + d_i, with probability p_i of the higher value.Source: §2 · p. 7
- A mechanism specifies bidder actions and maps each action to an allocation and price, which may be randomized and correlated.For each realized valuation, the bidder chooses a utility-maximizing action, with the paper specifying how ties are broken.Source: §2 · p. 8
- An efficient solution must encode the mechanism so its allocation and price can be sampled efficiently for a given type.The paper rules out treating the instance itself as an implicit description that cannot be efficiently evaluated.Source: §2 · pp. 8–9
- Computing circuits for the optimal BIC allocation and price rules is #P-hard, and the result also rules out expected polynomial-time solutions unless ZPP ⊇ P#P.The computationally meaningful description is an implicit, efficiently evaluable encoding rather than a list of rules for all 2^n types.Source: §2 · p. 9
2.1 Our Proof Plan
- The proof isolates instances with a unique optimal direct mechanism where deciding one binary allocation probability is #P-hard, then transfers hardness to general mechanisms.For these single-bidder instances, BIC and incentive compatibility coincide; the Revelation Principle connects arbitrary mechanisms to the unique optimal direct mechanism.Source: §2.1 · pp. 9–10, §2 · p. 9
3 A Linear Programming Approach
The paper formulates revenue optimization as an exponential-size linear program, relaxes it for analysis, and studies the relaxation through its dual flow interpretation. The construction identifies conditions under which relaxed-program solutions connect back to the original mechanism-design problem.
3.1 Mechanism Design as a Linear Program
- LP1 expresses the optimal BIC, individually rational mechanism as a linear program with exponentially many variables and constraints.Its objective uses the expected price paid by each type.Source: §3.1 · p. 10
3.2 A Relaxed Linear Program
- LP2 relaxes LP1 by retaining only neighboring-type incentive constraints and dropping non-negativity constraints on allocation probabilities.The paper identifies a subclass of instances where an optimal relaxed solution also solves the original program.Source: §3.2 · p. 10
- When B exceeds the probability-weighted sum of x_i, efficiently computable a_i and κ realize the specified LP2 parameters.The resulting parameters are rational when B, x, p, and d are rational.Source: §3.2 · p. 12
3.3 The Dual of the Relaxed Program, and its Min-Cost Flow Interpretation
- LP3, the dual of LP2, is interpreted as minimum-cost flow on a lattice whose nodes are item sets and whose downward edges cost d_i per unit.Positive nodes receive external supply, while negative nodes can send flow to an external sink.Source: §3.3 · p. 12
4 Characterizing the Linear Programming Solutions
A canonical minimum-cost flow solution to LP3 yields optimal solutions to LP2 and, under stated conditions, LP1. A partially saturated node determines a unique utility function and therefore a unique mechanism-design solution.
4.1 The Canonical Solution to LP3
- The canonical LP3 solution sends flow to negative nodes in nondecreasing cost order until they absorb the positive node’s net flow.It is unique up to division of flow among nodes with equal cost.Source: §4.1 · p. 13
4.2 From LP3 to LP2 Solutions
- When the highest-cost node receiving flow is not fully saturated, LP2 has the unique optimum u(S) = max{cost(S*) − cost(S), 0}.If that node is fully saturated, the same utility remains optimal, but the optimum may not be unique.Source: §4.2 · pp. 13–14
4.3 From LP2 to LP1 Solutions
- A monotone, supermodular optimal utility for LP2 can be extended to an optimal LP1 solution, and uniqueness carries over when the LP2 optimum is unique.The construction chooses allocation probabilities from utility increments and verifies LP1’s constraints.Source: §4.3 · pp. 14–15
4.4 Putting it All Together
- A partially saturated canonical-flow node yields a unique optimal mechanism, with the utility of type N equal to that node’s cost.The corresponding LP2 utility is monotone and supermodular, so it also uniquely solves LP1.Source: §4.4 · p. 15
5 Proof of Theorem 1: Hardness Of Mechanism Design
The proof reduces optimal mechanism design to LexRank, first establishing LexRank’s #P-hardness and then encoding its answer in an optimal auction’s allocation.
5.1 Hardness of LexRank
- LexRank is #P-hard by reduction from #-SubsetSum, whose subset counts can be recovered through rank-oracle queries.The proof computes counts of subsets summing to at most the target from the counts for each largest included index.Source: §5.1 · p. 16
5.2 Hardness of Mechanism Design: Reduction from LexRank
- The mechanism-design reduction starts from a LexRank instance and constructs an LP3 instance whose canonical flow places a chosen node at the target rank.A polynomial-time search finds the parameter with O(n log n) bits of precision.Source: §5.2 · pp. 17–19
- One allocation sample reveals the LexRank answer because the constructed auction allocates item n + 1 to the selected type with probability exactly 1 or 0.The reduction chooses its parameter in polynomial time so a partially filled canonical-flow node encodes the target rank.Source: §5.2 · pp. 17–19
6 Beyond Additive or Computationally Bounded Bidders
The section extends hardness to budget-additive bidders and discusses how computationally unbounded bidders can change implementation. It highlights a trade-off: indirect mechanisms can shift computational work from seller to bidder.
6.1 Budget-Additive Bidders
- Subset-sum reduces in polynomial time to optimal mechanism design for one budget-additive quasi-linear bidder with known rational item values and a probabilistic rational budget.The budgeted bidder’s optimal direct mechanism allocates a maximum-value subset not exceeding the budget and charges that value.Source: §6.1 · p. 20
6.2.1 NP Power
- An indirect mechanism can shift subset-sum computation from the seller to the bidder, whose optimal strategy may be intractable to determine.The seller’s mechanism is easy to construct and implement, but the bidder must compute her strategy.Source: §6.2.1 · p. 21
6.2.2 PSPACE and Beyond
- Interactive-proof mechanisms are described for computationally unbounded bidders, but the authors omit formal proofs and do not present these mechanisms as practical.The constructions rely on PSPACE power for one bidder or, with two or more bidders, NEXP computation.Source: §6.2.2 · pp. 21–22
7 Conclusion
The paper establishes strong lower bounds for revenue-optimal mechanism design in a simple single-bidder setting, while leaving open whether an FPTAS exists.
7 Conclusion
- The lower bound applies to a single additive bidder with independent item values and any efficiently samplable mechanism, regardless of its type or encoding.The instances are rich enough to encode #P-hard problems while remaining amenable to analysis.Source: §7 · p. 22
- The proof develops relaxations of a folklore revenue-optimization LP to construct instances that encode #P-hard problems.Source: §7 · p. 22
- The results do not rule out an FPTAS, whose existence remains open even for a single additive bidder.Source: §7 · p. 22