A Theoretical Study on the Case of Multiple Equilibrium Points in Game Theory An Analysis of Two-Player Zero-Sum Games Using the Graphical Method and Linear Programming
DOI:
https://doi.org/10.37375/esj.v9i1.4001Keywords:
Two-Player Zero-Sum Games, Multiplicity of Optimal Solutions, Graphical Method, Linear ProgrammingAbstract
In the classical theory of two-player zero-sum games, optimal strategies typically lead to a unique optimal solution characterized by a single equilibrium point for both players, where the game values coincide (|v = w|). This implies the existence of a unique set of probability variables (pᵢ), representing the first player’s mixed strategy over its pure strategies (xᵢ), which yields the game value (v) by maximizing the minimum payoff. Similarly, there exists a unique set of probability variables (qⱼ), corresponding to the second player’s mixed strategy over its pure strategies (yⱼ), which yields the game value (w) by minimizing the maximum loss. This study focuses on analyzing a special case in game theory in which multiple equilibrium points exist for both competitors, implying the presence of more than one optimal solution - indeed, infinitely many optimal solutions for both players. In such cases, multiple probability combinations (pᵢ) achieve the maximum value of the first player’s objective function (v), while multiple probability combinations (qⱼ) attain the minimum value of the second player’s objective function (w), all while preserving the equilibrium condition (|v = w|). The contribution of this study lies in providing a deeper understanding of this phenomenon by identifying the conditions that give rise to multiple equilibrium points, analyzing the strategic combinations that yield optimal solutions using both the graphical method (GM) and linear programming (LP), examining the impact of these solutions on the opposing player, and investigating the possibility of the coexistence of multiple optimal solutions for both players within the same game
References
- الشيخ، عبد الله محمد. الرمالي، عمر محمد. عبد الله، جمعة عمر. (2025). تحليل تأثير تعدد القيود على نقطة الحل في نظرية الألعاب: دراسة نظرية للمشاكل من نوع (m × 2) أو (2 × n). مجلة جامعة سرت للعلوم الإنسانية، 15(2)، 224–239
- Agrawal, B., Kumar, P. (2022). An Approach of L.P.P method –game problem using simplex method. International Journal of Research and Analytical Reviews (IJRAR), UGC and ISSN Approved-International Peer Reviewed Journal, Refereed Journal, Indexed Journal, Impact Factor, 9 (4), 1269-2348.
- Ashour, M. A. H., Al - Dahhan, I. A., & Al - Qabily, S. M. (2020). Solving game theory problems using linear programming and genetic algorithms. In Human Interaction and Emerging Technologies: Proceedings of the 1st International Conference on Human Interaction and Emerging Technologies (IHIET 2019), August 22-24, 2019, Nice, France (pp. 247-252). Springer International Publishing.
- Constantinos Daskalakis, Aranyak Mehta, and Christos Papadimitriou. A note on approximate nash equilibria. Theoretical Computer Science, 410(17):1581–1588, 2009.
- Ilan Adler. The equivalence of linear programs and zero-sum games. International Journal of Game Theory, 42(1):165, 2013.
- Ji, Y., Li, M., & Qu, S. (2018). Multi-objective linear programming games and applications in supply chain competition. Future Generation Computer Systems, 86, 591-597.
- Justin Dallant, Frederik Haagensen, Riko Jacob, László Kozma, and Sebastian Wild. Finding the saddle point faster than sorting. In 2024 Symposium on Simplicity in Algorithms (SOSA), pages 168–178. SIAM, 2024.
- Kearns, M., Littman, M. L., & Singh, S. (2013). Graphical models for game theory. arXiv preprint arXiv:1301.2281.
- Kumar, S., & Reddy, D. S. N. (1999). Graphical solution of (n× m) matrix of a game theory. European journal of operational research, 112 (2), 467-471.
- Kumar, S., & Reddy, D. S. N. (1999). Graphical solution of (n× m) matrix of a game theory. European journal of operational research, 112 (2), 467-471.
- Maiti, A., Boczar, R., Jamieson, K., & Ratliff, L. J. (2023). Query-Efficient Algorithm to Find All Nash Equilibria in a Two-Player Zero-Sum Matrix Game. University of Washington.
- Nash, J. F. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1), 48–49.
- Nash, J. F. (1951). Non-cooperative games. Annals of Mathematics, 54(2), 286–295.
- Peters, H. (2015). Game theory: A Multi- leveled approach. Springer. Texts in Business and Economics, Berlin Heidelberg, (2nd ed.)
- Thie, Paul R., and Gerard E. Keough. An Introduction to Linear Programming and Game Theory. John Wiley & Sons, 2016.
- Vang, C. (2022). Implementing the Simplex Algorithm to Solve Zero-Sum Games.
- Von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100 (1), 295–320
- Von Neumann, J., & Morgenstern, O. (1944/1947) Theory of games and economic behavior. Princeton: Princeton University Press
- Yakov Babichenko. Query complexity of approximate nash equilibria. Journal of the ACM (JACM), 63(4):1–24, 2016.
- Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proceedings of the fifth international congress of mathematicians (Vol. 2, pp. 501-504). Cambridge: Cambridge University Press.
