The Complexity of Infinitely Repeated Alternating Move Games

DOI10.1007/978-3-642-39206-1_69zbMath1336.68149arXiv1212.6632OpenAlexW30794926MaRDI QIDQ5326613

Yaron Velner

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Games in extensive form (91A18) Multistage and repeated games (91A20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Polynomial-time algorithms for energy games with special weight structures
• Faster algorithms for mean-payoff games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Positional strategies for mean payoff games
• The complexity of mean payoff games on graphs
• Mean Cost Cyclical Games
• The Complexity of Nash Equilibria in Limit-Average Games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs

This page was built for publication: The Complexity of Infinitely Repeated Alternating Move Games