Mechanism Design via Optimal Transport

Abstract

Optimal mechanisms have been provided in quite general multi-item settings, as long as each bidder's type distribution is given explicitly by listing every type in the support along with its associated probability. In the implicit setting, e.g. when the bidders have additive valuations with independent and/or continuous values for the items, these results do not apply, and it was recently shown that exact revenue optimization is intractable, even when there is only one bidder. Even for item distributions with special structure, optimal mechanisms have been surprisingly rare and the problem is challenging even in the two-item case. In this paper, we provide a framework for designing optimal mechanisms using optimal transport theory and duality theory. We instantiate our framework to obtain conditions under which only pricing the grand bundle is optimal in multi-item settings (complementing the work of [Manelli and Vincent 2006], as well as to characterize optimal two-item mechanisms. We use our results to derive closed-form descriptions of the optimal mechanism in several two-item settings, exhibiting also a setting where a continuum of lotteries is necessary for revenue optimization but a closed-form representation of the mechanism can still be found efficiently using our framework.

Cited by in corpus (20)

• Approximate Revenue Maximization with Multiple Items
• Selling Multiple Correlated Goods: Revenue Maximization and Menu-Size Complexity (old title: "The Menu-Size Complexity of Auctions")
• The Menu-Size Complexity of Revenue Approximation
• Bounding the Optimal Revenue of Selling Multiple Goods
• Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
• PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning
• Strong Duality for a Multiple-Good Monopolist
• Simple Mechanisms for Subadditive Buyers via Duality
• Simple Mechanisms for Profit Maximization in Multi-item Auctions
• Multi-dimensional Virtual Values and Second-degree Price Discrimination
• Adversarial learning for revenue-maximizing auctions
• A Note on Selling Optimally Two Uniformly Distributed Goods
• On the Competition Complexity of Dynamic Mechanism Design
• Optimal Mechanism Design with Risk-loving Agents
• A Duality-Based Unified Approach to Bayesian Mechanism Design
• Variational interacting particle systems and Vlasov equations
• Optimal Auctions with Restricted Allocations
• A Simple Mechanism for a Budget-Constrained Buyer
• Duality and Optimality of Auctions for Uniform Distributions
• The Sample Complexity of Up-to-$\epsilon$ Multi-Dimensional Revenue Maximization