A note on the complexity of determining optimal strategies in games with common payoffs

DOI10.1007/S001860300300zbMATH Open1069.91001OpenAlexW2112234116MaRDI QIDQ1416783

Gerhard J. Woeginger

Publication date: 16 December 2003

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001860300300

zbMATH Keywords

computational complexityGamescommon payoffs

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) 2-person games (91A05) (n)-person games, (n>2) (91A06) Games in extensive form (91A18)

Recommendations

• On the number of pure strategy Nash equilibria in finite common payoffs games 👍 👎
• On the NP-completeness of finding an optimal strategy in games with common payoffs 👍 👎
• Simple strategies for large zero-sum games with applications to complexity theory 👍 👎
• Complexity and Optimality of the Best Response Algorithm in Random Potential Games 👍 👎
• Simplifying Optimal Strategies in Stochastic Games 👍 👎
• Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games 👍 👎
• The complexity of mean payoff games 👍 👎

This page was built for publication: A note on the complexity of determining optimal strategies in games with common payoffs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1416783)