Nash Equilibria in Random Games

Pittsburgh, Pennsylvania, USA October 23-October 25

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.52

46th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Imre Barany Articles by Santosh Vempala Articles by Adrian Vetta

	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

Santosh Vempala, MIT

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.