# Sample Complexity of Posted Pricing for a Single Item

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2024.

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

- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks](https://mlsanity.com/paper/2507.05084/) (2025)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets](https://mlsanity.com/paper/2409.03505/) (2024)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Gradient Descent with Provably Tuned Learning-rate Schedules](https://mlsanity.com/paper/2512.05084/) (2025)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)
- [Pessimistic Minimax Learning for Public-Private Information Games under Unilateral Coverage](https://mlsanity.com/paper/2610.04997/) (2026)

## Abstract (arXiv)

Selling a single item to n self-interested buyers is a fundamental problem in economics, where the two objectives typically considered are welfare maximization and revenue maximization. Since the optimal mechanisms are often impractical and do not work for sequential buyers, posted pricing mechanisms, where fixed prices are set for the item for different buyers, have emerged as a practical and effective alternative. This paper investigates how many samples are needed from buyers' value distributions to find near-optimal posted prices, considering both independent and correlated buyer distributions, and welfare versus revenue maximization. We obtain matching upper and lower bounds (up to logarithmic factors) on the sample complexity for all these settings.