Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited

DOI10.1007/978-3-642-24372-1_11MaRDI QIDQ3172910zbMATH OpenOpenAlexFDO

Authors Patricia Bouyer, Nicolas Markey, J. Olschewski, Michael Ummels

Publication date 7 October 2011

Published in Automated Technology for Verification and Analysis (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Semantics in the theory of computing (68Q55)

Abstract: We study nondeterministic strategies in parity games with the aim of computing a most permissive winning strategy. Following earlier work, we measure permissiveness in terms of the average number/weight of transitions blocked by the strategy. Using a translation into mean-payoff parity games, we prove that the problem of computing (the permissiveness of) a most permissive winning strategy is in NP intersected coNP. Along the way, we provide a new study of mean-payoff parity games. In particular, we prove that the opponent player has a memoryless optimal strategy and give a new algorithm for solving these games.

Recommendations

• Measuring Permissivity in Finite Games
• Permissive strategies: from parity games to safety games
• Pareto curves of multidimensional mean-payoff games
• Perfect-information stochastic mean-payoff parity games
• A survey of partial-observation stochastic parity games
• Mean-payoff games with partial-observation (extended abstract)
• scientific article; zbMATH DE number 6538214
• scientific article; zbMATH DE number 7730610
• Reduction of stochastic parity to stochastic mean-payoff games

Cited in

(12)

• scientific article; zbMATH DE number 7447730 (Why is no real title available?)
• A logic with revocable and refinable strategies
• Energy parity games
• Compositional construction of most general controllers
• Quantitative reductions and vertex-ranked infinite games
• Permissive strategies: from parity games to safety games
• Faster algorithms for mean-payoff parity games
• Down the Borel hierarchy: solving Muller games via safety games
• Poster Abstract: Permissiveness for Strategy Adaptation
• Measuring Permissivity in Finite Games
• Equilibrium in two-player stochastic games with shift-invariant payoffs
• Synthesizing permissive winning strategy templates for parity games

This page was built for publication: Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited

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