Potential games, path independence and Poisson's binomial distribution

Sen, Debapriya (2018): Potential games, path independence and Poisson's binomial distribution. Forthcoming in: Mathematical Methods of Operations Research

Abstract

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.

• Item Type: MPRA Paper
• Language: English
• Keywords: potential games; zero strategy; path independence; Poisson's binomial distribution; storage requirement
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games

References

Anderson, S.P., Goeree, J.P., Holt, C.A. 2001. Minimum-effort coordination games: Stochastic potential and logit equilibrium. Games and Economic Behavior, 34: 177-199

Bramoulle, Y. 2007. Anti-coordination and social interactions. Games and Economic Behavior, 58: 30-49

Bramoulle, Y., Kranton, R., D'Amours, M. 2014. Strategic interaction and networks. American Economic Review, 104: 898-930

Cheng, D., Liu, T., Zhang, K., Qi, H. 2016. On decomposed subspaces of finite games. IEEE Transactions on Automatic Control, 61: 3651-3656

Chien, S., Sinclair, A. 2011. Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior, 71: 315-327

Darroch, J.N. 1964. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 35: 1317-1321

Ellingsaeter, B., Skjegstad, M., Maseng, T. 2012. A potential game for power and frequency allocation in large-scale wireless networks, arXiv preprint arXiv:1212.0724, pp. 1-10, 2012. Available: http://arxiv.org/abs/1212.0724

Hino, Y. 2011. An improved algorithm for detecting potential games. International Journal of Game Theory, 40: 199-205

Hoeffding, W. 1956. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27: 713-721

Marden, J.R., Arslan, G., Shamma, J.S. 2009. Cooperative control and potential games. IEEE Transactions on Systems, Man and Cybernetics-part B, 39: 1393-1407

Monderer, D., Shapley, L.S. 1996. Potential games. Games and Economic Behavior, 14: 124-143

Neel, J.O., Reed, J.H., Gilles, R.P. 2004. Convergence of cognitive radio networks, in Proceedings of IEEE Wireless Communications Network Conference (WCNC), Atlanta, GA, Mar. 2004, 2250-2255

Pitman, J. 1997. Probabilistic bounds on the coefficients of polynomials with only real zeros. Journal of Combinatorial Theory, Series A, 77: 279-303

Roughgarden, T., Tardos, E. 2002. How bad is selfish routing? Journal of the ACM, 49: 236-259

Sandholm, W.H. 2010. Decompositions and potentials for normal form games. Games and Economic Behavior, 70: 446-456

Todd, M.J. 2016. Computation, multiplicity, and comparative statics of Cournot equilibria in integers. Mathematics of Operations Research, 41: 1125-1134

Wang, Y.H. 1993. On the number of successes in independent trials. Statistica Sinica, 3: 295-312