Solving subclasses of multi‐player stochastic games via linear complementarity problem formulations–a survey and some new results

Solving subclasses of multi‐player stochastic games via linear complementarity problem formulations–a survey and some new results

0.00 Avg rating0 Votes
Article ID: iaor20124822
Volume: 13
Issue: 3
Start Page Number: 435
End Page Number: 457
Publication Date: Sep 2012
Journal: Optimization and Engineering
Authors: , ,
Keywords: optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.