An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games

DOI10.1007/978-3-540-87531-4_27zbMath1156.68478OpenAlexW1887255787MaRDI QIDQ3540191

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

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

Related Items (26)

Symmetric Strategy Improvement ⋮ The mu-calculus and Model Checking ⋮ Graph Games and Reactive Synthesis ⋮ From Parity and Payoff Games to Linear Programming ⋮ Incentive Stackelberg Mean-Payoff Games ⋮ Unnamed Item ⋮ Robust worst cases for parity games algorithms ⋮ Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Justifications and a reconstruction of parity game solving algorithms ⋮ Solving mean-payoff games via quasi dominions ⋮ Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Solving parity games via priority promotion ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Verification of reactive systems via instantiation of parameterised Boolean equation systems ⋮ A delayed promotion policy for parity games ⋮ Solving Parity Games Using an Automata-Based Algorithm ⋮ Solving Parity Games in Practice ⋮ Recursive algorithm for parity games requires exponential time

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