PaperlayerView exact revision on arXiv

Source-linked AI summary

Making the Most of Your Samples

Zhiyi Huang, Yishay Mansour, Tim Roughgarden

arXiv:1407.2479v2cs.GTcs.DS

TL;DR

The paper asks how a seller can price for a buyer whose valuation distribution is unknown but provides i.i.d. samples. It analyzes sample-based pricing and single-sample strategies, giving sample-complexity bounds and revenue guarantees for several distribution classes.

  • Problem

    How can a seller use samples from an unknown valuation distribution to choose a price that approaches the revenue of the monopoly price?

    Source: §1.1 · p. 2

  • Method

    The paper bounds the samples needed for near-optimal pricing across distribution classes and studies one-sample strategies, using distribution distinguishability for lower bounds.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Results

    For MHR distributions, m = Θ(ε^-3/2 log ε^-1) samples suffice, and a simple one-sample strategy guarantees 0.589 of maximum revenue.

    Source: §1.1 · p. 4, §3.1 · p. 7

  • Takeaways & Limitations

    The sample-based approach offers worst-case guarantees over distributions while approximating the strong benchmark of optimal expected revenue.

    Source: §1 · p. 2

    The best randomized one-sample strategy and the best use of a small number of samples remain future-work questions.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution $D$. The seller has "data"' about $D$ in the form of $m \ge 1$ i.i.d. samples, and the algorithmic challenge is to use these samples to obtain expected revenue as close as possible to what could be achieved with advance knowledge of $D$. Our first set of results quantifies the number of samples $m$ that are necessary and sufficient to obtain a $(1-\epsilon)$-approximation. For example, for an unknown distribution that satisfies the monotone hazard rate (MHR) condition, we prove that $\tilde{\Theta}(\epsilon^{-3/2})$ samples are necessary and sufficient. Remarkably, this is fewer samples than is necessary to accurately estimate the expected revenue obtained by even a single reserve price. We also prove essentially tight sample complexity bounds for regular distributions, bounded-support distributions, and a wide class of irregular distributions. Our lower bound approach borrows tools from differential privacy and information theory, and we believe it could find further applications in auction theory. Our second set of results considers the single-sample case. For regular distributions, we prove that no pricing strategy is better than $\tfrac{1}{2}$-approximate, and this is optimal by the Bulow-Klemperer theorem. For MHR distributions, we show how to do better: we give a simple pricing strategy that guarantees expected revenue at least $0.589$ times the maximum possible. We also prove that no pricing strategy achieves an approximation guarantee better than $\frac{e}{4} \approx .68$.

1 Introduction

The paper studies pricing from an unknown valuation distribution, using samples to bridge worst-case and known-distribution approaches. It quantifies the samples needed for near-optimal revenue and analyzes guarantees when only one sample is available.

1.1 Our Results

  • MHR pricing needs Ω(ε^-3/2) samples and O(ε^-3/2 log ε^-1) suffice; regular and [1,H]-supported distributions have ˜Θ(ε^-3) and ˜Θ(Hε^-2) sample complexity.These bounds target a (1−ε)-approximation; the paper also gives essentially tight bounds for distributions parameterized by sale probability at the monopoly price.Source: §1.1 · p. 3
  • With one sample, regular distributions admit no deterministic guarantee above 1/2, while MHR admits 0.589; no deterministic MHR strategy exceeds e/4, and no continuously differentiable one exceeds 0.677.For regular distributions, the strategy p(v)=v achieves the 1/2 guarantee.Source: §1.1 · pp. 3–4

1.2 A Few Technical Highlights

  • For MHR distributions, correlated revenue-estimation errors and strongly concave revenue curves help achieve near-optimal pricing with fewer samples than estimating one fixed price’s revenue accurately.The paper contrasts O(ε^-3/2 log ε^-1) samples for near-optimal pricing with approximately ε^-2 samples to estimate a fixed price’s expected revenue accurately.Source: §1.2 · p. 4
  • For MHR and regular distributions, no (1−ε)-pricing strategy exists with o(ε^-3/2) or o(ε^-3) samples, respectively; the lower bounds reduce pricing to distinguishing similar distributions.The construction uses differential-privacy methodology to create distributions with small KL divergence and disjoint sets of near-optimal prices, then applies Pinsker’s inequality.Source: §1.2 · p. 4
  • For irregular distributions, the R*_δ benchmark supports parameterized sample-complexity bounds without blanket restrictions such as regularity.R*_δ is the maximum expected revenue from a price that sells with probability at least δ; approximating it is equivalent to approximating optimal revenue when monopoly prices sell with probability at least δ across the distribution class.Source: §1.2 · pp. 4–5

