| 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(m2nloglog n + n2mloglog 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 |
