Tight Revenue Gaps among Simple Mechanisms
share
We consider the simplest and most fundamental problem of selling a single item to a number of buyers whose values are drawn from known independent and regular distributions. There are four most widely-used and widely-studied mechanisms in this literature: Anonymous Posted-Pricing (AP), Second-Price Auction with Anonymous Reserve (AR), Sequential Posted-Pricing (SPM), and Myerson Auction (OPT). Myerson Auction is optimal but complicated, which also suffers a few issues in practice such as fairness; AP is the simplest one but its revenue is also the lowest among these four; AR and SPM are of intermediate complexity and revenue. We study the revenue gaps among these four mechanisms, which is defined as the largest ratio between revenues from two mechanisms. We establish two tight ratios and one tighter bound: 1. SPM/AP. This ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of roughly 2.62, closing the previous known bounds [e / (e - 1), e]. 2. AR/AP. This ratio studies the relative power of auction vs. pricing schemes, when no discrimination is allowed. We get the tight ratio of π^2 / 6 ≈ 1.64, closing the previous known bounds [e / (e - 1), e]. 3. OPT/AR. This ratio studies the power of discrimination in auctions. Previously, the revenue gap is known to be in interval [2, e], and the lower-bound of 2 is conjectured to be tight HR09,H13,AHNPY15. We disprove this conjecture by obtaining a better lower-bound of 2.15.
READ FULL TEXT