On the NP-completeness of finding an optimal strategy in games with common payoffs

DOI10.1007/s001820100066zbMath1052.91004arXivcs/0103019OpenAlexW1800198041MaRDI QIDQ1414388

Joseph Y. Halpern, Francis C. Chu

Publication date: 23 November 2003

Published in: International Journal of Game Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0103019

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) (n)-person games, (n>2) (91A06) Games in extensive form (91A18)

Related Items

Computing equilibria: a computational complexity perspective, Revealed Preference Tests of Collectively Rational Consumption Behavior: Formulations and Algorithms, The computational complexity of rationalizing boundedly rational choice behavior, A Logic for Reasoning about Rational Agents, Reasoning about temporal properties of rational play