Corvinus
Corvinus

On symmetric bimatrix games

Forgó, Ferenc (2018) On symmetric bimatrix games. Working Paper. Corvinus University of Budapest Faculty of Economics, Budapest.

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
508kB

Abstract

Computation of Nash equilibria of bimatrix games is studied from the viewpoint of identifying polynomially solvable cases with special attention paid to symmetric random games. An experiment is conducted on a sample of 500 randomly generated symmetric games with matrix size 12 and 15. Distribution of support size and Nash equilibria are used to formulate a conjecture: for finding a symmetric NEP it is enough to check supports up to size 4 whereas for non-symmetric and all NEP's this number is 3 and 2, respectively. If true, this enables us to use a Las Vegas algorithm that finds a Nash equilibrium in polynomial time with high probability.

Item Type:Monograph (Working Paper)
Series Name:Corvinus Economics Working Papers - CEWP
Series Number / Identification Number:2018/04
Uncontrolled Keywords:bimatrix game, random games, experimental games, complexity
JEL classification:C72 - Noncooperative Games
Divisions:Faculty of Economics > Department of Operations Research and Actuarial Sciences
Subjects:Mathematics, Econometrics
Projects:NKFI K-1 119930
References:

Avis D, Rosenberg G, Savani R and von Stengel B (2010), Enumeration of Nash equilibria for two-player games. Economic Theory, 42:9-37. Online solver
available at http://banach.lse.ac.uk.

Bárány I, Vempala S and Vetta A (2005) Nash equilibria in random games.
In: Proceedings of the 4th International Symposium on Foundations of Com-
puter Science (FOCS'05), 123-131

Faris G and Maier S (1987) The value of a random game: The advantage of.rationality. Complex Systems 1:235-244

Fearnley J, Igwe T P and Savani R (2015) An empirical study of finding
approximate equilibria in bimatrix games. In: Bampis E. (eds) Experimental Algorithms. SEA 2015. Lecture Notes in Computer Science, vol 9125:339-351.
Springer

Feder T, Nazerzadeh H and Saberi A (2007) Approximating Nash equilibria using small-support strategies. In:Proceedings of the 8th ACM Conference on Electronic Commerce 352-354

Gilboa I and Zemel E (1989) Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior 15:745-770

Goldman A (1957) The probability of a saddlepoint. AmericanMath. Monthly 64:729-730

Griesmer J.H, Ho¤man A J and Robinson A (1963) On symmetric bimatrix games. IBM Research Paper RC-959 IBM Corp. Thomas J. Watson Research
Center Yorktown Heights New York

Jurg A, Jansen M J M, Potters T A M and Tijs S H (1992) A symmetrization for finite two-person games. Methods and Models of Operations Research 6:111-
123

Kannan R and Theobald T (2010) Games of fixed rank: A hierarchy of bimatrix games. Economic Theory 42:157-174

Kontogiannis S C and Spirakis P G (2009) On the support size of stable strategies in random games. Theoretical Computer Science 410:933-942

Kontogiannis S C and Spirakis P G (2011). Approximability of symmetric bimatrix games and related experiments. In: Proceedings of the 10th Interna-
tional Symposium on Experimental Algorithms (SEA'11), 1-20

Lemke C. E. and Howson J. T. Jr. (1964) Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics 12:413-423

Lipton R, Markakis E and Mehta A (2003) Playing large games using simple strategies. In:Proceedings of E-Commerce, 36-41

Mangasarian O L and Stone H (1964) Two-person nonzero-sum games and quadratic programming. Journal of Math. Anal. Appl. 9:348-355

Mehta R (2014) Constant rank bimatrix games are PPAD-hard. In: ACM Symposium on the Theory of Computing, 545-554

Mehta R, Vazirani V V and Yazdanbod S (2014) Settling some open problems on 2-player symmetric Nash equilibria. Cornell University Library, arXiv:1412.0969v1

Milchtaich I (2006) Computation of completely mixed equilibrium payo¤s in bimatrix games. International Game Theory Review 8:483-487

Moulin H and Vial J-P (1978) Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7:201-221

Nash J. F (1950) Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36:48-49.

Ortiz L E and Irfan M T (2017) Tractable algorithms for approximate Nash equilibria in generalized graphical games with tree structure. In: Proceedings of
the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 635-641

Panagopoulou P N and Spirakis P G (2014) Random bimatrix games are asymptotically easy to solve (A simple proof). Theory Comput. Syst. 54:479-490

Papadimitriou C H (1994) On the complexity of the parity argument and other ine¢ cient proofs of existence. Journal of Computer and System Sciences
48:498-532

Powers I (1990) Limiting distributions of the number of pure strategy Nash equilibria in N-person games. International Journal of Game Theory 19:277-286

Roberts D P (2006) Nash equilibria of Cauchy-random zero-sum and coordination matrix games. International Journal of Game Theory 34:167-184

Savani R and von Stengel B. (2004) Exponentially many steps for finding a
Nash equilibrium in a bimatrix game. In: Proceedings of the 45th FOCS. pp,
258-267

Stanford W (1995) A note on the probability of k pure Nash equilibria in matrix games. Games and Economic Behavior 9:238-246

Stanford W (1996) The limit distribution of pure strategy Nash equilibria in symmetric bimatrix games. Mathematics of Operations Research 21:726-733

Tsaknakis H and Spirakis P.G. (2008) An optimization approach for approximate Nash equilibria. Internet Mathematics 5:365-382

Tsaknakis H.and Spirakis P G (2010) A graph spectral approach for computing approximate Nash equilibria. In: Saberi, A. (ed.) WINE 2010. LNCS,
Springer, Heidelberg vol. 6484: 378-390

Weisstein E W (1995) Normal di¤erence distribution. From Mathworld-a
WolframWeb Resource. http://mathworld.wolfram.com/normaldi¤erencedistribution.html

ID Code:3747
Deposited By: Ádám Hoffmann
Deposited On:07 Nov 2018 09:38
Last Modified:30 Nov 2018 11:50

Repository Staff Only: item control page

Downloads

Downloads per month over past year

View more statistics