The Sample Complexity of Auctions with Side Information

1 Introduction

• ERM improves the non-identical independent-distribution upper bound from ˜O(n10ϵ−7) to ˜O(nϵ−4).The approach discretizes values with limited revenue loss, bounds the candidate mechanism class, and uses concentration to compare sample and true revenue.Source: §1 · pp. 3–4
• The signals model draws each bidder’s value and signal jointly, with the signal observed by the auctioneer and only the value misreportable.The signal is a real number in [0, 1] and captures side information such as income or ad click-through rate.Source: §1 · p. 3
• For the signals model, interpolation is needed because samples may not contain the participants’ exact signals; the method uses samples just below each actual signal and an empirical Myerson auction.The bounds depend on q(ϵ), the fraction of signals contributing an ϵ fraction of revenue.Source: §1 · p. 4
• The paper proves that an optimal auction’s revenue does not decrease when its component distributions are replaced by higher distributions in the componentwise first-order stochastic dominance order.The proof uses an amortization argument that couples auction revenues by quantiles.Source: §1 · p. 5
• The lower-bound construction packs scaled copies of instances from Huang et al. across signal conditionals and yields an Ω(ϵ−3) sample requirement.The reduction argues that high overall revenue requires high revenue in most conditionals.Source: §1 · p. 5

1.2 Future Directions

• The paper also extends its results to more general single-parameter environments and to smaller auction classes such as VCG with reserve prices.These extensions are discussed in Section 8.Source: §1 · p. 5

1.1 Other Related Work

• Related work includes sample-complexity bounds for MHR distributions and a multi-parameter exponential lower bound; ad-auction practice also maps features into categories or continuous variables.The paper identifies high-dimensional signals, prior-independent mechanisms, and market-size questions as future directions.Source: §1.1 · pp. 5–6, §1.2 · p. 6

2.1 Single Parameter Revenue Maximization

• The feasible set X specifies allowable allocations, with each coordinate x_i giving bidder i’s probability of receiving an item.The paper considers single-item, matroid, and arbitrary downward-closed feasibility; results apply to single-item settings, while broader coverage varies by theorem.Source: §2.1 · pp. 6–7
• The Myerson model uses product value distributions, and the paper’s sample-based mechanism design considers only dominant-strategy incentive-compatible and individually rational mechanisms.The paper denotes a mechanism’s expected revenue under distribution D by Rev(M, D).Source: §2.1 · p. 7
• Myerson’s optimal auction maximizes ironed virtual welfare, allocating to feasible bidders with the highest ironed virtual values and charging winners their minimum winning bids.For regular distributions, virtual values are monotone and need not be ironed.Source: §2.1 · pp. 7–8

2.2 Myerson Model

• The auctioneer learns from i.i.d. value samples, then runs a mechanism on a fresh value profile drawn from the unknown distribution.Sample complexity is the smallest sample count that guarantees the specified approximation across the distribution class; positive results achieve it with high probability.Source: §2.2 · p. 8

2.3 Signals Model

• The signals model draws each bidder’s value and signal i.i.d. from a joint distribution, with higher signals assumed to imply first-order stochastically dominating conditional value distributions.The mechanism observes the actual signals as well as reported values.Source: §2.3 · pp. 8–9
• In the signals model, the auctioneer uses i.i.d. value-signal samples to design an auction tailored to the fresh bidders’ realized signals.The sample requirement targets a 1 − ϵ fraction of the optimal signals-model revenue.Source: §2.3 · p. 9

3.1 Sample Complexity: Regular Distributions

• ˜O(nϵ−4) is an upper bound for learning revenue-optimal auctions with non-i.i.d. regular value distributions.This reduces the earlier upper bound of ˜O(n10ϵ−7) from Cole and Roughgarden [8].Source: §3.1 · p. 9

3.2 Sample Complexity: Beyond Regular Distributions and a Single Item

