Targeting Makes Sample Efficiency in Auction Design
share
This paper introduces the targeted sampling model in optimal auction design. In this model, the seller may specify a quantile interval and sample from a buyer's prior restricted to the interval. This can be interpreted as allowing the seller to, for example, examine the top 40 percents bids from previous buyers with the same characteristics. The targeting power is quantified with a parameter Δ∈ [0, 1] which lower bounds how small the quantile intervals could be. When Δ = 1, it degenerates to Cole and Roughgarden's model of i.i.d. samples; when it is the idealized case of Δ = 0, it degenerates to the model studied by Chen et al. (2018). For instance, for n buyers with bounded values in [0, 1], Õ(ϵ^-1) targeted samples suffice while it is known that at least Ω̃(n ϵ^-2) i.i.d. samples are needed. In other words, targeted sampling with sufficient targeting power allows us to remove the linear dependence in n, and to improve the quadratic dependence in ϵ^-1 to linear. In this work, we introduce new technical ingredients and show that the number of targeted samples sufficient for learning an ϵ-optimal auction is substantially smaller than the sample complexity of i.i.d. samples for the full spectrum of Δ∈ [0, 1). Even with only mild targeting power, i.e., whenever Δ = o(1), our targeted sample complexity upper bounds are strictly smaller than the optimal sample complexity of i.i.d. samples.
READ FULL TEXT