Part of Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
Yuan Deng, Jon Schneider, Balasubramanian Sivan
We study the problem of how to repeatedly sell to a buyer running a no-regret, mean-based algorithm. Previous work [Braverman et al., 2018] shows that it is possible to design effective mechanisms in such a setting that extract almost all of the economic surplus, but these mechanisms require the buyer's values each round to be drawn independently and identically from a fixed distribution. In this work, we do away with this assumption and consider the prior-free setting where the buyer's value each round is chosen adversarially (possibly adaptively). We show that even in this prior-free setting, it is possible to extract a (1−ε)-approximation of the full economic surplus for any ε>0. The number of options offered to a buyer in any round scales independently of the number of rounds T and polynomially in ε. We show that this is optimal up to a polynomial factor; any mechanism achieving this approximation factor, even when values are drawn stochastically, requires at least Ω(1/ε) options. Finally, we examine what is possible when we constrain our mechanism to a natural auction format where overbidding is dominated. Braverman et al. [2018] show that even when values are drawn from a known stochastic distribution supported on [1/H,1], it is impossible in general to extract more than O(loglogH/logH) of the economic surplus. We show how to achieve the same approximation factor in the prior-independent setting (where the distribution is unknown to the seller), and an approximation factor of O(1/logH) in the prior-free setting (where the values are chosen adversarially).