Distributing Potential Games on Graphs Part I. Game formulation

Abstract The paper presents the problem of distributing potential games over communication graphs. Suppose a potential game can be designed for a group of agents (players) where each has access to all others’ actions (strategies). The paper shows how to design a corresponding potential game for these agents if the full information assumption is replaced with communication over a network depicted by undirected graphs with certain properties. A state-based formulation for potential games is utilized. This provides degrees of freedom to handle the previous information limitation. Notions of Nash’s equilibria for the developed game (called here distributed potential game) are presented, and relations between these equilibria and those of the full information game are studied. In part II of the paper learning Nash equilibria for the newly developed game is studied. The development focuses on providing a way to utilize available algorithms of the full information game. The motivation for the results comes from a platoon matching problem for heavy duty vehicles. Utilizing the newly developed distributed game, recent results based on potential games can be extended, providing a basis for an on-the-go strategy where platoon matching on road networks can be solved locally.