loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
Nash Equilibria in Random Games
Pittsburgh, Pennsylvania, USA
October 23-October 25
ISBN: 0-7695-2468-0
ASCII Text
x 
 
Imre Barany, Santosh Vempala, Adrian Vetta, "Nash Equilibria in Random Games," Foundations of Computer Science, Annual IEEE Symposium on, pp. 123-131, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2005.52,
author = {Imre Barany and Santosh Vempala and Adrian Vetta},
title = {Nash Equilibria in Random Games},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2005},
isbn = {0-7695-2468-0},
pages = {123-131},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.52},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - Nash Equilibria in Random Games
SN - 0-7695-2468-0
SP123
EP131
A1 - Imre Barany,
A1 - Santosh Vempala,
A1 - Adrian Vetta,
PY - 2005
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
Imre Barany, Imre Barany
Adrian Vetta, Adrian Vetta

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

Citation:
Imre Barany, Santosh Vempala, Adrian Vetta, "Nash Equilibria in Random Games," focs, pp.123-131, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.