The Complexity of Nash Equilibria in Infinite Multiplayer Games

DOI10.1007/978-3-540-78499-9_3zbMath1138.91359OpenAlexW1589508846MaRDI QIDQ5458348

Michael Ummels

Publication date: 11 April 2008

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78499-9_3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) (n)-person games, (n>2) (91A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Incentive Stackelberg Mean-Payoff Games, On Pure Nash Equilibria in Stochastic Games, Unnamed Item, Subgame-perfect Equilibria in Mean-payoff Games (journal version), Constrained existence of weak subgame perfect equilibria in multiplayer Büchi games, Unnamed Item, Unnamed Item, Unnamed Item, A Note on Game Theory and Verification, Unnamed Item, Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives, Robust Equilibria in Mean-Payoff Games, On relevant equilibria in reachability games, The Complexity of Nash Equilibria in Limit-Average Games, Decision Problems for Nash Equilibria in Stochastic Games, Unnamed Item, A game-theoretic approach for the synthesis of complex systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• The complexity of computing a Nash equilibrium
• DAG-width
• Clique-Width and Parity Games
• Computer Science Logic
• Rational Behaviour and Strategy Construction in Infinite Multiplayer Games
• DAG-Width and Parity Games