Second-Order Potentials for Finite Games: Existence, Characterisation, and Game Decomposition

Abstract

Monderer and Shapley (1996) showed that a game is a potential game precisely when the players' second-order cross-differences agree pair by pair. This paper asks what can be built from them when the agreement fails. The resulting MS-potential, assembled from their common-interest part, is unique up to separable payoff terms and exists precisely when a higher-order MS-condition holds; on exact potential games it recovers the potential up to the players' main effects. A least-squares construction extends the MS-potential to all finite games and induces the \MS-decomposition: every game splits into a common-interest MS-potential game and a residual absorbing every player's individualistic effects. Everything read off the second differences is invariant under the transformations that leave strategic content untouched, relabelling, non-strategic translation and action duplication, where the CMOP decomposition is not; only the least-squares extension fails, since it averages and centres. The central result is an identity: when all players have equally many actions, an augmentation of the MS-potential coincides, up to the additive constant, with the potential of Candogan et al. (2011). If action counts are unequal they diverge, and no bound on that divergence is established here. Both rest on the same uniform weighting of the players' actions.