Efficient computation of discounted asymmetric information zero-sum stochastic games

Lichun Li, Jeff S. Shamma

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

7 Scopus citations

Abstract

In asymmetric information zero-sum games, one player has superior information about the game over the other. Asymmetric information games are particularly relevant for security problems, e.g., where an attacker knows its own skill set or alternatively a system administrator knows the state of its resources. In such settings, the informed player is faced with the tradeoff of exploiting its superior information at the cost of revealing its superior information. This tradeoff is typically addressed through randomization, in an effort to keep the uninformed player informationally off balance. A lingering issue is the explicit computation of such strategies. This paper, building on prior work for repeated games, presents an LP formulation to compute suboptimal strategies for the informed player in discounted asymmetric information stochastic games in which state transitions are not affected by the uninformed player. Furthermore, the paper presents bounds between the security level guaranteed by the sub-optimal strategy and the optimal value. The results are illustrated on a stochastic intrusion detection problem.
Original languageEnglish (US)
Title of host publication2015 54th IEEE Conference on Decision and Control (CDC)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages4531-4536
Number of pages6
ISBN (Print)9781479978861
DOIs
StatePublished - Feb 29 2016

Fingerprint Dive into the research topics of 'Efficient computation of discounted asymmetric information zero-sum stochastic games'. Together they form a unique fingerprint.

Cite this