Strong Duality for a Multiple-Good Monopolist

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

Abstract

We characterize optimal mechanisms for the multiple-good monopoly problem and provide a framework to find them. We show that a mechanism is optimal if and only if a measure $\mu$ derived from the buyer's type distribution satisfies certain stochastic dominance conditions. This measure expresses the marginal change in the seller's revenue under marginal changes in the rent paid to subsets of buyer types. As a corollary, we characterize the optimality of grand-bundling mechanisms, strengthening several results in the literature where only sufficient optimality conditions have been derived. As an application, 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. At the same time, our characterization also implies that, for all $c$ and for all sufficiently large $n$, the optimal mechanism for $n$ independent uniform items is not a grand bundling mechanism.

Introduction

In the realm of mechanism design, the single-item monopoly problem was elegantly solved by Roger Myerson in 1981. By identifying the "virtual value" of a buyer, Myerson showed that the revenue-maximizing strategy is a simple reserve price. However, when a monopolist sells multiple goods, the problem's complexity increases exponentially. The optimal strategy may involve selling items separately, bundling them together ("grand bundling"), or offering complex lotteries (e.g., a 50% chance at an item for a specific price).

Historically, researchers lacked a general framework to certify that a proposed multi-item mechanism was truly optimal. While "sufficient conditions" existed, they were often non-exhaustive. This paper addresses this gap by establishing a strong duality framework, bridging the divide between mechanism design and optimal transport theory to provide a definitive toolkit for identifying optimal multi-item auctions.

The Theoretical Framework: Measure $\mu$ and Strong Duality

The authors' approach begins by rephrasing revenue maximization as an optimization over the buyer's utility function $u$. Central to this transformation is a "signed measure" $\mu$, derived from the buyer's type distribution. This measure captures how the seller's revenue fluctuates when the "rent" (utility) allocated to specific buyer types is adjusted.

The core contribution is the Strong Duality Theorem. It proves that the maximum revenue (the primal problem) is exactly equal to the minimum cost of a dual problem. This dual problem is characterized by two processes:

  1. Convex Shuffling: Redistributing mass such that the new distribution "convexly dominates" the original, akin to a mean-preserving spread.
  2. Transportation: Moving mass from the positive regions of the measure $\mu$ to the negative regions, where the cost is proportional to the distance moved.

By establishing that the duality gap is zero, the authors provide "certificates of optimality." If a candidate mechanism's revenue matches the cost of a valid solution to the transport problem, that mechanism is mathematically guaranteed to be optimal. This turns what was previously a guessing game into a precise calculation.

Key Insights and Applications

The Limits of Grand Bundling

A significant application of this framework concerns the "grand bundling" strategy. The authors extend Pavlov’s (2011) results for two items to $n$ items. They demonstrate that for $n$ independent items with values uniform on $[c, c+1]$, grand bundling is optimal if the base value $c$ is sufficiently large.

However, they also uncover a "curse of dimensionality": for any fixed $c$, as the number of items $n$ increases, grand bundling eventually ceases to be optimal. This suggests that as a product catalog grows in variety, simple bundling strategies become increasingly inefficient compared to more nuanced mechanisms.

The Necessity of Infinite Menus

The framework also sheds light on the complexity of optimal menus. For certain distributions, such as Beta distributions, the authors prove that the optimal mechanism requires an "uncountably infinite" menu of lotteries. This finding implies that finite pricing schemes are sometimes fundamentally incapable of capturing maximum revenue, highlighting the inherent complexity of multi-dimensional screening.

Conclusion and Future Directions

This work provides the first necessary and sufficient conditions to characterize the optimality of mechanisms with finite menus. While the framework is theoretically robust, practical challenges remain. Verifying stochastic dominance conditions in high dimensions ($n > 2$) is computationally intensive, and the current proof for strong duality primarily applies to compact (bounded) type spaces.

The most significant remaining challenge is extending these results to settings with multiple competing bidders. Moving from a single-buyer monopolist to a multi-bidder auction remains the "major open problem" in the field, but the strong duality framework established here provides a critical foundation for future exploration.

Summary updated

Abstract

We characterize optimal mechanisms for the multiple-good monopoly problem and provide a framework to find them. We show that a mechanism is optimal if and only if a measure $\mu$ derived from the buyer's type distribution satisfies certain stochastic dominance conditions. This measure expresses the marginal change in the seller's revenue under marginal changes in the rent paid to subsets of buyer types. As a corollary, we characterize the optimality of grand-bundling mechanisms, strengthening several results in the literature, where only sufficient optimality conditions have been derived. As an application, 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'11]. At the same time, 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.
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},
}
Figure