The complexity of admissibility in omega-regular games

DOI10.1145/2603088.2603143MaRDI QIDQ4635606zbMATH OpenOpenAlexFDO

Authors Romain Brenguier, Mathieu Sassolas, Jean-François Raskin

Publication date 23 April 2018

Published in Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

synthesisLTLsafetyMuller gamesadmissible strategies

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Abstract: Iterated admissibility is a well-known and important concept in classical game theory, e.g. to determine rational behaviors in multi-player matrix games. As recently shown by Berwanger, this concept can be soundly extended to infinite games played on graphs with omega-regular objectives. In this paper, we study the algorithmic properties of this concept for such games. We settle the exact complexity of natural decision problems on the set of strategies that survive iterated elimination of dominated strategies. As a byproduct of our construction, we obtain automata which recognize all the possible outcomes of such strategies.

Recommendations

• Admissibility in Infinite Games
• The computational complexity of iterated elimination of dominated strategies
• Admissible Strategies in Infinite Games over Graphs
• scientific article; zbMATH DE number 6862070
• On iterated dominance, matrix elimination, and matched paths

Cited in

(14)

• scientific article; zbMATH DE number 7447732 (Why is no real title available?)
• A game-theoretic approach for the synthesis of complex systems
• The complexity of subgame perfect equilibria in quantitative reachability games
• Iterated regret minimization in game graphs
• Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives
• On the existence of weak subgame perfect equilibria
• On the existence of weak subgame perfect equilibria
• scientific article; zbMATH DE number 7649921 (Why is no real title available?)
• Admissibility in Infinite Games
• scientific article; zbMATH DE number 6862070 (Why is no real title available?)
• scientific article; zbMATH DE number 7447731 (Why is no real title available?)
• Dynamic hierarchical reactive controller synthesis
• Assume-admissible synthesis
• scientific article; zbMATH DE number 7533335 (Why is no real title available?)

This page was built for publication: The complexity of admissibility in omega-regular games

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