TY - GEN
T1 - LP formulation of asymmetric zero-sum stochastic games
AU - Li, Lichun
AU - Shamma, Jeff
N1 - Funding Information:
This work is partially funded by the National Science Foundation of China under Grant 61170165, 61602260, 61502095. We would like to thank all the anonymous reviewers for their helpful comments.
Publisher Copyright:
© 2014 IEEE.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84988289225&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84988289225&partnerID=8YFLogxK
U2 - 10.1109/CDC.2014.7039680
DO - 10.1109/CDC.2014.7039680
M3 - Conference contribution
AN - SCOPUS:84988289225
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 1930
EP - 1935
BT - 53rd IEEE Conference on Decision and Control,CDC 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014
Y2 - 15 December 2014 through 17 December 2014
ER -