2017-12-27 | Yaonan Jin：Tight Competitive Ratios among Simple Mechanisms
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 competitive ratios among these four mechanisms, which is defined as the largest relative revenue gap between 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/AP. This ratio studies the power of discrimination in auctions. Previously, the competitive ratio is known to be within [2, e], and the lower-bound of 2 is conjectured to be tight. We disprove this conjecture by a better lower-bound of 2.13.
Joint work with Pinyan Lu, Zhihao Gavin Tang and Tao Xiao.
Yaonan Jin is a first year MPhil student at Hong Kong University of Science and Technology, advised by Prof. Qi Qi. He graduate from Shanghai Jiao Tong University with a B.S. in Computer Science in 2017, where he had worked with Prof. Xiaotie Deng and Prof. Pinyan Lu.