Title :
Nash equilibria in random games
Author :
Bárány, Imre ; Vempala, Santosh ; Vetta, Adrian
Author_Institution :
R ´´enyi Inst. of Math., Hungarian Acad. of Sci., Hungary
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(m2n log log n + n2m log log m) with high probability. Our main tool is a polytope formulation of equilibria.
Keywords :
combinatorial mathematics; computational complexity; game theory; Las Vegas algorithm; Nash equilibria; combinatorial algorithm; polytope formulation; random games; Algorithm design and analysis; Educational institutions; Game theory; Gaussian distribution; Linear programming; Mathematics; Nash equilibrium; Polynomials; Probability distribution; Symmetric matrices;
Conference_Titel :
Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Print_ISBN :
0-7695-2468-0
DOI :
10.1109/SFCS.2005.52