• For bounded-support [1, h] distributions, the bounds are ˜O(nhϵ−3), and for MHR distributions they are ˜O(n/ϵ3), with constructive, computationally efficient results.The corresponding bounds from Morgenstern and Roughgarden are not computationally efficient.Source: §3.2 · pp. 9–10

3.3 Signals Model

• For a single bidder in the signals model, the upper bound is ˜O(q(ϵ)−1ϵ−3) and the lower bound is Ω(ϵ−4 log(q(ϵ)−1)).The bounds depend on q(ϵ), defined through the revenue loss from ignoring the top q(ϵ) signal quantiles.Source: §3.3 · p. 11
• For multiple bidders in the signals model, the paper gives an upper bound but no lower bound, and notes that more agents might help.The section identifies closing the gap or parameterizing bounds with other quantities as open questions.Source: §3.3 · p. 11

3.4 Strong Revenue Monotonicity

• In matroid single-parameter settings, an optimal auction for a product distribution retains the strong revenue-monotonicity property when run under a componentwise stochastically dominating distribution.Source: §3.4 · p. 11

3.5 Concentration Inequality for Product Distributions

• The product-distribution concentration inequality compares a mechanism’s revenue under the true product distribution with revenue under its product empirical distribution.The proof uses Bernstein rather than Chernoff concentration to improve the bound when the expectation is small relative to the maximum support value.Source: §3.5 · p. 12

3.6 Organization of the Proofs

• The proof sections establish the monotonicity and concentration lemmas before analyzing single-item bounds, signals, and broader single-parameter environments.Source: §3.6 · p. 12

4 Proof of Strong Revenue Monotonicity

• The revised proof establishes strong revenue monotonicity for general distributions and matroid constraints, beyond the original version’s discrete-support and single-item setting.The paper notes that the original conference proof had a subtle bug.Source: §4 · p. 12

4.1 Ironed Virtual Value

• The ironed virtual value is the slope of the convex hull of the revenue curve, which represents maximum revenue from randomized prices at a given sale probability.For continuous distributions, revenue at quantile q is R(q) = q · v(q).Source: §4.1 · pp. 13–14

4.2 Simplifications

• The proof restricts both distributions’ supports to revenue-curve convex-hull points, making bD regular while D may remain irregular.This lets the auction be interpreted as rounding values down to the closest such point before selecting a winner.Source: §4.2 · p. 14

4.3 Failing Strategies

• Direct payment comparisons fail because price discrimination can leave a newly winning bidder paying less, while virtual-value amortization fails because stochastic dominance need not imply virtual-value dominance.The virtual-value comparison can also fail when the auction selects different winners across the two profiles.Source: §4.3 · pp. 15–16

4.4.1 Our Amortization

• The proof uses nonnegative amortized gains that upper-bound expected revenue for each distribution and compare pointwise for common winners; matroid exchanges handle differing winner sets.The argument also establishes that D has at least as many winners as bD for each quantile profile.Source: §4.4.1 · pp. 16–17

4.4.2 Construction of the Amortized Gain Functions

• For fixed other bidders’ quantiles, the construction sets ˆg to the bD virtual value and, when θ_i ≤ ˆθ_i, sets g_i to that same virtual value, satisfying the comparison with equality.Thresholds identify the quantiles below which bidder i wins; the construction of g is organized by the order of the thresholds.Source: §4.4.2 · pp. 18–20
• The amortized gain curve follows bR_i until it meets a line of slope v*_i, then follows that line to R_i at θ_i.The construction is intended to satisfy three properties: meeting R_i at θ_i, having slope at least that of bR_i up to θhat_i, and meeting the winner-threshold slope condition between θhat_i and θ_i.Source: §4.4.2 · pp. 20–22
• The threshold quantile θ*_i is no greater than θhat_i(q_-i), because coordinate-wise larger competing values weakly raise i’s winning threshold.The proof compares the thresholds against the original and dominated value profiles, then uses their quantiles in bD_i.Source: §4.4.2 · p. 21
• The construction verifies the required inequalities by equality for property (a), the curve’s slope for property (b), and virtual-value maximization for property (c).For property (b), the proof separates the interval at θ*_i; for property (c), it considers θhat_i(q_-i) < q_i ≤ θ_i(q_-i).Source: §4.4.2 · pp. 21–22

