An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games

DOI10.1007/978-3-540-87531-4_27MaRDI QIDQ3540191zbMATH OpenOpenAlexFDO

Authors Sven Schewe

Publication date 20 November 2008

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-87531-4_27

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Games involving graphs (91A43)

Recommendations

• scientific article; zbMATH DE number 1670778
• Local strategy improvement for parity game solving
• Efficient parallel strategy improvement for parity games
• Non-oblivious strategy improvement
• Mathematical Foundations of Computer Science 2004

Cited in

(40)

• Incentive Stackelberg mean-payoff games
• Priority promotion with Parysian flair
• scientific article; zbMATH DE number 5292473 (Why is no real title available?)
• Efficient parallel strategy improvement for parity games
• Parity games with weights
• Graph Games and Reactive Synthesis
• Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
• Solving parity games in practice
• Solving mean-payoff games via quasi dominions
• Non-oblivious strategy improvement
• A global optimization algorithm for solving a four-person game
• Recursive algorithm for parity games requires exponential time
• On an algorithm for successive improvement of a strategy
• The complexity of all-switches strategy improvement
• Local strategy improvement for parity game solving
• A flexible toolchain for symbolic Rabin games under fair and stochastic uncertainties
• scientific article; zbMATH DE number 3892974 (Why is no real title available?)
• Solving mean-payoff games via quasi dominions
• The mu-calculus and Model Checking
• Verification of reactive systems via instantiation of parameterised Boolean equation systems
• Symmetric strategy improvement
• Solving parity games using an automata-based algorithm
• Strategy Construction for Parity Games with Imperfect Information
• Solving parity games via priority promotion
• An improved heuristic for the ``Ulam-Rényi game
• Partial solvers for parity games: effective polynomial-time composition
• Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
• Strategy optimization for static games based on STP method
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• scientific article; zbMATH DE number 6790166 (Why is no real title available?)
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• A delayed promotion policy for parity games
• Justifications and a reconstruction of parity game solving algorithms
• From Parity and Payoff Games to Linear Programming
• A delayed promotion policy for parity games
• The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
• Improvement in small progress measures
• A superpolynomial lower bound for strategy iteration based on snare memorization
• Robust worst cases for parity games algorithms

This page was built for publication: An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games

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