1

A systematic process for evaluating structured
perfect Bayesian equilibria in dynamic games with
asymmetric information
arXiv:1508.06269v3 [math.OC] 18 Mar 2018

Deepanshu Vasal, Abhinav Sinha and Achilleas Anastasopoulos
Abstract
We consider both finite-horizon and infinite-horizon versions of a dynamic game with N selfish players who
observe their types privately and take actions that are publicly observed. Players’ types evolve as conditionally
independent Markov processes, conditioned on their current actions. Their actions and types jointly determine
their instantaneous rewards. In dynamic games with asymmetric information a widely used concept of equilibrium
is perfect Bayesian equilibrium (PBE), which consists of a strategy and belief pair that simultaneously satisfy
sequential rationality and belief consistency. In general, there does not exist a universal algorithm that decouples
the interdependence of strategies and beliefs over time in calculating PBE. In this paper, for the finite-horizon game
with independent types we develop a two-step backward-forward recursive algorithm that sequentially decomposes
the problem (w.r.t. time) to obtain a subset of PBEs, which we refer to as structured Bayesian perfect equilibria
(SPBE). In such equilibria, a player’s strategy depends on its history only through a common public belief and
its current private type. The backward recursive part of this algorithm defines an equilibrium generating function.
Each period in the backward recursion involves solving a fixed-point equation on the space of probability simplexes
for every possible belief on types. Using this function, equilibrium strategies and beliefs are generated through
a forward recursion. We then extend this methodology to the infinite-horizon model, where we propose a timeinvariant single-shot fixed-point equation, which in conjunction with a forward recursive step, generates the SPBE.
Sufficient conditions for the existence of SPBE are provided. With our proposed method, we find equilibria that
exhibit signaling behavior. This is illustrated with the help of a concrete public goods example.
Index Terms
Dynamic games, asymmetric information, perfect Bayesian equilibrium, sequential decomposition, dynamic
programming, signaling.

I. I NTRODUCTION
Several practical applications involve dynamic interaction of strategic decision-makers with private and
public observations. Such applications include repeated online advertisement auctions, wireless resource
sharing, and energy markets. In repeated online advertisement auctions, advertisers place bids for locations
on a website to sell a product. These bids are calculated based on the value of that product, which is
privately observed by the advertiser and past actions of other advertisers, which are observed publicly.
The authors are with the Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI, 48105
USA e-mail: {dvasal, absi, anastas}@umich.edu.
This work is supported in part by NSF grants CIF-1111061 and ECCS-1608361.
This paper has originally appeared on arXiv.org on August 26, 2015 as working paper 1508.06269 and revised on September 14, 2016 as
1609.04221.

2

Each advertiser’s goal is to maximize its reward, which for an auction depends on the actions taken by
others. In wireless resource sharing, players are allocated channels that interfere with each other. Each
player privately observes its channel gain and takes an action, which can be the choice of modulation or
coding scheme and also the transmission power. The reward it receives depends on the rate the player
gets, which is a function of each player’s channel gain and other players’ actions (through the signalto-interference ratio). Finally, in an energy market, different suppliers bid their estimated power outputs
to an independent system operator (ISO) that formulates the market mechanism to determine the prices
assessed to the different suppliers. Each supplier wants to maximize its return, which depends on its cost
of production of energy, which is its private information, and the market-determined prices which depend
on all the bids.
Dynamical systems with strategic players are modeled as dynamic stochastic games, introduced by
Shapley in [1]. Discrete-time dynamic games with Markovian structure have been studied extensively
to model many practical applications, in engineering as well as economics literature [2, 3]. In dynamic
games with perfect and symmetric information, subgame perfect equilibrium (SPE) is an appropriate
equilibrium concept and there exists a backward recursive algorithm to find all the SPEs of these games
(refer to [4, 5, 6] for a more elaborate discussion). Maskin and Tirole in [7] introduced the concept of
Markov perfect equilibrium (MPE) for dynamic games with symmetric information, where equilibrium
strategies are dependent on some payoff relevant Markovian state of the system, rather than on the
entire history. This is a refinement of the SPE. Some prominent examples of the application of MPE
include [8, 9, 10]. Ericson and Pakes in [8] model industry dynamics for firms’ entry, exit and investment
participation, through a dynamic game with symmetric information, compute its MPE, and prove ergodicity
of the equilibrium process. Bergemann and Välimäki in [9] study a learning process in a dynamic oligopoly
with strategic sellers and a single buyer, allowing for price competition among sellers. They study MPE
of the game and its convergence behavior. Acemoğlu and Robinson in [10] develop a theory of political
transitions in a country by modeling it as a repeated game between the elites and the poor, and study its
MPE.
In dynamic games with asymmetric information, and more generally in multi-player, dynamic decision
problems (cooperative or non-cooperative) with asymmetric information, there is a signaling phenomenon
that can occur, where a player’s action reveals part of its private information to other players, which in
turn affects their future payoff (see [11] for a survey of signaling models).1 In one of the first works
demonstrating signaling, a two-stage dynamic game was considered by Spence [15], where a worker
signals her abilities to a potential employer using the level of education as a signal. Since then, this
phenomenon has been shown in many settings, e.g., warranty as a signal for better quality of a product,
in [16], larger deductible or partial insurance as a signal for better health of a person, in [17, 18], and in
evolutionary game theory, extra large antlers by a deer to signal fitness to a potential mate, in [19].
1

There are however instances where even though actions reveal private information, at equilibrium the signaling effect is non-existent [12,
13] and [14, sec III.A]. Thus, MPE is an appropriate equilibrium concept for such games. In [12], authors extend the model of [8] where
firms’ set-up costs and scrap values are random and their private information. However, these are assumed to be i.i.d. across time and thus
the knowledge of this private information in any period does not affect the future reward. In[13],[14, sec III.A], authors discuss games
with one-step delayed information pattern, where all players get access to players’ private information with delay one. In this case as well,
signaling does not occur.

3

For dynamic games with asymmetric information, where players’ observations belong to different
information sets, in order to calculate expected future rewards players need to form a belief on the
observations of other players (where players need not have consistent beliefs). As a result, SPE or MPE, 2
are not appropriate equilibrium concepts for such settings. There are several notions of equilibrium for
such games, such as perfect Bayesian equilibrium (PBE), sequential equilibrium, and trembling hand
equilibrium [4, 5]. Each of these equilibrium notions consist of an assessment, i.e., a strategy and a
belief profile for the entire time horizon. The equilibrium strategies are optimal given the equilibrium
beliefs and the equilibrium beliefs are derived from the equilibrium strategy profile using Bayes’ rule
(whenever possible), with some equilibrium concepts requiring further refinements. Thus there is a cyclical
requirement of beliefs being consistent with strategies, which are in turn optimal given the beliefs,
and finding such equilibria can be thought of as being equivalent to solving a fixed point equation in
the space of strategy and belief profiles over the entire time horizon. Furthermore, these strategies and
beliefs are functions of histories and thus their domain grows exponentially in time, which makes the
problem computationally intractable. To date, there is no universal algorithm that provides simplification
by decomposing the aforementioned fixed-point equation for calculating PBEs.
Some practically motivated work in this category is the work in [20, 21, 22, 23]. Authors in [20, 21, 22]
study the problem of social learning with sequentially-acting selfish players who act exactly once in the
game and make a decision to adopt or reject a trend based on their estimate of the system state. Players
observe a private signal about the system state and publicly observe actions of past players. The authors
analyze PBE of the dynamic game and study the convergent behavior of the system under an equilibrium,
where they show occurrence of herding. Devanur et al. in [23] study PBE of a repeated sales game where
a single buyer has a valuation of a good, which is its private information, and a seller offers to sell a
fresh copy of that good in every period through a posted price.

A. Contributions
In this paper, we present a sequential decomposition methodology for calculating a subset of all PBEs for
finite and infinite horizon dynamic games with asymmetric information. Our model, consists 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). Furthermore, we show that all SPBE can
be computed using this methodology. 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.
2

SPE and MPE are used for games where beliefs in the game are strategy-independent and consistent among players. Equivalently, these
beliefs are derived from basic parameters of the problems and are not part of the definition of the equilibrium concept.

4

Our motivation for considering SPBE stems from ideas in decentralized team problems and specifically
the works of Ho [24] and Nayyar et al. [25]. We utilize the agent-by-agent approach in [24] to motivate a
Markovian structure where players’ strategies depend only on their current types. In addition, we utilize
the common information based approach introduced in [25] to summarize the common information into
a common belief on players’ private types. Even though these ideas motivate the special structure of
our equilibrium strategies, they can not be applied in games to evaluate SPBE because they have been
developed for dynamic teams and are incompatible with equilibrium notions. Our main contribution is a
new construction based on which SPBE can be systematically evaluated.
Specifically, for the finite horizon model, we 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 an one-step fixed point equation on the space of probability
simplexes. 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. The SPBE that
are developed in this paper are analogous to MPEs (for games with symmetric information) in the sense
that players choose their actions based on beliefs that depend on common information, and private types,
both of which have Markovian dynamics.
For the infinite horizon model, instead of the backwards recursion step, the algorithm solves a single-shot
time invariant fixed-point equation involving both an equilibrium generating function and an equilibrium
reward-to-go function. We show that using our method, existence of SPBE in the asymmetric information
dynamic game is guaranteed if the aforementioned fixed-point equation admits a solution. We provide
sufficient conditions under which this is true. We demonstrate our methodology of finding SPBE through
a multi-stage public goods game, whereby we observe the aforementioned signaling effect at equilibrium.

B. Relevant Literature
Related literature on this topic include [14, 26] and [27]. Nayyar et al. in [14, 26] consider dynamic
games with asymmetric information. There is an underlying controlled Markov process and players
jointly observe part of the process and whilst making additional private observations. It is shown that
the considered game with asymmetric information, under certain assumptions, can be transformed to
another game with symmetric information. A backward recursive algorithm is provided to find MPE of
the transformed game. For this strong equivalence to hold, authors in [14, 26] make a critical assumption
in their model: based on the common information, a player’s posterior beliefs about the system state and
about other players’ information are independent of the past strategies used by the players. This leads to
all strategies being non-signaling. Our model is different from this since we assume that the underlying
state of the system has independent components, each constituting a player’s private type. However, we
do not make any assumption regarding update of beliefs and allow the belief state to depend on players’
past strategies, which in turn allows the possibility of signaling in the game.
Ouyang et al. in [27] consider a dynamic oligopoly game with strategic sellers and buyers. Each seller
privately observes the valuation of their good, which is assumed to have independent Markovian dynamics,

5

thus resulting in a dynamic game of asymmetric information. The common belief is strategy dependent
and the authors consider equilibria based on this common information belief. It is shown that if all other
players play actions based on the common belief and their private information using equilibrium strategies,
and if all players use equilibrium belief update function, then player i faces a Markov decision process
(MDP) with respect to its action with state being the common belief and its private type. Thus calculating
equilibrium boils down to solving a fixed-point equation on belief update functions and strategies of all
players. Existence of such equilibrium is shown for a degenerate case where players act myopically at
equilibrium and the equilibrium itself is non-signaling.
Other than the common information based approach, Li et al. [28] consider a finite horizon zero-sum
dynamic game, where at each time only one player out of the two knows the state of the system. The
value of the game is calculated by formulating an appropriate linear program. Cole et al. [29] consider
an infinite horizon discounted reward dynamic game where actions are only privately observable. They
provide a fixed-point equation for calculating a subset of sequential equilibrium, which is referred to as
Markov private equilibrium (MPrE). In MPrE strategies depend on history only through the latest private
observation.
C. Notation
We use uppercase letters for random variables and lowercase for their realizations. For any variable, subscripts represent time indices and superscripts represent player indices. We use notation −i
to represent all players other than player i i.e. −i = {1, 2, . . . i − 1, i + 1, . . . , N }. We use notation
At:t0 to represent the vector (At , At+1 , . . . At0 ) when t0 ≥ t or an empty vector if t0 < t. We use
i+1
. . . , AN
At−i to mean (A1t , A2t , . . . , Ai−1
t , At
t ) . We remove superscripts or subscripts if we want to
represent the whole vector, for example At represents (A1t , . . . , AN
t ). In a similar vein, for any collection
i
i
of sets (X )i∈N , we denote ×i∈N X by X . We denote the indicator function of a set A by IA (·).
For any finite set S, ∆(S) represents the space of probability measures on S and |S| represents its
cardinality. We denote by Pg (or Eg ) the probability measure generated by (or expectation with respect
to) strategy profile g. We denote the set of real numbers by R. For a probabilistic strategy profile of
players (βti )i∈N where the probability of action ait conditioned on a1:t−1 , xi1:t is given by βti (ait |a1:t−1 , xi1:t ),
Q
j j
j
−i
we use the notation βt−i (a−i
t |a1:t−1 , x1:t ) to represent
j6=i βt (at |a1:t−1 , x1:t ). All equalities/inequalities
involving random variables are to be interpreted in the a.s. sense. For mappings with range function sets
f : A → (B → C) we use square brackets f [a] ∈ B → C to denote the image of a ∈ A through f and
parentheses f [a](b) ∈ C to denote the image of b ∈ B through f [a]. A controlled Markov process with
state Xt , action At , and horizon T is denoted by (Xt , At )t∈T .
The paper is organized as follows. In Section II, we present the model for games with finite and infinite
horizon. Section III serves as motivation for focusing on SPBE. In Section IV, for finite-horizon games, we
present a two-step backward-forward recursive algorithm to construct a strategy profile and a sequence
of beliefs, and show that it is a PBE of the dynamic game considered. In Section V, we extend that
methodology to infinite-horizon games. Section VII discusses concrete example of a public goods game
with two players and results are presented for both, finite and infinite horizon versions of the example.
All proofs are provided in appendices.

6

II. M ODEL AND P RELIMINARIES
4

We consider a discrete-time dynamical system with N strategic players in the set N = {1, 2, . . . N }. We
4
consider two cases: finite horizon T = {1, 2, . . . T } with perfect recall and infinite horizon with perfect
4
recall. The system state is Xt = (Xt1 , Xt2 , . . . XtN ), where Xti ∈ 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
P(x1 ) =

N
Y

Qi1 (xi1 )

(1a)

i=1

P(xt |x1:t−1 , a1:t−1 ) = P(xt |xt−1 , at−1 )
=

N
Y

Qit (xit |xit−1 , at−1 ),

(1b)
(1c)

i=1

where Qit are known kernels. Player i at time t takes action ait ∈ Ai on observing the actions a1:t−1 =