1.3 Further Related Work

  • Cole and Roughgarden’s framework yields weaker bounds when specialized to these sample-complexity questions, and prior work had not established lower bounds or optimal single-sample guarantees for this problem.The specialization gives a lower bound of ε^-1/2 and an upper bound of ε^-c for a large constant c.Source: §1.3 · p. 5

2 Preliminaries

The preliminaries represent pricing revenue in quantile space and describe distribution classes through the shape of their revenue curves. For irregular distributions, they introduce a benchmark that restricts prices by their sale probability.

2 Preliminaries

  • The revenue curve R(q) = qv(q) gives revenue by quantile, where q is a reserve price’s sale probability and v(q) is its corresponding value.For regular distributions, R(q) is concave and reaches its maximum at the monopoly quantile q* where the virtual value is zero.Source: §2 · pp. 5–6
  • A distribution is regular when its revenue curve is concave; it is MHR when its hazard rate is nondecreasing.For MHR distributions, the optimal quantile satisfies q* ≥ 1/e.Source: §2 · p. 6
  • α-strong regularity interpolates between regularity and MHR, and some MHR properties extend to this class with different constants.For α-strongly regular distributions, q* ≥ α^(1/(1−α)).Source: §2 · p. 6
  • For irregular distributions, the benchmark R*δ is the best revenue among reserve prices with sale probability at least δ.The paper notes that parameterized sample complexity can depend on both ε and δ.Source: §2 · p. 6

3 Asymptotic Upper Bounds

The section gives empirical-reserve guarantees for MHR and α-strongly regular distributions, then extends the approach to sale-probability-restricted benchmarks and bounded support.

3.1 MHR Upper Bound

  • Θ(ε^-3/2 log ε^-1) samples make the empirical reserve (1−ε)-approximate for MHR distributions, with a matching lower bound up to a logarithmic factor.The proof uses the MHR distribution’s constant lower bound on optimal sale probability and quadratic revenue loss with quantile distance from the optimum.Source: §3.1 · p. 7

3.2 α-Strongly Regular Upper Bound

  • Θ(ε^-3/2 log ε^-1) samples make the empirical reserve (1−ε)-approximate for α-strongly regular distributions when α is a positive constant.The proof adapts the MHR argument using weaker versions of its sale-probability and revenue-curve properties.Source: §3.2 · p. 9

3.3 General Upper Bounds

  • A 2-guarded empirical reserve using Θ(δ^-1 ε^-2 log(δ^-1 ε^-1)) samples achieves (1−ε)R*δ for all distributions; one sample guarantees at least (δ/2)R*δ.R*δ is the optimal revenue among prices with sale probability at least δ.Source: §3.3 · p. 10
  • Θ(Hε^-2 log(Hε^-1)) samples make the empirical reserve (1−ε)-approximate for distributions supported in [1,H].This follows as a corollary of the general bound using R*δ.Source: §3.3 · p. 10

4 Asymptotic Lower Bounds

The lower-bound framework turns near-optimal pricing into a distribution-classification problem. Information-theoretic bounds on distinguishing similar distributions then yield pricing sample lower bounds.

4 Asymptotic Lower Bounds

  • The framework applies to all pricing strategies, including randomized ones, and gives asymptotically tight lower bounds up to a logarithmic factor.It first reduces pricing to classification, then instantiates the framework for distribution classes.Source: §4 · p. 10

4.1 Lower Bound Framework: Reducing Pricing to Classification

  • For m i.i.d. samples, KL divergence is additive: the divergence between the sample distributions is m times the one-sample divergence.This supports bounding how distinguishable the two sample distributions are.Source: §4.1 · p. 11
  • If two distributions have disjoint (1−3ε)-approximate price sets, a pricing algorithm that is (1−ε)-approximate for both induces a classifier that distinguishes them with probability at least 2/3.The classifier uses the pricing algorithm’s same number of samples.Source: §4.1 · p. 11
  • Such a pricing algorithm must use at least 4/[9(DKL(D1∥D2)+DKL(D2∥D1))] samples.The bound combines the classification reduction with an information-theoretic bound on distinguishing the distributions.Source: §4.1 · p. 11

A Tool for Constructing Distributions with Small KL Divergence

The section uses a differential-privacy result to construct distributions that are hard to distinguish, then applies the lower-bound framework to bounded-support, regular, and MHR pricing.

