Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
2 results

The Complexity of All-switches Strategy Improvement

John Fearnley ; Rahul Savani.
Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parameterized by a switching rule, and one of the most natural rules is "all switches" which switches as many edges as possible in each iteration. Continuing a&nbsp;[&hellip;]
Published on October 31, 2018
Volume 14, Issue 4

Reachability Switching Games

John Fearnley ; Martin Gairing ; Matthias Mnich ; Rahul Savani.
We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case&nbsp;[&hellip;]
Published on April 22, 2021
Volume 17, Issue 2
  • < Previous
  • 1
  • Next >