(ak )k=1,...,t−1 where ak = ajk j∈N , which is common information among players, and the types xi1:t ,
which it observes privately. The sets Ai , X i are assumed to be finite. Let g i = (gti )t∈T be a probabilistic
strategy of player i where gti : At−1 × (X i )t → ∆(Ai ) such that player i plays action Ait according to
4
Ait ∼ gti (·|a1:t−1 , xi1:t ). Let g = (g i )i∈N be a strategy profile of all players. At the end of interval t, player
i receives an instantaneous reward Rti (xt , at ). To preserve the information structure of the problem, we
assume that players do not observe their rewards until the end of game.3 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
( T
)
X
4
Rti (Xt , At ) .
(2)
J i,g = Eg
t=1

For the infinite-horizon case, the transition kernels Qit are considered to not depend on time t. We also
substitute Rti (Xt , At ) = δ t Ri (Xt , At ) take limT →∞ in the above equation, where δ ∈ [0, 1) is the common
discount factor and Ri is the time invariant stage reward function for player i. With all players being
strategic, this problem is modeled as a dynamic game, DT for finite horizon and D∞ for infinite horizon,
with asymmetric information and simultaneous moves.
A. Preliminaries
Any history of this game at which players take action is of the form ht = (a1:t−1 , x1:t ). Let Ht be
4
the set of such histories, HT = ∪Tt=0 Ht be the set of all possible such histories in finite horizon and
4
i
i
H∞ = ∪∞
t=0 Ht for infinite horizon. At any time t player i observes ht = (a1:t−1 , x1:t ) and all players
together have hct = a1:t−1 as common history. Let Hti be the set of observed histories of player i at time t
and Htc be the set of common histories at time t. An appropriate concept of equilibrium for such games is
PBE [5], which consists of a pair (β ∗ , µ∗ ) of strategy profile β ∗ = (βt∗,i )t∈T ,i∈N where βt∗,i : Hti → ∆(Ai )
Alternatively, we could have assumed instantaneous reward of a player to depend only on its own type, i.e. be of the form Rti (xit , at ),
and have allowed rewards to be observed by the players during the game as this would not alter the information structure of the game
3

7

and a belief profile µ∗ = (i µ∗t )t∈T ,i∈N where i µ∗t : Hti → ∆(Ht ) that satisfy sequential rationality so that
∀i ∈ N , t ∈ T , hit ∈ Hti , β i
∗,i
i
Wti,β ,T (hit ) ≥ Wti,β ,T (hit )
(3)
where the reward-to-go is defined as
i,β i ,T

Wt

β i β ∗,−i , i µ∗t [hit ]

(hit ) , E

( T
X

)
Rni (Xn , An ) hit

,

(4)

n=t

and the beliefs satisfy some consistency conditions as described in [5, p. 331]. Similarly, for the game
D∞ PBE (β ∗ , µ∗ ) requires: ∀i ∈ N , t ≥ 1, hit ∈ Hti , β i
∗,i

i

Wti,β (hit ) ≥ Wti,β (hit )

(5)

where the reward-to-go is
i,β i

Wt

i ∗,−i , i µ∗ [hi ]
t t

(hit ) , Eβ β

(∞
X

)
Rni (Xn , An ) hit

.

(6)

n=t

In general, a belief for player i at time t, i µ∗t is defined on history ht = (a1:t−1 , x1:t ) given its private history
hit = (a1:t−1 , xi1:t ). Here player i’s private history hit = (a1:t−1 , xi1:t ) consists of a public part hct = a1:t−1
and a private part xi1:t . At any time t, the relevant uncertainty player i has is about other players’ types
t
j
x−i
1:t ∈ ×n=1 (×j6=i X ) and their future actions. In our setting, due to independence of types, and given the
common history hct , player i’s type history xi1:t does not provide any additional information about x−i
1:t ,
as will be shown later. For this reason we consider beliefs that are functions of each player’s history hit
only through the common history hct . Hence, for each player i, its belief for each history hct = a1:t−1 is
derived from a common belief µ∗t [a1:t−1 ]. Furthermore, as will be shown later, this belief factorizes into a
Q
∗
∗
product of marginals j∈N µ∗,j
t [a1:t−1 ]. Thus we can sufficiently use the system of beliefs, µ = (µt )t∈T ,
∗,i
−i
c
i
where µ∗t = (µ∗,i
t )i∈N , and µt : Ht → ∆(X ), with the understanding that player i’s belief on xt is
Q
∗,j
j
µt∗,−i [a1:t−1 ](x−i
t ) =
j6=i µt [a1:t−1 ](xt ). Under the above structure, all consistency conditions that are
required for PBEs [5, p. 331] are automatically satisfied.
III. M OTIVATION FOR STRUCTURED EQUILIBRIA
In this section, we present structural results for the considered dynamical process that serve as a
motivation for finding SPBE of the underlying game DT . Specifically, we define a belief state based on
common information history and show that any reward profile that can be obtained through a general
strategy profile can also be obtained through strategies that depend on this belief state and players’
current types, which are their private information. These structural results are inspired by the analysis
of decentralized team problems, which serve as guiding principles to design our equilibrium strategies.
While these structural results provide intuition and the required notation, they are not directly used in the
proofs for finding SPBE later in Section IV.
At any time t, player i has information (a1:t−1 , xi1:t ) where a1:t−1 is the common information among
players, and xi1:t is the private information of player i. Since (a1:t−1 , xi1:t ) increases with time, any strategy
of the form Ait ∼ gti (·|a1:t−1 , xi1:t ) becomes unwieldy. Thus it is desirable to have an information state in

8

a time-invariant space that succinctly summarizes (a1:t−1 , xi1:t ), and that can be sequentially updated. We
first show in Lemma 1 that given the common information a1:t−1 and its current type xit , player i can
discard its type history xi1:t−1 and play a strategy of the form Ait ∼ sit (·|a1:t−1 , xit ). Then in Lemma 2,
we show that a1:t−1 can be summarized through a belief πt , defined as follows. For any strategy profile
4
g, belief πt on Xt , πt ∈ ∆(X ), is defined as πt (xt ) = Pg (Xt = xt |a1:t−1 ), ∀xt ∈ X . We also define the
4
marginals πti (xit ) = Pg (Xti = xit |a1:t−1 ), ∀xit ∈ X i .
For player i, we use the notation g to denote a general policy of the form Ait ∼ gti (·|a1:t−1 , xi1:t ), notation
s, where sit : At−1 × X i → ∆(Ai ), to denote a policy of the form Ait ∼ sit (·|a1:t−1 , xit ), and notation m,
where mit : ∆(×i∈N X i ) × X i → ∆(Ai ), to denote a policy of the form Ait ∼ mit (·|πt , xit ). It should be
noted that since πt is a function of random variables a1:t−1 , m policy is a special type of s policy, which
in turn is a special type of g policy.
Using the agent-by-agent approach [24], we show in Lemma 1 that any expected reward profile of the
players that can be achieved by any general strategy profile g can also be achieved by a strategy profile
s.
Lemma 1: Given a fixed strategy g −i of all players other than player i and for any strategy g i of player
i, there exists a strategy si of player i such that ∀t ∈ T , xt ∈ X , at ∈ A,
i −i

i −i

Ps g (xt , at ) = Pg g (xt , at )
i −i

(7)

i −i

which implies J i,s g = J i,g g .
Proof: Please see Appendix A.
Since any si policy is also a g i type policy, the above lemma can be iterated over all players which implies
that for any g policy profile there exists an s policy profile that achieves the same reward profile i.e.,
(J i,s )i∈N = (J i,g )i∈N .
Policies of types s still have increasing domain due to increasing common information a1:t−1 . In order to
summarize this information, we take an equivalent view of the system dynamics through a common agent,
as taken in [30]. The common agent approach is a general approach that has been used extensively in
dynamic team problems [31, 32, 33, 34]. Using this approach, the problem can be equivalently described
as follows: player i at time t observes a1:t−1 and takes action γti , where γti : X i → ∆(Ai ) is a partial
(stochastic) function from its private information xit to ait , of the form Ait ∼ γti (·|xit ). These actions are
generated through some policy ψ i = (ψti )t∈T , ψti : At−1 → {X i → ∆(Ai )}, that operates on the common
information a1:t−1 such that γti = ψti [a1:t−1 ]. Then any policy of the form Ait ∼ sit (·|a1:t−1 , xit ) is equivalent
to Ait ∼ ψti [a1:t−1 ](·|xit ).
We call a player i’s policy through common agent to be of type ψ i if its actions γti are taken as
γti = ψti [a1:t−1 ]. We call a player i’s policy through common agent to be of type θi where θti : ∆(X ) →
{X i → ∆(Ai )}, if its actions γti are taken as γti = θti [πt ]. A policy of type θi is also a policy of type ψ i .
There is a one-to-one correspondence between policies of type si and of type ψ i and between policies of
type mi and of type θi . In summary, the notation for the various functional form of strategies is
Ait ∼ sit (·|a1:t−1 , xit )

Ait ∼ ψti [a1:t−1 ](·|xit ),

(8a)

Ait ∼ mit (·|πt , xit )

Ait ∼ θti [πt ](·|xit ).

(8b)

9

In the following lemma, we show that the space of profiles of type s is outcome-equivalent to the space
of profiles of type m.
Lemma 2: For any given strategy profile s of all players, there exists a strategy profile m such that
Pm (xt , at ) = Ps (xt , at )

∀t ∈ T , xt ∈ X , at ∈ A,

(9)

which implies (J i,m )i∈N = (J i,s )i∈N .
Proof: Please see Appendix B.
The above two lemmas show that any reward profile that can be generated through a policy profile of
type g can also be generated through a policy profile of type m. This is precisely the motivation for using
SPBE which are equilibria based on policies of type m. It should be noted that the construction of si
depends only on g i (as shown in (37)), while the construction of mi depends on the whole policy profile g
and not just on g i , since the construction of θi depends on ψ in (49). Thus any unilateral deviation of player
i in g policy profile does not necessarily translate to unilateral deviation of player i in the corresponding
m policy profile. Therefore g being an equilibrium of the game (in some appropriate notion) does not
necessitate the corresponding m also being an equilibrium. Thus the set of equilibria of type g contains
those of type m but not vice-versa (in general); characterizing the relationship between the two sets of
equilibria is an interesting open problem.
We end this section by noting that although finding general PBEs of type g of the games DT or D∞
would be a desirable goal, since the space of strategies is growing exponentially with time, it would be
computationally intractable. However, Lemmas 1 and 2 suggest that strategies of type m form a rich
class that achieves every possible reward profile. Since these strategies are functions of beliefs πt that
lie in a time-invariant space and are easily updatable, equilibria of this type are potential candidates for
computation through backward recursion. Our goal is to devise an algorithm to find structured equilibria
of type m of the dynamic games DT or D∞ .
Definition 1 (SPBE): A structured perfect Bayesian equilibrium is a PBE of the considered dynamic
game where at any time t, for any agent i, its equilibrium strategy βt∗,i is of type m (as in (8b)).
IV. A M ETHODOLOGY FOR SPBE

COMPUTATION IN FINITE HORIZON

In this section we consider the finite horizon dynamic game DT . In the previous section, (specifically
in Claim 1, included in the proof of Lemma 2 in Appendix B), it is shown that due to the independence
of types and their evolution as independent controlled Markov processes, for any strategy of the players,
Q
i i
the joint common belief can be factorized as a product of its marginals i.e., πt (xt ) = N
i=1 πt (xt ), ∀xt .
Since in this paper, we only deal with such joint beliefs, to accentuate this independence structure, we
define π t ∈ ×i∈N ∆(X i ) as vector of marginal beliefs where π t := (πti )i∈N . In the rest of the paper, we
will use π t instead of πt whenever appropriate, where of course, πt can be constructed from π t . Similarly,
we define the vector of belief updates as F (π, γ, a) := (F i (π i , γ i , a))i∈N where (using Bayes rule)
 P πi (xi )γ i (ai |xi )Qi (xi |xi ,a)
P i i i i i
t
t t+1 t
 xit Pt
if
i
i
i
i
i
x̃it π (x̃t )γ (a |x̃t ) > 0
π (x̃t )γ (a |x̃t )
x̃it
(10)
F i (π i , γ i , a)(xit+1 ) =
P
P

π i (xi )Qi (xi |xi , a) if
π i (x̃i )γ i (ai |x̃i ) = 0.
xit

t

t

t+1

t

x̃it

t

t

10

The update function F i defined above depends on time t through the kernel Qit (for the finite horizon
model). For notational simplicity we suppress this dependence on t. We also change the notation of
policies of type m and θ as follows, so they depend on π t instead of πt
mit : ×i∈N ∆(X i ) × X i → ∆(Ai )

θti : ×i∈N ∆(X i ) → X i → ∆(Ai ) .

(11a)
(11b)

In the following we present a backward-forward algorithm that evaluates SPBE. As will be shown in
Theorem 2, this is a “canonical” methodology, in the sense that all SPBE can be generated this way.
A. Backward Recursion
In this section, we define an equilibrium generating function θ = (θti )i∈N ,t∈T , where θti : ×i∈N ∆(X i ) →
{X i → ∆(Ai )}. In addition, we define a sequence of reward-to-go functions of player i at time t,
(Vti )i∈N ,t∈{1,2,...T +1} , where Vti : ×i∈N ∆(X i )×X i → R. These quantities are generated through a backward
recursive way, as follows.
1. Initialize ∀π T +1 ∈ ×i∈N ∆(X i ), xiT +1 ∈ X i ,
4

VTi +1 (π T +1 , xiT +1 ) = 0.
(12)
Q
2. For t = T, T − 1, . . . 1, ∀π t ∈ ×i∈N ∆(X i ), πt = i∈N πti , let θt [π t ] be generated as follows. Set
γ̃t = θt [π t ], where γ̃t is the solution, if it exists,4 of the following fixed-point equation, ∀i ∈ N , xit ∈ X i ,
o
n
i
i
i
i
γti (·|xit )γ̃t−i , πt
i
i
γ̃t (·|xt ) ∈ arg max
(13)
E
Rt (Xt , At ) + Vt+1 (F (π t , γ̃t , At ), Xt+1 ) xt ,
i
i
γt (·|xt )

i
where expectation in (13) is with respect to random variables (Xt−i , At , Xt+1
) through the measure
i i i −i −i −i
i
i
i
πt−i (x−i
t )γt (at |xt )γ̃t (at |xt )Qt+1 (xt+1 |xt , at ) and F is defined above.
Furthermore, using the quantity γ̃t found above, define
o
n
i
i 4 γ̃ti (·|xit )γ̃t−i , πt
i
i
i
i
Vt (π t , xt ) =E
(14)
Rt (Xt , At ) + Vt+1 (F (π t , γ̃t , At ), Xt+1 ) xt .