• Independent random permutations pair the coordinate samples into vectors that are i.i.d. from the product distribution, though the vectors are correlated when the samples are fixed.Source: §5 · p. 22
• The proof bounds the difference between expectations under the product empirical distribution and the true distribution through a sequence of inequalities.It invokes Bernstein’s inequality and later Markov’s inequality in the proof.Source: §5 · pp. 22–23

• For finite support V within [0, h], Algorithm 1 constructs an empirical Myerson auction for an additive approximation target.The construction serves as a building block for analyses of other distribution classes.Source: §6.1 · p. 23
• Under the theorem’s finite-support and parameter conditions, the learned auction achieves expected revenue of at least Opt−β on the true distribution.The analysis uses concentration and union bounds; its parameters are analysis-only and need not be known by the algorithm.Source: §6.1 · pp. 23–24
• The algorithm uses m i.i.d. value-profile samples to form each bidder’s empirical distribution and outputs the Myerson auction for their product.For bids unseen in the samples, it rounds down to the closest sample.Source: §6.1 · p. 24

6.2 Bounded-support Distributions: Additive Approximation

• The algorithm learns a mechanism with additive revenue loss at most ϵ from m samples when values have bounded support in [0,h].The theorem passage does not include the sample-count formula.Source: §6.2 · p. 24
• The construction samples each bidder’s original value within the rounded-value interval, applies the optimal mechanism’s allocation, and charges threshold payments to ensure truthfulness.For every realization of its random bits, the allocation is a 0-1 step function in each bidder’s value, making the resulting mechanism DSIC.Source: §6.2 · p. 25
• Rounding each winner’s threshold payment down changes it by at most δ, so with at most k winners the revenue difference is bounded by kδ.The payment comparison follows from coupling the original and rounded valuation profiles.Source: §6.2 · p. 25
• Rounding each value down to a multiple of δ yields a finite support of size O(h/ϵ), while the discretization lemma bounds the optimal-revenue loss additively.The section sets δ = O(ϵ) for its bounded-support additive-approximation result.Source: §6.2 · pp. 24–25

6.3 Bounded-support Distributions: Multiplicative Bound

• Rounding values down to powers of 1+δ gives a finite-support reduction and supports a mechanism whose revenue is at least a 1−ϵ fraction of optimal.The theorem applies to value distributions with bounded support in [1,h].Source: §6.3 · pp. 26–27
• The multiplicative discretization lemma states that rounding values down to powers of 1+δ loses at most a 1−δ multiplicative factor in optimal revenue.The lemma is stated for product value distributions and also applies to single-parameter problems.Source: §6.3 · p. 26
• The mechanism samples each original value from the interval corresponding to its rounded report, applies the optimal allocation, and charges winner threshold payments.The resulting mechanism is DSIC for every realization of its random bits.Source: §6.3 · pp. 26–27
• Rounding threshold payments down to powers of 1+δ makes the two mechanisms’ payments differ by at most a factor of (1+δ)−1 ≥ 1−δ.The comparison couples valuations from the original and rounded distributions while preserving the allocation.Source: §6.3 · p. 27

6.4 Regular Distributions

• Truncating regular distributions at a sufficiently high finite value addresses unbounded support while losing little revenue; the truncation lemma also holds in downward-closed settings.The lemma’s proof is deferred to Subsection 6.4.3.Source: §6.4 · p. 28

Analysis Assuming Opt

• With Opt known, truncating high values and rounding low and geometric values creates a discretized distribution for empirical learning while preserving the revenue guarantee.The analysis establishes the desired sample-complexity bound after these transformations.Source: Analysis Assuming Opt · p. 28

