Google Research

Bayesian Repeated Zero-Sum Games with Persistent State, with Application to Security Games

International Conference on Web and Internet Economics (2020), pp. 444-458

Abstract

We study infinitely-repeated two-player zero-sum games with one-sided private information and a persistent state. Here, only one of the two players learns the state of the repeated game. We consider two models: either the state is chosen by nature, or by one of the players. For the former, the equilibrium of the repeated game is known to be equivalent to that of a one-shot public signaling game, and we make this equivalence algorithmic. For the latter, we show equivalence to one-shot team max-min games, and also provide an algorithmic reduction. We apply this framework to repeated zero-sum security games with private information on the side of the defender and provide an almost complete characterization of their computational complexity.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work