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

Hedyeh Beyhaghi (), Negin Golrezaei (), Renato Paes Leme (), Martin Pál () and Balasubramanian Sivan ()
Additional contact information
Hedyeh Beyhaghi: Toyota Technological Institute at Chicago, Chicago, Illinois 60637-2803
Negin Golrezaei: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Renato Paes Leme: Google Research, New York, New York 10011
Martin Pál: Google Research, New York, New York 10011
Balasubramanian Sivan: Google Research, New York, New York 10011

Operations Research, 2021, vol. 69, issue 6, 1805-1822

Abstract: 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.

Keywords: posted-price mechanisms; eager second-price auctions; multiunit; position auction; online advertising (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2121 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:6:p:1805-1822

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().