On symmetric bimatrix games

Ferenc Forgó

Corvinus Economics Working Papers (CEWP) from Corvinus University of Budapest

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.

Keywords: bimatrix game; random games; experimental games; complexity (search for similar items in EconPapers)
JEL-codes: C72 (search for similar items in EconPapers)
Date: 2018-11-07
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations:

Downloads: (external link)
https://unipub.lib.uni-corvinus.hu/3747/ original version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cvh:coecwp:2018/04

Access Statistics for this paper

More papers in Corvinus Economics Working Papers (CEWP) from Corvinus University of Budapest 1093 Budapest, Fõvám tér 8.. Contact information at EDIRC.
Bibliographic data for series maintained by Adam Hoffmann ().