Tight Revenue Gaps among Simple Mechanisms

We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independent and regular (not necessarily identical) distributions. There are four widely-used and widely-studied mechanisms in the literature: sf Myerson Auction~(sf OPT), sf Sequential Posted-Pricing~(sf SPM), sf Second-Price Auction with Anonymous Reserve~(sf AR), and sf Anonymous Pricing~(sf AP). sf OPT is revenue-optimal but complicated, which also experiences several issues in practice such as fairness; sf AP is the simplest mechanism, but also generates the lowest revenue among these four mechanisms; sf SPM and sf AR are of intermediate complexity and revenue. We explore revenue gaps among these mechanisms, each of which is defined as the largest ratio between revenues from a pair of mechanisms. We establish two tight bounds and one improved bound: 1. sf SPM vs. sf AP: this ratio studies the power of discrimination in pricing schemes. We obtain the tight ratio of C^* ≈ 2.62, closing the gap between big[fracee - 1, ebig] left before. 2. sf AR vs. sf AP: this ratio measures the relative power of auction scheme vs. pricing scheme, when no discrimination is allowed. We attain the tight ratio of fracπ26 ≈ 1.64, closing the previously known bounds big[fracee - 1, ebig]. 3. sf OPT vs. sf AR: this ratio quantifies the power of discrimination in auction schemes, and is previously known to be somewhere between big[2, ebig]. The lower-bound of 2 was conjectured to be tight by Hartline and Roughgarden (2009) and Alaei et al. (2015). We acquire a better lower-bound of 2.15, and thus disprove this conjecture.