Nash equilibria in random games

By Imre Bárány, Santosh Srinivas Vempala, Adrian R. Vetta. 2005

84 citations recorded by the source corpus.

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 /spl times/ n payoff matrices, it runs in time O(m/sup 2/n log log n + n/sup 2/m log log m) with high probability. Our main tool is a polytope formulation of equilibria.

Subfields: Economics and Econometrics, Management Science and Operations Research, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

1. Simon Lacoste-Julien
2. Gauthier Gidel

In Management Science and Operations Research

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Tony Jebara

In Game & Decision Theory

1. Simon Lacoste-Julien
2. Gauthier Gidel

Citations in the corpus

• Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “Empirically, faster rates seem to arise if the solution is at a corner (a pure equilibrium, to be expected for random payoff matrices in light of (B´ar´any et al., 2007)).”