PaperlayerView exact revision on arXiv

Source-linked AI summary

Mechanism Design via Optimal Transport

Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos

arXiv:1503.01958v1cs.GT

TL;DR

Optimal mechanisms for multi-item settings with explicitly listed type distributions do not cover implicit settings such as additive buyers with independent item values, where exact optimization is #P-hard even for one bidder. The paper uses optimal transport and duality to develop a framework for optimal mechanisms. It gives conditions for grand-bundle optimality and characterizes two-item mechanisms, including settings with a continuum of lotteries.

  • Problem

    Existing general multi-item results apply to explicitly listed type distributions, while implicit additive settings remain challenging and exact optimization is #P-hard even for one bidder.

    Source: §1 · p. 2

  • Method

    The paper develops an optimal-mechanism framework by relaxing the utility optimization problem, taking an optimal-transport dual, and restoring convexity for its structural results.

    Source: §1 · p. 3, §5 · p. 8

  • Results

    The framework gives a condition for optimal grand-bundle pricing, a general characterization of canonical two-item mechanisms, and closed-form results including a setting requiring a continuum of lotteries.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results provide closed-form descriptions of optimal mechanisms in several two-item settings, including one with a continuum of lotteries.

    Source: §1 · pp. 3–4

    A critical grand-bundle price alone does not guarantee that offering the bundle at that price is optimal.

    Source: §7 · p. 9

Abstract

from arXiv · show

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.

1 Introduction

Implicit multi-item settings remain difficult: existing results for explicitly listed type distributions do not cover them, and exact optimization is #P-hard even for one additive bidder. The paper develops an optimal-transport framework and uses it to characterize optimal mechanisms and derive closed-form results in several two-item settings.

1 Introduction

  • Exact optimization is #P-hard even for one additive bidder with independent item values of support 2, while existing general results apply to explicitly listed type distributions.Implicit additive distributions can be described more succinctly, but the paper notes that they pose greater computational challenges.Source: §1 · p. 2
  • The framework relaxes the utility-function convexity constraint, forms a dual optimal-transport problem, then restores convexity for its final structural results.The transport cost for moving probability mass from x to y is the sum of max{x_i − y_i, 0}.Source: §1 · p. 3
  • Theorem 3 gives a condition for optimality of a take-it-or-leave-it grand-bundle offer at a critical price defined by the boundary of a convex region of a measure.The paper also develops an alternate condition that implies the stochastic-domination condition used in its results and applications.Source: §1 · pp. 3–4
  • For non-identical exponential item distributions, the optimal mechanism offers the grand bundle and a second option allocating the thinner-tailed item with probability 1 and the other with probability min{λ_i}/max{λ_i}.The grand bundle is offered at some price, and the second option is offered at a different price.Source: §1 · p. 3
  • For a setting with non-identical power-law item distributions, the optimal mechanism offers only the grand bundle.Source: §1 · p. 3
  • Theorem 6 characterizes optimal two-item mechanisms for canonical settings through a decreasing, concave, continuous function that determines allocations and payments.Types below the function receive nothing; others are matched to points on it, with allocation probabilities given by derivatives.Source: §1 · pp. 3–4
  • For a setting with non-identical beta item distributions, the optimal mechanism offers a continuum of lotteries, the first such explicit setting known to the authors for two independent values.The paper says its framework can still provide a closed-form representation of the mechanism efficiently.Source: §1 · pp. 3–4

2 The Revenue-Maximization Program

The revenue-maximization program represents a mechanism for one additive buyer through utility as a function of reported values. It maximizes expected revenue subject to utility conditions that encode incentive compatibility and individual rationality.

2 The Revenue-Maximization Program

  • A mechanism maps the buyer’s value vector to allocation probabilities for each good and a price.Source: §2 · p. 4
  • Under truthful reporting, utility is the buyer’s value for the allocation minus its price; incentive compatibility and individual rationality require truthful incentives and nonnegative utility.Source: §2 · p. 4
  • The program maximizes expected revenue over nonnegative, nondecreasing, convex, continuous utility functions whose gradients lie in [0, 1]^n almost everywhere.For an incentive-compatible mechanism, allocation probabilities are given by the utility gradient and payment by ∇u(z) · z − u(z).Source: §2 · pp. 4–5

3 Separating into Two Spaces

The formulation separates the domain into regions X and Y according to the sign of a density-derived quantity, then augments X with d− to balance the two measures. The revenue objective is to choose a utility function satisfying monotonicity, convexity, continuity, and gradient constraints.

3 Separating into Two Spaces

  • X contains points where −∇f(z)·z exceeds (n+1)f(z), while Y contains points where it does not.The domain is separated into these two regions, excluding d−.Source: §3 · p. 5
  • Adding d− to X creates X0, whose measure is set so that µX0(X0) equals νY(Y).The paper motivates equal masses by the expected revenue of the constant utility function being −1.Source: §3 · p. 6
  • The objective is to maximize the utility-based integral over the domain while requiring utility to be nondecreasing, convex, continuous, and to have gradients in [0, 1]^n almost everywhere.The formulation also fixes utility at d− to zero.Source: §3 · p. 6
  • In the examples considered, d− is surrounded only by points in the Y region.Source: Figure 1 · p. 6

