Existence of structured perfect Bayesian equilibrium in dynamic games of asymmetric information

Authors in [1] considered a model consisting of strategic players having types that evolve as conditionally independent Markov controlled processes. Players observe their types privately and actions taken by all players are observed publicly. Instantaneous reward for each player depends on everyone’s types and actions. The proposed methodology provides a decomposition of the interdependence between beliefs and strategies in PBE and enables a systematic evaluation of a subset of PBE, namely structured perfect Bayesian equilibria (SPBE). Here SPBE are defined as equilibria with players strategies based on their current private type and a set of beliefs on each player’s current private type, which is common to all the players and whose domain is time-invariant. The beliefs on players’ types are such that they can be updated individually for each player and sequentially w.r.t. time. The model allows for signaling amongst players as beliefs depend on strategies. They present a sequential decomposition methodology for calculating all SPBEs for finite and infinite horizon dynamic games with asymmetric information.

For the finite horizon model, they provide a two-step algorithm involving a backward recursion followed by a forward recursion. The algorithm works as follows. In the backward recursion, for every time period, the algorithm finds an equilibrium generating function defined for all possible common beliefs at that time. This involves solving a one-step fixed point equation on the space of probability simplexes. Existence of this fixed-point equation was left as an open question. If there exists a solution for every common belief $\pi_{t}$, then the equilibrium strategies and beliefs are obtained through a forward recursion using the equilibrium generating function obtained in the backward step and the Bayes update rule. A similar notion of equilibrium was defined in [2, 3] where authors provide a sequential decomposition algorithm to compute common information based perfect Bayesian equilibrium. In [3], it was shown that such an equilibrium exists for zero-sum games.

In this paper, we consider the finite horizon game with all sets of variables in a compact metric space. We show that there always exists an SPBE for such a game. Since it is proved in [1] that all SPBEs can be found using their algorithm, we conclude that there always exists a solution to the fixed-point equation considered in [1] for each time period $t$.

We consider a discrete-time dynamical system with $N$ strategic players in the set $\mathcal{N}\buildrel\triangle\over{=}\{1,2,\ldots N\}$. We consider two cases: finite horizon $\mathcal{T}\buildrel\triangle\over{=}\{1,2,\ldots T\}$ with perfect recall and infinite horizon with perfect recall. The system state is $X_{t}\buildrel\triangle\over{=}(X_{t}^{1},X_{t}^{2},\ldots X_{t}^{N})$, where $X_{t}^{i}\in\mathcal{X}^{i}$ is the type of player $i$ at time $t$, which is perfectly observed and is its private information. Players’ types evolve as conditionally independent, controlled Markov processes such that

where $Q^{i}_{t}$ are known kernels. Player $i$ at time $t$ takes action $a_{t}^{i}\in\mathcal{A}^{i}$ on observing the actions $a_{1:t-1}=(a_{k})_{k=1,\ldots,t-1}$ where $a_{k}=\left(a_{k}^{j}\right)_{j\in\mathcal{N}}$, which is common information among players, and the types $x_{1:t}^{i}$, which it observes privately. The sets $\mathcal{A}^{i},\mathcal{X}^{i}$ are assumed to be finite. Let $g^{i}=(g^{i}_{t})_{t\in\mathcal{T}}$ be a probabilistic strategy of player $i$ where $g^{i}_{t}:\mathcal{A}^{t-1}\times(\mathcal{X}^{i})^{t}\to\Delta(\mathcal{A}^{i})$ such that player $i$ plays action $A_{t}^{i}$ according to $A_{t}^{i}\sim g^{i}_{t}(\cdot|a_{1:t-1},x_{1:t}^{i})$. Let $g\buildrel\triangle\over{=}(g^{i})_{i\in\mathcal{N}}$ be a strategy profile of all players. At the end of interval $t$, player $i$ receives an instantaneous reward $R_{t}^{i}(x_{t},a_{t})$. To preserve the information structure of the problem, it is assumed that players do not observe their rewards until the end of game.¹¹1Alternatively, we could have assumed instantaneous reward of a player to depend only on its own type, i.e. be of the form $R_{t}^{i}(x_{t}^{i},a_{t})$, and have allowed rewards to be observed by the players during the game as this would not alter the information structure of the game The reward functions and state transition kernels are common knowledge among the players. For the finite-horizon problem, the objective of player $i$ is to maximize its total expected reward

