International Journal of Computer Science and Artificial Intelligence
An Open Access Journal
ISSN:2226-4450(Print)       ISSN:2226-4469(Online)
CODEN: IJCSPS                
Editor-in-Chief: Prof.Bing-Fei 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 2-player 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 2-player games to polymatrix games.
Keywords:N-player Non-cooperative Game in Normal Form; Polymatrix Games; Nash Equilibrium; Expected Payoff Function; Fuzzy Average; Linguistic Variables; Triangular Fuzzy Number
Author: Lunshan (Shaun) GAO1
1.Engineering Department, Raytheon Canada Limited, 400 Phillip Street, Waterloo, ON. N2L6R7, Canada
References:
  1. C. E. Lemke and J. T. Howson, Jr, “Equilibrium Points in Bimatrix Games,” SIAM Journal on Applied Math, vol. 12, pp. 413-423, 1964.
  2. J. Howson, “Equilibria of Polymatrix Games,” Management Science, vol. 18, iss. 5, pp. 312-318, 1972.
  3. J. Rosenmuller, “On a generalization of the Lemke-Howson Algorithm to Noncooperative N-person Games,” SIAM Journal of Applied Mathematics, vol. 1, pp. 73-79, 1971.
  4. R. Wilson, “Computing Equilibria of n-Person Games,” SIAM Journal of Applied Mathematics, vol. 21, pp. 80-87, 1971.
  5. H. Scarf, “The Approximation of Fixed Points of a Continuous Mapping,” SIAM Journal on Applied Mathematics, vol. 15, pp. 1328-1343, 1967.
  6. J. Dickhaut and T. Kaplan, “A Program for Finding Nash Equilibria,” The Mathematica Journal, pp. 87-93, 1991.
  7. S. Govindan and R. Wilson, “A Global Newton method to Compute Nash Equilibria,” Journal of Economic Theory, vol. 110, pp. 65-86, 2003.
  8. S. Govindan and R. Wilson, “Computing Nash Equilibria by Iterated Polymatrix Approximation,” Journal of Economic Dynamics and Control, vol. 28, iss. 7, pp. 1229-1241, 2004.
  9. 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. 457-502, 2006.
  10. R. Porter, E. Nudelman, and Y. Shoham, “Simple Search Methods for Finding a Nash Equilibrium,” Games and Economic Behavior, vol. 63, pp. 642-662, 2008.
  11. Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou, “Zero-Sum Polymatrix Games: A Generalization of Minmax,” available at: people.csail.mit.edu/costis/zerosum_final3.pdf.
  12. 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.
  13. X. Chen and X. Deng, “3-Nash is PPAD-complete,” ECCC, TR05-134, 2005.
  14. X. Chen and X. Deng, “Settling the Complexity of 2-Player Nash Equilibrium,” ECCC, TR05-140, 2005.
  15. C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The Complexity of Computing a Nash Equilibrium,” ECCC, TR05-115, 2005.
  16. C. Daskalakis and C. H. Papadimitriou, “Three-Player Games are Hard,” ECCC, TR05-139, 2005.
  17. X. Chen, D. Paparas, and M. Yannakakis, “The Complexity of Non-Monotone Markets,” In Proceeding of the 45th Annual ACM Symposium on Theory of Computing, pp. 181-190, 2013.
  18. A. Chakeri and F. Sheikholeslam, “Fuzzy Nash Equilibriums in Crisp and Fuzzy Games,” IEEE Transactions on Fuzzy Systems, vol. 21, iss. 1, pp. 171-176, 2012.
  19. 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. 475-491, 2003.
  20. S.H. Wu and V.W. Soo, “Fuzzy Game Theoretic Approach to Multi-Agent Coordination,” T. Ishida: PRIMA’98, LNAI1599, pp. 76-87, 1999.
  21. A. Kaufmann, and M. M. Gupta, Fuzzy Mathematical Models in Engineering and Management Science, Elsevier, Amsterdam, 1998.
  22. L. Gao, “The Fuzzy Arithmetic Mean,” Fuzzy Sets and Systems, vol. 107, pp. 335-348, 1999.
  23. L. A. Zadeh, “The Concept of Linguistic Variable and its Application to Approximate Reasoning-1,” Information Sciences, vol. 8, pp. 199-249, 1975.
  24. H. J. Zimmermann, Fuzzy Set Theory and Its Application, 2nd ed., Kluwer Academic Publishers, Boston, 1991.
  25. L. Gao, “The Discussion of Applications of the Fuzzy Average to Matrix Game Theory,” The Proceeding of CCECE2012, May 2012.
  26. L. Gao, “A Direct Algorithm for Computing Nash Equilibriums,” International Journal of Computer Science and Artificial Intelligence, vol. 3, iss. 2, pp. 80-86, 2013.
  27. V. D. Blondel and J. N. Tsitsiklis, “A Survey of Computational Complexity Results,” Automatica, Elsevier, vol. 36, pp. 1249-1274, 2000.
  28. T. Sonmez, available at: www.tayfunsonmez.net/wp-content/uploads/2013/10/E308SL4.pdf.