Paths to Equilibrium in Games

Multi-agent reinforcement learning (MARL) algorithms often aim to find Nash equilibria in games, where all players are optimally responding to each other. A key challenge in MARL is that players’ learning processes interact, sometimes leading to cycles and preventing convergence. Existing approaches sometimes struggle to guarantee convergence, especially in complex, general-sum games.

This paper focuses on “satisficing paths,” a more relaxed condition than best-response updates. A satisficing path only requires that an agent that’s already best responding does not change its strategy in the next period. The paper proves that for any finite n-player game, a satisficing path exists to a Nash equilibrium from any starting strategy profile. This theoretical guarantee holds even without coordination between players, highlighting the potential for distributed and uncoordinated learning strategies. The core idea is to show that it is always possible to update strategies to eventually reach the Nash equilibrium. The authors propose a novel counter-intuitive approach by strategically increasing the number of unsatisfied players during the updating process.