Abstract
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.
Time
2017-12-27 15:00 ~ 16:00Speaker
Yaonan Jin, Hong Kong University of Science and TechnologRoom
Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics
