Strong Duality for a Multiple-Good Monopolist

Constantinos Daskalakis; Alan Deckelbaum; Christos Tzamos

Source-linked AI summary

Strong Duality for a Multiple-Good Monopolist

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

arXiv:1409.4150v3Sep 15, 2014cs.GT

TL;DR

The paper asks how to find and certify revenue-optimal mechanisms for a monopolist selling multiple goods to an additive buyer. It develops a strong-duality framework using a measure derived from the type distribution and an optimal-transport dual, then characterizes optimality through stochastic dominance conditions. The framework yields necessary-and-sufficient grand-bundling criteria and contrasting results for uniform-item distributions.

Problem
The paper studies revenue maximization for a monopolist selling n goods to a single additive buyer, a problem that can involve complex mechanisms and an infinite-dimensional, non-strictly-convex optimization program.
Method
The paper formulates mechanism design through buyer utility and a signed measure derived from the type distribution, then constructs an optimal-transport dual with equal optimal value.
Results
The paper gives necessary-and-sufficient stochastic-dominance conditions for optimal mechanisms and, as a special case, for grand bundling.
Takeaways & Limitations
For n i.i.d. uniform [c,c+1] items, grand bundling is optimal for sufficiently large c but not for sufficiently large n at any fixed c.
Takeaways & Limitations
Checking stochastic dominance in higher dimensions becomes significantly harder for arbitrary numbers of items.

Abstract

from arXiv · show

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 $μ$ 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.

EECS, MIT

The paper lists keywords including revenue maximization, mechanism design, strong duality, and grand bundling, alongside funding acknowledgments.

The listed keywords are revenue maximization, mechanism design, strong duality, and grand bundling.
The acknowledgments cite support from the Sloan Foundation, Microsoft Research, NSF, and the Fannie and John Hertz Foundation.

1 Introduction

The paper studies revenue-optimal mechanisms for selling multiple goods to a single additive buyer and develops a strong-duality framework based on optimal transport. It characterizes optimal mechanisms through stochastic dominance conditions and applies the framework to grand bundling and uniform-item settings.

The problem is revenue maximization for a monopolist selling n goods to a single additive buyer with values distributed according to f.
The dual framework provides certificates of mechanism optimality through dual witnesses for arbitrary n and f.
Theorem 2 establishes strong duality by formulating a dual optimal-transport problem whose optimal value equals the mechanism-design optimum.
The paper formulates mechanism design as an optimization over convex, non-decreasing, 1-Lipschitz buyer-utility functions and a signed measure μ derived from f.
Theorem 3 characterizes arbitrary finite-menu mechanisms as optimal if and only if μ satisfies stochastic dominance conditions, one for each partition region.
For grand bundling, optimality is characterized by a pair of stochastic dominance conditions, strengthening prior sufficient-only results.
For n i.i.d. uniform [c,c+1] items, grand bundling is optimal for sufficiently large c but is not optimal for sufficiently large n at any fixed c.
The framework addresses an infinite-dimensional, non-strictly-convex optimization problem where first-order conditions cannot directly characterize the optimum.

2 Revenue Maximization as Optimization Program

The multi-item monopoly problem is formulated as optimization over utility functions representing IC and IR mechanisms. Expected revenue becomes a linear functional of a transformed measure derived from the type distribution, yielding an equivalent optimization program.

Problem formulation: The seller chooses a mechanism maximizing expected revenue from an additive buyer whose values for n goods follow a joint density f.The mechanism specifies allocation probabilities and prices for reported types.
Feasible utilities: IC and IR mechanisms correspond exactly to nonnegative utility functions that are continuous, nondecreasing, convex, and 1-Lipschitz under the ℓ1 norm.Allocation and payment functions can be recovered from the utility function using P(x)=∇u(x) and T(x)=P(x)·x−u(x).
Normalization: Subtracting the utility at the lowest type preserves feasibility and weakly improves revenue, so optimization can restrict attention to utilities satisfying u(xlow)=0.This normalization also permits removing the explicit nonnegativity constraint from the equivalent program.
Transformed measure: The transformed measure μ converts expected revenue into the linear objective ∫X u dμ and represents marginal revenue changes from changing rents paid to subsets of types.The measure is defined from the density and boundary terms and is a Radon measure under bounded derivative assumptions.
Equivalent program: Theorem 1 establishes equivalence between finding the optimal IC and IR mechanism and optimizing the transformed-measure objective over feasible utility functions.The formulation is infinite dimensional and not strictly convex, so first-order conditions do not directly characterize its optimum.
Uniform example: For independent uniform items, μ combines a positive point mass at the lowest type, a negative uniform interior mass, and signed masses on upper and lower boundary faces.The resulting revenue maximization remains an infinite-dimensional optimization over feasible utilities.