4 The Relaxed Problem

The paper relaxes the utility optimization problem by replacing its original constraints with a pairwise inequality involving a cost function. The relaxed optimum bounds the mechanism-design optimum from above, and is also optimal for the original problem if it satisfies all original constraints.

4 The Relaxed Problem

  • The relaxed problem maximizes the objective subject to u(x) − u(y) ≤ c(x, y) for every x in X0 and y in Y.This inequality follows from the original gradient and continuity constraints.Source: §4 · p. 7
  • The relaxed optimum is at least the optimal revenue of the original mechanism-design problem.If a relaxed solution also satisfies all original constraints, it is optimal for the original problem.Source: §4 · p. 7

5 Dual Relaxed Problem

The dual relaxed problem minimizes transport cost between measures on X0 and Y, forming a continuous counterpart to minimum-weight bipartite matching. A feasible utility and transport measure are both optimal when their utility differences equal the cost almost surely under the transport measure.

5 Dual Relaxed Problem

  • The dual relaxed problem minimizes the cost of transporting mass between X0 and Y over measures with marginals µX0 and νY.The paper describes it as a continuous analog of minimum-weight bipartite matching.Source: §5 · p. 8
  • If feasible u* and γ* satisfy u*(x) − u*(y) = c(x, y) γ*-almost surely, both are optimal for their respective relaxed problems.The paper establishes matching primal and dual values for the constructed solutions.Source: §5 · p. 8

6 Strassen’s Theorem and Stochastic Dominance

Stochastic dominance provides a way to establish the existence of a transport measure with specified marginals whose paired points obey the coordinatewise order. The paper connects that order to equality of utility differences and costs when both types receive the grand bundle at the same price.

6 Strassen’s Theorem and Stochastic Dominance

  • Stochastic dominance means that every increasing bounded measurable function has at least as large an integral under the dominating measure.Source: §6 · p. 9
  • If α stochastically dominates β under the coordinatewise order, a coupling exists with marginals α and β whose pairs satisfy b ⪯ a almost surely.The paper uses this result to establish the existence of transport measures.Source: §6 · pp. 8–9
  • When both types receive the grand bundle at price p, u(x) − u(y) equals c(x, y) exactly when y ⪯ x.Source: §6 · p. 9

7 Optimality of Grand Bundling

The paper gives a sufficient condition for grand-bundle pricing to be optimal: a critical bundle price must satisfy a geometric condition, and the restricted measures must satisfy stochastic dominance. Optimality is certified by constructing a transport map for the bundling utility.

7 Optimality of Grand Bundling

  • A critical bundle price requires Zp* ⊆ Y and a corresponding mass condition; its zero-utility region must also be transportable to the zero type.The section seeks a price for which Zp is contained in Y and the transport map can send all of Zp to the zero type.Source: §7 · pp. 9–10
  • Even when a critical bundle price exists, grand-bundle pricing need not be optimal unless the restricted measures satisfy the stochastic-dominance condition.The paper gives a sufficient two-dimensional verification route using conditions on density differences and integrals along horizontal or vertical lines.Source: §7 · pp. 9–11
  • If a critical bundle price p* satisfies μX|Wp* ⪰ νY|Wp*, offering the grand bundle at p* is optimal, for any number of items.The proof constructs a transport map showing the bundling utility is optimal for the relaxed problem and observes that it satisfies the original mechanism-design constraints.Source: §7 · pp. 9–10

8 Numerical Example: Bundling Two Power-Law Items

For one pair of power-law item distributions, the paper numerically identifies a critical bundle price and checks the conditions needed to establish that bundling is optimal.

8.1 Numerically Computing the Critical Bundle Price

  • The critical bundle price is numerically determined as p* ≈ .35725, then checked against the condition Zp* ⊆ Y.For c1 = 6 and c2 = 7, the relevant expression is maximized at z1 = 0.133226, where it equals 1.98654, below 3.Source: §8.1 · p. 11

8 Numerical Example: Bundling Two Power-Law Items

  • For the instance with densities f1(z1) = 5/(1 + z1)^6 and f2(z2) = 6/(1 + z2)^7, the optimal mechanism offers both goods for p* ≈ .35725.The authors use numerical computations to establish grand-bundling optimality for this instance, noting that the integrals may be complicated.Source: §8 · p. 11, §8.2 · p. 12

8.2 Verifying Stochastic Dominance

  • The stochastic-dominance verification completes the argument that the numerically identified price yields an optimal grand-bundle offer for this instance.The resulting mechanism offers the bundle at approximately .35725.Source: §8 · p. 11, §8.2 · p. 12

9 Complete Solution for Two Exponential Items

For two independent exponential items, the paper specifies the optimal mechanism, including cases where it offers more than the grand bundle alone. Its proof uses a critical price and a transport-map argument.

9 Complete Solution for Two Exponential Items

  • For two independent exponential items, the optimal mechanism can have richer structure than a take-it-or-leave-it grand-bundle offer.The section derives a closed-form description, while also performing calculations for n exponential items where they do not add significant complications.Source: §9 · p. 12

