Pivoting algorithms for some classes of stochastic games: A survey (Q2772856)

Pivoting algorithms are the well-known simplex algorithm or the Lemke-Howson algorithm for solving a linear programming (LP) or a linear complementarity problem (LCP), resp. These also are the key algorithms for solving a matrix or bimatrix game, resp. and lead in general after a finite number of steps to a solution. A pleasing fact is that, although not all but a considerable number of classes of zero-sum or nonzero-sum stochastic games can be transformed into a single LP or LCP, resp. This holds for the discounted total as well as for the limiting average return problem position. NEWLINENEWLINENEWLINEThe authors who have already published together several papers, give a comprehensive survey on classes of stochastic games which can be solved by pivoting algorithms and, how to practice it, and they refer to many original papers that have been published recently. The classes are: One-player control, SER-SIT, switching control, ARAT and vertical LCP. Of course, for the nonzero-sum case, not so many results exist as for the zero-sum case. The survey also includes a few new results and observations.