Premium
Nash equilibria in random games
Author(s) -
Bárány Imre,
Vempala Santosh,
Vetta Adrian
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20199
Subject(s) - nash equilibrium , las vegas , mathematics , stochastic game , best response , combinatorics , simple (philosophy) , epsilon equilibrium , polytope , mathematical economics , medicine , philosophy , metropolitan area , pathology , epistemology
Abstract 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 × n payoff matrices, it runs in time O ( m 2 n loglog n + n 2 m loglog 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. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007