Second-Order Potentials for Finite Games: Existence, Characterisation, and Game Decomposition
2026-08-03 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors build on Monderer and Shapley's work, which found a special symmetry condition in games called exact potential games. They explore what happens when this symmetry is missing and define a new concept called the MS-potential, capturing common-interest parts of the game. This MS-potential is unique except for individual player effects and exists under a specific higher-order condition. They also show that any finite game can be split into two parts: a common-interest MS-potential game and a leftover part with personal payoffs. Finally, they connect their MS-potential to a known potential in games where players have equal numbers of actions.
Exact potential gameCross-differencesMS-potentialCommon-interest gamesSeparable payoffHigher-order MS-conditionLeast-squares constructionGame decompositionCandogan-Menache-Ozdaglar-Parrilo potential
Authors
Robert P. Gilles
Abstract
Monderer and Shapley (1996) showed that a game is an exact potential game exactly when the players' cross-differences agree pair by pair, a symmetry condition on how any two players' incentives interlock. This paper asks what can be built from these characteristics when symmetry fails. The resulting MS-potential is constructed from the second differences that represent the game's common-interest elements. The MS-potential is unique up to separable payoff terms and it exists precisely when a higher-order MS-condition holds. On the class of exact potential games it recovers the potential up to the players' individualistic main effects. A least-squares construction subsequently extends the MS-potential to the class of all finite games. The construction induces the MS-decomposition: every finite game splits into a common-interest MS-potential game and a residual that absorbs every player's individualistic payoffs. The paper's central result is an identity: for games in which all players have equally many actions, an augmentation of the MS-potential coincides --- up to the additive constant --- with the potential of Candogan, Menache, Ozdaglar and Parrilo (2011).