2019/12/20 by Jin, Yaonan, Lu, Pinyan, Xiao, Tao · 1 citation
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1912.10069
This paper proves the tight sample complexity of \sf Second-Price Auction with Anonymous Reserve, up to a logarithmic factor, for each of all the value distribution families studied in the literature: [0, 1]-bounded, [1, H]-bounded, regular, and monotone hazard rate (MHR). Remarkably, the setting-specific tight sample complexity poly(ε-1) depends on the precision ε ∈ (0, 1), but not on the number of bidders n ≥ 1. Further, in the two bounded-support settings, our learning algorithm allows \em correlated value distributions. In contrast, the tight sample complexity Θ(n) ⋅ poly(ε-1) of \sf Myerson Auction proved by Guo, Huang and Zhang (STOC~2019) has a nearly-linear dependence on n ≥ 1, and holds only for \em independent value distributions in every setting. We follow a similar framework as the Guo-Huang-Zhang work, but replace their information theoretical arguments with a direct proof.