DocumentCode
2385928
Title
On the complexity of two-player win-lose games
Author
Abbott, Tim ; Kane, Daniel ; Valiant, Paul
Author_Institution
Comput. Sci. & Artificial Intelligence Lab., Massachusetts Inst. of Technol., Cambridge, MA, USA
fYear
2005
fDate
23-25 Oct. 2005
Firstpage
113
Lastpage
122
Abstract
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.
Keywords
computational complexity; game theory; Nash equilibria; computational complexity; two-player game; two-player games; two-player win-lose games; win-or-lose games; Artificial intelligence; Computational complexity; Computer science; Game theory; Laboratories; Linear programming; Nash equilibrium; Probability distribution; Search problems;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Print_ISBN
0-7695-2468-0
Type
conf
DOI
10.1109/SFCS.2005.59
Filename
1530706
Link To Document