It should be noted that in (13), γ̃ti is not the outcome of a maximization operation as is the case in a best
response equation of a Bayesian Nash equilibrium. Rather (13) is a different fixed point equation. This is
because the maximizer γ̃ti appears in both, the left-hand-side and the right-hand-side of the equation (in
the belief update F (π t , γ̃t , At ) = (F i (πti , γ̃ti , At ))i∈N ). This distinct construction is pivotal in the proof of
Theorem 1, as will be further elaborated in the Discussion section.
B. Forward Recursion
As discussed above, a pair of strategy and belief profile (β ∗ , µ∗ ) is a PBE if it satisfies (4). Based on
θ defined above in (12)–(14), we now construct a set of strategies β ∗ and beliefs µ∗ for the game DT in
a forward recursive way, as follows.5 As before, we will use the notation µ∗t [a1:t−1 ] := (µ∗,i
t [a1:t−1 ])i∈N ,
4

The problem of existence in this step will be discussed in Section VI.
As discussed in the preliminaries subsection on Section II, the equilibrium beliefs in SPBE, µ∗t are functions of each player’s history hit
only through the common history hct and are the same for all players.
5

11

where µ∗,i
[a1:t−1 ] is a belief on xit , and µ∗t [a1:t−1 ] can be constructed from µ∗t [a1:t−1 ] as µ∗t [a1:t−1 ](xt ) =
QN ∗,it
i
c
i=1 µt [a1:t−1 ](xt ), ∀a1:t−1 ∈ Ht .
1. Initialize at time t = 1,
µ∗1 [φ](x1 )

:=

N
Y

Qi1 (xi1 ).

(15)

i=1
c
2. For t = 1, 2 . . . T, ∀i ∈ N , a1:t ∈ Ht+1
, xi1:t ∈ (X i )t

βt∗,i (ait |a1:t−1 , xi1:t ) = βt∗,i (ait |a1:t−1 , xit )
:= θti [µ∗t [a1:t−1 ]](ait |xit )

(16)

and
∗,i
i
i ∗
µ∗,i
t+1 [a1:t ] := F (µt [a1:t−1 ], θt [µt [a1:t−1 ]], at )

(17)

where F i is defined in (10).
We now state our main result.
Theorem 1: A strategy and belief profile (β ∗ , µ∗ ), constructed through the backward-forward recursion
algorithm is a PBE of the game, i.e., ∀i ∈ N , t ∈ T , a1:t−1 ∈ Htc , xi1:t ∈ (X i )t , β i ,
∗,i ∗,−i
βt:T
βt:T , µ∗t [a1:t−1 ]

E

( T
X

)
Rni (Xn , An ) a1:t−1 , xi1:t

n=t

i β ∗,−i , µ∗ [a
βt:T
t 1:t−1 ]
t:T

≥E

( T
X

)
Rni (Xn , An ) a1:t−1 , xi1:t

.

n=t

(18)
Proof: Please see Appendix C.
We emphasize that even though the backward-forward algorithm presented above finds a class of equilibrium strategies that are structured, the unilateral deviations of players in (18) are considered in the space
of general strategies, i.e., the algorithm does not make any bounded rationality assumptions.
The following result shows that the backward-forward construction described above is “canonical”, in
the sense that all SPBE can be found through this methodology. Clearly, an SPBE can be defined as a
PBE (β ∗ , µ∗ ) of the game that is generated through forward recursion in (15)–(17), using an equilibrium
generating function φ, where φ = (φit )i∈N ,t∈T , φit : ×i∈N ∆(X i ) → {X i → ∆(Ai )}, common belief update
function F and prior distributions Q1 . As a consequence, βt∗,i only depends on current type xit of player
i, and on the common information a1:t−1 through the set of marginals µ∗t [a1:t−1 ], and µ∗,i
t depends only
on common information history a1:t−1 .
Theorem 2 (Converse): Let (β ∗ , µ∗ ) be an SPBE. Then there exists an equilibrium generating function
φ that satisfies (13) in backward recursion ∀ πt = µ∗t [a1:t−1 ], ∀ a1:t−1 , such that (β ∗ , µ∗ ) is defined through
forward recursion using φ.6
Proof: Please see Appendix E.
6

Note that for π t 6= µ∗t [a1:t−1 ] for any a1:t−1 , φ can be arbitrarily defined without affecting the definition of (β ∗ , µ∗ ).

12

C. Discussion
Several remarks are in order with regard to the above methodology and the result.
Remark 1: The second sub-case in (10) dictates how beliefs are updated for histories with zero
probability. The particular expression used is only one of many possible updates than can be used here.
Dynamics that govern the evolution of public beliefs at histories with zero probability of occurrence affect
equilibrium strategies. Thus, the construction proposed for calculating PBEs in this paper will produce a
different set of equilibria if one changes the second sub-case above. The most well-known example of
another such update is the intuitive criterion proposed in [35] for Nash equilibria, later generalized to
sequential equilibria in [36]. The intuitive criterion assigns zero probability to states that can be excluded
based on data available to all players (in our case action profile history a1:t−1 ). Another example of belief
update is universal divinity, proposed in [37].
Remark 2: To highlight the significance of the unique structure of (13), one can think as follows. When
all players other than player i play structured strategies, i.e., strategies of the form Ajt ∼ mjt (·|π t , xjt ) =
θtj [π t ](·|xjt ), one may want to characterize the optimization problem from the viewpoint of the i-th player
in order to characterize its best response. In particular one may want to show that although player i can
play general strategies of the form Ait ∼ gti (·|xi1:t , a1:t−1 ), it is sufficient to best respond with structured
strategies of the form Ait ∼ mit (·|π t , xit ) = θti [π t ](·|xit ) as well. To show that, one may entertain the thought
that player i faces an MDP with state (Xti , Πt ), and action Ait at time t. If that were true, then player i’s
optimal action could be characterized (using standard MDP results) by a dynamic-programming equation
similar to (13), of the form
o
n
i
i
i
−i
i
i
γti (·|xit )γ̃t−i , πt
i
i
γ̃ti (·|xit ) ∈ arg max
,
γ
(·|x
),
γ̃
(·|·),
γ̃
,
A
),
X
)
x
(19)
E
(π
R
(X
,
A
)
+
V
(F
t
t
t
t t
t
t
t
t+1
t ,
t
t+1
i
i
γt (·|xt )

where, unlike (13), in the belief update equation the partial strategy γti (·|xit ) is also optimized over.
However, as it turns out, user i does not face such an MDP problem! The reason is that the update
equation π t+1 = F (π t , γt , at ) also depends on γti which is the partial strategy of player i and this has
not been fixed in the above setting. If however the update equation is first fixed (so it is updated as
π t+1 = F (π t , γ̃ti , γ̃t−i , at ) = F (π t , θt [πt ], at ), i.e., using the equilibrium strategies even for player i) then
indeed the problem faced by user i is the MDP defined above. It is now clear why (13) has the flavor
of a fixed-point equation: the update of beliefs needs to be fixed beforehand with the equilibrium action
γ̃ti even for user i, and only then user i’s best response can depend only on the MDP state (Xti , Πt ) thus
being a structured strategy as well. This implies that his optimal action γ̃ti appears both on the left and
right hand side of this equation giving rise to (13).
Remark 3: In this paper, we find a class of PBEs of the game, while there may exist other equilibria
that are not “structured”, and can not be found by directly using the proposed methodology. The rationale
for using structured equilibria over others is the same as that for using MPE over SPE for a symmetric
information game; a focussing argument for using simpler strategies being one of them.
V. A M ETHODOLOGY FOR SPBE COMPUTATION IN I NFINITE H ORIZON
In this section we consider the infinite horizon discounted reward dynamic game D∞ . We state the
fixed-point equation that defines the value function and strategy mapping for the infinite horizon problem.

13

This is analogous to the backwards recursion ((13) and (14)) that define the value function and θ mapping
for the finite horizon problem.
j
i
i
i
i
Define the set of functions V i : ×N
j=1 ∆(X ) × X → R and strategies γ̃ : X → ∆(A ) (which are
generated formally as γ̃ i = θi [π] for given π) via the following fixed-point equation: ∀ i ∈ N , xi ∈ X i ,

o
n

i
i
γ i (·|xi ),γ̃ −i ,π −i
i
i
0i
i
γ̃ (· | x ) ∈ argmax E
R (X, A) + δV F (π, γ̃, A), X | π, x ,
(20a)
γ i (·|xi )∈∆(Ai )

n

o
i
i
−i −i
i
V i (π, xi ) = Eγ̃ (·|x ),γ̃ ,π
Ri (X, A) + δV i F (π, γ̃, A), X 0 | π, xi .
(20b)
Note that the above is a joint fixed-point equation in (V, γ̃), unlike the backwards recursive algorithm
earlier which required solving a fixed-point equation only in γ̃. Here the unknown quantity is distributed
as (X −i , Ai , A−i , X 0 i ) ∼ π −i (x−i )γ i (ai | xi )γ̃ −i (a−i | x−i )Qi (x0 i | xi , a), and F i (·) is defined in (10).
Define the belief µ∗ inductively similar to the forward recursion from Section IV-B. By construction
the belief defined above satisfies the consistency condition needed for a PBE. Denote the strategy arising
out of γ̃ by β ∗ i.e.,
i
h
i,∗ i
∗
i
i
(21)
βt (at | x1:t , a1:t−1 ) = θ µt [a1:t−1 ] (ait | xit ).
Note that although the mapping θi is stationary, the strategy βti,∗ derived from it is not so. Below we state
the central result of this section, that the strategy-belief pair (β ∗ , µ∗ ) constructed from the solution of the
fixed-point equation (20) and the forward recursion indeed constitutes a PBE.
Theorem 3: Assuming that the fixed-point equation (20) admits an absolutely bounded solution V i (for
all i ∈ N ), the strategy-belief pair (β ∗ , µ∗ ) defined in (21) is a PBE of the infinite horizon discounted
reward dynamic game i.e., ∀ i ∈ N , β i , t ≥ 1, hit ∈ Hti ,
(∞
)
(∞
)
X
X
i,∗
−i,∗
∗
c
i
−i,∗
∗
c
Eβ ,β ,µt [ht ]
δ n−t Ri (Xn , An ) | hit ≥ Eβ ,β ,µt [ht ]
δ n−t Ri (Xn , An ) | hit .
(22)
n=t

n=t

Proof: Please see Appendix F.
Our approach to proving Theorem 3 is as follows. We begin by noting that the standard contraction
mapping arguments used in infinite horizon discounted reward MDPs/POMDPs viewed as a limit of
finite horizon problems, do not apply here, since the policy equation (20a) is not a maximization, but a
different fixed-point equation. So we attempt to “fit” the infinite horizon problem into the framework of
finite-horizon model developed in the previous section. We do that by first introducing a terminal reward
that depends on common beliefs, in the backward-forward recursion construction of Section IV for finite
horizon games. We consider a finite horizon, T > 1, dynamic game with rewards same as in the infinite
horizon version and time invariant transition kernels Qi . For each player i, there is a terminal reward
Gi (πT +1 , xiT +1 ) that depends on the terminal type of player i and the terminal belief. It is 
assumed that
i,T
Gi (·) is absolutely bounded. We define the value functions Vt : ×j∈N ∆(X j ) × X i → R
and
i∈N ,t∈T


strategies γ̃ti,T
backwards inductively in the same way as in Section IV-A except Step 1, where
i∈N ,t∈T

i
∗
∗
instead of (12) we set VTi,T
+1 ≡ G . This consequently results in a strategy/belief pair (β , µ ), based on
the forward recursion in Section IV-B. Now, due to the above construction, the value function Vti,T from
above and V i from (20) are related (please see Lemma 9 in Appendix G). This result combined with
continuity arguments as T → ∞ complete the proof of Theorem 3.

14

VI. A N E XISTENCE R ESULT FOR THE F IXED -P OINT E QUATION
In this section, we discuss the problem of existence of signaling equilibria.7 While it is known that for
any finite dynamic game with asymmetric information and perfect recall, there always exists a PBE [4,
Prop. 249.1], existence of SPBE is not guaranteed. It is clear from our algorithm that existence of SPBE
boils down to existence of a solution to the fixed-point equation (13) in finite horizon and (20) in infinite
i
for all i ∈ N from
horizon. Specifically, for the finite horizon, at each time t given the functions Vt+1
the previous round (in the backwards recursion) equation (13) must have a solution γ̃ti for all i ∈ N .
Generally, existence of equilibria is shown through Kakutani’s fixed point theorem, as is done in proving
existence of a mixed strategy Nash equilibrium of a finite game [4, 38]. This is done by showing existence
of fixed point of the best-response correspondences of the game. Among other conditions, it requires the
“closed graph” property of the correspondences, which is usually implied by the continuity property of
the utility functions involved. For (13) establishing existence is not straightforward due to: (a) potential
discontinuity of the πt update function F when the denominator in the Bayesian update is 0 and (b)
i
potential discontinuity of the value functions, Vt+1
. In the following we provide sufficient conditions that
can be checked at each time t to establish the existence of a solution.
We consider a generic fixed-point equation similar to the one encountered in Section IV and Section V
and state conditions under which they are guaranteed to have a solution. To concentrate on the essential
aspects of the problem we consider a simple case with N = 2, type sets X i = {xH , xL } and action sets
Ai = {0, 1}. Furthermore, types are static and instantaneous rewards Ri (x, a) do not depend on x−i .
i
1
2
Given public belief π = (π 1 , π2 ) ∈ ×2i=1
 ∆(A ), value functions V , V , one wishes to solve the
following system of equations for γ̃ i (· | xi )
.
xi ∈{xH ,xL },i∈{1,2}

i

i

γ̃ (· | x ) ∈

γ i (·|xi ),γ̃ −i

argmax E




 
i i
i
1
1
1
1
2
2
2
2
i
i
(23)
R (x , A)+V
F (π , γ̃ , A ), F (π , γ̃ , A ) , x | x , π

γ i (·|xi )∈∆(Ai )

where the expectation is evaluated using the probability distribution on (A1 , A2 ),
h
i
i i
i
j
H
j j
H
j
L j j
L
γ (a | x ) π (x )γ̃ (a | x ) + π (x )γ̃ (a | x ) .
(24)


The probabilistic policy γ̃ can be represented by the 4-tuple p = p̃1L , p̃2L , p̃1H , p̃2H where p̃iH =
γ i (ai = 1 | xH ) and p̃iL = γ i (ai = 1 | xL ), i = 1, 2.
The fixed-point equation of interest reduces to



1H
p̃ ∈ argmax a π 2 p̃2H +(1−π 2 )p̃2L V 1 (F1 (π 1 , p̃1 ), F1 (π 2 , p̃2 ), xH )−V 1 (F0 (π 1 , p̃1 ), F1 (π 2 , p̃2 ), xH )
a∈[0,1]



+ 1 − π 2 p̃2H − (1 − π 2 )p̃2L V 1 (F1 (π 1 , p̃1 ), F0 (π 2 , p̃2 ), xH ) − V 1 (F0 (π 1 , p̃1 ), F0 (π 2 , p̃2 ), xH )



+ π 2 p̃2H + (1 − π 2 )p̃2L R1 (xH , 1, 1) − R1 (xH , 0, 1)



2 2H
2 2L
1 H
1 H
+ 1 − π p̃ − (1 − π )p̃
R (x , 1, 0) − R (x , 0, 0)
(25)
In the special case of uncontrolled types where player i’s instantaneous reward does not depend on its private type xit , the fixed point
equation always has a type-independent, myopic solution γ̃ti (·), since it degenerates to a best-response-like equation similar to the one for
computing Nash equilibrium. This result is shown in [27].
7

15

and three other similar equations for p̃1L , p̃2H , p̃2L .
πpH
πpH + πpL
π(1 − pH )
F0 (π, (pH , pL )) ,
π(1 − pH ) + π(1 − pL )

F1 (π, (pH , pL )) ,

(26a)
(26b)

and in both definitions, if the denominator is 0 then the RHS is taken as π.
A. Points of Discontinuities and the Closed graph result
Equation (25) and the other three similar equations are essentially of the form (for a given π)
x ∈ argmax af1 (x, y, w, z),
a∈[0,1]

w ∈ argmax cf3 (x, y, w, z),
c∈[0,1]

y ∈ argmax bf2 (x, y, w, z)
b∈[0,1]

z ∈ argmax df4 (x, y, w, z)

(27)

d∈[0,1]

with x, y, z, w as p̃1H , p̃1L , p̃2H , p̃2L , respectively.
Define Di ⊆ [0, 1]4 as the set of discontinuity points of fi and D , ∪4i=1 Di .
For any point x0 ∈ D, define S(x0 ) as the subset of indexes i ∈ {1, 2, 3, 4} for which fi (x) is
discontinuous at x0 .
Assumption (E1): At any point x0 ∈ D, ∀ i ∈ S(x0 ) one of the following is satisfied:
1) fi (x0 ) = 0, or
2) ∃  > 0 such that ∀ x ∈ B (x0 ) (inside an -ball of x0 ) the sign of fi (x) is same as the sign of fi (x0 ).
In the following we provide a sufficient condition for existence.
Theorem 4: Under Assumption (E1), there exists a solution to the fixed-point equation (27).
Proof: Please see Appendix H.
The above set of results provide us with an analytical tool for establishing existence of a solution to
the concerned fixed-point equation.
While the above analytical result is useful in understanding a theoretical basis for existence, it doesn’t
cover all instances. For instance, fixed-point equation arising out of (13) for t = 1 from Section VII-A,
does not satisfy assumption (E1). In the following we provide a more computationally orientated approach
to establishing existence and/or solving the generic fixed-point equation (27).
We motivate this case-by-case approach with the help of an example. Suppose we hypothesize that the
solution to (27) is such that x = 0, w = 0 and y, z ∈ (0, 1). Then (27) effectively reduces to checking if
there exists y ∗ , z ∗ ∈ (0, 1) such that
y ∗ ∈ argmax b f2 (0, y ∗ , 0, z ∗ ) z ∗ ∈ argmax d f4 (0, y ∗ , 0, z ∗ )
b

