On Subgame Perfect Equilibria in Turn-Based Reachability Timed Games

2020/06/18 by Brihaye, Thomas, Goeminne, Aline
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2006.10491

Abstract

We study multiplayer turn-based timed games with reachability objectives. In particular, we are interested in the notion of subgame perfect equilibrium (SPE). We prove that deciding the constrained existence of an SPE in this setting is EXPTIME-complete.

Related

• Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability
• Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives (full version)
• Subgame-perfect Equilibria in Mean-payoff Games
• On the Complexity of SPEs in Parity Games
• Permissive Equilibria in Multiplayer Reachability Games