Learning to Play General-Sum Games against Multiple Boundedly Rational Agents

• DOI: 10.1609/aaai.v37i10.26391
• Publication Date: 2023-06-27T17:59:17Z
• Authors: Eric Zhao; Alexander R. Trott; Caiming Xiong; Stephan Zheng
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; 0502 economics and business; 05 social sciences; Machine Learning (cs.LG)

We study the problem of training a principal in a multi-agent general-sum game using reinforcement learning (RL). Learning a robust principal policy requires anticipating the worst possible strategic responses of other agents, which is generally NP-hard. However, we show that no-regret dynamics can identify these worst-case responses in poly-time in smooth games. We propose a framework that uses this policy evaluation method for efficiently learning a robust principal policy using RL. This framework can be extended to provide robustness to boundedly rational agents too. Our motivating application is automated mechanism design: we empirically demonstrate our framework learns robust mechanisms in both matrix games and complex spatiotemporal games. In particular, we learn a dynamic tax policy that improves the welfare of a simulated trade-and-barter economy by 15%, even when facing previously unseen boundedly rational RL taxpayers.