Semi-Decentralized Coordinated Online Learning for Continuous Games with Coupled Constraints via Augmented Lagrangian
This work addresses coordination challenges in multi-agent systems with constraints, offering a decentralized approach that reduces information requirements, though it appears incremental in its algorithmic design.
The paper tackles the problem of finding Nash equilibria in concave continuous games with coupled constraints by proposing a semi-decentralized online learning algorithm based on mirror ascent and augmented Lagrangian methods, which converges to a generalized Nash equilibrium under specific step size and augmentation conditions.
We consider a class of concave continuous games in which the corresponding admissible strategy profile of each player underlies affine coupling constraints. We propose a novel algorithm that leads the relevant population dynamic toward Nash equilibrium. This algorithm is based on a mirror ascent algorithm, which suits with the framework of no-regret online learning, and on the augmented Lagrangian method. The decentralization aspect of the algorithm corresponds to the aspects that the iterate of each player requires the local information about how she contributes to the coupling constraints and the price vector broadcasted by a central coordinator. So each player needs not know about the population action. Moreover, no specific control by the central primary coordinator is required. We give a condition on the step sizes and the degree of the augmentation of the Lagrangian, such that the proposed algorithm converges to a generalized Nash equilibrium.