A Tool for Constructing Distributions with Small KL Divergence

  • A differential-privacy lemma provides a way to construct pairs of distributions with small KL divergence by keeping their densities close.The section also presents variants of the lemma, including one for distributions that agree on a subset of outcomes.Source: A Tool for Constructing Distributions… · pp. 11–12

4.2 Applications

  • For all distributions, every pricing algorithm guaranteeing at least (1−ε)R*δ revenue uses at least Ω(δ^-1 ε^-2) samples.Source: §4.2 · p. 12
  • Regular distributions require Ω(ε^-3) samples for (1−ε)-approximate pricing; the paper gives lower bounds of 12 samples for 95% and 1935 for 99% of optimal revenue.The regular-distribution construction uses two distributions with disjoint approximately optimal price sets.Source: §4.2 · pp. 13–14
  • MHR distributions require Ω(ε^-3/2) samples for (1−ε)-approximate pricing.The construction uses a uniform distribution on and a modified density that shifts probability between two value intervals.Source: §4.2 · p. 14

5 Single Sample Regime: Beating Identity Pricing for MHR Distributions

For MHR distributions, scaling the sampled value improves on identity pricing, with a 0.589 approximation guarantee. The intuition analyzes quantiles above and below the optimal reserve separately.

5 Single Sample Regime: Beating Identity Pricing for MHR Distributions

  • 0.589: pricing at 0.85 times the sampled value is approximate for MHR distributions.The section seeks a scaling factor that beats the 1/2 guarantee.Source: §5 · p. 15
  • For quantiles above the optimal reserve quantile, MHR revenue curves are at least as concave as the exponential curve, making identity pricing strictly better than 1/2 there.Scaling by c < 1 loses at most a factor of c, so a value sufficiently close to 1 preserves a guarantee above one half for this part.Source: §5 · p. 15
  • Below the optimal reserve quantile, an approximate point mass is a worst case for identity pricing, while scaling down slightly doubles its selling probability without much price reduction.This makes the expected revenue from this part strictly better than half the optimum.Source: §5 · p. 15

6 Single Sample Negative Results

For regular distributions, identity pricing is optimal among deterministic one-sample strategies and achieves a 1/2 approximation. For MHR distributions, the section gives upper limits on what deterministic strategies can guarantee.

6 Single Sample Negative Results

  • No deterministic one-sample strategy exceeds a 1/2 approximation for regular distributions.Identity pricing is an optimal deterministic strategy for this class.Source: §6 · p. 15
  • No continuously differentiable one-sample pricing strategy exceeds a 0.677 approximation for MHR distributions.The proof considers exponential and truncated exponential distributions; the truncation approximates a point mass and forces scaling down, while scaling too much hurts revenue on the exponential distribution.Source: §6 · pp. 15–16
  • No deterministic one-sample strategy exceeds an e/4 ≈ 0.68 approximation for MHR distributions.The proof considers a distribution over exponential distributions and identifies identity pricing as the best response for that distribution of instances.Source: §6 · p. 16

A Missing Proofs from Section 3

The proof uses a deviation bound for the number of samples in a quantile interval and applies a Chernoff bound to control the probability of that event.

A Missing Proofs from Section 3

  • The proof gives lower bounds on q_i and q̃_i and on Δ in terms of α and δ.It states q_i, q̃_i = Ω(α^(1/(1−α))) and Δ ≥ Ω(αδ^2).Source: A Missing Proofs from Section 3 · p. 17
  • The count of samples between q1 and q2 differs from its expectation by at least Ω(α^(1/(1−α))Δm); a Chernoff bound controls the probability of this event.With the proof's choice of m, the probability is stated to be exp(−Ω(log ε^-1)) = o(1/m^2).Source: A Missing Proofs from Section 3 · p. 18

B Missing Proofs from Section 4

The appendix supplies missing proofs from Section 4. In the proof of Theorem 4.12, it compares constructed revenue curves and establishes disjoint sets of near-optimal prices.

B Missing Proofs from Section 4

  • The proof of Lemma 4.3 proceeds from the definition of KL divergence.The supplied passage introduces the calculation but does not state its ensuing expression.Source: B Missing Proofs from Section 4 · p. 18

