Timezone: »
Poster
Prior-Free Dynamic Auctions with Low Regret Buyers
Yuan Deng · Jon Schneider · Balasubramanian Sivan
Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #225
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-\varepsilon)$-approximation of the full economic surplus for any $\varepsilon > 0$. The number of options offered to a buyer in any round scales independently of the number of rounds $T$ and polynomially in $\varepsilon$. 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 $\Omega(1/\varepsilon)$ 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(\log\log H / \log H)$ 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 / \log H)$ in the prior-free setting (where the values are chosen adversarially).
Author Information
Yuan Deng (Duke University)
Jon Schneider (Google Research)
Balasubramanian Sivan (Google Research)
More from the Same Authors
-
2021 Poster: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms »
Sreenivas Gollapudi · Guru Guruganesh · Kostas Kollias · Pasin Manurangsi · Renato Leme · Jon Schneider -
2021 Poster: Margin-Independent Online Multiclass Learning via Convex Geometry »
Guru Guruganesh · Allen Liu · Jon Schneider · Joshua Wang -
2021 Poster: Robust Auction Design in the Auto-bidding World »
Santiago Balseiro · Yuan Deng · Jieming Mao · Vahab Mirrokni · Song Zuo -
2021 Poster: Prior-independent Dynamic Auctions for a Value-maximizing Buyer »
Yuan Deng · Hanrui Zhang -
2020 Poster: Myersonian Regression »
Allen Liu · Renato Leme · Jon Schneider -
2019 Poster: Contextual Bandits with Cross-Learning »
Santiago Balseiro · Negin Golrezaei · Mohammad Mahdian · Vahab Mirrokni · Jon Schneider -
2019 Poster: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Oral: Strategizing against No-regret Learners »
Yuan Deng · Jon Schneider · Balasubramanian Sivan -
2019 Poster: A Robust Non-Clairvoyant Dynamic Mechanism for Contextual Auctions »
Yuan Deng · Sébastien Lahaie · Vahab Mirrokni