The complexity of decision problems about nash equilibria in win-lose games
作者： Vittorio Bilò , Marios Mavronicolas
DOI: 10.1007/978-3-642-33996-7_4
关键词:
摘要: We revisit the complexity of deciding, given a (finite) strategic game, whether Nash equilibria with certain natural properties exist; such decision problems are well-known to be $\cal NP$-complete [2, 6, 10] . show that this remains unchanged when all utilities restricted 0 or 1; thus, win-lose games as complex general respect problems.
springer.com
sci-hub.st 参考文章(18)
Gianni Dal Maso, Ennio De Giorgi Vite matematiche. pp. 205- 216 ,(2007) , 10.1007/978-88-470-0640-9_17
Nimrod Megiddo, Christos H. Papadimitriou, On total functions, existence theorems and computational complexity Theoretical Computer Science. ,vol. 81, pp. 317- 324 ,(1991) , 10.1016/0304-3975(91)90200-L
Paul Valiant, Shang-Hua Teng, Xi Chen, The approximation complexity of win-lose games symposium on discrete algorithms. pp. 159- 168 ,(2007) , 10.5555/1283383.1283401
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou, The Complexity of Computing a Nash Equilibrium SIAM Journal on Computing. ,vol. 39, pp. 195- 259 ,(2009) , 10.1137/070699652
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Vincent Conitzer, Tuomas Sandholm, New complexity results about Nash equilibria Games and Economic Behavior. ,vol. 63, pp. 621- 641 ,(2008) , 10.1016/J.GEB.2008.02.015
Bruno Codenotti, Daniel Štefankovič, On the computational complexity of Nash equilibria for (0,1) bimatrix games Information Processing Letters. ,vol. 94, pp. 145- 150 ,(2005) , 10.1016/J.IPL.2005.01.010
Xi Chen, Xiaotie Deng, Shang-Hua Teng, Settling the complexity of computing two-player Nash equilibria Journal of the ACM. ,vol. 56, pp. 1- 57 ,(2009) , 10.1145/1516512.1516516
J. F. Nash, Equilibrium points in n-person games Proceedings of the National Academy of Sciences. ,vol. 36, pp. 48- 49 ,(1950) , 10.1073/PNAS.36.1.48