9.1 The Critical Price p*

  • For all λ1 ≥ λ2 > 0, the optimal menu includes no goods for 0, a partial lottery for 2/λ1, and both goods for p*.The partial lottery gives item 1 with probability 1 and item 2 with probability λ2/λ1; p* is the critical price.Source: §9.1 · pp. 12–13

9.2 The Absorption Hyperplane

  • The absorption hyperplane has the property that integrating the difference between the two measures outward along any positive direction from it yields zero.This geometric property provides intuition for the optimal mechanism's structure under independent exponential distributions.Source: §9.2 · p. 13

9.3 Proof of Optimality

  • The optimality proof decomposes a transport map into pieces for the zero-utility, partial-allocation, and grand-bundle regions.For the grand-bundle region, stochastic dominance supplies a coupling; when p* ≤ 2/λmax, the intermediate region is empty and grand bundling alone is optimal.Source: §9.3 · pp. 13–15

10 General Characterization of Two-Item Optimal Mechanisms

The paper characterizes two-item mechanisms through a canonical partition of the type space. For well-formed partitions, the boundary determines the allocation and payment in each region.

10 General Characterization of Two-Item Optimal Mechanisms

  • A canonical zero set is a nonempty, closed, decreasing, convex subset of D1 × D2 whose outer boundary defines a partition into Z, A, B, and W.The partition is well-formed only when it meets additional measure and dominance conditions.Source: §10 · p. 15
  • The well-formedness conditions require equal mass along specified outward lines and stochastic dominance on increasing subsets of W.The stated conditions include matching mass on vertical and horizontal lines and requiring μX|W to stochastically dominate νY|W.Source: §10 · p. 16
  • Theorem 6 assigns no goods in Z, lotteries in A and B, and both goods at a fixed price in W.The lottery probabilities and payments in A and B are determined by the boundary function s and its slope.Source: §10 · p. 16
  • The mechanism is truthful because a bidder's utility does not increase by declaring a different type; the proof also constructs a transport map dual to the utility.The map couples the corresponding regions, with Strassen's theorem used for W.Source: §10 · pp. 16–17

11 Numerical Example: Optimal Mechanism for Two Beta Distributions

This section applies the paper’s characterization and stochastic-dominance analysis to optimal mechanisms for two-item distributions, including a Beta-distributed example and a power-law case. It derives a closed-form mechanism for the former and establishes the optimality of grand-bundle pricing in the latter.

11 Numerical Example: Optimal Mechanism for Two Beta Distributions

  • The construction defines Stop and Sright, computes p∗ = 0.71307, builds a canonical partition, and applies Theorem 6 after verifying its required conditions.The curve s is concave, decreasing, and continuous; the chosen price makes νY(Z) = µX0({⃗0}), and the measures satisfy the stated stochastic-dominance condition on W.Source: §11 · pp. 17–19
  • The optimal mechanism partitions types into Z, A, B, and W: no goods in Z, randomized allocations in A and B, and both goods for 0.71307 in W.Since s(z1) is not linear on [0, .16016] and [.62307, .63718], Example 4 shows that an optimal mechanism might offer a continuum of randomized outcomes.Source: §11 · p. 19

A.1 An Equivalent Condition for Stochastic Dominance

  • A measure α stochastically dominates β exactly when α(A) ≥ β(A) for every increasing measurable set A; Lemma 2 reduces verification to finite unions of bases.Every discretized increasing set has finitely many corners and is the union of the corresponding bases.Source: §A.1 · pp. 20–23

A.2 Stochastic Dominance in Two Dimensions: Proof of Theorem 4

  • Theorem 4 gives a sufficient condition for stochastic dominance in two dimensions under stated density, integral, boundary, and monotonicity assumptions.Its proof reduces the verification to finite unions of bases and proceeds by induction on their number.Source: §A.2 · pp. 24–25
  • In the two-dimensional stochastic-dominance proof, the inductive hypothesis makes the final derived quantity nonnegative.Source: §A.2 · pp. 26–27

B Bundling Two Power-Law Items

C Optimal Mechanism Design in Two Dimensions: Proof of Theorem 6

The proof establishes that the mechanism is truthful by checking deviations between declared-type regions. Concavity of s supports the incentive arguments, including cases involving the bundle region W.

Proof of Theorem 6

  • In Z the bidder gets nothing for zero; A and B offer probabilistic allocations, while W gives both goods for a fixed price.In A the probabilities are −s′(z1) for item 1 and 1 for item 2; in B they are 1 and −1/s′(s−1(z2)), respectively.Source: C Optimal Mechanism Design in Two… · p. 28
  • A bidder in Z cannot gain by declaring a type in W, because z1 + z2 ≤ a + s(a) makes the resulting utility nonpositive.The proof also notes that truthful utility is never negative.Source: C Optimal Mechanism Design in Two… · p. 28
  • The proof checks deviations across region pairs and concludes that truthful bidding is incentive-compatible.For key cases, it uses the concavity of s to show that truthful utility is at least utility from a false declaration.Source: C Optimal Mechanism Design in Two… · pp. 28, 30

Related papers

Loading 1503.01958v1…