Mechanism Design via Optimal Transport

Constantinos Daskalakis, Alan Deckelbaum, Christos TzamosEC 2013 · DOI · OpenReview

TL;DR

This paper introduces a novel framework for designing revenue-optimal auctions in complex multi-item settings, particularly when bidder valuations are continuous and implicitly defined. By leveraging optimal transport theory, the authors provide a way to derive closed-form descriptions of these optimal mechanisms, overcoming previous intractability results.

What Problem Does This Paper Address?

Designing revenue-optimal auctions, especially for multiple items, has been a long-standing challenge. While solutions exist for "explicit" settings where all possible bidder valuations and their probabilities are known, these break down when valuations are continuous or have underlying structure (e.g., additive valuations for individual items). In such "implicit" settings, finding optimal mechanisms is computationally intractable, even for a single bidder. This paper tackles this gap by developing a general framework to find optimal mechanisms in these more realistic, yet previously intractable, implicit settings.

Methods

The core of the paper's contribution lies in its novel framework that reformulates the mechanism design problem as an optimal transport problem. Key techniques include:

  • Relaxation of Convexity: The authors relax the convexity constraint on the bidder's utility function, which is crucial for incentive compatibility. This relaxation allows them to formulate a dual problem.
  • Optimal Transport Duality: The dual problem is framed as a continuous analog of minimum-weight bipartite matching, solved using optimal transport theory. The cost function for transport is defined as the sum of positive differences in item valuations.
  • Complementary Slackness: A condition is established to certify optimality for both the primal (mechanism design) and dual (optimal transport) problems.
  • Structural Theorems: The framework leads to two key structural theorems that characterize optimal mechanisms. One theorem identifies conditions under which a simple "take-it-or-leave-it" offer of the grand bundle is optimal. The other provides a general characterization for two-item mechanisms.
  • Stochastic Dominance: Strassen's theorem on stochastic dominance is employed to prove the existence of optimal transport maps, which is crucial for establishing the optimality of the derived mechanisms.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and applies it to specific theoretical distributions (exponential, power-law, beta) rather than empirical datasets.

Key Insights and Ideas

  • Optimal Transport as a Unifying Framework: The paper demonstrates that optimal transport theory provides a powerful and unifying tool to tackle complex revenue-maximization problems in settings previously considered intractable.
  • Bundling is Not Always Sufficient: While bundling the grand bundle is often optimal, the paper shows that for certain distributions (e.g., exponential), a continuum of lotteries might be necessary for revenue maximization, revealing a richer structure than previously assumed.
  • Structural Characterizations: The derived structural theorems offer significant insights into the form of optimal mechanisms, identifying conditions for simple "take-it-or-leave-it" offers and providing a general characterization for two-item settings.
  • Bridging Theory and Practice: The paper provides a recipe for deriving closed-form solutions for optimal mechanisms, making theoretical results more applicable.

Key Results

  • A general optimization framework for designing optimal mechanisms in implicit, multi-item settings with additive bidders.
  • Conditions are identified under which pricing only the grand bundle is optimal.
  • A general characterization of optimal mechanisms for two-item settings is provided.
  • Closed-form descriptions of optimal mechanisms are derived for specific distributions, including:
  • Two items with exponential distributions, revealing a mechanism that can involve lotteries.
  • Two items with power-law distributions, where a grand bundle offer is optimal.
  • Two items with beta distributions, demonstrating a complex mechanism that can involve randomized outcomes.

Limitations and Future Work

  • Computational Complexity: While the framework provides closed-form descriptions, the actual computation of these mechanisms might still be complex, especially for higher dimensions or more intricate distributions.
  • Generalization to Multiple Bidders: The current framework primarily focuses on a single additive bidder. Extending it to multiple bidders, especially with correlated valuations, remains an open challenge.
  • Approximation Schemes: The paper focuses on exact optimal mechanisms. Developing efficient approximation schemes for cases where exact solutions are still too computationally demanding could be a valuable future direction.
  • Verification of Stochastic Dominance: While Theorem 4 provides a sufficient condition for stochastic dominance, its practical application might still require careful verification. The authors suggest that this condition is of independent interest.

Summary updated

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.
BibTeX
@inproceedings{daskalakis2013mechanism,
  author = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title = {{Mechanism Design via Optimal Transport}},
  booktitle = {EC},
  year = {2013},
  doi = {10.1145/2482540.2482593},
}
Figure