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:
- 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.
- 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.
- 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.
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