(28a)

d

f1 (0, y ∗ , 0, z ∗ ) ≤ 0

f3 (0, y ∗ , 0, z ∗ ) ≤ 0.

(28b)

Thus the 4-variable system reduces to solving a 2-variable system and 2 conditions to verify. For instance, if
f2 (0, y, 0, z), f4 (0, y, 0, z) as functions of y, z satisfy the conditions of Theorem 4 then the sub-system (28a)
has a solution. If one of these solution is also consistent with (28b) then this sub-case indeed provides a
solution to (27).

16

Generalizing the simplification provided in the above example, we divide solutions into 34 = 81 cases8
based on whether each of x, y, w, z are in {0}, (0, 1), {1}. There are (1) 16 corner cases where none are
in the strict interior (0, 1); (2) 32 cases where exactly one is in the strict interior (0, 1); (3) 24 cases where
2 variables are in the strict interior (0, 1); (4) 8 cases where 3 variables are in the strict interior (0, 1);
(5) 1 case where all 4 variables are in the strict interior (0, 1).
Similar to the calculations above, for each of the 81 cases one can write a sub-system to which the
problem (27) effectively reduces to. Clearly, if any one of the 81 sub-systems has a solution then the
problem (27) has a solution. Furthermore, searching for a solution reduces to an appropriate sub-problem
depending on the case.
The approach then is to enumerate each of these 81 cases (as stated above) and check them in order.
However this case-by-case division provides a computational simplification - not all cases require solving
the entire fixed-point equation. Whenever a variable, say y, is not in the strict interior (0, 1) then the
corresponding equation (27) need not be solved, since one only needs to verify the sign at a specific
point. Hence, all sub-cases of (1) reduce to simply checking the value of functions fi at corner points no need for solving a fixed-point equation. All sub-cases of (2) reduce to solving a 1-variable fixed-point
equation and three corresponding conditions to verify, etc.
VII. A C ONCRETE E XAMPLE OF M ULTI - STAGE INVESTMENT IN P UBLIC G OODS
Here we discuss both, a two-stage (finite) and an infinite-horizon version of a public goods example to
illustrate the methodology described above for the construction of SPBE.
A. A two stage public goods game
We consider a discrete version of Example 8.3 from [5, ch.8], which is an instance of a repeated public
goods game. There are two players who play a two-period game. In each period t, they simultaneously
decide whether to contribute to the period t public good, which is a binary decision ait ∈ {0, 1} for
players i = 1, 2. Before the start of period 2, both players know the action profile from period 1. In each
period, each player gets a reward of 1 if at least one player contributed and 0 if none contributed. Player
i’s cost of contributing is xi which is its private information. Both players believe that xi ’s are drawn
independently and identically with probability distribution Q with support {xL , xH }; 0 < xL < 1 < xH ,
and PQ (X i = xH ) = q ∈ (0, 1).
In our model this corresponds to N = 2, T = 2 and reward for player i in period t is Rti (x, at ) =
i
δ t Ri (x, at ), with Ri (x, at ) = (1 − xi )1(ait = 1) + a−i
t 1(at = 0). We set δ = 1 in this two-stage case. We
use the backward recursive algorithm from Section IV to find an SPBE of this game. Here the partial
iH
functions γti can equivalently be defined through the scalars piL
∈ [0, 1], for t = 1, 2 and i = 1, 2,
t , pt
where
γti (1|xL ) = piL
t ,
γti (1|xH ) = piH
t ,

γti (0|xL ) = 1 − piL
t ,

(29a)

γti (0|xH ) = 1 − piH
t ,

(29b)

iH
Henceforth, piL
is used interchangeably with γti .
t , pt
8

Generally, the number of cases is 3

PN

i=1

Mi

where N is the number of agents and Mi is the number of types for player i.

17

For t = 2 and for any fixed π 2 = (π21 , π22 ), where π2i = π2i (xH ) ∈ [0, 1] represents a probability measure
2L 1H
2H
on the event {X i = xH }. Let γ̃2 = (p̃1L
2 , p̃2 , p̃2 , p̃2 ) = θ2 [π 2 ] be defined through the fixed point
equation (13). Since 1 − xH < 0, p̃iH
2 = 0 is the solution. Thus the fixed-point equation can be reduced
to, ∀i ∈ {1, 2},
iL
−i −iL
L
+ piL
p̃iL
2 (1 − x ).
2 ∈ arg max(1 − p2 )(1 − π2 )p̃2
piL
2

This implies (31) below, the solutions to which are


0
if



1
if
p̃iL
2 =



 arbitrary if

(30)

shown in Figure 1 in the space of (π21 , π22 ).
xL > 1 − (1 − π2−i )p̃−iL
2 ,
xL < 1 − (1 − π2−i )p̃−iL
2 ,

(31)

xL = 1 − (1 − π2−i )p̃−iL
2 .

2H
2L 1H
Fig. 1: Solutions of fixed point equation in (31). Solutions are shown as quadruplets (p̃1L
2 , p̃2 , p̃2 , p̃2 )
with intervals used whenever the solution is not uniquely defined.

Thus for any π 2 , there can exist multiple equilibria and correspondingly multiple θ2 [π 2 ] can be defined.
For any particular θ2 , at t = 1, the fixed point equation arising out of (13) defines θ1 [Q2 ], where Q2 = Q×Q
denotes the profile of initial belief.
Using one such θ2 defined below, we find an SPBE of the game for q = 0.1, xL = 0.2, xH = 1.2. We
use θ2 [π 2 ] as one possible set of solutions of (31), described below,

L 1−xL

( 1−x
π21 ∈ [0, xL ), π22 ∈ [0, xL )
1 , 1−π 2 , 0, 0)

1−π

2
2


 (1, 0, 0, 0)
π21 ∈ [0, xL ], π22 ∈ [xL , 1]
2H
1L 2L 1H
θ2 [π2 ] = (p̃2 , p̃2 , p̃2 , p̃2 ) =
(32)
 (0, 1, 0, 0)
π21 ∈ [xL , 1], π22 ∈ [0, xL ]




 (1, 1, 0, 0)
π21 ∈ (xL , 1], π22 ∈ (xL , 1].
Then, through iteration on the fixed point equation and using the aforementioned θ2 [π 2 ], we numerically
2L 1H
2H
find (and analytically verify) that θ1 [Q2 ] = (p̃1L
1 , p̃1 , p̃1 , p̃1 ) = (0, 1, 0, 0) is a fixed point. Thus
β11 (A11 = 1|X 1 = xL ) = 0

β12 (A21 = 1|X 2 = xL ) = 1

β11 (A11 = 1|X 1 = xH ) = 0

β12 (A21 = 1|X 2 = xH ) = 0

18

with beliefs µ∗2 [00] = (q, 1), µ∗2 [01] = (q, 0), µ∗2 [10] = (q, 1), µ∗2 [11] = (q, 0) and (β2i (·|a1 , ·))i∈{1,2} =
θ2 [µ∗2 [a1 ]] is an SPBE of the game. In this equilibrium, player 2 at time t = 1, contributes according to
her type whereas player 1 never contributes, thus player 2 reveals her private information through her action
whereas player 1 does not. Since θ2 is symmetric, there also exists an (antisymmetric) equilibrium where
at time t = 1, players’ strategies reverse i.e. player 2 never contributes and player 1 contributes according
1−xL
1−xL
to her type. We can also obtain a symmetric equilibrium where θ1 [Q2 ] = ( (1−q)(1+x
L ) , (1−q)(1+xL ) , 0, 0) as
q
, resulting in beliefs µ∗2 [00] = (p, p), µ∗2 [01] = (p, 0), µ∗2 [10] = (0, p), µ∗2 [11] =
a fixed point when xL > 2−q
(0, 0) where p =

q(1+xL )
.
q(1+xL )+(1−xL )

B. Infinite horizon version
For the infinite horizon version we consider three values δ = 0, 0.5, 0.95 and solve the corresponding
fixed point equation (arising out of (20)) numerically to calculate the mapping θ. The fixed-point equation
is solved numerically by discretizing the π−space [0, 1]2 and all solutions that we find are symmetric
w.r.t. players i.e., p̃1L for π = (π 1 , π 2 ) is the same as p̃2L for π 0 = (π 2 , π 1 ) and similarly for p̃1H , p̃2H .
For δ = 0, the game is instantaneous and actually corresponds to the second round t = 2 play in
the finite horizon two-stage version above. Thus whenever player 1’s type is xH , it is instantaneously
profitable not to contribute. This gives p̃1H = 0, for all π. Thus we only plot p̃1L ; in Fig. 2 (this can be
inferred from the discussion and Fig. 1 above). Intuitively, with type xL the only values of π for which
player 1 would not wish to contribute is if he anticipates player 2’s type to be xL with high probability
and rely on player 2 to contribute. This is why for lower values of π 2 (i.e., player 2’s type likely to be
xL ) we see p̃1L = 0 in Fig. 2.

Fig. 2: p̃1L vs. (π 1 , π 2 ) at δ = 0; (p̃1L , p̃1H ) = θ1 [π 1 , π 2 ].
Now consider p̃1L plotted in Fig. 2 and 3. As δ increases, future rewards attain more priority and
signaling comes into play. So while taking an action, players not only look for their instantaneous reward
but also how their action affects the future public belief π about their private type. It is evident in the
figures that as δ increases, at high π 1 , up to larger values of π 2 player 1 chooses not to contribute when
his type is xL . This way he intends to send a “wrong” signal to player 2 i.e., that his type is xH and
subsequently force player 2 to invest. This way player 1 can free-ride on player 2’s investment.
Now consider p̃1H plotted in Fig. 3. For δ = 0 we know that not contributing is profitable, however as δ
increases from 0, players are mindful of future rewards and thus are willing to contribute at certain beliefs.
Specifically, coordination via signaling is evident here. Although it is instantaneously not profitable to

19

Fig. 3: p̃1L , p̃1H vs. (π 1 , π 2 ) at δ = 0.5 (upper left and right). p̃1L , p̃1H vs. (π 1 , π 2 ) at δ = 0.95 (lower left
and right).

contribute if player 1’s type is xH , by contributing at higher values of π 2 (i.e., player 2’s type is likely
xH ) and low π 1 , player 1 coordinates with player 2 to achieve net profit greater than 0 (reward when
no one contributes). This is possible since the loss when contributing is −0.2 whereas the profit from
free-riding on player 2’s contribution is 1.
Under the equilibrium strategy, beliefs Πt form a Markov chain. One can trace this Markov chain
to study the signaling effect at equilibrium. On numerically simulating this Markov chain for the above
example (at δ = 0.95) we observe that for almost all initial beliefs, within a few rounds players completely
learn each other’s private type truthfully (or at least with very high probability). In other words, players
manage to reveal their private type via their actions at equilibrium and to such an extent that it negates
any possibly incorrect initial belief about their type.
As a measure of cooperative coordination at equilibrium one can perform the following calculation.
Compare the value function V 1 (·, x) of agent 1 arising out of the fixed-point equation, for δ = 0.95 and
x ∈ {xH , xL } (normalize it by multiplying with 1 − δ so that it represents per-round value) with the best
possible attainable single-round reward under a symmetric mixed strategy with a) full coordination and
b) no coordination. Note that the two cases need not be equilibrium themselves, which is why this will
result in a bound on the efficiency of the evaluated equilibria.
In case a), assuming both agents have the same type x, full coordination can lead to the best possible
reward of 1+1−x
= 1 − x2 i.e., agent 1 contributes with probability 0.5 and agent 2 contributes with
2
probability 0.5 but in a coordinated manner so that it doesn’t overlap with agent 1 contributing.
In case b) when agents do not coordinate and invest with probability p each, then the expected singleround reward is p(1 − x) + p(1 − p). The maximum possible value of this expression is (1 − x2 )2 .
For x = xL = 0.2, the range of values of V 1 (π1 , π2 , xL ) over (π1 , π2 ) ∈ [0, 1]2 is [0.865, 0.894]. Whereas
full coordination produces 0.9 and no coordination 0.81. It is thus evident that agents at equilibrium end