3 The Strong Mechanism Design Duality Theorem

The paper formulates mechanism design and an optimal transportation problem as strongly dual optimization problems, enabling dual solutions to certify mechanism optimality.

The original mechanism-design formulation is infinite-dimensional and lacks strict convexity, so first-order conditions cannot directly characterize its optimum.
Strong duality makes the primal mechanism-design optimum equal the optimum of a transportation-based dual problem.
The dual uses a signed measure derived from the type density and imposes convex-dominance constraints on transportation marginals.
Its transportation cost is the ℓ1 distance between source and destination types, after transforming the measure into a zero-total-mass measure and transporting it.
A feasible primal mechanism and dual transport plan satisfying complementary-slackness conditions form a tight pair and certify optimality.

4 Single-Item Applications and Interpretation

For a single regular item, the dual transportation problem is governed directly by Myerson virtual values; when regularity fails, ironing is required before transport.

The single-item application relates minimizing dual transportation cost to Myerson’s solution.
For a differentiable regular distribution F on [z, z̄], the dual measure μ is derived from the density f according to the paper’s general construction.
The transportation interpretation assigns excess supply to boundary types and demand to other types, with mass moving according to virtual-value signs.
Buyers with positive virtual types push mass left, whereas buyers with negative virtual types push mass right.
The resulting transport is optimal because the utility max{z − p*, 0} satisfies complementary-slackness conditions for the associated map.
When F is regular, virtual values exactly determine optimal transportation; for non-regular F, ironing first performs the necessary mean-preserving spreads.

5 Multi-Item Applications of Duality

The duality theorem verifies optimal multi-item mechanisms by constructing transport plans, including the MV mechanism and a non-identical two-item example with region-specific allocations.

5.1 Two Uniform [0, 1] Items: The theorem provides a short optimality proof for the MV mechanism for two i.i.d. uniform [0, 1] items.
5.1 Two Uniform [0, 1] Items: The MV mechanism partitions types into regions receiving no goods, only good 1, only good 2, or both goods.
5.1 Two Uniform [0, 1] Items: Its dual measure has a point mass at (0, 0), uniform negative mass over [0, 1]^2, and positive boundary mass.
5.1 Two Uniform [0, 1] Items: Optimality follows by decomposing the transport plan across regions and matching positive to negative mass through leftward, downward, or combined movements.
5.2 Two Uniform But Not Identical Items: In the non-identical example, values are uniform and independent on [4, 16] and [4, 7], and the optimal mechanism partitions this type space into regions.
5.2 Two Uniform But Not Identical Items: In region Y, the buyer pays 8 and receives the first good with probability 50% and the second with probability 1.
5.2 Two Uniform But Not Identical Items: The examples illustrate duality-based verification, while later sections provide stochastic-dominance characterization and a procedure for identifying optimal mechanisms.

6 Characterizing Optimal Finite-Menu Mechanisms

The section gives necessary and sufficient stochastic-dominance conditions for optimal finite-menu mechanisms, using a transformed measure analyzed separately across allocation regions. It also characterizes grand-bundle optimality and derives contrasting results for uniform-item distributions.

Verifying optimality is equivalent to checking measure-theoretic inequalities separately in regions whose types receive the same allocation.The dual witness and convex-shuffling arguments avoid transporting mass across different allocation regions.
The characterization uses convex stochastic dominance with respect to vectors that encode coordinatewise monotonicity, extending standard convex-dominance notions.Dominance with respect to a vector v compares expectations of convex functions monotone according to v.
A finite-menu mechanism is optimal if and only if its essential form satisfies the optimal menu conditions with respect to the transformed measure μ.The conditions apply to incentive-compatible and individually rational mechanisms for additive buyers with arbitrary finite menus.
The grand-bundle mechanism at price p is optimal if and only if μ restricted to affordable types second-order dominates zero and zero convexly dominates μ on unaffordable types.Here W contains types that can afford the bundle and Z contains types that cannot.
For every fixed number of iid uniform items, grand bundling is optimal when c is sufficiently large, whereas for every c it fails to be optimal when n is sufficiently large.The thresholds are stated existentially: for each n there is c0, and for each c there is n0.

