  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)}\cdot 2^n$-time. Prior to our work no deterministic
algorithm running in time $2^{o(n\log n)}$ regardless of the discount factor
was known.
  We call our approach polyhedral value iteration. We rely on a well-known fact
that the values of a discounted game can be found from the so-called optimality
equations. In the algorithm we consider a polyhedron obtained by relaxing
optimality equations. We iterate points on the border of this polyhedron by
moving each time along a carefully chosen shift as far as possible. This
continues until the current point satisfies optimality equations.
  Our approach is heavily inspired by a recent algorithm of Dorfman et al.
(ICALP 2019) for energy games. For completeness, we present their algorithm in
terms of polyhedral value iteration. Our exposition, unlike the original
algorithm, does not require edge weights to be integers and works for arbitrary
real weights.
