Abstract
We consider 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, the optimal mechanism is unknown for general valuation distributions. We obtain two categories of structural results that shed light on the optimal mechanisms. The first category of results states that, under certain mild conditions, 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. 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. The second category of results states that, under certain conditions, the optimal mechanisms have few menu items. Our first result in this category says, for certain distributions, the optimal menu contains at most 4 items. The condition admits power (including uniform) density functions. Based on a similar proof of this result, we are able to obtain a wide class of distributions where bundling is optimal. Our second result in this category works for a weaker condition, under which the optimal menu contains at most 6 items. This condition includes exponential density functions. 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.
Introduction
Designing an optimal mechanism to sell multiple items is a cornerstone challenge in mechanism design. While Roger Myerson’s 1981 work provided a complete solution for the single-item case, the multi-item scenario remains notoriously complex. When a buyer has independent, additive valuations for two items, the space of possible mechanisms—often represented as "menus" of lottery options—can be infinitely large and mathematically intractable.
Recent theoretical work by Hart and Nisan highlighted the potential for extreme complexity, showing that for correlated valuations, simple menus might capture only a negligible fraction of optimal revenue. This paper investigates the inverse: identifying the specific conditions under which simple, structured menus are actually optimal. By characterizing the structural properties of optimal mechanisms, we bridge the gap between theoretical complexity and practical implementation.
Methodology: Geometric Revenue Representation
The core of our analytical approach involves a geometric transformation of the revenue maximization problem. We define the power rate of a probability density function $h$ as $PR(h(x)) = \frac{xh'(x)}{h(x)}$. This metric serves as a primary tool for categorizing valuation distributions.
To analyze revenue, we utilize Green’s Theorem to represent expected revenue as a function of the buyer's utility $U(x, y)$. This allows us to visualize the optimal mechanism as a convex utility surface.
As shown in Figure 1, menu items can be visualized as planes (the red dashed lines) that touch the utility boundaries. The optimal utility function is the upper envelope of these planes. We employ semi-constructive proofs, fixing portions of the utility function and "rotating" these planes to ensure the resulting function satisfies incentive compatibility and maximizes revenue.
Structural Results
Our findings reveal a significant "phase transition" in the structure of optimal menus based on the power rates of the item distributions.
Part I: Monotone Menus
When the sum of the power rates of the two item distributions is less than or equal to -3, the optimal mechanism is guaranteed to have a monotone menu. In a monotone menu, a higher payment always corresponds to a simultaneous increase in the allocation probabilities for both items. This result is significant because it aligns with economic intuition—paying more should not result in receiving less of any item.
A key corollary of this finding is a new version of the revenue monotonicity theorem. We prove that in this regime, stochastically superior distributions (where the buyer is likely to value items more highly) always yield strictly more revenue for the seller. Furthermore, this theorem provides a unified framework that includes previous conditions for the optimality of bundling.
Part II: Small Menus
When the sum of power rates is greater than or equal to -3, the optimal mechanism simplifies in a different way: it requires only a few discrete menu items.
Figure 2 illustrates how the valuation space (the rectangle ABCD) is partitioned into regions where different menu options are chosen. For example, the region labeled (1,1) represents the buyer receiving both items, while (0,0) represents receiving neither. Our results bound the number of such regions:
- Power/Uniform Distributions: For distributions with constant power rates, the optimal menu contains at most 4 items.
- Exponential/Polynomial Distributions: For distributions with monotone power rates, the optimal menu contains at most 6 items.
- Unit-Demand Setting: For uniform distributions where the buyer wants at most one item, the optimal menu contains at most 5 items.
Conclusion and Future Work
This research demonstrates that for a wide class of independent distributions, the optimal mechanism for selling two items is remarkably simple. Whether through monotonicity or a small number of fixed options, sellers can often achieve maximum revenue without resorting to complex, infinite menus.
However, several challenges remain. Our current proofs are specifically tailored to the case of two items; extending these results to $k > 2$ items involves significantly more complex geometry. Additionally, while we have identified conditions for independence, the stark contrast with Hart and Nisan's results for correlated valuations suggests that the "simplicity" of optimal mechanisms is highly sensitive to the independence of buyer preferences. Future work will focus on generalizing these structural insights to broader classes of multi-dimensional mechanism design problems.
Summary updated