International Journal of Computer Science and Artificial Intelligence
An Open Access Journal

ISSN:22264450(Print)
ISSN:22264469(Online)

CODEN: IJCSPS 
EditorinChief: Prof.BingFei Wu(Taiwan)


Finding Nash Equilibria for Polymatrix Games 

Full Paper(PDF, 523KB) 


Abstract: 

This paper describes the derivation of the expected payoff function of polymatrix games according to the induction method. It also presents a new algorithm for calculating mixed Nash equilibrium (NE) in polymatrix games. Results indicate that the new algorithm can compute mixed NEs for polymatrix games within polynomial time. This paper is a continuation result of previous research which describes that the expected payoff function of 2player games in normal form is identical to the mathematical representation of the fuzzy average of two linguistic values of a linguistic variable; this paper extends the identification of 2player games to polymatrix games. 

Keywords:Nplayer Noncooperative Game in Normal Form; Polymatrix Games; Nash Equilibrium; Expected Payoff Function; Fuzzy Average; Linguistic Variables; Triangular Fuzzy Number 

Author: Lunshan (Shaun) GAO^{1}  1.Engineering Department, Raytheon Canada Limited, 400 Phillip Street, Waterloo, ON. N2L6R7, Canada 

References:  C. E. Lemke and J. T. Howson, Jr, “Equilibrium Points in Bimatrix Games,” SIAM Journal on Applied Math, vol. 12, pp. 413423, 1964.
 J. Howson, “Equilibria of Polymatrix Games,” Management Science, vol. 18, iss. 5, pp. 312318, 1972.
 J. Rosenmuller, “On a generalization of the LemkeHowson Algorithm to Noncooperative Nperson Games,” SIAM Journal of Applied Mathematics, vol. 1, pp. 7379, 1971.
 R. Wilson, “Computing Equilibria of nPerson Games,” SIAM Journal of Applied Mathematics, vol. 21, pp. 8087, 1971.
 H. Scarf, “The Approximation of Fixed Points of a Continuous Mapping,” SIAM Journal on Applied Mathematics, vol. 15, pp. 13281343, 1967.
 J. Dickhaut and T. Kaplan, “A Program for Finding Nash Equilibria,” The Mathematica Journal, pp. 8793, 1991.
 S. Govindan and R. Wilson, “A Global Newton method to Compute Nash Equilibria,” Journal of Economic Theory, vol. 110, pp. 6586, 2003.
 S. Govindan and R. Wilson, “Computing Nash Equilibria by Iterated Polymatrix Approximation,” Journal of Economic Dynamics and Control, vol. 28, iss. 7, pp. 12291241, 2004.
 B. Blum, C. R. Shelton, and D. Koller, “A Continuation Method for Nash Equilibria in Structured Games,” Journal of Artificial Intelligence Research, vol. 25, pp. 457502, 2006.
 R. Porter, E. Nudelman, and Y. Shoham, “Simple Search Methods for Finding a Nash Equilibrium,” Games and Economic Behavior, vol. 63, pp. 642662, 2008.
 Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou, “ZeroSum Polymatrix Games: A Generalization of Minmax,” available at: people.csail.mit.edu/costis/zerosum_final3.pdf.
 S. Belhaiza, “On Perfect Nash Equilibria of Polymatrix Games,” Hindawi Publishing Corp. Game Theory, vol. 2014, available at: http://dx.doi.org/10.1155/2014/937070.
 X. Chen and X. Deng, “3Nash is PPADcomplete,” ECCC, TR05134, 2005.
 X. Chen and X. Deng, “Settling the Complexity of 2Player Nash Equilibrium,” ECCC, TR05140, 2005.
 C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The Complexity of Computing a Nash Equilibrium,” ECCC, TR05115, 2005.
 C. Daskalakis and C. H. Papadimitriou, “ThreePlayer Games are Hard,” ECCC, TR05139, 2005.
 X. Chen, D. Paparas, and M. Yannakakis, “The Complexity of NonMonotone Markets,” In Proceeding of the 45th Annual ACM Symposium on Theory of Computing, pp. 181190, 2013.
 A. Chakeri and F. Sheikholeslam, “Fuzzy Nash Equilibriums in Crisp and Fuzzy Games,” IEEE Transactions on Fuzzy Systems, vol. 21, iss. 1, pp. 171176, 2012.
 D. Garagic and J. B. Cruz, Jr, “An Approach to Fuzzy Noncooperative Nash Games,” Journal of Optimization Theory and Applications, vol. 118, no. 3, pp. 475491, 2003.
 S.H. Wu and V.W. Soo, “Fuzzy Game Theoretic Approach to MultiAgent Coordination,” T. Ishida: PRIMA’98, LNAI1599, pp. 7687, 1999.
 A. Kaufmann, and M. M. Gupta, Fuzzy Mathematical Models in Engineering and Management Science, Elsevier, Amsterdam, 1998.
 L. Gao, “The Fuzzy Arithmetic Mean,” Fuzzy Sets and Systems, vol. 107, pp. 335348, 1999.
 L. A. Zadeh, “The Concept of Linguistic Variable and its Application to Approximate Reasoning1,” Information Sciences, vol. 8, pp. 199249, 1975.
 H. J. Zimmermann, Fuzzy Set Theory and Its Application, 2nd ed., Kluwer Academic Publishers, Boston, 1991.
 L. Gao, “The Discussion of Applications of the Fuzzy Average to Matrix Game Theory,” The Proceeding of CCECE2012, May 2012.
 L. Gao, “A Direct Algorithm for Computing Nash Equilibriums,” International Journal of Computer Science and Artificial Intelligence, vol. 3, iss. 2, pp. 8086, 2013.
 V. D. Blondel and J. N. Tsitsiklis, “A Survey of Computational Complexity Results,” Automatica, Elsevier, vol. 36, pp. 12491274, 2000.
 T. Sonmez, available at: www.tayfunsonmez.net/wpcontent/uploads/2013/10/E308SL4.pdf.

