Research map / Learning theory and algorithms / Submodular and game algorithms
Sample Complexity of Posted Pricing for a Single Item
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Determines sample complexity of posted pricing for a single item across welfare/revenue objectives and independent/correlated buyer distributions, giving matching (up to logs) upper and lower bounds.
Problem
How many IID samples of buyer value distributions are needed to learn near-optimal posted prices for selling a single item to n buyers, for welfare vs. revenue and product vs. correlated distributions?
Approach
For product distributions, welfare sample complexity is independent of n via a martingale/Freedman analysis of the empirical dynamic program, while revenue needs Omega(n/eps^2). For correlated distributions, pseudo-dimension of change-point-restricted policy classes gives O(|S| log|S|) bounds, matched by lower bounds.
Key results
- For product distributions, welfare maximization via posted pricing has sample complexity O(1/eps^2 * log^2(1/delta)), independent of number of buyers n.
- For product distributions, revenue maximization requires Omega(n/eps^2) samples, tight up to log factors versus the known O~(n/eps^2) upper bound.
- For correlated distributions with change-points S, sample complexity is O((1+|S|)log(1+|S|)+log(1/delta))/eps^2) and matching lower bound Omega((1+|S|)/eps^2) holds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the optimal policy learned from product empirical distributions for welfare pricing | Posted pricing with independent buyer values · Product distributions, welfare | sample complexity: O(1/ε^2 · log^2(1/δ)) | Helped |
| Optimize revenue rather than welfare with independent buyer values | Posted pricing · Product distributions, revenue | sample complexity: Ω(n/ε^2) | Hurt |
| Allow correlated rather than independent buyer values for welfare pricing | Posted pricing · Correlated distributions, welfare | sample complexity: Ω(n/ε^2) | Hurt |
| Restrict prices to change only at the specified change-points S | Posted pricing for correlated buyer values · Correlated distributions, welfare | sample complexity: O(((1+|S|)log(1+|S|) + log(1/δ))/ε^2) | Helped |
| Restrict prices to change only at the specified change-points S | Posted pricing for correlated buyer values · Correlated distributions, revenue | sample complexity: O(((1+|S|)log(1+|S|) + log(1/δ))/ε^2) | Helped |
Surprising findings
- Welfare maximization for product distributions needs no dependence on n, unlike revenue maximization, showing a separation between the two objectives.
- For correlated distributions, the linear-in-n dependence is needed even for welfare maximization.
Limitations
- Correlated-case SAA runtime is exponential in |S| (polynomial in T and n with exponent 1+|S|).
- Upper and lower bounds match only up to logarithmic factors.
- Results are theoretical with no empirical evaluation.
Experimental setup
Metrics: sample complexity additive approximation error
Baselines: Guo et al. O(n/eps^2) bound Balcan et al. O(n/eps^2) bound for correlated posted pricing
Builds on: Freedman's inequality Guo et al. sample complexity for revenue maximization pseudo-dimension piecewise decomposable bounds (Balcan et al.) Myerson optimal auction prophet inequality
Closest papers by meaning
- Learning Optimal Auctions with Correlated Valuations from Samples (ICML 2021 · similarity 0.90)
- Optimal Pricing in Repeated Posted-Price Auctions with Different Patience of the Seller and the Buyer (NeurIPS 2019 · similarity 0.90)
- Posted Pricing and Dynamic Prior-independent Mechanisms with Value Maximizers (NeurIPS 2022 · similarity 0.89)
- Optimal Auction Design for Mixed Bidders (AAAI 2025 · similarity 0.87)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (AAAI 2025 · similarity 0.86)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.