7 Constructing Optimal Mechanisms

This section develops a construction framework based on exclusion sets, canonical partitions, and stochastic-dominance checks. For two goods, a well-formed canonical partition is sufficient to certify the induced mechanism's optimality.

The finite-menu characterization guides candidate construction by requiring stochastic-dominance conditions on each region sharing the same allocation.Equal positive and negative mass in each region is a necessary preliminary condition.
An exclusion set is a convex, compact, decreasing subset of types receiving no goods and paying nothing; it induces utility equal to the ℓ1 distance to that set.The associated utility is nonnegative, non-decreasing, convex, and 1-Lipschitz, so it defines an IC and IR mechanism.
For two goods, the canonical partition divides the type space into Z, A, B, and W according to the exclusion set's critical point and boundary functions.A and B are the regions below the respective critical coordinates outside Z, while W is the remaining region.
Within the canonical partition, utility is determined by whether the closest point in Z is reached by moving down, left, or diagonally.The boundary functions s1 and s2 and critical price P specify the corresponding allocation and payment formulas.
A well-formed canonical partition imposes stripwise dominance conditions in A and B and dominance conditions in Z and W.The strip conditions correspond to matching positive mass downward or leftward; these are stronger than the convex-dominance conditions required by Theorem 3.
If an exclusion set induces a canonical partition well-formed with respect to μ, its mechanism is optimal for the corresponding two-item distribution.The mechanism gives no allocation in Z, randomized single-item allocations in A and B, and both goods at price P in W.

8 Applying Theorem 7 to find optimal mechanisms

The section applies the exclusion-set theorem and a first-order dominance lemma to compute optimal mechanisms across several two-item distributions. The examples include infinite menus, grand bundling, and unbounded-support cases.

The main technical challenge is verifying the stochastic-dominance condition in W; the examples simplify this by proving the stronger first-order dominance condition.Lemma 3 supplies sufficient conditions for checking that dominance relation.
Lemma 3 certifies first-order stochastic dominance when density differences satisfy support, line-integral, and structural conditions over a decreasing subset of a box.The lemma can also apply to distributions with unbounded support.
For independent items, the transformed-measure density can be analyzed through the item densities and derivative-based monotonicity conditions.In the cited setting, checking that f′2(y)y f2(y) is decreasing suffices for the lemma's final condition.
The framework solves two-item Beta examples, including mechanisms with uncountably infinite menus of lotteries that still admit succinct descriptions.The paper reports that the optimal mechanism in the worked Beta example is essentially unique, making the uncountable menu unavoidable.
For f1(x)=2(1−x) and f2(y)=2(1−y), the optimal mechanism charges p*≈.5535 for both goods in W and uses randomized allocations in A and B.In A and B, one item is allocated surely while the other is allocated according to the relevant boundary derivative.
For two independent exponential items with densities 5/(1+x)^6 and 6/(1+y)^7, the optimal mechanism is a grand-bundle offer at p*≈.35725.The section also states that the broader exponential example has a complete optimal-mechanism solution.

9 Conclusions

The paper develops a duality-based framework for multiple-good revenue maximization and characterizes optimal mechanisms through stochastic dominance conditions on an induced measure. It also identifies unresolved challenges in higher dimensions, simple closed forms, and multiple-bidder settings.

Conclusions: The framework gives every optimal mechanism an optimal-transportation certificate and characterizes optimality through stochastic dominance conditions on a measure induced by the buyer distribution.The measure represents the marginal revenue effect of changing rents for subsets of types.
Conclusions: Two-dimensional tools establish optimality for many two-item examples, while verifying stochastic dominance becomes significantly harder in higher dimensions.Developing higher-dimensional verification tools is identified as useful for mechanisms with three or more items.
Conclusions: The paper also calls for conditions on type distributions under which optimal mechanisms admit simple closed-form descriptions.
Conclusions: The paper leaves open broad conditions guaranteeing grand bundling or the mechanism forms described by Theorem 7.The conclusion frames these as directions for further characterization.
Conclusions: Extending the results to multiple bidders remains a major open problem, including two bidders with independent identical values for two uniformly distributed items on [0,1].The revenue-optimal mechanism is unknown in that setting.

