×

Nash equilibria in random games. (English) Zbl 1130.91312

Summary: We consider Nash equilibria in 2-player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on \(m \times n\) payoff matrices, it runs in time \(O(m^{2}n \log \log n + n^{2}m \log \log m)\) with high probability. Our result follows from showing that a 2-player random game has a Nash equilibrium with supports of size two with high probability, at least \(1 - O(1/\log n)\). Our main tool is a polytope formulation of equilibria.

MSC:

91A60 Probabilistic games; gambling
91A15 Stochastic games, stochastic differential games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Affentranger, Discrete Comput Geometry 6 pp 291– (1991)
[2] and , The Probabilistic method, 2nd edition, Wiley, New York, 2000.
[3] Bárány, Math Ann 285 pp 671– (1989)
[4] Bárány, Mathematika 35 pp 274– (1988)
[5] Algorithms and Combinatorics, Vol. 1 Springer-Verlag, 1980.
[6] and , Settling the complexity of 2-player Nash-equilibrium, Proceedings of 47th FOCS, Berkeley, October 2006, pp. 267–272.
[7] Devroye, Inform Process Lett 11 pp 53– (1980)
[8] Dickhaut, The Math J 1 pp 87– (1991)
[9] Dresher, J Combin Theory 8 pp 134– (1970)
[10] Dwyer, J Appl Probab 25 pp 688– (1988)
[11] Dwyer, Discrete Appl Math 31 pp 113– (1991)
[12] , and , The complexity of pure-strategy Nash equilibria, Proceedings of 36th STOC, Chicago, June, 2004.
[13] Goldberg, J Res Natl Bur Stand, Section B, 72 pp 93– (1968) · Zbl 0164.20203
[14] Groemer, Pac J Math 45 pp 525– (1973) · Zbl 0258.52004
[15] Heuter, Trans Am Math Soc 351 pp 4337– (1999)
[16] personal communication, 2005.
[17] Kirkpatrick, SIAM J Comput 15 pp 287– (1988)
[18] Lemke, J Soc Ind Appl Math 12 pp 413– (1964)
[19] , and , Playing large games using simple strategies, Proceedings of E-Commerce, San Diego, June, 2003, pp. 36–41.
[20] McLennan, Game Econ Behav 51 pp 264– (2005)
[21] Megiddo, Math Program 35 pp 140– (1986)
[22] Algorithms, games and the internet, Proceedings of 33rd STOC, Heraklion, Crete, July, 2001, pp. 749–753.
[23] , and , Simple search methods for finding a Nash equilibrium, Proceedings of 19th AAAI, San Jose, July, 2004, pp. 664–669.
[24] Raynaud, J Appl Probab 7 pp 35– (1970)
[25] Integral geometry and geometric probability, Addison-Wesley, 1976. · Zbl 0342.53049
[26] and , Exponentially many steps for finding a Nash equilibrium in a bimatrix game, Proceedings of 45th FOCS, Rome, October, 2004, pp. 258–267.
[27] ” Discrete aspects of stochastic geometry,” In Eds. and , Handbook of discrete and computational geometry, Boca Raton, CRC Press, 2004, pp. 255–278.
[28] Smale, Math Program 27 pp 241– (1983)
[29] Spielman, J ACM 51 pp 385– (2004)
[30] van Wel, J Appl Probab 26 pp 259– (1989)
[31] and , ” Stochastic geometry,” In Eds. and , Handbook of convex geometry, North-Holland, Amsterdam, 1993, pp. 1391–1438.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.