Strong Duality for a Multiple-Good Monopolist

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

TL;DR

This paper solves a long-standing challenge in economics and algorithmic game theory: how to prove a mechanism is truly revenue-optimal when a monopolist sells multiple goods. By establishing a "strong duality" framework, the authors show that maximizing revenue is mathematically equivalent to a specific "optimal transport" problem, providing a definitive toolkit for identifying and certifying optimal multi-item auctions.

What Problem Does This Paper Address?

Imagine you are a seller with two different items (say, an iPhone and an Android tablet). You have one buyer, but you don't know exactly how much they value each item—only the probability distribution of their preferences. Your goal is to design a "mechanism" (a set of prices and bundles) to extract the maximum possible expected revenue.

In the single-item case, this was solved by Roger Myerson in 1981: you just set a single "reserve price." However, for multiple items, the problem becomes incredibly messy. The optimal strategy might involve "grand bundling" (selling everything as one package), selling items separately, or even offering "lotteries" (e.g., "pay $10 for a 50% chance at the iPhone").

Before this paper, there was no general framework to prove that a specific multi-item mechanism was the best possible one. Researchers often relied on "sufficient conditions"—rules that said, "if these conditions are met, the mechanism is good"—but they couldn't guarantee they had found the absolute best.

Methods

The authors bridge the gap between Mechanism Design and Optimal Transport Theory. Their approach follows these steps:

  1. Transformation to Utility: They rephrase the revenue maximization problem as an optimization over the buyer's utility function $u$.
  2. The Transformed Measure ($\mu$): They derive a "signed measure" $\mu$ from the buyer's type distribution. This measure represents how the seller's revenue changes when the "rent" (utility) paid to certain buyer types changes.
  3. Strong Duality Theorem: This is the core contribution. They prove that the maximum revenue (the "primal" problem) is exactly equal to the minimum cost of a dual problem. This dual problem involves:
  4. Convex Shuffling: Moving mass around such that the new distribution "convexly dominates" the old one (related to mean-preserving spreads).
  5. Transportation: Moving mass from the positive parts of the measure to the negative parts at a cost equal to the distance moved.
  6. Complementary Slackness: They provide "certificates of optimality." If you have a candidate mechanism and can find a matching solution to the transport problem, you have mathematically proven your mechanism is optimal.

Datasets

As a theoretical paper in mathematical economics and computer science, this work does not use empirical datasets. Instead, it evaluates its framework using standard mathematical probability distributions, including:

  • Uniform distributions (e.g., values for items are independent and uniform on $[c, c+1]$).
  • Beta distributions.
  • Exponential and Power-law distributions.

Key Insights and Ideas

  • The Duality Gap is Zero: Previous researchers found "weak" duals where the dual value was an upper bound on revenue. This paper proves "strong" duality, meaning the bound is tight. This turns a guessing game into a precise calculation.
  • The "Curse" of High Dimensions: One of the most surprising findings (Theorem 6) concerns selling $n$ items where values are uniform on $[c, c+1]$. They show that while "grand bundling" is optimal if the base value $c$ is very high, it is never optimal if you keep $c$ fixed and increase the number of items $n$ sufficiently. This suggests that as the variety of goods grows, simple bundling fails.
  • Infinite Menus: They show that for certain distributions (like Beta distributions), the optimal mechanism requires an "uncountably infinite" menu of lotteries. This proves that simple, finite pricing schemes are sometimes fundamentally incapable of reaching maximum revenue.

Key Results

  • Theorem 3 (Optimal Menu Theorem): Provides the first necessary and sufficient conditions to characterize the optimality of any mechanism with a finite menu.
  • Grand Bundling Characterization: They provide a sharp mathematical test to determine exactly when a seller should just bundle everything together versus offering separate options.
  • Generalization of Pavlov’s Result: They extend 2-item results to $n$-item settings, providing a roadmap for solving complex multi-dimensional screening problems that were previously considered "dauntingly difficult."

Limitations and Future Work

  • Computational Complexity: While the framework is mathematically "strong," verifying the stochastic dominance conditions in high dimensions ($n > 2$) remains computationally hard. Developing efficient algorithms to check these conditions is a major next step.
  • Unbounded Distributions: The proof for strong duality relies on compact (bounded) type spaces. While the authors discuss how to extend this to unbounded spaces (like Exponential distributions), they note that technical issues prevent a full "strong duality" proof in those cases.
  • Multiple Bidders: The paper focuses on a monopolist with a single buyer. Extending these results to auctions with multiple competing bidders is described as the "major open problem" in the field.

Summary updated

Abstract

We provide a duality-based framework for revenue maximization in a multiple-good monopoly. Our framework shows that every optimal mechanism has a certificate of optimality, taking the form of an optimal transportation map between measures. Using our framework, we prove that grand-bundling mechanisms are optimal if and only if two stochastic dominance conditions hold between specific measures induced by the buyer's type distribution. This result strengthens several results in the literature, where only sufficient conditions for grand-bundling optimality have been provided. As a corollary of our tight characterization of grand-bundling optimality, we show that the optimal mechanism for n independent uniform items each supported on [c; c + 1] is a grand-bundling mechanism, as long as c is sufficiently large, extending Pavlov's result for 2 items [Pavlov 2011]. Surprisingly, our characterization also implies that, for all c and for all sufficiently large n, the optimal mechanism for n independent uniform items supported on [c; c + 1] is not a grand bundling mechanism. The necessary and sufficient condition for grand bundling optimality is a special case of our more general characterization result that provides necessary and sufficient conditions for the optimality of an arbitrary mechanism for an arbitrary type distribution.
BibTeX
@inproceedings{daskalakis2015strong,
  author = {Constantinos Daskalakis and Alan Deckelbaum and Christos Tzamos},
  title = {{Strong Duality for a Multiple-Good Monopolist}},
  booktitle = {EC},
  year = {2015},
  url = {https://openreview.net/forum?id=cc2Kw0tfZC},
}

Loading related content...

Figure