On symmetric bimatrix games

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.