Solving Infinite-Horizon Discounted Markov Games Using a Superharmonic Least-Element Algorithm

In this paper we present an algorithm for solving infinite-horizon discounted Markov games based upon the fact that the value function is a least element of a superharmonic set. The algorithm produces a pair of policies whose value function is within a specified error of the solution to the fixed point equation. Part of the algorithm involves solving a set of fractional programs which are replaced by equivalent linear programs.