20

up achieving reward close to the best possible and gain significantly compared to the strategy of no
coordination.
Similarly for x = xH = 1.2 the range is [0.3, 0.395]. Whereas full coordination produces 0.4 and no
coordination 0.16. The gain via coordination is evident here too.
VIII. C ONCLUSION
In this paper we presented a methodology for evaluating SPBE for games with asymmetric information
and independent private types evolving as controlled Markov processes. The main contribution is a time
decomposition akin to dynamic programming. This decomposition allows one to find SPBE that exhibit
signaling behavior with linear complexity in the time horizon. Using this methodology, dynamic LQG
games with asymmetric information are studied in [39] where it is shown that under certain conditions,
there exists an SPBE of the game with strategies being linear in players’ private types. In [40], authors
extend the finite-horizon model in this paper such that players do not observe their own types, rather make
independent noisy observations of their types. An analogous backward-forward algorithm is presented for
that model. It is worth noting that although structured strategies are useful in making the equilibrium
finding process tractable, no claim can be made about whether the resulting equilibrium outcomes are
better or worse than those corresponding to general strategies. We believe this is an interesting future
research direction. Another interesting future direction is dynamic mechanism design for asymmetric
information systems.
ACKNOWLEDGMENT
The authors wish to acknowledge Vijay Subramanian for his contribution to the paper. Achilleas
Anastasopoulos wishes to acknowledge Ashutosh Nayyar for the fruitful discussion and criticism of an
early draft of this work presented during the ITA 2012 conference.
A PPENDIX A
P ROOF OF L EMMA 1
We prove this Lemma in the following steps.
(a) In Claim 1, we prove that for any policy profile g and ∀t ∈ T , xi1:t for i ∈ N are conditionally
independent given the common information a1:t .
(b) In Claim 2, using Claim 1, we prove that for every fixed strategy g −i of the players −i, ((A1:t−1 , Xti ), Ait )t∈T
is a controlled Markov process for player i.
i 4 g i
i
(c) For a given policy g, we define a policy si of player i from g as sit (ait |a1:t−1
 , xt ) = P (at |a1:t−1
 , xt ).
(d) In Claim 3, we prove that the dynamics of this controlled Markov process (A1:t−1 , Xti ), Ait
under
i −i

t∈T

(si g −i ) are same as under g i.e. Ps g (xit , xit+1 , a1:t ) = Pg (xit , xit+1 , a1:t ).
(e) In Claim 4, we prove that w.r.t. random variables (xt , at ), xit is sufficient for player i’s private information
−i
history xi1:t i.e. Pg (xt , at |a1:t−1 , xi1:t , ait ) = Pg (xt , at |a1:t−1 , xit , ait ).
i −i
(f) From (c), (d) and (e) we then prove the result of the lemma that Ps g (xt , at ) = Pg (xt , at ).

21

Claim 1: For any policy profile g and ∀t,
Pg (x1:t |a1:t−1 ) =

N
Y

i

Pg (xi1:t |a1:t−1 )

(34)

i=1

Proof:
Pg (x1:t , a1:t−1 )
g
x1:t P (x1:t , a1:t−1 )

Qt
QN
i
i
i
i i
i
i
i
i
i
i
n=2 Qn (xn |xn−1 , an−1 )gn (an |a1:n−1 , x1:n )
i=1 Q1 (x1 )g1 (a1 |x1 )
= P QN

Qt
i
i
i
i i
i
i i
i
i
i
i=1 Q (x1 )g1 (a1 |x1 )
n=2 Qn (xn |xn−1 , an−1 )gn (an |a1:n−1 , x1:n )
x1:t

QN
Qt
i
i
i
i i
i
i
i
i
i
i
Q
(x
)g
(a
|x
)
Q
(x
|x
,
a
)g
(a
|a
,
x
)
n−1
1:n−1
n n
1:n
n=2 n n n−1
P 1 1 1 1 1

