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

DOI10.1007/978-3-642-24372-1_11zbMATH Open1348.68093arXiv1102.3615OpenAlexW1887826286MaRDI QIDQ3172910FDOQ3172910

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

Publication date: 7 October 2011

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

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.

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

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
• scientific article; zbMATH DE number 7730610
• Reduction of stochastic parity to stochastic mean-payoff games

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)

Cited In (12)

• A logic with revocable and refinable strategies
• Title not available (Why is that?)
• Compositional construction of most general controllers
• Energy parity games
• Strategy synthesis for multi-dimensional quantitative objectives
• Quantitative reductions and vertex-ranked infinite games
• Permissive strategies: from parity games to safety games
• Down the Borel hierarchy: solving Muller games via safety games
• Poster Abstract: Permissiveness for Strategy Adaptation
• Equilibrium in two-player stochastic games with shift-invariant payoffs
• Synthesizing permissive winning strategy templates for parity games
• Title not available (Why is that?)

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)