On Random Symmetric Bimatrix Games

József Abaffy () and Ferenc Forgó
Additional contact information
József Abaffy: Institute of Applied Mathematics, Óbuda University, 1034 Budapest, Bécsi út 96/b, Hungary
Ferenc Forgó: Department of Operations Research and Actuarial Sciences, Corvinus University of Budapest, 1093 Budapest, Fővám tér 8, Hungary

International Game Theory Review (IGTR), 2020, vol. 22, issue 03, 1-16

Abstract: An experiment was conducted on a sample of 500 randomly generated symmetric bimatrix games with size 12 and 15. Distribution of support sizes 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 nonsymmetric and all NEPs 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)
Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198920500024
Access to full text is restricted to subscribers

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:wsi:igtrxx:v:22:y:2020:i:03:n:s0219198920500024

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198920500024

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().