Improved Revenue Bounds for Posted-Price and Second-rice Mechanisms

• 成果类型: Article
• 署名作者: Beyhaghi, Hedyeh; Golrezaei, Negin; Leme, Renato Paes; Pai, Martin; Sivan, Balasubramanian
• 署名单位: Toyota Technological Institute - Chicago; Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2121
• 发表日期: 2021
• 页码: 1805-1822
• 关键词: auction

摘要

We study revenue maximization through sequential posted-price (SPP) mechanisms in single-dimensional settings with n buyers and independent but not necessarily identical value distributions. We construct the SPP mechanisms by considering the best of two simple pricing rules: one that imitates the revenue optimal mechanism, namely, the Myersonian mechanism, via the taxation principle and the other that posts a uniform price. Our pricing rules are rather generalizable and yield the first improvement over long established approximation factors in several settings. We design factor-revealing mathematical programs that crisply capture the approximation factor of our SPP mechanism. In the single-unit setting, our SPP mechanism yields a better approximation factor than the state of the art prior to our work. In the multiunit setting, our SPP mechanism yields the first improved approximation factor over the state of the art after over nine years. Our results on SPP mechanisms immediately imply improved performance guarantees for the equivalent free-order prophet inequality problem. In the position auction setting, our SPP mechanism yields the first higher-than (1 -1=e) approximation factor. In eager second-price auctions, our two simple pricing rules lead to the first improved approximation factor that is strictly greater than what is obtained by the SPP mechanism in the single-unit setting.