Optimal mechanisms with simple menus

Zihe Wang, Pingzhong Tang

TL;DR

In the notoriously difficult field of multi-item auction design, this paper proves that for a single buyer and two items, the optimal mechanism is often surprisingly "simple." Depending on the valuation distributions, the best way to sell is either through a "monotone" menu (where higher prices always buy more items) or a menu with a very small number of fixed options—sometimes as few as four.

What Problem Does This Paper Address?

Designing an optimal mechanism to sell multiple items is a classic challenge in economics and game theory. While Roger Myerson solved the single-item case in 1981, the multi-item case remains largely open. When a buyer has independent valuations for two different items, the "menu" of options a seller offers can theoretically be infinitely complex.

Recent research (notably by Hart and Nisan) has shown that in some cases, simple menus can be disastrously inefficient, capturing only a tiny fraction of the potential revenue. This paper tackles the inverse question: Under what conditions are simple menus actually optimal? The authors seek structural results that characterize when a seller can maximize revenue using only a handful of options or menus that follow intuitive properties like monotonicity.

Methods

The authors employ a rigorous analytical approach centered on the "power rate" of a probability density function $h$, defined as $PR(h(x)) = \frac{xh'(x)}{h(x)}$. They use this metric to categorize valuation distributions into two main regimes.

To prove their results, they:

  1. Geometric Revenue Representation: Use Green’s Theorem to transform the expected revenue formula into a function of the buyer's utility. This allows them to visualize how revenue changes based on the utility values at the boundaries of the valuation space.
  2. Semi-Constructive Proofs: For the monotonicity results, they fix part of the buyer's utility function and "rise" or "rotate" planes (representing menu items) to construct an optimal utility function that satisfies convexity and incentive compatibility.
  3. Pavlov’s Characterization: For the "small menu" results, they build upon previous work by Gregory Pavlov, which describes the geometric regions in the valuation space where different items are sold.

Datasets

Not discussed in the paper. As a theoretical work in mathematical economics, it relies on formal proofs rather than empirical datasets.

Key Insights and Ideas

  • The "Phase Transition" at -3: The paper identifies a critical threshold. When the sum of the power rates of the two item distributions is less than or equal to -3, the optimal menu is monotone. When it is greater than or equal to -3, the optimal menu is small (finite).
  • Monotonicity is Not Guaranteed: In multi-item settings, it’s possible for an optimal menu to be non-monotone—meaning a buyer might pay more but receive a lower probability of getting one of the items. This paper identifies the exact "mild conditions" (Condition 1) under which this counter-intuitive behavior disappears.
  • Finite is Enough: The authors prove that for many common distributions (like uniform, power, or exponential), the seller doesn't need an infinite list of lottery options. A few discrete choices are perfectly sufficient to capture 100% of the possible optimal revenue.
  • Bundling as a Corollary: The results provide a more general framework that subsumes previous findings. For example, they show that the optimality of "bundling" (selling both items only as a package) is a specific consequence of their broader menu monotonicity theorem.

Key Results

The paper divides its findings into two main parts based on the power rate conditions:

Part I: Monotone Menus (Sum of Power Rates $\leq -3$)

  • Theorem 4.2: Under this condition, the optimal mechanism has a monotone menu. As the payment increases, the allocation probabilities for both items increase simultaneously.
  • Revenue Monotonicity: They prove that in this regime, "stochastically superior" distributions (where the buyer is likely to value items more) always yield more revenue for the seller.

Part II: Small Menus (Sum of Power Rates $\geq -3$)

  • Theorem 5.2: If the power rates are constant (e.g., uniform or power functions), the optimal menu contains at most 4 items.
  • Theorem 5.7: If the power rates are monotone (e.g., exponential or polynomial densities), the optimal menu contains at most 6 items.
  • Theorem 5.10: In a unit-demand setting (where the buyer wants at most one item) with uniform distributions, the optimal menu contains at most 5 items.
This figure illustrates how a menu item in the optimal mechanism can be visualized as a plane (red dashed) that touches the utility boundaries.

Limitations and Future Work

  • Two-Item Constraint: The current proofs are specifically tailored to the case of two items. Extending these "simple menu" results to $k > 2$ items remains a significant challenge.
  • Independence Assumption: The paper assumes the buyer's valuations for the two items are independent. As the authors note, correlated distributions can lead to cases where finite menus are highly sub-optimal.
  • Continuous vs. Discrete: While the paper addresses continuous distributions, the complexity of finding these "simple" menus in practice for any arbitrary distribution is still an area for algorithmic refinement.

Summary updated

Abstract

We consider revenue-optimal mechanism design for the case with one buyer and two items. The buyer's valuations towards the two items are independent and additive. In this setting, optimal mechanism is unknown for general valuation distributions. We obtain two categories of structural results that shed light on the optimal mechanisms. These results can be summarized into one conclusion: under certain conditions, the optimal mechanisms have simple menus. The first category of results state that, under a centain condition, the optimal mechanism has a monotone menu. In other words, in the menu that represents the optimal mechanism, as payment increases, the allocation probabilities for both items increase simultaneously. This theorem complements Hart and Reny's recent result regarding the nonmonotonicity of menu and revenue in multi-item settings. Applying this theorem, we derive a version of revenue monotonicity theorem that states stochastically superior distributions yield more revenue. Moreover, our theorem subsumes a previous result regarding sufficient conditions under which bundling is optimal[Hart and Nisan 2012]. The second category of results state that, under certain conditions, the optimal mechanisms have few menu items. Our first result in this category says that, for certain distributions, the optimal menu contains at most 4 items. The condition admits power (including uniform) density functions. Our second result in this category works for a weaker (hence more general) condition, under which the optimal menu contains at most 6 items. This condition is general enough to include a wide variety of density functions, such as exponential functions and any function whose Taylor series coefficients are nonnegative. Our last result in this category works for unit-demand setting. It states that, for uniform distributions, the optimal menu contains at most 5 items. All these results are in sharp contrast to Hart and Nisan's recent result that finite-sized menu cannot guarantee any positive fraction of optimal revenue for correlated valuation distributions.
BibTeX
@inproceedings{wang2014optimal,
  author = {Zihe Wang and Pingzhong Tang},
  title = {{Optimal mechanisms with simple menus}},
  booktitle = {EC},
  year = {2014},
  url = {https://openreview.net/forum?id=IXBNCxiGGip},
}

Loading related content...

Figure