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 $\mathcal{ C^*} \approx 2.62$, closing the gap between $\big[\frac{ e}{ e - 1}, e\big]$ 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{ \pi^2}{ 6} \approx 1.64$, closing the previously known bounds $\big[\frac{ e}{ e - 1}, e\big]$. 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, e\big]$. 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.
Categories: cs.GT