Strategizing against No-Regret Learners in First-Price Auctions
This addresses strategic interactions in auction theory and game theory, offering theoretical insights for designing robust learning algorithms, but it is incremental as it builds on prior work by Mansour et al. (2022).
The paper tackles the problem of strategizing against no-regret learners in repeated first-price auctions and Bayesian games, showing that for mean-based algorithms, the optimizer cannot exceed Stackelberg utility in full-information auctions but can achieve much higher in Bayesian auctions, while proving that no-polytope-swap-regret algorithms are necessary to cap utility in general Bayesian games and providing an improved algorithm for Bayesian first-price auctions.
We study repeated first-price auctions and general repeated Bayesian games between two players, where one player, the learner, employs a no-regret learning algorithm, and the other player, the optimizer, knowing the learner's algorithm, strategizes to maximize its own utility. For a commonly used class of no-regret learning algorithms called mean-based algorithms, we show that (i) in standard (i.e., full-information) first-price auctions, the optimizer cannot get more than the Stackelberg utility -- a standard benchmark in the literature, but (ii) in Bayesian first-price auctions, there are instances where the optimizer can achieve much higher than the Stackelberg utility. On the other hand, Mansour et al. (2022) showed that a more sophisticated class of algorithms called no-polytope-swap-regret algorithms are sufficient to cap the optimizer's utility at the Stackelberg utility in any repeated Bayesian game (including Bayesian first-price auctions), and they pose the open question whether no-polytope-swap-regret algorithms are necessary to cap the optimizer's utility. For general Bayesian games, under a reasonable and necessary condition, we prove that no-polytope-swap-regret algorithms are indeed necessary to cap the optimizer's utility and thus answer their open question. For Bayesian first-price auctions, we give a simple improvement of the standard algorithm for minimizing the polytope swap regret by exploiting the structure of Bayesian first-price auctions.