Forgó, Ferenc (2018) On symmetric bimatrix games. Working Paper. Corvinus University of Budapest Faculty of Economics, Budapest.
|
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
Bárány I, Vempala S and Vetta A (2005) Nash equilibria in random games.
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
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
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-
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-
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
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
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
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,
Weisstein E W (1995) Normal di¤erence distribution. From Mathworld-a
|
| 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
Download Statistics
Download Statistics