Targeting Makes Sample Efficiency in Auction Design

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 buyers 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 $Delta in [0, 1]$ which lower bounds how small the quantile intervals could be. When $Delta = 1$, it degenerates to Cole and Roughgardens model of i.i.d. samples; when it is the idealized case of $Delta = 0$, it degenerates to the model studied by Chen et al. (2018). For instance, for $n$ buyers with bounded values in $[0, 1]$, $tilde{O}(epsilon^{-1})$ targeted samples suffice while it is known that at least $tilde{Omega}(n epsilon^{-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 $epsilon^{-1}$ to linear. In this work, we introduce new technical ingredients and show that the number of targeted samples sufficient for learning an $epsilon$-optimal auction is substantially smaller than the sample complexity of i.i.d. samples for the full spectrum of $Delta in [0, 1)$. Even with only mild targeting power, i.e., whenever $Delta = o(1)$, our targeted sample complexity upper bounds are strictly smaller than the optimal sample complexity of i.i.d. samples.