6.4.1 Estimating the Optimal Revenue

• A bootstrapping algorithm estimates Opt using separate sales with n item copies and VCG with two copies of each bidder; their optimal revenues are respectively an n-approximation and a 2-approximation.The resulting constant-factor estimate is used to instantiate the regular-distribution sample-complexity analysis.Source: Analysis Assuming Opt · p. 28, §6.4.1 · p. 29

6.4.2 Sample Complexity Upper Bound

• For regular distributions, the algorithm has a ˜O(nϵ−4) sample-complexity upper bound; Theorem 6.9 states Algorithm 5 learns a mechanism with probability at least 1 −γ when m meets the stated threshold.Source: Analysis Assuming Opt · p. 28, §6.4.2 · p. 31

6.4.3 Proof of Lemma 6.6

• The truncation proof handles multiple bidders by charging the extra revenue from multiple values above the cutoff to the case with a single such value, since truncations are rare.The proof is stated for arbitrary downward-closed problems; the supplied passage does not include the full quantitative bounds.Source: §6.4.3 · p. 32
• For regular D and D̄, the proof uses Myerson’s auction, whose revenue is virtual welfare, and partitions quantile profiles by whether any bidder has a high value.It upper-bounds the optimal revenue by allowing separate feasible winner sets for bidders above and below the threshold.Source: §6.4.3 · pp. 33–34
• Regularity makes the single-bidder reserve-revenue function concave, yielding R_i(q̄_i) ≥ (1 − q̄_i) max_{q∈[0,q̄_i]} R_i(q).The proof then uses q̄_i ≤ δ to establish the inequality.Source: §6.4.3 · p. 35
• A hybrid argument compares integration over the full quantile space with integration where every bidder’s quantile exceeds its threshold, bounding the difference by a factor of 1 − 2δ.The argument changes one bidder’s quantile threshold at a time and uses the resulting inclusion of eligible bidder sets.Source: §6.4.3 · p. 35

6.5 MHR Distributions

• The MHR algorithm is nearly identical to the regular-distribution algorithm, with a better tail bound supplied by the MHR assumption.The section cites an extreme-value theorem by Cai and Daskalakis.Source: §6.5 · pp. 35–36
• The algorithm truncates values above a chosen threshold and rounds values below δApx down to zero before discretizing the remaining values.The truncation threshold is selected using a tail bound associated with the MHR assumption.Source: §6.5 · pp. 35–36
• The section gives a sample-complexity upper bound for learning a 1−ϵ revenue approximation when values are MHR-distributed.The theorem’s sample-count expression is not present in the supplied passage.Source: §6.5 · pp. 35–36
• After rounding the truncated values down to powers of 1+δ, the algorithm applies the empirical Myerson auction to the resulting finite support.The analysis uses the multiplicative discretization lemma and a high-probability guarantee for the resulting mechanism.Source: §6.5 · pp. 36–37

7.1 Single Bidder Upper Bound

• Algorithm 7 addresses scarce same-signal samples by pricing from nearby lower-signal values, achieving a 1−O(ϵ) approximation for regular, q-bounded distributions with sufficient samples.It mixes distributions associated with signals just below the bidder’s signal and posts an ϵ-guarded empirical price, while guarding against too few values.Source: §7.1 · p. 37

7.1.1 The Analysis in an Idealized World

• Under an idealization with one sample per signal and a uniform signal distribution, the analysis obtains a 1−4ϵ approximation in expected revenue.The proof compares against a nearby lower-signal distribution and uses q-boundedness to control the contribution of dropped signals.Source: §7.1.1 · pp. 38, 40

7.1.2 Proof of Theorem 7.1

• Without the idealized signal assumption, a three-stage argument still gives Algorithm 7 a 1−4ϵ approximation in expectation.The proof uses q-boundedness to limit the revenue contribution of the dropped signal mass.Source: §7.1.2 · pp. 40–41

7.2 Multiple Bidders