B.1 Proof of Theorem 4.12

  • For D1, the revenue curve R1(q) = q(2 − q) peaks at q = 1 with revenue 1.The proof uses Figure 2 to summarize the revenue curves of D1 and D2.Source: §B.1 · p. 18
  • For D2, the stated optimum is at q = 1 − √ε0 + 2ε0, with revenue 1 + ε0 + 2ε0^(3/2); the (1−3ε)-optimal price sets of D1 and D2 are disjoint.The proof derives the disjointness from its construction of the two distributions.Source: §B.1 · pp. 18–19

C Missing Proofs from Section 5

The appendix establishes that identity pricing can approach only a 1/2 approximation on MHR distributions, then develops exponential-distribution comparisons to bound expected revenue across quantile ranges.

C.1 Lower Bound for Identity Pricing

  • As ε approaches zero, identity pricing on MHR distributions approaches a 1/2 approximation ratio.The lower-bound example uses a uniform distribution over [1 − ε, 1].Source: §C.1 · p. 19

C.2 Proof of Theorem 5.1

  • The proof normalizes the candidate and exponential distributions to have matching value and revenue at quantile q*, then compares their revenue curves.The stated normalization sets v(q*) = vexp(q*) and R(q*) = Rexp(q*).Source: §C.2 · p. 19

Technical Lemmas about MHR Distributions

  • For quantiles q ≥ q*, the exponential distribution has revenue no greater than any MHR distribution with the same revenue at q*; the comparison does not extend below q*.The limitation below q* arises because the proof may encounter q1 = 0, producing a zero-divided-by-zero issue.Source: Technical Lemmas about MHR Distributions · pp. 19–20

Expected Revenue of Large Quantiles

  • For q ≥ q*, the expected revenue under the candidate pricing rule is at least its value for the exponential distribution.The appendix uses the exponential distribution as the worst-case comparison for this quantile range.Source: Expected Revenue of Large Quantiles · p. 20

Expected Revenue of Small Quantiles

  • For smaller quantiles, the proof splits the range at q0 and uses an inductive bound based on revenue-curve concavity and the higher sale probability of lower reserve prices.The appendix also evaluates the resulting function at its extrema, reporting a minimum near x = 0.546 and a boundary value of 0.85.Source: Expected Revenue of Small Quantiles · pp. 21–22

Proof of Theorem 5.1

The proof bounds the pricing strategy’s performance through a function of c. At c = 0.85, its minimum value is at least 0.589.

Proof of Theorem 5.1

  • At c = 0.85, the analyzed function has minimum value at least 0.589, establishing the lemma’s revenue bound.The minimum occurs at a root between x = 0.544 and x = 0.545.Source: Proof of Theorem 5.1 · p. 23

D Missing Proofs in 6

The appendix tests pricing rules against point-mass, exponential, and truncated-exponential distributions. It derives bounds for linear and continuously differentiable rules and analyzes a distribution over exponential distributions.

Proof of Theorem 6.1

  • Any deterministic pricing rule with a non-trivial approximation on a point mass must satisfy p(v) ≤ v; on the second considered distribution, identity pricing is at least as good as any such rule.Identity pricing is 2-approximate for that second distribution.Source: D Missing Proofs in 6 · p. 23

Linear Pricing Functions

  • No scaling parameter c achieves better than a 0.67 approximation on both exponential and truncated-exponential distributions.The truncation is used as an approximation to a point mass and forces the scaling trade-off described in the passage.Source: D Missing Proofs in 6 · p. 23

Exponential Distribution

  • For linear pricing b(v) = cv, the exponential-distribution approximation ratio is c/(c + 1)^2.The passage compares this ratio with the exponential distribution’s optimal revenue.Source: D Missing Proofs in 6 · p. 24

Truncated Exponential Distribution

  • The truncated-exponential construction sets q* = 0.43 and α = 0.74, with revenue maximized at q* and optimal revenue q*.It replaces values above the truncation threshold with a uniform distribution over [1, 1 + α].Source: D Missing Proofs in 6 · p. 24

Continuously Differentiable Pricing Functions

  • The linear-pricing bound extends to continuously differentiable pricing functions by approximating them near zero with a linear function; the reported upper bound is about 0.6762.The bound is obtained by numerically maximizing over c in [0.878, 1].Source: D Missing Proofs in 6 · p. 25

Proof of Theorem 6.3

  • For a distribution over exponential value distributions, the best response subject to p(v) ≤ v is identity pricing, whose approximation ratio is at most e/4 ≈ 0.68.For each λ, the passage gives optimal revenue 1/(eλ) and identity-pricing revenue 1/(4λ).Source: D Missing Proofs in 6 · pp. 25–26
Loading 1407.2479v2…