Pivoting algorithms for some classes of stochastic games: A survey
Lemke-Howson algorithmlinear complementarity problemlinear programmingpivoting algorithmsimplex algorithmstochastic game
Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance (91-02) Stochastic games, stochastic differential games (91A15)
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.
- A finite algorithm for the switching control stochastic game
- A finite step algorithm via a bimatrix game to a single controller non- zero sum stochastic game
- An algorithm for discounted switching control stochastic games
- An orderfield property for stochastic games when one player controls transition probabilities
- Bimatrix Equilibrium Points and Mathematical Programming
- Discounted, positive, and noncooperative stochastic games
- Equilibrium Points of Bimatrix Games
- Existence and Uniqueness of Equilibrium Points for Concave N-Person Games
- Linear complementarity and discounted switching controller stochastic games
- Linear Programming and Markov Decision Chains
- Linear programming and undiscounted stochastic games in which one player controls transitions
- Non-cooperative games
- Noncooperative Stochastic Games
- Polytope games
- Stochastic games
- Stochastic Games
- Vertical linear complementarity and discounted zero-sum stochastic games with ARAT structure
- Completely mixed strategies for generalized bimatrix and switching controller stochastic game
- Preface: International conference on game theory and optimization, June 6--10, 2016, Indian Institute of Technology Madras, Chennai, India
- Orderfield property of mixtures of stochastic games
- Linear programming and zero-sum two-person undiscounted semi-Markov games
- On discounted AR-AT semi-Markov games and its complementarity formulations
- Max Plus Algebra, Optimization and Game Theory
- Linear complementarity and P-matrices for stochastic games
- Solving subclasses of multi-player stochastic games via linear complementarity problem formulations -- a survey and some new results
- On solving mean payoff games using pivoting algorithms
- Discounted semi-Markov games and algorithms for solving two structured classes
- A policy improvement algorithm for solving a mixture class of perfect information and AR-at semi-Markov games
- On hidden \(\mathbf{Z}\)-matrices and the linear complementarity problem
- Stationary equilibria in discounted stochastic games
- Completely mixed strategies for two structured classes of semi-Markov games, principal pivot transform and its generalizations
- More on Scarf's complementarity problem and its error bounds
- Generalized principal pivot transforms, complementarity theory and their applications in stochastic games
- On some special matrices and their applications in linear complementarity problem
- Vertical block matrices and vertical linear complementarity problem
- On Lemke processibility of LCP formulations for solving discounted switching control stochastic games
This page was built for publication: Pivoting algorithms for some classes of stochastic games: A survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2772856)
