Sequential decomposition of repeated games with asymmetric information and dependent states
For game theorists and economists studying dynamic games with asymmetric information, this work provides a computationally efficient method to find equilibria, though it is incremental as it builds on prior SPBE concepts.
This paper tackles the problem of computing equilibria in finite horizon repeated games with asymmetric information and dependent states, where standard Perfect Bayesian Equilibrium (PBE) complexity grows double-exponentially in time. They present a sequential decomposition methodology that computes structured perfect Bayesian equilibria (SPBE) in linear time.
We consider a finite horizon repeated game with $N$ selfish players who observe their types privately and take actions, which are publicly observed. Their actions and types jointly determine their instantaneous rewards. In each period, players jointly observe actions of each other with delay 1, and private observations of the state of the system, and get an instantaneous reward which is a function of the state and everyone's actions. The players' types are static and are potentially correlated among players. An appropriate notion of equilibrium for such games is Perfect Bayesian Equilibrium (PBE) which consists of a strategy and a belief profile of the players which is coupled across time and as a result, the complexity of finding such equilibria grows double-exponentially in time. We present a sequential decomposition methodology to compute \emph{structured perfect Bayesian equilibria} (SPBE) of this game, introduced in~\cite{VaAn15arxiv}, where equilibrium policy of a player is a function of a common belief and a private state. This methodology computes SPBE in linear time. In general, the SPBE of the game problem exhibit \textit{signaling} behavior, i.e. players' actions reveal part of their private information that is payoff relevant to other players.