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.
Recommendations
Cited in
(60)- Foundations of mechanism design: a tutorial. II. Advanced concepts and results
- On the difficulty of approximately maximizing agreements.
- Solomon's dilemma: An experimental study on dynamic implementation
- The complexity of optimal multidimensional pricing for a unit-demand buyer
- Approximate revenue maximization with multiple items
- Third-degree price discrimination versus uniform pricing
- Optimizing affine maximizer auctions via linear programming: an application to revenue maximizing mechanism design for zero-day exploits markets
- Robust multidimensional pricing: separation without regret
- On symmetries in multi-dimensional mechanism design
- A simple mechanism for a budget-constrained buyer
- Optimal mechanism design with risk-loving agents
- Prior independent mechanisms via prophet inequalities with limited information
- Selling multiple correlated goods: revenue maximization and menu-size complexity
- Bounding the optimal revenue of selling multiple goods
- The power of randomness in Bayesian optimal mechanism design
- Optimal combinatorial mechanism design
- Extreme value theorems for optimal multidimensional pricing
- On the computational complexity of optimal simple mechanisms
- Revenue maximization for market intermediation with correlated priors
- Multidimensional mechanism design: finite-dimensional approximations and efficient computation
- Duality and optimality of auctions for uniform distributions
- Efficiency-revenue trade-offs in auctions
- Robust auctions for revenue via enhanced competition
- Auction design with a revenue target
- Algorithmic signaling of features in auction design
- scientific article; zbMATH DE number 5343724 (Why is no real title available?)
- scientific article; zbMATH DE number 3961285 (Why is no real title available?)
- The menu complexity of ``one-and-a-half-dimensional mechanism design
- On the complexity of simple and optimal deterministic mechanisms for an additive buyer
- A simple and approximately optimal mechanism for a buyer with complements
- A Duality-Based Unified Approach to Bayesian Mechanism Design
- Large-scale bundle-size pricing: a theoretical analysis
- On the Futility of Dynamics in Robust Mechanism Design
- Bernoulli Factories and Black-box Reductions in Mechanism Design
- On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
- Efficient computation of optimal auctions via reduced forms
- Optimal mechanisms with simple menus
- Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
- An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications
- The complexity of optimal multidimensional pricing
- An algorithmic characterization of multi-dimensional mechanisms
- Pricing randomized allocations
- On optimal single-item auctions
- Optimal auctions with correlated bidders are easy
- Simple and nearly optimal multi-item auctions
- scientific article; zbMATH DE number 7053323 (Why is no real title available?)
- Multi-Item Nontruthful Auctions Achieve Good Revenue
- Generalized Permutahedra and Optimal Auctions
- On the hardness of dominant strategy mechanism design
- Mechanism design with general ex-ante investments
- Mechanism Design Under Approximate Incentive Compatibility
- Optimal mechanism design when both allocative inefficiency and expenditure inefficiency matter
- Separation in distributionally robust monopolist problem
- Near-optimal auctions on independence systems
- Towards data auctions with externalities
- Variational interacting particle systems and Vlasov equations
- Multidimensional screening with precise seller information
- An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design
- Nonbossy mechanisms: mechanism design robust to secondary goals
- Coase theorem, complexity and transaction costs
This page was built for publication: The complexity of optimal mechanism design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384058)
