Header menu link for other important links
X
Solving subclasses of multi-player stochastic games via linear complementarity problem formulations-a survey and some new results
, Parthasarathy T., Ravindran G.
Published in Springer Nature
2012
Volume: 13
   
Issue: 3
Pages: 435 - 457
Abstract
We briefly survey some results on the orderfield property of 2-player and multi-player stochastic games and their mixtures. Some of these classes of stochastic games can be solved by formulating them as a Linear Complementarity Problem (LCP) or (Generalized) Vertical Linear Complementarity Problem (VLCP). We discuss some of these results and prove that certain new subclasses and mixtures of multi-player (or n-person) stochastic games can be solved via LCP formulations. Mohan, Neogy and Parthasarathy (in Proceedings of the International Conference on Complementarity Problems, 1997) proposed an LCP formulation of β-discounted (multi-player) polystochastic games where the transitions are controlled by one player, and proved that this LCP is processible by Lemke's algorithm. Using this formulation repeatedly, we prove that we can solve a subclass of β-discounted switching control polystochastic games. As our proof is constructive, we have an algorithm for solving this subclass. This algorithm only involves iteratively solving different LCPs and hence, it follows that this subclass has the orderfield property, a question left open in the paper on orderfield property of mixtures of stochastic games by Krishnamurthy et al., (Indian J. Stat. 72:246-275, 2010). Furthermore, we use results from Krishnamurthy et al., Indian J. Stat. 72:246-275, (2010) to solve some mixture classes using LCP (or VLCP) formulations. We also propose two different VLCP formulations for β-discounted zero-sum perfect information stochastic games, the underlying matrices of both formulations being R 0. As a result, we also have an alternative proof of the orderfield property of such games. © 2011 Springer Science+Business Media, LLC.
About the journal
JournalData powered by TypesetOptimization and Engineering
PublisherData powered by TypesetSpringer Nature
Open AccessNo