At any time $t$, player $i$ has information $(a_{1:t-1},x_{1:t}^{i})$ where $a_{1:t-1}$ is the common information among players, and $x_{1:t}^{i}$ is the private information of player $i$. Since $(a_{1:t-1},x_{1:t}^{i})$ increases with time, any strategy of the form $A_{t}^{i}\sim g^{i}_{t}(\cdot|a_{1:t-1},x_{1:t}^{i})$ becomes unwieldy. Thus it is desirable to have an information state in a time-invariant space that succinctly summarizes $(a_{1:t-1},x_{1:t}^{i})$, and that can be sequentially updated. IFor any strategy profile $g$, belief $\pi_{t}$ on $X_{t}$, $\pi_{t}\in\Delta(\mathcal{X})$, is defined as $\pi_{t}(x_{t})\buildrel\triangle\over{=}\mathbb{P}^{g}(X_{t}=x_{t}|a_{1:t-1}),\;\forall x_{t}\in\mathcal{X}$. Define the marginals $\pi_{t}^{{i}}(x_{t}^{i})\buildrel\triangle\over{=}\mathbb{P}^{g}(X_{t}^{i}=x_{t}^{i}|a_{1:t-1}),\;\forall x_{t}^{i}\in\mathcal{X}^{i}$.

Then using common information approach [5], the problem is posed as follows: player $i$ at time $t$ observes $a_{1:t-1}$ and takes action $\gamma_{t}^{i}$, where $\gamma_{t}^{i}:\mathcal{X}^{i}\to\Delta(\mathcal{A}^{i})$ is a partial (stochastic) function from its private information $x_{t}^{i}$ to $a_{t}^{i}$, of the form $A_{t}^{i}\sim\gamma_{t}^{i}(\cdot|x_{t}^{i})$. These actions are generated through some policy $\psi^{i}=(\psi^{i}_{t})_{t\in\mathcal{T}}$, $\psi^{i}_{t}:\mathcal{A}^{t-1}\to\left\{\mathcal{X}^{i}\to\Delta(\mathcal{A}^{i})\right\}$, that operates on the common information $a_{1:t-1}$ such that $\gamma_{t}^{i}=\psi_{t}^{i}[a_{1:t-1}]$. Then any policy of the form $A_{t}^{i}\sim s_{t}^{i}(\cdot|a_{1:t-1},x_{t}^{i})$ is equivalent to $A_{t}^{i}\sim\psi^{i}_{t}[a_{1:t-1}](\cdot|x_{t}^{i})$.

In this section, we present the main result of this paper where we show that for all $\forall\underline{\pi}_{t}\in\times_{i\in\mathcal{N}}\Delta(\mathcal{X}^{i}),\pi_{t}=\prod_{i\in\mathcal{N}}\pi_{t}^{i}$, there always exists a $\tilde{\gamma}=\theta[\pi_{t}]$ that satisfies (9). We show that existence holds true for any compact metric spaces $\mathcal{X},\mathcal{A}$. Let $\Sigma$ be the set of all mixed strategies of the form $\sigma_{t}^{i}(\cdot|a_{1:t-1},x_{1:t}^{i})$ and $\Sigma^{\prime}$ be the set of all mixed strategies of the form $\sigma_{t}^{i}(\cdot|a_{1:t-1},x_{t}^{i})$. Then both $\Sigma,\Sigma^{\prime}$ are compact.

Remark In this paper, we showed that there exists a solution of smaller fixed-point equations (9) for each $t,\pi_{t}$ by showing that there exists a solution to the fixed-point equation which is the Nash equilibrium of the whole game, using Glicksberg Fixed-point equation. It is interesting because the smaller fixed-point equations may and does have discontinuous utilities, as seen through numerical solutions. There have been some results known in existence of solutions of games with discontinuous utilities [8, 9]. It would be an interesting exercise to explore the connection between existence of the two results.

Authors in [1] proposed a novel methodology to find structured perfect Bayesian equilibria of a general model of dynamic games of asymmetric information where players observe their types privately, which evolve as a controlled Markov process, condition on everyones actions. Players also observe everyone’s actions publicly. In this paper, we prove the existence of the fixed-point equation that crucially appears in their methodology for each time $t$ and that was left open in that paper.

The author would like to thank K.S. Mallikarjuna Rao for suggestion to prove existence of SPBE.