@inproceedings{
jin2024sample,
title={Sample Complexity of Posted Pricing for a Single Item},
author={Billy Jin and Thomas Kesselheim and Will Ma and Sahil Singla},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=EK1tyHcb3W}
}
Selling a single item to $n$ self-interested bidders is a fundamental problem in economics, where the two  objectives  typically considered are welfare maximization and revenue maximization.   Since the optimal auctions are often impractical and do not work for sequential bidders, posted pricing auctions, where fixed prices are set for the item for different bidders, have emerged as a practical and effective alternative. This paper investigates how many samples are needed from bidders' value distributions to find near-optimal posted prices, considering both independent and correlated bidder distributions, and welfare versus revenue maximization.  We obtain matching upper and lower bounds (up to logarithmic terms) on the sample complexity for all these settings.
Sample Complexity of Posted Pricing for a Single Item
Billy Jin Thomas Kesselheim Will Ma Sahil Singla