Tight Revenue Gaps among Multi-Unit Mechanisms

Yaonan Jin, Shunhua Jiang, Pinyan Lu, Hengjie Zhang

Introduction

In Bayesian mechanism design, Myerson’s Auction is the gold standard for revenue maximization. However, its complexity and perceived unfairness often limit its real-world application. Sellers typically prefer simpler mechanisms like Anonymous Pricing (a single price for all) or Sequential Posted Pricing (different prices offered to buyers sequentially). A central question in algorithmic game theory is the "revenue gap": the ratio of revenue between an optimal mechanism and a simpler one. While these gaps were well-understood for single-item sales ($k=1$), they remained an open problem for multi-unit settings ($k > 1$).

Revenue gaps for the single-item ($k=1$) case, illustrating established constants and bounds.

The Multi-Unit Setting

This paper provides a definitive mapping of revenue gaps for the $k$-unit setting, where a seller has $k$ identical items to sell to $n$ unit-demand buyers. The authors categorize mechanisms into two primary groups: Discriminating (e.g., Myerson Auction, Sequential Posted Pricing) and Anonymous (e.g., Anonymous Pricing, Anonymous Reserve).

Methodological Innovations

To establish tight asymptotic bounds, the authors utilize a combination of mathematical programming and probability theory:

  • Bernoulli Sum Lemma: A new structural lemma for Poisson binomial distributions that allows for the comparison of sums of independent, non-identical Bernoulli trials.
  • Ex-Ante Relaxation (EAR): A theoretical benchmark used to prove upper bounds for discriminating mechanisms by comparing them against an easier-to-analyze relaxation of the Myerson revenue.
  • Triangle Distributions: A specific class of regular distributions used to construct lower-bound examples, proving the gaps are asymptotically tight.

Key Results: The Power of Discrimination

The paper reveals a fundamental "Hierarchy of Simplicity." The most significant finding is the divide between discriminating and anonymous schemes. While the advantage of an auction over simple pricing vanishes as the number of items increases (at a rate of $1 + \Theta(1/\sqrt{k})$), the power to price-discriminate offers a massive revenue boost of $\Theta(\log k)$ over anonymous schemes.

Asymptotic revenue gaps in the $k$-unit setting, highlighting the $\Theta(\log k)$ gap between discriminating and anonymous mechanisms.

Specifically, the authors establish the following gaps for the $k$-unit case:

  • Auctions vs. Pricing: The gap between an Optimal Auction and Discriminating Pricing (and similarly between an Anonymous Auction and Anonymous Pricing) is $1 + \Theta(1/\sqrt{k})$. As markets scale, a well-chosen price becomes nearly as effective as a complex auction.
  • Discriminating vs. Anonymous: Any comparison between a discriminating mechanism and an anonymous one results in a gap of $\Theta(\log k)$.
  • Matroid Constraints: For more complex constraints beyond simple item counts, the gap between even the simplest auction and pricing becomes $\Omega(\log k)$.

Conclusion

These results provide a theoretical foundation for observed market behaviors. In high-volume retail, complex auctions are rare because their marginal benefit over pricing decreases as $k$ grows. However, the significant $\Theta(\log k)$ advantage of discrimination explains the heavy investment in personalized pricing strategies like coupons and loyalty programs. Future research may explore these gaps under "irregular" distribution assumptions or further close the constants for the single-item case.

Summary updated

BibTeX
@inproceedings{jin2021tight,
  author = {Yaonan Jin and Shunhua Jiang and Pinyan Lu and Hengjie Zhang},
  title = {{Tight Revenue Gaps among Multi-Unit Mechanisms}},
  booktitle = {EC},
  year = {2021},
  doi = {10.1145/3465456.3467621},
}
Figure