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
Subjects:Mathematics, Econometrics
Projects:NKFI K-1 119930
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