LP formulation of asymmetric zero-sum stochastic games

Lichun Li, Jeff S. Shamma

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations

Abstract

This paper provides an efficient linear programming (LP) formulation of asymmetric two player zero-sum stochastic games with finite horizon. In these stochastic games, only one player is informed of the state at each stage, and the transition law is only controlled by the informed player. Compared with the LP formulation of extensive stochastic games whose size grows polynomially with respect to the size of the state and the size of the uninformed player's actions, our proposed LP formulation has its size to be linear with respect to the size of the state and the size of the uninformed player, and hence greatly reduces the computational complexity. A travelling inspector problem is used to demonstrate the efficiency of the proposed LP formulation.
Original languageEnglish (US)
Title of host publication53rd IEEE Conference on Decision and Control
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1930-1935
Number of pages6
ISBN (Print)9781467360906
DOIs
StatePublished - Feb 17 2015
Externally publishedYes

Fingerprint

Dive into the research topics of 'LP formulation of asymmetric zero-sum stochastic games'. Together they form a unique fingerprint.

Cite this