= Q i=1
Qt
N
i
i
i
i
i i
i
i
i
i
i
|x
(a
)g
)
Q
(x
|x
,
a
)g
(a
|a
,
x
)
Q
(x
i
1 1 1 1
1:n
i=1
n=2 n n n−1 n−1 n n 1:n−1
x1:t
Q
N
Y
Qi (xi )g i (ai |xi ) t Qin (xin |xin−1 , an−1 )gni (ain |a1:n−1 , xi1:n )
=
Qt
P 1 i1 i1 i1 i1 i n=2
i
i
i
i
i
i
Q
(x
)g
(a
|x
)
i
1
1
1
1
n=2 Qn (xn |xn−1 , an−1 )gn (an |a1:n−1 , x1:n )
x
i=1

Pg (x1:t |a1:t−1 ) = P

(35a)
(35b)
(35c)

(35d)

1:t

=

N
Y

i

Pg (xi1:t |a1:t−1 )

(35e)

i=1

Claim 2: For a fixed g −i , {(A1:t−1 , Xti ), Ait }t is a controlled Markov process with state (A1:t−1 , Xti ) and
control action Ait .
Proof:
Pg (ã1:t , xit+1 |a1:t−1 , xi1:t , ai1:t )
X
i
i
=
Pg (ã1:t , xit+1 , x−i
1:t |a1:t−1 , x1:t , at )

(36a)

x−i
1:t

=

X

i
−i
i
i
i
Pg (ã−i
t , xt+1 , x1:t |a1:t−1 , x1:t , at )I(a1:t−1 ,ait ) (ã1:t−1 , ãt )

(36b)

x−i
1:t

!
=

X

P

x−i
1:t

=P

g −i

g −i

(x−i
1:t |a1:t−1 )

Y

i
gtj (ãjt |a1:t−1 , xj1:t ) Qit (xit+1 |xit , ait , ã−i
t )I(a1:t−1 ,ait ) (ã1:t−1 , ãt )

(36c)

j6=i

(ã1:t , xit+1 |a1:t−1 , xit , ait ),

(36d)

i
where (36c) follows from Claim 1 since x−i
1:t is conditionally independent of x1:t given a1:t−1 and the
corresponding probability is only a function of g −i .
For any given policy profile g, we construct a policy si in the following way,
4

sit (ait |a1:t−1 , xit ) = Pg (ait |a1:t−1 , xit )
P
g i
i
xi1:t−1 P (at , x1:t |a1:t−1 )
=P P
i
i
g i
ãit
x̃i1:t−1 P (ãt , x̃1:t−1 xt |a1:t−1 )
P
gi
i
i i
i
xi1:t−1 P (x1:t |a1:t−1 )gt (at |a1:t−1 , x1:t )
=P P
Pgi (x̃i1:t−1 xit |a1:t−1 )gti (ãit |a1:t−1 , x̃i1:t−1 xit )
ãit
x̃i
1:t−1

(37a)
(37b)

(37c)

22

i

= Pg (ait |a1:t−1 , xit ),

(37d)

where dependence of (37c) on only g i is due to Claim 1.
Claim 3: The dynamics of the Markov process {(A1:t−1 , Xti ), Ait }t under (si g −i ) are the same as under
g i.e.,
i −i

Ps g (xit , xit+1 , a1:t ) = Pg (xit , xit+1 , a1:t )

∀t

(38)

Proof: We prove this by induction. Clearly,
i −i

Pg (xi1 ) = Ps g (xi1 ) = Qi1 (xi1 ).

(39)
i −i

Now suppose (38) is true for t − 1 which also implies that the marginals Pg (xit , a1:t−1 ) = Ps g (xit , a1:t−1 ).
Then
Pg (xit , a1:t−1 , xit+1 , at ) = Pg (xit , a1:t−1 )Pg (ait |a1:t−1 , xit )Pg (xit+1 , a1:t |xit , a1:t−1 , ait )
=P

si g −i

(xit , a1:t−1 )sit (ait |a1:t−1 , xit )P

=P

si g −i

(xit , a1:t−1 , xit+1 , at ),

g −i

(xit+1 , a1:t |xit , a1:t−1 , ait )

(40a)
(40b)
(40c)

where (40b) is true from induction hypothesis, definition of si in (37d) and since {(a1:t−1 , xit ), ait }t is a
controlled Markov process as proved in Claim 2 and its update kernel does not depend on policy g i .This
completes the induction step.
Claim 4: For any policy g,
−i

Pg (x̃t , ãt |a1:t−1 , xi1:t , ait ) = Pg (x̃t , ãt |a1:t−1 , xit , ait ).

(41)

−i
i
Pg (x̃t , ãt |a1:t−1 , xi1:t , ait ) = Ixit ,ait (x̃it , ãit )Pg (x̃−i
t , ãt |a1:t−1 , x1:t ).

(42)

Proof:

Now
−i
i
Pg (x̃−i
t , ãt |a1:t−1 , x1:t ) =

X

−i
i
Pg (x̃−i
1:t , ãt |a1:t−1 , x1:t )

(43a)

x̃−i
1:t−1

!
=

X

i
Pg (x̃−i
1:t |a1:t−1 , x1:t )

x̃−i
1:t−1

Y

gtj (ãjt |a1:t−1 , x̃j1:t )

(43b)

j6=i

!
=

X

−i

Pg (x̃−i
1:t |a1:t−1 )

x̃−i
1:t

Y

gtj (ãjt |a1:t−1 , x̃j1:t )

(43c)

j6=i

−i

−i
= Pg (x̃−i
t , ãt |a1:t−1 )

(43d)

where (43c) follows from Claim 1.
Hence
−i

−i
Pg (x̃t , ãt |a1:t−1 , xi1:t , ait ) = Ixit ,ait (x̃it , ãit )Pg (x̃−i
t , ãt |a1:t−1 )

(44a)

23

−i

= Pg (x̃t , ãt |a1:t−1 , xit , ait )

(44b)

Finally,
Pg (x̃t , ãt ) =

X

Pg (x̃t , ãt |a1:t−1 , xi1:t , ait )Pg (a1:t−1 , xi1:t , ait )

(45a)

a1:t−1 xi1:t ait

=

−i

X

Pg (x̃t , ãt |a1:t−1 , xit , ait )Pg (a1:t−1 , xi1:t , ait )

(45b)

a1:t−1 xi1:t ,ait

=

X

−i

Pg (x̃t , ãt |a1:t−1 , xit , ait )Pg (a1:t−1 , xit , ait )

(45c)

a1:t−1 xit ,ait

=

X

−i

i −i

Pg (x̃t , ãt |a1:t−1 , xit , ait )Ps g (a1:t−1 , xit , ait )

(45d)

a1:t−1 xit ,ait
i −i

= Ps g (x̃t , ãt ).

(45e)

where (45b) follows from (41) in Claim 4 and (45d) from (38) in Claim 3.
A PPENDIX B
P ROOF OF L EMMA 2
For this proof we will assume the common agents strategies to be probabilistic as opposed to being
deterministic, as was the case in Section III. This means actions of the common agent, γti ’s are generated
probabilistically from ψ i as Γit ∼ ψti (·|a1:t−1 ), as opposed to being deterministically generated as γti =
ψti [a1:t−1 ], as before. These two are equivalent ways of generating actions ait from a1:t−1 and xit . We avoid
using the probabilistic strategies of common agent throughout the main text for ease of exposition, and
because it conceptually does not affect the results.
Proof: We prove this lemma in the following steps. We view this problem from the perspective
of a common agent. Let ψ be the coordinator’s policy corresponding to policy profile g. Let πti (xit ) =
i
Pψ (xit |a1:t−1 ).
Q
i
i i
(a) In Claim 5, we show that πt can be factorized as πt (xt ) = N
i=1 πt (xt ) where each πt can be updated
i
through an update function πt+1
= F i (πti , γti , at ) and F i is independent of common agent’s policy ψ.
(b) In Claim 6, we prove that (Πt , Γt )t∈T is a controlled Markov process.
4
(c) We construct a policy profile θ from g such that θt (dγt |πt ) = Pψ (dγt |πt ).
(d) In Claim 7, we prove that dynamics of this Markov process (Πt , Γt )t∈T under θ is same as under ψ i.e.
Pθ (dπt , dγt , dπt+1 ) = Pψ (dπt , dγt , dπt+1 ).
(e) In Claim 8, we prove that with respect to random variables (Xt , At ), πt can summarize common
information a1:t−1 i.e. Pψ (xt , at |a1:t−1 , γt ) = P(xt , at |πt , γt ).
(f) From (c), (d) and (e) we then prove the result of the lemma that Pψ (xt , at ) = Pθ (xt , at ) which is
equivalent to Pg (xt , at ) = Pm (xt , at ), where m is the policy profile of players corresponding to θ.
Q
i i
i
Claim 5: πt can be factorized as πt (xt ) = N
i=1 πt (xt ) where each πt can be updated through an
i
update function πt+1
= F i (πti , γti , at ) and F i is independent of common agent’s policy ψ. We also say
π t+1 = F (π t , γt , at ).

24

Proof: We prove this by induction. Since π1 (x1 ) =
Q
i
suppose πt = N
i=1 πt . Then,

QN

i=1

Qit (xi1 ), the base case is verified. Now

πt+1 (xt+1 ) = Pψ (xt+1 |a1:t , γ1:t+1 )

(46a)

= Pψ (xt+1 |a1:t , γ1:t )
P ψ
P (xt , at , xt+1 |a1:t−1 , γ1:t )
= P xt
ψ
x̃t+1 x̃t P (x̃t , x̃t+1 , at |a1:t−1 , γ1:t )
P
QN i i i i i
i
xt πt (xt )
i=1 γt (at |xt )Qt (xt+1 |xt , at )
=P
QN i i i i i
i
i=1 γt (at |x̃t )Qt (x̃t+1 |x̃t , at )
x̃t x̃t+1 πt (x̃t )
P i i i i i i i
N
i
Y
xit πt (xt )γt (at |xt )Qt (xt+1 |xt , at )
P i i i i i
=
x̃it πt (x̃t )γt (at |x̃t )
i=1
=

N
Y

i
πt+1
(xit+1 ),

(46b)
(46c)
(46d)
(46e)
(46f)

i=1

where (46e) follows from induction hypothesis. It is assumed in (46c)-(46e) that the denominator is not
0. If denominator corresponding to any γti is zero, we define
X
i
πt+1
(xit+1 ) =
πti (xit )Qit (xit+1 |xit , at ),
(47)
xit
i
= F i (πti , γti , at ) and π t+1 = F (π t , γt , a1 ) where F i and F are
where πt+1 still satisfies (46f). Thus πt+1
appropriately defined from above.
Claim 6: (Πt , Γt )t∈T is a controlled Markov process with state Πt and control action Γt
Proof:
X
Pψ (dπt+1 , at , xt |π1:t , γ1:t )
(48a)
Pψ (dπt+1 |π1:t , γ1:t ) =
at ,xt

=

X

Pψ (xt |π1:t , γ1:t )

at ,xt

=

X
at ,xt

(N
Y

)
γti (ait |xit ) IF (πt ,γt ,at ) (πt+1 )

(48b)

i=1

πt (xt )

(N
Y

)
γti (ait |xit ) IF (πt ,γt ,at ) (πt+1 )

(48c)

i=1

= P(dπt+1 |πt , γt ).

(48d)

For any given policy profile ψ, we construct policy profile θ in the following way.
4

θt (dγt |πt ) = Pψ (dγt |πt ).

(49)

Claim 7:
Pψ (dπt , dγt , dπt+1 ) = Pθ (dπt , dγt , dπt+1 )

∀t ∈ T .

(50)

25

Proof: We prove this by induction. For t = 1,
Pψ (dπ1 ) = Pθ (dπ1 ) = IQ (π1 ).

(51)

Now suppose P ψ (dπt ) = P θ (dπt ) is true for t, then
Pψ (dπt , dγt , dπt+1 ) = Pψ (dπt )P ψ (dγt |πt )Pψ (dπt+1 |πt γt )

(52a)

= Pθ (dπt )θt (dγt |πt )P (dπt+1 |πt , γt )

(52b)

= Pθ (dπt , dγt , dπt+1 ).

(52c)

where (52b) is true from induction hypothesis, definition of θ in (49) and since (Πt , Γt )t∈T is a controlled
Markov process as proved in Claim 6 and thus its update kernel does not depend on policy ψ. This
completes the induction step.
Claim 8: For any policy ψ,
Pψ (xt , at |a1:t−1 , γt ) = P(xt , at |πt , γt ).

(53)

Proof:
Pψ (xt , at |a1:t−1 , γt ) = Pψ (xt |a1:t−1 , γt )

Y

γti (ait |xit )

(54a)

i∈N

= πt (xt )

Y

γti (ait |xit )

(54b)

i∈N

= P(xt , at |πt , γt ).

(54c)

Pψ (xt , at |a1:t−1 , γt )Pψ (a1:t−1 , γt )

(55a)

P(xt , at |πt , γt )Pψ (a1:t−1 , γt )

(55b)

Finally,
Pψ (xt , at ) =

X
a1:t−1 ,γt

=

X
a1:t−1 γt

=

X

P(xt , at |πt , γt )Pψ (πt , γt )

(55c)

P(xt , at |πt , γt )Pθ (πt , γt )

(55d)

πt ,γt

=

X
πt ,γt

= Pθ (xt , at ).
where (55b) follows from (53), (55c) is due to change of measure and (55d) follows from (50).

(55e)

26

A PPENDIX C
P ROOF OF T HEOREM 1
Proof: We prove (18) using induction and the results in Lemma 3, 4 and 5 proved in Appendix D.
For base case at t = T , ∀i ∈ N , (a1:T −1 , xi1:T ) ∈ HTi , β i
n
o
∗,i ∗,−i
∗
(56a)
EβT βT , µT [a1:T −1 ] RTi (XT , AT ) a1:T −1 , xi1:T = VTi (µ∗T [a1:T −1 ], xiT )
o
n
i ∗,−i
∗
≥ EβT βT , µT [a1:T −1 ] RTi (XT , AT ) a1:T −1 , xi1:T , (56b)
where (56a) follows from Lemma 5 and (56b) follows from Lemma 3 in Appendix D.
c
Let the induction hypothesis be that for t + 1, ∀i ∈ N , a1:t ∈ Ht+1
, xi1:t+1 ∈ (X i )t+1 , β i ,
( T
)
X
∗,i
∗,−i
∗
Eβt+1:T βt+1:T , µt+1 [a1:t ]
Rni (Xn , An ) a1:t , xi1:t+1

(57a)

n=t+1
∗,−i
i
βt+1:T
βt+1:T
, µ∗t+1 [a1:t ]

≥E

(

T
X

)
Rni (Xn , An ) a1:t , xi1:t+1

.

(57b)

n=t+1

Then ∀i ∈ N , (a1:t−1 , xi1:t ) ∈ Hti , β i , we have
( T
)
X
∗,i ∗,−i
∗
Eβt:T βt:T , µt [a1:t−1 ]
Rni (Xn , An ) a1:t−1 , xi1:t
=

n=t
i
∗
i
Vt (µt [a1:t−1 ], xt )

(58a)

o
n
i
i
≥E
Rti (Xt , At ) + Vt+1
(µ∗t+1 [a1:t−1 At ], Xt+1
) a1:t−1 , xi1:t
(
( T
X
∗,i
∗,−i
βti βt∗,−i , µ∗t [a1:t−1 ]
i
βt+1:T
βt+1:T
, µ∗t+1 [a1:t−1 ,At ]
=E
Rt (Xt , At ) + E
Rni (Xn , An )
βti βt∗,−i , µ∗t [a1:t−1 ]

(58b)

n=t+1

o

a1:t−1 , At , xi1:t+1 a1:t−1 , xi1:t

i ∗,−i
∗
≥ Eβt βt , µt [a1:t−1 ] Rti (Xt , At )+
( T
)
)
X
∗,−i
i
∗
i
Eβt+1:T βt+1:T µt+1 [a1:t−1 ,At ]
Rni (Xn , An ) a1:t−1 , At , xi1:t , Xt+1
a1:t−1 , xi1:t
βti βt∗,−i , µ∗t [a1:t−1 ]

=E

i β ∗,−i µ∗ [a
βt:T
t 1:t−1 ]
t:T

E

(

(58c)

(58d)

n=t+1
n
i
Rt (Xt , At )+
T
X

)
i
Rni (Xn , An ) a1:t−1 , At , xi1:t , Xt+1

a1:t−1 , xi1:t

o

(58e)

n=t+1
i β ∗,−i
βt:T
t:T

=E

µ∗t [a1:t−1 ]

( T
X

)
Rni (Xn , An ) a1:t−1 , xi1:t

,

(58f)

n=t

where (58a) follows from Lemma 5, (58b) follows from Lemma 3, (58c) follows from Lemma 5, (58d)
follows from induction hypothesis in (57b) and (58e) follows from Lemma 4. Moreover, construction of
θ in (13), and consequently definition of β ∗ in (16) are pivotal for (58e) to follow from (58d).
We note that µ∗ satisfies the consistency condition of [5, p. 331] from the fact that (a) for all t and for
every common history a1:t−1 , all players use the same belief µ∗t [a1:t−1 ] on xt and (b) the belief µ∗t can be
Q
∗,i
∗,i
c
i
factorized as µ∗t [a1:t−1 ] = N
i=1 µt [a1:t−1 ] ∀a1:t−1 ∈ Ht where µt is updated through Bayes’ rule F as
in Lemma 5 in Appendix B.

27

A PPENDIX D
I NTERMEDIATE LEMMAS USED IN PROOF OF T HEOREM 1
Lemma 3: ∀t ∈ T , i ∈ N , (a1:t−1 , xi1:t ) ∈ Hti , βti
Vti (µ∗t [a1:t−1 ], xit ) ≥
βti βt∗,−i , µ∗t [a1:t−1 ]

E

o
n
i
i
i
i
∗
∗
Rt (Xt , At ) + Vt+1 (F (µt [a1:t−1 ], βt (·|a1:t−1 , ·), At ), Xt+1 ) a1:t−1 , x1:t . (59)

Proof: We prove this Lemma by contradiction.
Suppose the claim is not true for t. This implies ∃i, βbti , b
a1:t−1 , x
bi1:t such that
o
n
i
βbti βt∗,−i , µ∗t [b
a1:t−1 ]
i
i
i
∗
∗
E
Rt (Xt , At ) + Vt+1 (F (µt [b
a1:t−1 , x
b1:t
a1:t−1 , ·), At ), Xt+1 ) b
a1:t−1 ], βt (·|b
> Vti (µ∗t [b
a1:t−1 ], x
bit ). (60)
We will show that this leads to a contradiction.
Construct
(
bit
a1:t−1 , x
bi1:t ) xit = x
βbti (ait |b
γ
bti (ait |xit ) =
arbitrary
otherwise.

(61)

Then for b
a1:t−1 , x
bi1:t , we have
Vti (µ∗t [b
a1:t−1 ], x
bit )
o
n
∗
∗
i
i
i i −i
i
= max
E
a1:t−1 ], βt (·|b
a1:t−1 , ·), At ), Xt+1 ) x
bt , (62a)
Rt (b
xt xt , at ) + Vt+1 (F (µt [b
γti (·|b
xit )
o
n
∗,−i
i
i
∗
i
i
a1:t−1 ], βt∗ (·|b
a1:t−1 , ·), At ), Xt+1
)x
bit
(62b)
≥ Eγbt (·|bxt )βt , µt [ba1:t−1 ] Rti (Xt , At ) + Vt+1
(F (µ∗t [b
n
o
X
i
∗
=
Rti (b
xit x−i
a1:t−1 ], βt∗ (·|b
a1:t−1 , ·), at ), xit+1 )
t , at ) + Vt+1 (F (µt [b
γti (·|b
xit )βt∗,−i , µ∗t [b
a1:t−1 ]

x−i
t ,at ,xt+1

=

i i
× µ∗,−i
[b
a1:t−1 ](x−i
γti (ait |b
xit )βt∗,−i (a−i
a1:t−1 , x−i
xit , at )
t
t )b
t |b
t )Qt (xt+1 |b
o
n
X
∗
∗
i
i i −i
i
a1:t−1 ], βt (·|b
a1:t−1 , ·), at ), xt+1 )
Rt (b
xt xt , at ) + Vt+1 (F (µt [b

(62c)

x−i
t ,at ,xt+1
i i
bi i a1:t−1 , x
a1:t−1 , x−i
xit , at )
bi1:t )βt∗,−i (a−i
× µ∗,−i
[b
a1:t−1 ](x−i
t
t |b
t )Qt (xt+1 |b
t )βt (at |b
o
n
bi ∗,−i ∗
i
∗
∗
i
i
= Eβt βt ,µt [ba1:t−1 ] Rti (b
xit x−i
,
a
)
+
V
(F
)
b
a
,
x
b
(µ
[b
a
],
β
(·|b
a
,
·),
A
),
X
t
1:t−1
t
1:t−1
t+1
1:t
t
t
t+1
t 1:t−1

(62d)

> Vti (µ∗t [b
a1:t−1 ], x
bit ),

(62f)

(62e)

where (62a) follows from definition of Vti in (14), (62d) follows from definition of γ
bti and (62f) follows
from (60). However this leads to a contradiction.
i
Lemma 4: ∀i ∈ N , t ∈ T , (a1:t , xi1:t+1 ) ∈ Ht+1
and βti
( T
)
X
i β ∗,−i , µ∗ [a
βt:T
]
i
i
t 1:t−1
t:T
E
Rn (Xn , An ) a1:t , x1:t+1
(63a)
n=t+1

=E

∗,−i
i
βt+1:T
βt+1:T
, µ∗t+1 [a1:t ]

(

T
X

n=t+1

)
Rni (Xn , An ) a1:t , xi1:t+1

.

(63b)

28

Thus the above quantities do not depend on βti .
∗,−i
Proof: Essentially this claim stands on the fact that µt+1
[a1:t ] can be updated from µt∗,−i [a1:t−1 ], βt∗,−i
Q
∗,j
∗,j
and at , as µ∗,−i
t+1 [a1:t ] =
j6=i F (µt [a1:t−1 ], βt , at ) as in Claim 5. Since the above expectations involve
−i
random variables Xt+1
, At+1:T , Xt+2:T , we consider the probability
∗,−i

i

Pβt:T βt:T

, µ∗t [a1:t−1 ]

i
(x−i
t+1 , at+1:T , xt+2:T |a1:t , x1:t+1 ) =

Nr
Dr

(64)

where
Nr =

X

i

∗,−i

∗,−i

, µ∗t [a1:t−1 ]

Pβt:T βt:T

, µ∗t [a1:t−1 ]

i
(x−i
t , at , xt+1 , at+1:T , xt+2:T |a1:t−1 , x1:t )

(65a)

x−i
t

=

X

i

Pβt:T βt:T

i
(x−i
t a1:t−1 , x1:t )

x−i
t
∗,−i

i

−i
βt:T βt:T
βti (ait |a1:t−1 , xi1:t )βt∗,−i (a−i
t |a1:t−1 , xt )Q(xt+1 |xt , at )P

=

X

, µ∗t [a1:t−1 ]

(at+1:T , xt+2:T |a1:t , xi1:t−1 , xt:t+1 )
(65b)

i i
i
µt∗,−i [a1:t−1 ](x−i
t )βt (at |a1:t−1 , x1:t )

x−i
t
i

∗,−i

∗

−i
i i
i
−i −i
−i
βt+1:T βt+1:T , µt+1 [a1:t ]
βt∗,−i (a−i
(at+1:T , xt+2:T |a1:t , xi1:t , xt+1 ),
t |a1:t−1 , xt )Q (xt+1 |xt , at )Q (xt+1 |xt , at )P
(65c)

where (65c) follows from the conditional independence of types given common information, as shown
in Claim 1, and the fact that probability on (at+1:T , x2+t:T ) given a1:t , xi1:t−1 , xt:t+1 , µ∗t [a1:t−1 ] depends on
∗,−i
i
βt+1:T
. Similarly, the denominator in (64) is given by
a1:t , xi1:t , xt+1 , µ∗t+1 [a1:t ] through βt+1:T
X i ∗,−i ∗
i
i
Pβt:T βt:T , µt [a1:t−1 ] (x̃−i
Dr =
t , at , xt+1 a1:t−1 , x1:t )
x̃−i
t

X

i

∗,−i

Pβt:T βt:T

, µ∗t

∗,−i −i
i
i i
i
i i
i
(x̃−i
(at |a1:t−1 , x̃−i
t |a1:t−1 , x1:t )βt (at |a1:t−1 , x1:t )βt
t )Q (xt+1 |xt , at )

(65d)

x̃−i
t

=

X

∗,−i −i
i i
i
i i
i
µ∗,−i
[a1:t−1 ](x̃−i
(at |a1:t−1 , x̃−i
t
t )βt (at |a1:t−1 , x1:t )βt
t )Q (xt+1 |xt , at ).

(65e)

x̃−i
t

By canceling the terms βti (·) and Qi (·) in the numerator and the denominator, (64) is given by
P
∗,−i −i
−i
−i
−i
µ∗,−i
[a1:t−1 ](x−i
(at |a1:t−1 , x−i
t
t )βt
t )Qt+1 (xt+1 |xt , at )
x−i
t
P
∗,−i −i
µ∗,−i
[a1:t−1 ](x̃−i
(at |a1:t−1 , x̃−i
t
t )βt
t )
x̃−i
t
i

∗,−i

∗

× Pβt+1:T βt+1:T , µt+1 [a1:t ] (at+1:T , xt+2:T |a1:t , xi1:t , xt+1 )
−i
= µ∗,−i
t+1 [a1:t ](xt+1 )P

=P

∗,−i
i
βt+1:T
βt+1:T
, µ∗t+1 [a1:t ]

∗,−i
i
βt+1:T
βt+1:T
, µ∗t+1 [a1:t ]

(at+1:T , xt+2:T |a1:t , xi1:t , xt+1 )

i
(x−i
t+1 , at+1:T , xt+2:T |a1:t , x1:t+1 ),

(65f)
(65g)
(65h)

∗,−i
where (65g) follows from using the definition of µt+1
[a1:t ](x−i
t ) in the forward recursive step in (17) and
the definition of the belief update in (46).
Lemma 5: ∀i ∈ N , t ∈ T , (a1:t−1 , xi1:t ) ∈ Hti ,
)
( T
X
∗,i ∗,−i ∗
Rni (Xn , An ) a1:t−1 , xi1:t .
(66)
Vti (µ∗t [a1:t−1 ], xit ) = Eβt:T βt:T ,µt [a1:t−1 ]
n=t

29

Proof: We prove the lemma by induction. For t = T ,
n
o
∗,i ∗,−i
∗
EβT βT , µT [a1:T −1 ] RTi (XT , AT ) a1:T −1 , xi1:T
X
∗,−i −i
∗,i i
i
=
(aT |a1:T −1 , x−i
RTi (xT , aT )µ∗T [a1:T −1 ](x−i
T )
T )βT (aT |a1:T −1 , xT )βT

(67a)

x−i
T aT

= VTi (µ∗T [a1:T −1 ], xiT ),

(67b)

where (67b) follows from the definition of Vti in (14) and the definition of βT∗ in the forward recursion
in (16).
i
Suppose the claim is true for t + 1, i.e., ∀i ∈ N , t ∈ T , (a1:t , xi1:t+1 ) ∈ Ht+1
)
( T
X
∗,i
∗,−i
∗
i
(68)
Rni (Xn , An ) a1:t , xi1:t+1 .
(µ∗t+1 [a1:t ], xit+1 ) = Eβt+1:T βt+1:T , µt+1 [a1:t ]
Vt+1
n=t+1

Then ∀i ∈ N , t ∈ T , (a1:t−1 , xi1:t ) ∈ Hti , we have
( T
)
X
∗,i ∗,−i
∗
Eβt:T βt:T , µt [a1:t−1 ]
Rni (Xn , An ) a1:t−1 , xi1:t
n=t
∗,i ∗,−i
βt:T
βt:T , µ∗t [a1:t−1 ]

=E
( T
X

n
∗,i ∗,−i
∗
Rti (Xt , At ) + Eβt:T βt:T , µt [a1:t−1 ]
)
)

i
Rni (Xn , An ) a1:t−1 , At , xi1:t , Xt+1

a1:t−1 , xi1:t

(69a)

n=t+1


∗,i ∗,−i
∗
= Eβt:T βt:T , µt [a1:t−1 ] Rti (Xt , At )+
( T
)
)
X
i
Rni (Xn , An ) a1:t−1 , At , xi1:t , Xt+1
a1:t−1 , xi1:t

(69b)

n=t+1

n
o
i
i
∗
i
i
=E
Rt (Xt , At ) + Vt+1 (µt+1 [a1:t−1 At ], Xt+1 ) a1:t−1 , x1:t
n
o
βt∗,i βt∗,−i , µ∗t [a1:t−1 ]
i
∗
i
i
i
=E
Rt (Xt , At ) + Vt+1 (µt+1 [a1:t−1 At ], Xt+1 ) a1:t−1 , x1:t

(69d)

= Vti (µ∗t [a1:t−1 ], xit ),

(69e)

∗,i ∗,−i
βt:T
βt:T , µ∗t [a1:t−1 ]

(69c)

where (69b) follows from Lemma 4 in Appendix D, (69c) follows from the induction hypothesis in (68),
i
(69d) follows because the random variables involved in expectation, Xt−i , At , Xt+1
do not depend on
∗,i
∗,−i
βt+1:T βt+1:T and (69e) follows from the definition of βt∗ in the forward recursion in (16), the definition
of µ∗t+1 in (17) and the definition of Vti in (14).
A PPENDIX E
P ROOF OF T HEOREM 2
Proof: We prove this by contradiction. Suppose for any equilibrium generating function φ that
generates (β ∗ , µ∗ ) through forward recursion, there exists t ∈ T , i ∈ N , a1:t−1 ∈ Htc , such that for
π t = µ∗t [a1:t−1 ], (13) is not satisfied for φ i.e. for γ̃ti = φi [π t ] = βt∗,i (·|µ∗t [a1:t−1 ], xit ),
n
o
i
γti (·|xi )γ̃t−i , πt
i
i
i
i
γ̃t 6∈ arg max
E
Rt (Xt , At ) + Vt+1 (F (π t , γ̃t , At ), Xt+1 ) xt .
(70)
i
γt

30

Let t be the first instance in the backward recursion when this happens. This implies ∃ γ
bti such that
n
o
i
i −i
i
i
(F (π t , γ̃t , At ), Xt+1
) xit
Eγbt (·|x )γ̃t , πt Rti (Xt , At ) + Vt+1
o
n
i
i −i
i
i
(F (π t , γ̃t , At ), Xt+1
(71)
) xit
> Eγ̃t (·|x )γ̃t , πt Rti (Xt , At ) + Vt+1
This implies for βbt (·|µ∗t [a1:t−1 ], ·) = γ
bti ,
)
( T
X
∗,i ∗,−i
∗
Rni (Xn , An ) a1:t−1 , xi1:t
Eβt:T βt:T , µt [a1:t−1 ]
n=t
βt∗,i βt∗,−i , µ∗t [a1:t−1 ]

=E
( T
X

n
∗,i ∗,−i
∗
Rti (Xt , At ) + Eβt:T βt:T , µt [a1:t−1 ]
)
)

