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

arXiv: https://arxiv.org/abs/1807.03435 · HTML: https://mlsanity.com/paper/1807.03435/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2018.

## Built on by (most cited first, 3 of 3)

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [The Competition Complexity of Prophet Inequalities with Correlations](https://mlsanity.com/paper/2409.06868/) (2024)

## Abstract (arXiv)

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 mchanism, 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 (Azar, Chiplunkar & Kaplan, 2018). In the multi-unit setting, our SPP mechanism yields the first improved approximation factor over the state of the art after over nine years (Yan, 2011 and Chakraborty et al., 2010). 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 (ESP) 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.