• For multiple bidders, Theorem 7.5 establishes a sample-complexity upper bound for regular distributions with q-bounded tails in the signal space.The supplied passage does not include the bound's expression.Source: §7.2 · p. 41

7.2.1 Algorithm

• For each bidder, the multi-bidder algorithm uses values from signals closest below that bidder’s signal and runs preconditioned empirical Myerson on rounded values.The mixture of regular distributions need not be regular, so the method uses a coarser n-approximation; a coupling argument addresses the empirical-distribution issue.Source: §7.2.1 · pp. 41–42

Algorithm.

• The multi-bidder analysis randomizes among m+n signal draws to assign bidder and sample signals, and its key lemmas also hold in the matroid setting.The algorithm’s revenue-estimation step handles values that are not i.i.d. from the auxiliary mixture using the approach from the single-bidder case.Source: Algorithm · pp. 42–43
• The empirical Myerson auction's revenue on D is at least a 1 − O(ϵ) fraction of its revenue on E, which dominates its revenue on ¯E.The proof constructs E to stochastically dominate ¯E while keeping the auction's revenue on E close to its revenue on D.Source: Algorithm · p. 44

7.3 Lower bounds for n = 1

• Theorem 7.12 gives a sample-complexity lower bound for any single-agent mechanism against a q-bounded distribution in the Signals model.The supplied theorem statement omits the bound's formula.Source: §7.3 · p. 45
• Any pricing algorithm that is (1 − ϵ) approximate overall must be (1 − 3ϵ) approximate for at least half of the signals.The construction makes expected revenue from each conditional approximately equal, so failing on too many signals prevents the overall approximation guarantee.Source: §7.3 · pp. 45–46
• For signal σ_i, any pricing algorithm (1 − 3ϵ)-approximate for both distributions needs samples from the distribution conditioned on σ_i, even with exact knowledge of the distributions conditioned on other signals.Source: §7.3 · p. 47

Tail-bound for Regular Distributions

• For regular distributions, rounding values above a threshold down to that threshold preserves at least a 1 − ϵ fraction of optimal revenue in downward-closed settings.This tail bound reduces regular-distribution analysis to bounded distributions.Source: §8 · p. 48

Discretization in Value Space

• Value discretization reduces the relevant value set to ˜O(ϵ−1) elements, with additive or multiplicative approximation guarantees depending on the discretization.The section pairs multiples of ϵ with additive approximation and powers of 1 + ϵ with multiplicative 1 − ϵ approximation.Source: §8 · p. 48

Ranking Viewpoint

• The Ranking Viewpoint characterizes optimal auctions by ordering bidder-value pairs and a dummy element, and extends to matroid settings.For finite value sets, the section says this leaves (n|V|+1)! possible rankings to consider.Source: §8 · pp. 48–49

Mapping Viewpoint

• The Mapping Viewpoint discretizes virtual values to obtain approximately optimal auctions for single-parameter problems in the downward-closed setting.The section states that such auctions can be characterized by n mappings to ˜O(ϵ−1) discretized virtual values.Source: §8 · pp. 48–49

Concentration Inequality for Product Distributions

• A Bernstein-style concentration inequality for product distributions supports constructive, computationally efficient sample-complexity upper bounds for single-parameter problems.The section states that the theorem applies to any single-parameter problem.Source: §8 · p. 49

Strong Revenue Monotonicity

• Strong revenue monotonicity holds for single-parameter matroid problems: Myerson’s optimal auction for one distribution earns at least its optimal revenue on a stochastically dominating distribution.The section identifies this as Theorem 3.1.Source: §8 · p. 49

Scopes of Technical Ingredients

• Tables 2 and 3 summarize where the technical ingredients apply and how sample-complexity upper bounds depend on them.The section notes that some extensions described in an earlier version were omitted because subsequent work subsumed those bounds.Source: §8 · pp. 48–49, Table 2 · p. 49, Table 3 · p. 49