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

PDF
MPRA_paper_84409.pdf Download (749kB)  Preview 
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 

Original Title:  Potential games, path independence and Poisson's binomial distribution 
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 
Item ID:  84409 
Depositing User:  Debapriya Sen 
Date Deposited:  08 Feb 2018 10:49 
Last Modified:  08 Feb 2018 10:49 
References:  Anderson, S.P., Goeree, J.P., Holt, C.A. 2001. Minimumeffort coordination games: Stochastic potential and logit equilibrium. Games and Economic Behavior, 34: 177199 Bramoulle, Y. 2007. Anticoordination and social interactions. Games and Economic Behavior, 58: 3049 Bramoulle, Y., Kranton, R., D'Amours, M. 2014. Strategic interaction and networks. American Economic Review, 104: 898930 Cheng, D., Liu, T., Zhang, K., Qi, H. 2016. On decomposed subspaces of finite games. IEEE Transactions on Automatic Control, 61: 36513656 Chien, S., Sinclair, A. 2011. Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior, 71: 315327 Darroch, J.N. 1964. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 35: 13171321 Ellingsaeter, B., Skjegstad, M., Maseng, T. 2012. A potential game for power and frequency allocation in largescale wireless networks, arXiv preprint arXiv:1212.0724, pp. 110, 2012. Available: http://arxiv.org/abs/1212.0724 Hino, Y. 2011. An improved algorithm for detecting potential games. International Journal of Game Theory, 40: 199205 Hoeffding, W. 1956. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27: 713721 Marden, J.R., Arslan, G., Shamma, J.S. 2009. Cooperative control and potential games. IEEE Transactions on Systems, Man and Cyberneticspart B, 39: 13931407 Monderer, D., Shapley, L.S. 1996. Potential games. Games and Economic Behavior, 14: 124143 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, 22502255 Pitman, J. 1997. Probabilistic bounds on the coefficients of polynomials with only real zeros. Journal of Combinatorial Theory, Series A, 77: 279303 Roughgarden, T., Tardos, E. 2002. How bad is selfish routing? Journal of the ACM, 49: 236259 Sandholm, W.H. 2010. Decompositions and potentials for normal form games. Games and Economic Behavior, 70: 446456 Todd, M.J. 2016. Computation, multiplicity, and comparative statics of Cournot equilibria in integers. Mathematics of Operations Research, 41: 11251134 Wang, Y.H. 1993. On the number of successes in independent trials. Statistica Sinica, 3: 295312 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/84409 