Game Redesign in No-regret Game Playing

Game Redesign in No-regret Game Playing

Yuzhe Ma, Young Wu, Xiaojin Zhu

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 3321-3327. https://doi.org/10.24963/ijcai.2022/461

We study the game redesign problem in which an external designer has the ability to change the payoff function in each round, but incurs a design cost for deviating from the original game. The players apply no-regret learning algorithms to repeatedly play the changed games with limited feedback. The goals of the designer are to (i) incentivize players to take a specific target action profile frequently; (ii) incur small cumulative design cost. We present game redesign algorithms with the guarantee that the target action profile is played in T-o(T) rounds while incurring only o(T) cumulative design cost. Simulations on four classic games confirm the ef- fectiveness of our proposed redesign algorithms.
Keywords:
Machine Learning: Adversarial Machine Learning
Agent-based and Multi-agent Systems: Multi-agent Learning