John Fearnley

The Complexity of All-switches Strategy Improvement

2015

Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parametrized by a switching rule, and one of the most natural rules is “all switches” which switches …