Strategizing against No-Regret Learners in First-Price Auctions
<|reference_start|>Strategizing against No-Regret Learners in 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.<|reference_end|>
@article{rubinstein2024strategizing,
    title={Strategizing against No-Regret Learners in First-Price Auctions},
    author={Aviad Rubinstein and Junyao Zhao},
    journal={arXiv preprint arXiv:2402.08637},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08637},
    primaryClass={cs.GT cs.DS cs.LG}
}