On the Complexity of Two-PlayerWin-Lose Games

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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 Tim Abbott Articles by Daniel Kane Articles by Paul Valiant

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)

Pittsburgh, Pennsylvania, USA

October 23-October 25

ISBN: 0-7695-2468-0

	ASCII Text	x
	Tim Abbott, Daniel Kane, Paul Valiant, "On the Complexity of Two-PlayerWin-Lose Games," Foundations of Computer Science, Annual IEEE Symposium on, pp. 113-122, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.

	BibTex	x
	@article{ 10.1109/SFCS.2005.59, author = {Tim Abbott and Daniel Kane and Paul Valiant}, title = {On the Complexity of Two-PlayerWin-Lose Games}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2005}, isbn = {0-7695-2468-0}, pages = {113-122}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.59}, 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 - On the Complexity of Two-PlayerWin-Lose Games SN - 0-7695-2468-0 SP113 EP122 A1 - Tim Abbott, A1 - Daniel Kane, A1 - Paul Valiant, PY - 2005 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Tim Abbott, MIT

Daniel Kane, MIT

Paul Valiant, MIT, Computer Science and Artificial Intelligence Laboratory

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.59

The efficient computation of Nash equilibria is one of the most formidable challenges in computational complexity today. The problem remains open for two-player games. We show that the complexity of two-player Nash equilibria is unchanged when all outcomes are restricted to be 0 or 1. That is, win-or-lose games are as complex as the general case for two-player games.

Citation:

Tim Abbott, Daniel Kane, Paul Valiant, "On the Complexity of Two-PlayerWin-Lose Games," focs, pp.113-122, 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.