A Strong Mechanism Design Duality - Proof of Theorem 2

The proof formalizes strong mechanism-design duality using Radon measures and Fenchel–Rockafellar duality. It reduces the dual expression to an optimal-transportation problem governed by convex stochastic dominance constraints.

A Strong Mechanism Design Duality - Proof of Theorem 2: The proof works with signed and unsigned Radon measures on a compact type space, with the transformed distribution represented as a signed Radon measure.A Radon measure is specified as a locally finite inner-regular Borel measure.
A Strong Mechanism Design Duality - Proof of Theorem 2: The proof establishes equality between the mechanism-design maximization and the transport minimization, with attainment under the stated compactness and measure assumptions.The auxiliary lemmas provide the dual representation and attainment needed for the theorem.
A Strong Mechanism Design Duality - Proof of Theorem 2: Fenchel–Rockafellar duality is applied to convex functionals on bounded continuous functions over X × X.The compactness of X identifies the dual space with Radon measures through the Riesz representation theorem.
A Strong Mechanism Design Duality - Proof of Theorem 2: The resulting dual is finite only for positive transport measures whose marginals satisfy convex stochastic dominance relative to the positive and negative parts of the transformed measure.Failure of either dominance condition makes the corresponding optimization expression unbounded.

A.3 Proof of Theorem 2

The proof combines earlier lemmas to show that the transport dual attains its infimum and that an optimal utility function attains the mechanism-design supremum. Compactness and equicontinuity provide the required convergent subsequence.

A.3 Proof of Theorem 2: The final minimization problem attains its infimum at a transport plan γ*, which is also feasible and optimal for the preceding dual problem.The argument establishes equality of the two minimization objectives.
A.3 Proof of Theorem 2: The optimal transport plan has equal marginal masses, with γ*_1(X) = γ*_2(X) = μ+(X).
A.3 Proof of Theorem 2: An optimizing sequence of feasible utilities is normalized at the origin and bounded and equicontinuous because feasible utilities are 1-Lipschitz.Arzelà–Ascoli then yields a uniformly convergent subsequence.
A.3 Proof of Theorem 2: The uniform limit remains feasible, and linearity of the objective makes its induced mechanism attain the supremum revenue.

A.5 Omitted Proofs from Section 5 - Example 2

The Example 2 proof constructs an optimal dual transport plan by decomposing the canonical partition into regions Z, Y, and W. Each regional plan is designed to satisfy the transport and utility-saturation conditions required for optimality.

A.5 Omitted Proofs from Section 5 - Example 2: The dual plan is decomposed as γ* = γZ + γY + γW, with each component supported within its corresponding canonical-partition region.The construction is paired with verification of the conditions in Corollary 1.
A.5 Omitted Proofs from Section 5 - Example 2: In region Z, the positive transformed measure is concentrated at (4,4), while the negative measure lies coordinatewise above it, so the zero transport plan suffices.
A.5 Omitted Proofs from Section 5 - Example 2: In region W, positive mass on the top and right edges is transported into negative mass in the interior and bottom by moving downward and leftward.This matches the region’s allocation structure, where both items are allocated with probability 1.
A.5 Omitted Proofs from Section 5 - Example 2: The construction verifies that each regional transport plan satisfies the required marginal and utility-difference conditions, completing the optimality certificate.For W, the utility satisfies u*(x) = ||x||_1 − 12; for Y, the second-good utility difference equals the value difference.
A.5 Omitted Proofs from Section 5 - Example 2: In region Y, positive mass is first shuffled along the upper boundary and then transported vertically downward to the negative part.The shuffling is needed because negative mass on the left boundary prevents direct downward transport.

B Proof of Stochastic Conditions of Section 6

The proof develops coupling tools based on Jensen’s inequality and Strassen’s theorem, then constructs region-specific measures to establish the stochastic conditions for optimality.

