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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom