Potential games, path independence and Poisson's binomial distribution

This paper provides a simple characterization of potential games in terms of path independence. Using this characterization we propose an algorithm to determine if a finite game is potential or not. We define the storage requirement for our algorithm and provide its upper bound. The number of equations required in this algorithm is lower or equal to the number obtained in the algorithms proposed in the recent literature. We also show that for games with same numbers of players and strategy profiles, the number of equations for our algorithm is maximum when all players have the same number of strategies. To obtain our results, the key technique of this paper is to identify an associated Poisson's binomial distribution. This distribution enables us to derive explicit forms of the number of equations, storage requirement and related aspects.