Probabilistic lemmas: The proof uses convex dominance and coupling representations to relate random vectors through conditional expectations and componentwise inequalities.Extended Strassen’s theorem supplies coupled variables with the required marginal distributions and dominance properties.
Probabilistic lemmas: Jensen’s inequality provides the equality conditions needed to identify when convex functions remain unchanged under conditional averaging.The conditional variant applies the equality characterization to conditional distributions.
Probabilistic lemmas: Lemma 10 constructs a coupling in which shared subgradients, utility preservation, and componentwise conditional dominance hold simultaneously.These properties support the later construction of feasible dual measures.
Optimality proof: For each menu region, the proof applies the extended Strassen theorem and defines Ĉ as the coordinatewise minimum of Â and E[B̂|Â].The resulting measure γ_R is designed to satisfy the conditions of Corollary 1.
Optimality proof: Summing the region-specific measures yields a feasible measure γ satisfying Corollary 1, proving that the optimal menu conditions imply mechanism optimality.The converse direction begins with an optimal finite-menu mechanism in essential form.

C Missing Proofs of Section 6 - Theorem 5

The proof of Theorem 5 transforms the uniform-item problem to the unit hypercube and verifies stochastic dominance by partitioning the relevant region and constructing measure-preserving matchings.

Measure transformation: For the shifted hypercube, the transformed measure has point mass +1 at the origin, interior mass −(n+1), and surface masses depending on c.The original support is [c,c+1]^n; shifting to [0,1]^n isolates the c-dependent surface terms.
Measure transformation: A decreasing threshold p*(c) is chosen so that μ_c(Z(p*(c))) = 0 for sufficiently large c, with p*(c) approaching 0 as c grows.The proof then defines Z_c by the threshold’s lower ℓ1 region and W_c as its complement.
Conclusion: The construction verifies the stochastic dominance conditions needed by Theorem 3 for sufficiently large c, supporting grand bundling at price p*(c)+c.The additive c term arises from shifting the hypercube to the origin.
Stochastic dominance: The region W_c is partitioned into permutation-indexed regions, enabling a bijection ϕ that preserves surface measures while mapping each point componentwise downward.The surface-density ratio is ρ = (c+1)/c, and the Jacobian calculation verifies the required scaling.

E.1 Verifying Stochastic Dominance - Proof of Lemma 3

The proof reduces first-order stochastic dominance checks from arbitrary increasing sets to finite unions of elementary bases, using discretization and approximation.

Dominance criterion: First-order stochastic dominance means that one measure assigns at least as much mass as another to every increasing measurable set.This is equivalent to comparing integrals of increasing test functions.
Dominance criterion: The proof represents bounded increasing functions as weighted sums of indicator functions of increasing level sets.This converts function inequalities into setwise inequalities.
Discretization: Lemma 13 shows that verifying the measure inequality on finite unions of bases suffices to establish dominance on all increasing measurable sets.The argument uses discretized approximations and induction on the number of bases.
Discretization: Increasing sets can be approximated by k-discretized sets whose finitely many corners generate finite unions of bases.The corner decomposition provides a finite combinatorial representation for each discretized approximation.
Two-dimensional case: The proof handles the two-dimensional decreasing-region case by comparing vertical integrals and extending the argument inductively across unions of bases.Monotonicity of the density difference controls the relevant integral signs.

F Extending to Unbounded Distributions

The framework can extend partially to unbounded distributions under integrability and tail-decay conditions, but the strong-duality proof remains tied to compactness.

Extensions: Transformed measures can often be defined for unbounded distributions when the density decays sufficiently quickly to eliminate surface terms at infinity.One example requires lim z_i→∞ f_i(z_i)z_i^2 → 0.
Limitations: Without sufficient decay of the density, achievable revenue may be infinite and an optimal mechanism may not exist.The examples in the paper satisfy the required finiteness properties for utility integrals.
Extensions: Weak duality remains valid for unbounded measures when the first moment ∫||x||_1 d|μ| is finite.Tight dual certificates can therefore still certify optimality in the unbounded case.
Limitations: The strong-duality proof does not immediately extend to unbounded μ because its technical tools require compact spaces.Additional work is needed to determine whether strong duality holds in such settings.