Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Games
This addresses strategic decision-making in hierarchical multi-agent systems, such as in economics or robotics, with incremental contributions to learning in Stackelberg games.
The paper tackles the problem of learning equilibrium in hierarchical multi-player games with multiple leaders and a single follower, proposing a novel Correlated Stackelberg Equilibrium concept and designing online learning algorithms that achieve no-external Stackelberg-regret and converge to approximate equilibrium.
Many real-world strategic games involve interactions between multiple players. We study a hierarchical multi-player game structure, where players with asymmetric roles can be separated into leaders and followers, a setting often referred to as Stackelberg game or leader-follower game. In particular, we focus on a Stackelberg game scenario where there are multiple leaders and a single follower, called the Multi-Leader-Single-Follower (MLSF) game. We propose a novel asymmetric equilibrium concept for the MLSF game called Correlated Stackelberg Equilibrium (CSE). We design online learning algorithms that enable the players to interact in a distributed manner, and prove that it can achieve no-external Stackelberg-regret learning. This further translates to the convergence to approximate CSE via a reduction from no-external regret to no-swap regret. At the core of our works, we solve the intricate problem of how to learn equilibrium in leader-follower games with noisy bandit feedback by balancing exploration and exploitation in different learning structures.