Strategizing against No-Regret Learners in First-Price Auctions
Aviad Rubinstein Junyao Zhao
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.