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 |
| 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
