Polyhedral value iteration for discounted games and energy games

Alexander Kozachinskiy

We present a deterministic algorithm, solving discounted games with $n$ nodes in $n^{O(1)}\cdot (2+\sqrt{2}{)}^n$-time. For bipartite discounted games our algorithm runs in $n^{O(1…