Tight approximation ratio of anonymous pricing

DOI10.1145/3313276.3316331MaRDI QIDQ5212808zbMATH OpenOpenAlexFDO

Authors Yaonan Jin, Pinyan Lu, Qi Qi, Zhihao Gavin Tang, Tao Xiao

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.00763

zbMATH Keywords

anonymous pricingmathematical optimizationoptimal auctionrevenue maximizationtight bound

Mathematics Subject Classification ID

Mechanism design theory (91B03) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We consider two canonical Bayesian mechanism design settings. In the single-item setting, we prove tight approximation ratio for anonymous pricing: compared with Myerson Auction, it extracts at least $frac12.62$-fraction of revenue; there is a matching lower-bound example. In the unit-demand single-buyer setting, we prove tight approximation ratio between the simplest and optimal deterministic mechanisms: in terms of revenue, uniform pricing admits a $2.62$-approximation of item pricing; we further validate the tightness of this ratio. These results settle two open problems asked in~cite{H13,CD15,AHNPY15,L17,JLTX18}. As an implication, in the single-item setting: we improve the approximation ratio of the second-price auction with anonymous reserve to $2.62$, which breaks the state-of-the-art upper bound of $eapprox2.72$.

Recommendations

• Optimal auctions vs. anonymous pricing
• On the approximability of simple mechanisms for MHR distributions
• Tight revenue gaps among simple mechanisms
• Tight revenue gaps among simple mechanisms
• Optimal pricing for MHR distributions

Cited in

(9)

• Optimal pricing for MHR distributions
• Optimal auctions vs. anonymous pricing
• Anonymous auctions maximizing revenue
• Tight revenue gaps among multiunit mechanisms
• Tight revenue gaps among simple mechanisms
• Tight revenue gaps among simple mechanisms
• First price auction is 1-1/e^2 efficient
• q-partitioning valuations: exploring the space between subadditive and fractionally subadditive valuations
• On the approximability of simple mechanisms for MHR distributions

This page was built for publication: Tight approximation ratio of anonymous pricing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212808)