Rni (Xn , An ) a1:t−1 , At , xi1:t+1

a1:t−1 , xi1:t

(72a)

n=t+1
βt∗,i βt∗,−i , µ∗t [a1:t−1 ]

=E
( T
X

n
∗,i
∗,−i
∗
Rti (Xt , At ) + Eβt+1:T βt+1:T , µt+1 [a1:t−1 ,At ]
)
)

Rni (Xn , An ) a1:t−1 , At , xi1:t+1

a1:t−1 , xi1:t

(72b)

n=t+1

n
o
i
i
Rti (Xt , At ) + Vt+1
(F (π t , γ̃t , At ), Xt+1
) xit
o
n
∗
i −i
bi
i
i
) xit
< Eβt (·|µt [a1:t−1 ],xt )γ̃t , πt Rti (Xt , At ) + Vt+1
(F (π t , γ̃t , At ), Xt+1
n
∗,i
∗,−i
∗
βbti βt∗,−i , µ∗t [a1:t−1 ]
=E
Rti (Xt , At ) + Eβt+1:T βt+1:T µt+1 [a1:t−1 ,At ]
( T
)
o
X
i
Rni (Xn , An ) a1:t−1 , At , xi1:t , Xt+1
a1:t−1 , xi1:t
i

i

−i

= Eγ̃t (·|xt )γ̃t

, πt

(72c)
(72d)

(72e)

n=t+1
∗,i
∗,−i
βbti ,βt+1:T
βt:T
, µ∗t [a1:t−1 ]

=E

( T
X

)
Rni (Xn , An ) a1:t−1 , xi1:t

,

(72f)

n=t

where (72b) follows from Lemma 4, (72c) follows from the definitions of γ̃ti and µ∗t+1 [a1:t−1 , At ] and
Lemma 5, (72d) follows from (71) and the definition of βbti , (72e) follows from Lemma 3, (72f) follows
from Lemma 4. However, this leads to a contradiction since (β ∗ , µ∗ ) is a PBE of the game.
A PPENDIX F
P ROOF OF T HEOREM 3
We divide the proof into two parts: first we show that the value function V i is at least as big as any
reward-to-go function; secondly we show that under the strategy βi∗ , reward-to-go is V i .
Part 1: For any i ∈ N , β i define the following reward-to-go functions
)
(∞
X
i
i
−i,∗
∗
c
(73a)
Wti,β (hit ) = Eβ ,β ,µt [ht ]
δ n−t Ri (Xn , An ) | hit
( T
)
n=t
X
i,β i ,T
i
β i ,β −i,∗ ,µ∗t [hct ]
n−t i
δ R (Xn , An ) + δ T +1−t V i (ΠT +1 , XTi +1 ) | hit .
Wt
(ht ) = E
(73b)
n=t
i

Since X i , Ai are finite sets the reward Ri is absolutely bounded, the reward-to-go Wti,β (hit ) is finite ∀
i, t, β i , hit .

31

For any i ∈ N , hit ∈ Hti ,

 





i,β i
i,β i ,T
i,β i ,T
i,β i
∗ c
i
i
i
∗ c
i
i
i
i
i
(ht ) + Wt
(ht ) − Wt (ht ) (74)
V µt [ht ], xt − Wt (ht ) = V µt [ht ], xt − Wt
Combining results from Lemmas 8 and 9 in Appendix G, the term in the first bracket in RHS of (74) is
non-negative. Using (73), the term in the second bracket is


∞
X
 β i ,β −i,∗ ,µ∗ [hc ]
n−(T +1) i
i
T +1−t
i
i
t
t
−
δ
R (Xn , An ) + V (ΠT +1 , XT +1 ) | ht .
E
δ
(75)
n=T +1

The summation in the expression above is bounded by a convergent geometric series. Also, V i is bounded.
Hence the above quantity can be made arbitrarily small by choosing T appropriately large. Since the LHS
of (74) does not depend on T , this results in


i
(76)
V i µ∗t [hct ], xit ≥ Wti,β (hit ).
Part 2: Since the strategy β ∗ generated in (21) is such that βti,∗ depends on hit only through µ∗t [hct ]
i,∗
and xit , the reward-to-go Wti,β , at strategy β ∗ , can be written (with abuse of notation) as
)
(∞
X
i,∗
i,∗
∗
∗
c
Wti,β (hit ) = Wti,β (µ∗t [hct ], xit ) = Eβ ,µt [ht ]
(77)
δ n−t Ri (Xn , An ) | µ∗t [hct ], xit .
n=t

For any hit ∈ Hti ,
i,∗
Wti,β (µ∗t [hct ], xit )

V

i

(µ∗t [hct ], xit )

β ∗ ,µ∗t [hct ]

= E

β ∗ ,µ∗t [hct ]

= E


o
n

i,β i,∗
∗ c
∗ c
i
∗ c
i
i
R (Xt , At ) + δWt+1 F (µt [ht ], θ[µt [ht ]], At+1 ), Xt+1 | µt [ht ], xt

 (78a)



∗ c
∗ c
i
∗ c
i
i
i
R (Xt , At ) + δV F (µt [ht ], θ[µt [ht ]], At+1 ), Xt+1 | µt [ht ], xt . (78b)

Repeated application of the above for the first n time periods gives


t+n−1




X
i,β i,∗
i,β i,∗
∗ c
i
β ∗ ,µ∗t [hct ]
m−t i
n
i
∗ c
i
δ
R (Xt , At ) + δ Wt+n Πt+n , Xt+n | µt [ht ], xt
(79a)
Wt
(µt [ht ], xt ) = E


m=t



 t+n−1


X
i
∗ c
i
β ∗ ,µ∗t [hct ]
∗ c
i
i
m−t i
n i
V (µt [ht ], xt ) = E
δ
R (Xt , At ) + δ V Πt+n , Xt+n | µt [ht ], xt . (79b)


m=t

Here Πt+n is the n−step belief update under strategy and belief prescribed by β ∗ , µ∗ .
Taking differences results in
i,∗

Wti,β (µ∗t [hct ], xit ) − V i (µ∗t [hct ], xit )
= δ n Eβ

∗ ,µ∗ [hc ]
t t

n

i,∗

i,β
Wt+n






o
i
i
Πt+n , Xt+n
− V i Πt+n , Xt+n
| µ∗t [hct ], xit . (80)

Taking absolute value of both sides then using Jensen’s inequality for f (x) = |x| and finally taking
supremum over hit reduces to
i,∗

sup Wti,β (µ∗t [hct ], xit ) − V i (µ∗t [hct ], xit )
hit

≤ δ n sup Eβ
hit

∗ ,µ∗ [hc ]
t t

n

o
i,β i,∗
i
Wt+n
(Πt+n , Xt+n
) − V i (µ∗t [hct ], xit ) | µ∗t [hct ], xit . (81)

Now using the fact that Wt+n , V i are bounded and that we can choose n arbitrarily large, we get
i,∗
suphit |Wti,β (µ∗t [hct ], xit ) − V i (µ∗t [hct ], xit )| = 0.

32

A PPENDIX G
I NTERMEDIATE L EMMA USED IN P ROOF OF T HEOREM 3
In this section, we present four lemmas. Lemma 6 and 7 are intermediate technical results needed in
the proof of Lemma 8. Then the results in Lemma 8 and 9 are used in Appendix F for the proof of
Theorem 3. The proofs for Lemma 6 and 7 below aren’t stated as they are analogous (the only difference
being a non-zero terminal reward in the finite horizon model) to the proofs of Lemma 3 and 4, from
Appendix D, used in the proof of Theorem 1.
i
Define the reward-to-go Wti,β ,T for any agent i and strategy β i as
i
Wti,β ,T (hit )

β i ,β −i,∗ ,µ∗t [hct ]

=E

T
hX

i
δ n−t Ri (Xn , An ) + δ T +1−t Gi (ΠT +1 , XTi +1 ) | hit .

(82)

n=t

Here agent i’s strategy is β whereas all other agents use strategy β −i,∗ defined above. Since X i , Ai are
assumed to be finite and Gi absolutely bounded, the reward-to-go is finite ∀ i, t, β i , hit .
In the following, any quantity with a T in the superscript refers the finite horizon model with terminal
reward Gi . For further discussion, please refer to the comments after the statement of Theorem 3.
Lemma 6: For any t ∈ T , i ∈ N , hit and β i ,

h

i
i −i,∗ ∗ c
i,T
i
F (µ∗t [hct ], βt∗ (·|µ∗t [hct ], ·), At ), Xt+1
Vti,T (µ∗t [hct ], xit ) ≥ Eβ ,β ,µt [ht ] Ri (Xt , At ) + δVt+1
| hit . (83)
i

Lemma 7:
i

−i,∗

∗

c

Eβt+1:T ,βt+1:T ,µt+1 [ht ,at ]

T
h X

δ n−(t+1) Ri (Xn , An ) + δ T +1−t Gi (ΠT +1 , XTi +1 ) | hit , at , xit+1

i

n=t+1
i ,β −i,∗ ,µ∗ [hc ]
βt:T
t t
t:T

=E

T
h X

δ

n−(t+1)

i

R (Xn , An ) + δ

T +1−t

i

G

(ΠT +1 , XTi +1 )

|

hit , at , xit+1

i

. (84)

n=t+1

The result below shows that the value function from the backwards recursive algorithm is higher than any
reward-to-go.
Lemma 8: For any t ∈ T , i ∈ N , hit and β i ,
i

Vti,T (µ∗t [hct ], xit ) ≥ Wti,β ,T (hit ).

(85)

Proof: We use backward induction for this. At time T , using the maximization property from (13)
(modified with terminal reward Gi ),
VTi,T (µ∗T [hcT ], xiT )
i,T

(86a)
h
c

(·|xiT ),γ̃T−i,T ,µ∗T [ht ]





i

Ri (XT , AT ) + δGi F (µ∗T [hcT ], γ̃TT , AT ), XTi +1 | µ∗T [hcT ], xiT
h


i
i,T
−i,T ∗
i
c
≥ EγT (·|xT ),γ̃T ,µT [ht ] Ri (XT , AT ) + δGi F (µ∗T [hcT ], γ̃TT , AT ), XTi +1 | µ∗T [hcT ], xiT
, Eγ̃T

i

= WTi,β ,T (hiT )

(86b)
(86c)
(86d)

Here the second inequality follows from (13) and (14) and the final equality is by definition in (82).
Assume that the result holds for all n ∈ {t + 1, . . . , T }, then at time t we have
Vti,T (µ∗t [hct ], xit )

(87a)

33

i

−i,∗

≥ Eβt ,βt

,µ∗t [hct ]

βti ,βt−i,∗ ,µ∗t [hct ]

≥E

h


i

i,T
i
| hit
Ri (Xt , At ) + δVt+1
F (µ∗t [hct ], βt∗ (·|µ∗t [hct ], ·), At ), Xt+1

T
h
h X
−i,∗
i
i
βt+1:T
,βt+1:T
,µ∗t+1 [hct ,At ]
R (Xt , At ) + δE
δ n−(t+1) Ri (Xn , An )

(87b)
(87c)

n=t+1

+δ

T −t

i

G

(ΠT +1 , XTi +1 )

i ,β −i,∗ ,µ∗ [hc ]
βt:T
t t
t:T

=E

T
hX

δ

|

i
hit , At , Xt+1

n−t

i

i

|

hit

i

R (Xn , An ) + δ

T +1−t

i

G

(ΠT +1 , XTi +1 )

|

hit

i

(87d)

n=t
i

= Wti,β ,T (hit )

(87e)

Here the first inequality follows from Lemma 6, the second inequality from the induction hypothesis, the
third equality follows from Lemma 7 and the final equality by definition (82).
The following result highlights the similarities between the fixed-point equation in infinite horizon and
the backwards recursion in the finite horizon.
Lemma 9: Consider the finite horizon game with Gi ≡ V i . Then Vti,T = V i , ∀ i ∈ N , t ∈ {1, . . . , T }
satisfies the backwards recursive construction stated above (adapted from (13) and (14)).
Proof: Use backward induction for this. Consider the finite horizon algorithm at time t = T , noting
i
i
that VTi,T
+1 ≡ G ≡ V ,
h

i

−i,T
−i
i
i
γ̃Ti,T (· | xiT ) ∈ argmax EγT (·|xT ),γ̃T ,πT Ri (XT , AT ) + δV i F (π T , γ̃TT , AT ), XTi +1 | π T , xiT (88a)
γTi (·|xiT )∈∆(Ai )
i,T

VTi,T (π T , xiT ) = Eγ̃T

(·|xiT ),γ̃T−i,T ,π −i
T

h


i

Ri (XT , AT ) + δV i F (π T , γ̃TT , AT ), XTi +1 | π T , xiT .

(88b)

Comparing the above set of equations with (20), we can see that the pair (V, γ̃) arising out of (20)
satisfies the above. Now assume that Vni,T ≡ V i for all n ∈ {t + 1, . . . , T }. At time t, in the finite horizon
i,T
construction from (13), (14), substituting V i in place of Vt+1
from the induction hypothesis, we get the
i,T
i
same set of equations as (88). Thus Vt ≡ V satisfies it.
A PPENDIX H
P ROOF OF T HEOREM 4
Denote the vector correspondence defined by the RHS of (27) by

 

φ1 (x)
argmaxa af1 (x)
 .  

..

..  = 
φ(x) = 
.

 

φ4 (x)

(89)

argmaxd df4 (x)

where x = (x, y, w, z). For any x ∈ [0, 1]4 , φ(x) is non-empty and closed, since the argmax solution
always exists and is one of {0}, {1}, [0, 1]. If in addition φ also has a closed graph then by Kakutani
Fixed Point Theorem there exists a solution to (27).
Consider any sequence (xn , an , bn , cn , dn ) → (x0 , a0 , b0 , c0 , d0 ) such that ∀ n ≥ 1,
an ∈ argmax af1 (xn ),
a∈[0,1]

cn ∈ argmax cf3 (xn ),
c∈[0,1]

bn ∈ argmax bf2 (xn ),

(90a)

b∈[0,1]

dn ∈ argmax df4 (xn ).
d∈[0,1]

(90b)

34

We need to verify that (90) also holds for the limit (x0 , a0 , b0 , c0 , d0 ). If x0 ∈
/ D then due to continuity, (90)
indeed holds at the limit. For x0 ∈ D, for any i ∈ S(x0 ) if fi (x0 ) = 0 then in the relation to be verified,
the requirement is either of a0 , b0 , c0 , d0 ∈ [0, 1], which is always true. For x0 ∈ D1 ∩ D2{ ∩ D3{ ∩ D4{ , if
f1 (x0 ) > 0 then for any sequence xn → x0 , for large n the points in the sequence are within B (x0 )
and thus f1 (xn ) > 0 for large n. This means that the relation from (90) holds at the limit (noting that
f2 , f3 , f4 are continuous at x0 in this case).
Similarly if f1 (x0 ) < 0 and for any x0 ∈ D1{ ∩ D2 ∩ D3{ ∩ D4{ .For x0 ∈ D1 ∩ D2 ∩ D3{ ∩ D4{ if f1 (x0 ) > 0
and f2 (x0 ) < 0 then there exists an  > 0 such that ∀ x ∈ B (x0 ) we have f1 (x) > 0 and f2 (x) < 0.
From this it follows that the relation (90) holds at the limit. Similar argument works for any other sign
combination of f1 , f2 , f3 , f4 .
The two arguments above cover all cases.

R EFERENCES
[1] L. S. Shapley, “Stochastic games,” Proceedings of the national academy of sciences, vol. 39, no. 10,
pp. 1095–1100, 1953.
[2] T. Başar and G. Olsder, Dynamic Noncooperative Game Theory, 2nd Edition. Society for Industrial
and Applied Mathematics, 1998.
[3] J. Filar and K. Vrieze, Competitive Markov decision processes. Springer Science & Business Media,
2012.
[4] M. J. Osborne and A. Rubinstein, A Course in Game Theory, ser. MIT Press Books. The MIT
Press, 1994, vol. 1.
[5] D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA: MIT Press, 1991.
[6] G. J. Mailath and L. Samuelson, Repeated games and reputations: long-run relationships. Oxford
university press, 2006.
[7] E. Maskin and J. Tirole, “Markov perfect equilibrium: I. observable actions,” Journal of Economic
Theory, vol. 100, no. 2, pp. 191–219, 2001.
[8] R. Ericson and A. Pakes, “Markov-perfect industry dynamics: A framework for empirical work,”
The Review of Economic Studies, vol. 62, no. 1, pp. 53–82, 1995.
[9] D. Bergemann and J. Välimäki, “Learning and strategic pricing,” Econometrica: Journal of the
Econometric Society, pp. 1125–1149, 1996.
[10] D. Acemoğlu and J. A. Robinson, “A theory of political transitions,” American Economic Review,
pp. 938–963, 2001.
[11] D. M. Kreps and J. Sobel, “Chapter 25 signalling,” ser. Handbook of Game Theory with Economic
Applications. Elsevier, 1994, vol. 2, pp. 849 – 867.
[12] U. Doraszelski and A. Pakes, “A framework for applied dynamic analysis in IO,” Handbook of
industrial organization, vol. 3, pp. 1887–1966, 2007.
[13] E. Altman, V. Kambley, and A. Silva, “Stochastic games with one step delay sharing information
pattern with application to power control,” in Game Theory for Networks, 2009. GameNets’ 09.
International Conference on. IEEE, 2009, pp. 124–129.

35

[14] A. Nayyar, A. Gupta, C. Langbort, and T. Başar, “Common information based Markov perfect
equilibria for stochastic games with asymmetric information: Finite games,” IEEE Trans. Automatic
Control, vol. 59, no. 3, pp. 555–570, March 2014.
[15] M. Spence, “Job market signaling,” The quarterly journal of Economics, pp. 355–374, 1973.
[16] S. J. Grossman, “The informational role of warranties and private disclosure about product quality,”
The Journal of Law & Economics, vol. 24, no. 3, pp. 461–483, 1981.
[17] C. Wilson, “A model of insurance markets with incomplete information,” Journal of Economic theory,
vol. 16, no. 2, pp. 167–207, 1977.
[18] M. Rothschild and J. Stiglitz, “Equilibrium in competitive insurance markets: An essay on the
economics of imperfect information,” in Foundations of Insurance Economics. Springer, 1976,
pp. 355–375.
[19] A. Zahavi, “Mate selection–a selection for a handicap,” Journal of theoretical Biology, vol. 53, no. 1,
pp. 205–214, 1975.
[20] A. V. Banerjee, “A simple model of herd behavior,” The Quarterly Journal of Economics, pp. 797–
817, 1992.
[21] S. Bikhchandani, D. Hirshleifer, and I. Welch, “A theory of fads, fashion, custom, and cultural
change as informational cascades,” Journal of Political Economy, vol. 100, no. 5, pp. pp. 992–1026,
1992. [Online]. Available: http://www.jstor.org/stable/2138632
[22] L. Smith and P. Sörensen, “Pathological outcomes of observational learning,” Econometrica, vol. 68,
no. 2, pp. 371–398, 2000. [Online]. Available: http://dx.doi.org/10.1111/1468-0262.00113
[23] N. R. Devanur, Y. Peres, and B. Sivan, “Perfect Bayesian equilibria in repeated sales,” in Proceedings
of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2015, pp. 983–
1002.
[24] Y.-C. Ho, “Team decision theory and information structures,” Proceedings of the IEEE, vol. 68,
no. 6, pp. 644–654, 1980.
[25] A. Nayyar, A. Mahajan, and D. Teneketzis, “Optimal control strategies in delayed sharing information
structures,” IEEE Trans. Automatic Control, vol. 56, no. 7, pp. 1606–1620, July 2011.
[26] A. Gupta, A. Nayyar, C. Langbort, and T. Başar, “Common information based Markov perfect
equilibria for linear-gaussian games with asymmetric information,” SIAM Journal on Control and
Optimization, vol. 52, no. 5, pp. 3228–3260, 2014.
[27] Y. Ouyang, H. Tavafoghi, and D. Teneketzis, “Dynamic oligopoly games with private Markovian
dynamics,” in Proc. 54th IEEE Conf. Decision and Control (CDC), 2015.
[28] L. Li and J. Shamma, “Lp formulation of asymmetric zero-sum stochastic games,” in 53rd IEEE
Conference on Decision and Control, Dec 2014, pp. 1930–1935.
[29] H. L. Cole and N. Kocherlakota, “Dynamic games with hidden actions and hidden states,” Journal
of Economic Theory, vol. 98, no. 1, pp. 114–126, 2001.
[30] A. Nayyar, A. Mahajan, and D. Teneketzis, “Decentralized stochastic control with partial history
sharing: A common information approach,” IEEE Transactions on Automatic Control, vol. 58, no. 7,
pp. 1644–1658, July 2013.
[31] A. Mahajan, “Optimal decentralized control of coupled subsystems with control sharing,” Automatic

36

[32]

[33]

[34]
[35]
[36]
[37]
[38]
[39]
[40]

Control, IEEE Transactions on, vol. 58, no. 9, pp. 2377–2382, 2013.
A. Mahajan and D. Teneketzis, “On the design of globally optimal communication strategies for
real-time communcation systems with noisy feedback,” IEEE J. Select. Areas Commun., no. 4, pp.
580–595, May 2008.
A. Nayyar and D. Teneketzis, “On globally optimal real-time encoding and decoding strategies in
multi-terminal communication systems,” in Proc. IEEE Conf. on Decision and Control, Cancun,
Mexico, Dec. 2008, pp. 1620–1627.
D. Vasal and A. Anastasopoulos, “Stochastic control of relay channels with cooperative and strategic
users,” IEEE Transactions on Communications, vol. 62, no. 10, pp. 3434–3446, Oct 2014.
I.-K. Cho and D. M. Kreps, “Signaling games and stable equilibria,” The Quarterly Journal of
Economics, vol. 102, no. 2, pp. 179–221, 1987.
I.-K. Cho, “A refinement of sequential equilibria,” Econometrica, vol. 55, no. 6, pp. 1367–1389,
1987.
J. S. Banks and J. Sobel, “Equilibrium selection in signaling games,” Econometrica, vol. 55, no. 3,
pp. 647–661, 1987.
J. Nash, “Non-cooperative games,” Annals of mathematics, pp. 286–295, 1951.
D. Vasal and A. Anastasopoulos, “Signaling equilibria for dynamic LQG games with asymmetric
information,” in Proc. IEEE Conf. on Decision and Control, Dec. 2016, pp. 6901–6908.
——, “Decentralized Bayesian learning in dynamic games,” in Proc. Allerton Conf. Commun.,
Control, Comp., Sept. 2016.

