Distributed Nash equilibrium computation in multi-group resource allocation games over digraphs

The existing distributed resource allocation (DRA) algorithms for multi-agent networks can rarely be implemented for multiple interacting groups of agents with conflicts of interest. The directed interaction, together with the hard balance constraint that follows from maintaining supply–demand balance during the execution process, make the DRA more challenging. To address this problem, the paper studies DRA over multiple interacting groups from a game-theoretic perspective, introducing the resource allocation game (RAG). A novel out-Laplacian matrix based methodology is developed for distributed Nash equilibrium (NE) computation. Following this methodology, distributed algorithms are designed using leader-follower tracking protocols to estimate partial derivatives of individual objective functions for the RAG. A reduced-order distributed algorithm is further developed for the RAG by integrating a gradient-tracking mechanism for estimating partial derivatives of group-level objective functions. It is shown that agent states converge to the NE of the games linearly while satisfying the balance constraint during the whole execution process under the proposed algorithms. The effectiveness of the proposed algorithms is illustrated through numerical examples.