# Learning in General Games with Nature’s Moves

Authors: Patrick L. Leoni
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper investigates simultaneous learning about both nature and others’ actions in repeated games and identifies a set of sufficient conditions for which Harsanyi’s doctrine holds. Players have a utility function over infinite histories that are continuous for the sup-norm topology. Nature’s drawing after any history may depend on any past actions. Provided that (1) every player maximizes her expected payoff against her own beliefs, (2) every player updates her beliefs in a Bayesian manner, (3) prior beliefs about both nature and other players’ strategies have a grain of truth, and (4) beliefs about nature are independent of actions chosen during the game, we construct a Nash equilibrium, that is, realization-equivalent to the actual plays, where Harsanyi’s doctrine holds. Those assumptions are shown to be tight.


---

## Body

## 1. Introduction

Consider a finite number of agents interacting simultaneously. Every agent possibly plays an infinite number of times, and her payoff depends on the joint choice of actions as well as events beyond agents’ control (calledchoices of nature). To analyze such interactions, it is always assumed that the players share a common prior about the probability distribution of nature. Such an approach is known as Harsanyi’s doctrine, introduced in Harsanyi [1].We provide a learning foundation for this doctrine. We consider a class of games where nature’s choices may (or not) depend on any past actions by players, and payoff functions are continuous for the sup-norm topology over the set of infinite histories. Provided that Bayesian players have a grain of truth, we show that resulting outcomes converge for the sup-norm topology to a Nash equilibrium that we construct, where Harsanyi’s doctrine holds.Kalai and Lehrer [2, 3] consider a similar type of learning model, without nature’s choice and with a weaker topology of convergence that significantly restricts their class of games. More precisely, those last references use a structure, that is, not a topology, in sharp contrast with the general sup-norm topology. The notion in Kalai and Lehrer states that, for any two probability measures μ and μ
~ and for some small real ϵ
>
0, the measure μ is ϵ-close to μ
~ if two conditions hold. There must exist a measurable set Q that is assigned a measure of at least 1
-
ϵ both by μ and μ
~, and for any measurable set A
⊂
Q it must be true that
(1)
(
1
-
ϵ
)
μ
~
(
A
)
≤
μ
(
A
)
≤
(
1
+
ϵ
)
μ
~
(
A
)
.
A given strategy profile f with associated probability measure μ
f is then said to play ϵ-like another strategy profile g with associated probability measure μ
g if μ
f is ϵ-close to μ
g. The main problem with this concept is the lack of symmetry; that is, if μ
f is ϵ-close to μ
g, then μ
g is not ϵ-close to μ
f in general. This issue excludes any form of topology of convergence, and the restriction of the set of infinite play paths for which this property must hold severely restricts the class of games under consideration.To derive a convergence result for the sup-norm topology with choices of nature, a significantly different approach than that in Kalai and Lehrer [2, 3] is needed. We explicitly construct the Nash equilibrium toward which convergence occurs, where Harsanyi’s doctrine holds. The (almost) Nash equilibrium is as follows:(1)
along every equilibrium play path, every player chooses the (possibly randomized) action that maximizes her subjective expected payoff against her beliefs on others’ strategies;
(2)
in case of unilateral deviation, every player plays the strategy described in the beliefs of the deviator;
(3)
in case of multilateral deviation, strategies are defined arbitrarily.Continuity for the sup-norm topology allows for a form of control over future payoffs. We use this property to approximate resulting plays by a Nash equilibrium for a game with a finite number of histories derived from the original game (a somewhat equivalent notion of truncated games for our setting). This approximation is a direct consequence of continuity for the sup-norm topology, and global approximation by a Nash equilibrium for the whole game is also a consequence of the control over subsequent payoffs derived from continuity. The resulting equilibrium is also proven to satisfy Harsanyi’s doctrine.The proof requires the introduction of the concept ofstochastic subjective equilibrium, which generalizes the concept of subjective equilibrium (see Battigalli et al. [4] for a history and a discussion of this concept), as well as the concept of self-confirming equilibrium (see [5]). We show that, in finite time and for almost every infinite history, players’ behaviors become identical to behaviors described in a stochastic subjective equilibrium. Given the properties of (stochastic) subjective equilibria discussed in the above references, this last result provides a second decision-theoretic foundation for the concept of the Nash equilibrium. We then show that any stochastic subjective equilibrium is realization-equivalent to the strategy profile above, which is an almost-Nash equilibrium for accurate enough beliefs, where Harsanyi’s doctrine holds. The proof of this last statement uses the continuity of the utility functions to ensure convergence of payoffs as beliefs become correct. Finally, eventual correctness of beliefs follows from the grain of truth assumption, together with Blackwell-Dubins’ theorem (see [6]).The literature typically deals with more restrictive settings than ours; for instance, most follow Kalai and Lehrer by assuming that the same game is repeated over time and that the payoff function is a discounted sum of one-shot payoffs. Continuity for the sup-norm topology, as considered here, goes far beyond this setting. Absolute continuity of beliefs, an issue of paramount importance in our work, is not a necessary condition for convergence in general. Sandroni [7] shows that this assumption does not rule out plays that are asymptotically consistent with the Nash equilibrium play. Convergence to the Nash equilibrium is difficult to obtain in broader settings, even without choice of nature. Noguchi [8] considers the case of bounded rationality, where agents smoothly approximate optimal behavior, and he gives a set of prior beliefs leading to convergence to an approximate Nash equilibrium. Foster and Young [9] show that rational agents may not always learn others’ strategies when payoffs are random; Nachbar [10] also shows that under a weak learning condition, if players are potentially able to learn to predict opponents’ strategies for rich enough strategy sets, and if their learning process is symmetric, then one player cannot learn to predict others’ optimal strategies given their own beliefs.The paper is organized as follows. In Section2 we formally describe the class of games and the equilibrium concepts; in Section 3 we give the main result; Section 4 contains some intermediary results; Section 5 presents the counterexamples and concluding remarks; and finally all the technical proofs are in the Appendices.


## 2. The Model

The model and some assumptions needed to obtain the main result of the paper are now described.Time is discrete and continues forever. A period is denoted by the lettert
(
t
=
1,2
,
3
,
…
). There are n players (
n
≥
1
), who play forever. In every period t
(
t
∈
ℕ
), every player i has a finite set of actions Σ
i. Let Σ be defined as ∏
i
=
1
n
Σ
i, the set of action combinations. There is a nonempty and finite (or possibly countable) set 𝒮 of states of naturein every period.For everys
t
∈
(
Σ
×
𝒮
)
t
(
t
∈
ℕ
), a cylinder with base s
t is defined to be the set C
(
s
t
)
=
{
s
∈
(
Σ
×
𝒮
)
∞
|
s
=
(
s
t
,
…
)
} of all infinite histories whose t initial elements coincide with s
t. We define the set Γ
t
(
t
∈
ℕ
) to be the σ-algebra that consists of all finite unions of cylinders with base on (
Σ
×
𝒮
)
t, and Γ
0 is defined to be the trivial σ-algebra. The sequence (
Γ
t
)
t
∈
ℕ generates a filtration, and we define Γ to be the σ-algebra generated by ∪
t
∈
ℕ
Γ
t.LetH
t be the set of all histories of length t
(
t
∈
ℕ
); that is, H
t
=
(
Σ
×
𝒮
)
t (The set H
0 is defined to be the singleton consisting of the null history.) and let H
¯ be the set of all finite histories; that is, the set H
¯
=
∪
t
∈
ℕ
H
t.A(behavioral) strategy for every player assigns to every possible finite history a (possibly randomized) action. We represent a (behavioral) strategy for player i
(
i
=
1
,
…
,
n
) as a function
(2)
f
i
:
H
¯
⟶
Δ
(
Σ
i
)
,
where Δ
(
Σ
i
) is the set of all probability distributions on Σ
i.Nature draws a state in every period, after every possible history. We thus represent nature’ choices by a behavioral strategy(3)
ν
:
H
¯
⟶
Δ
(
𝒮
)
,
where Δ
(
𝒮
) is the set of all probability distributions on 𝒮. The state of nature is not revealed to the players before they have simultaneously made their choices of actions.The game is played withperfect monitoring; that is, the players know all realized past action combinations actually played, as well as all the states of nature drawn prior to the current period. The state of nature drawn in the current period is revealed to the players at the end of this period (without necessarily revealing the payoff of the other players).


### 2.1. Realized Play Paths

The concept ofinfinite play path is now defined. (What follows is described in Kalai and Lehrer [3].)  This notion of infinite (or realized) play path represents the actual actions chosen by the players over time, in the following sense.Consider a(
n
+
1
)-vector of behavioral strategies f
=
(
ν
,
(
f
i
)
i
=
1
,
…
,
n
). The null history h
0 leads to the realized action combination z
1 in the support of f
(
h
0
). Defined recursively, in period t
+
1, the players will choose the randomizations f
(
z
(
t
)
), which will result in the action combination z
t
+
1. The vector (
z
1
,
z
2
,
z
3
,
…
) is called the realized play path.A realized play path, finite or infinite, will be denoted by the letter z.Denote byA
f the support of f; that is, the set of infinite play paths was assigned strictly positive probability by f.


### 2.2.  Beliefs

The beliefs of the players about others’ strategies and the realizations of the states of nature are now formally described.Every player is assumed to have subjective prior beliefs about both other players’ strategies and nature. Those prior beliefs are formed before the first period of the game, and they will be updated in every subsequent period in a Bayesian manner, according to available information (see Kalai and Lehrer [2, 3] for a formal definition, as we use the same approach here).Formally, the beliefs of playeri
(
i
=
1
,
…
,
n
) regarding the strategies of the other players are represented by a n-vector of strategies f
i
=
(
f
j
i
)
j
=
1
,
…
,
n. The belief f
j
i represents the belief of player i about player j’s strategy. Moreover, player i knows her own strategy (i.e., f
i
i
=
f
i for every i).The belief of playeri about nature is represented by a behavioral strategy ν
i
:
H
¯
→
Δ
(
𝒮
), for every i
(
i
=
1
,
…
,
n
).We consider the following probabilistic representation of beliefs. We associate an-vector of strategies f and a choice of nature ν to a unique probability measure μ
f
,
ν on the set on infinite play paths, as follows.First, the measureμ
f
,
ν is defined inductively on the set of finite play paths and then uniquely extended to the set of infinite play paths.Defineμ
f
,
ν to be 1 for the null history. Consider now a finite history h
∈
H
¯ whose corresponding realized play path is given by the vector z, a vector of actions a
∈
Σ, and a state of nature s
∈
𝒮. The value μ
f
,
ν
(
z
,
a
,
s
) is inductively defined to be
(4)
μ
f
,
ν
(
z
)
·
ν
(
h
)
(
s
)
·
∏
i
‍
f
i
(
h
)
(
a
i
)
.So defined, we now uniquely extend this measure to(
Σ
×
𝒮
)
∞. Any finite history h
∈
H
¯ is now interpreted as the cylinder C
(
h
), which is by definition the set of infinite paths whose initial segment is h.Define the probability measureμ
~
f
,
ν as μ
~
f
,
ν
(
C
(
h
)
)
≡
μ
f
,
ν
(
h
) for every such cylinder, and consider its unique extension to (
(
Σ
×
𝒮
)
∞
,
Γ
) given by Caratheodory’s theorem. The extension of the probability measure μ
~
f
,
ν to (
(
Σ
×
𝒮
)
∞
,
Γ
) is the unique extension of μ
f
,
ν on (
(
Σ
×
𝒮
)
∞
,
Γ
). See for instance Kalai and Lehrer [2] for more details.The above representation implicitly requires that the belief of every player about nature is independent (in a probabilistic sense) of the actions chosen by other players. Moreover, it is also that every player believes that other players choose their actions independently of each other.In Section5.1, an example is given showing that none of the current results hold without those last two assumptions. The reader is also referred to Section 5.2 for a discussion of those assumptions on beliefs and their behavioral implications.For sake of notational convenience, we shall denote by the same symbol(
f
i
,
ν
i
) the prior belief about the nature and others’ strategies of player i and her updated beliefs obtained by iterated applications of Bayes’ formula.


### 2.3.  Payoffs

The intertemporal payoff functions of the players are now described. Every player has the utility function over the set of infinite histories(5)
u
i
:
(
Σ
×
𝒮
)
∞
⟶
ℝ
.We assume that, for every playeri,(1)
the functionu
i is continuous with respect to the sup-norm topology on (
Σ
×
𝒮
)
∞, and
(2)
u
i is uniformly bounded above and below.For any(
n
-
)vector of strategies f, player i
(
i
=
1
,
…
,
n
), whose belief about the states of nature is ν
i, receives the expected payoff
(6)
U
i
(
f
,
ν
i
)
=
E
f
,
ν
i
[
u
i
(
z
)
]
,
where E
f
,
ν
i is the expected value with respect to the probability measure μ
f
,
ν
i induced by the strategies f and nature’ choices ν
i.Moreover, every player is assumed to maximize the above expression, namely, her (subjective) expected payoff given her subjective belief about nature’ drawings and against her subjective belief about other players’ strategies.The above specification of payoffs encompasses the case treated in Kalai and Lehrer [2, 3] and Sandroni [7], where the payoff over infinite histories takes the form of expected discounted sum of one-period payoff.


### 2.4.  Equilibrium Concepts

This section is devoted to defining the solution concepts that will be used throughout.First, the concept of best-response against others’ strategies, given a belief about nature, is defined. Pick any playeri
(
i
=
1
,
…
,
n
) and consider her belief about nature ν
i and a (
n
-
1
)-vector strategies f
-
i (this last vector can represent either beliefs about others’ strategies or actual strategies). For every α
≥
0, a strategy f
i is a α-best response to
(
f
-
i
,
ν
i
) if
(7)
U
i
(
g
,
f
-
i
,
ν
i
)
-
U
i
(
f
i
,
f
-
i
,
ν
i
)
≤
α
,
for every other strategy g available to player i.Fix nowα
>
0. A Nash
α
-equilibrium is a n-vector f of strategies such that f
i is an α-best responseto
(
f
-
i
,
ν
) for every i
(
i
=
1
,
…
,
n
), where ν is the true probability of the states of nature. In particular, in any (almost) Nash equilibrium, beliefs about nature and others’ strategies are exact.The next notion allows us to specify a concept of closeness, in a probabilistic sense, between two vectors of strategies and for two particular choices of nature. Define first, forψ and ψ
′ probability measures on the same measurable space (
Ω
,
ℱ
), the sup-normto be
(8)
∥
ψ
-
ψ
′
∥
∞
=
sup
⁡
A
∈
ℱ
|
ψ
(
A
)
-
ψ
′
(
A
)
|
.Definition 1.
Fixɛ
>
0. The strategy profile (
f
,
ν
1
) plays ɛ-like the strategy profile (
g
,
ν
2
) if
(9)
∥
μ
f
,
ν
1
-
μ
g
,
ν
2
∥
∞
≤
ɛ
.The concept of “playingɛ-like” for two given strategies measures how distant those strategies are from each other in a probabilistic sense. It is preferable to approach this issue from a probabilistic standpoint, as explained in detail in Kalai and Lehrer [2, 3], even though the authors use a different concept.With the above definitions, it is now possible to introduce the concept ofstochastic subjective equilibrium (up to some constants), which generalizes the concept of subjective equilibrium introduced in Kalai and Lehrer [2, 3] and the concept of self-confirming equilibrium introduced in Fudenberg and Levine [5, 11]. This notion will play an important role in the proof of the main result of this paper.Definition 2.
Fixɛ
>
0. A stochastic ɛ-subjective equilibrium is a matrix of beliefs (
f
j
,
ν
j
)
j
=
1
,
…
,
n, satisfying for every i
(
i
=
1
,
…
,
n
) that(i)
the strategyf
i
i is a best-response to (
f
-
i
i
,
ν
i
), and
(ii)
the strategy profile(
f
j
j
,
ν
)
j
=
1
,
…
,
n plays ɛ-like (
f
i
,
ν
i
).In other words, in any stochastic subjective equilibrium, the following requirements hold: (i) every player maximizes her intertemporal utility function against her beliefs about others’ strategies and given her beliefs about nature, and (ii) the beliefs about others’ strategies and nature are realization-equivalent (up toɛ) to actual plays. No particular condition on beliefs about nature is required in such equilibrium; for instance there is no need at this point for requirement ensuring that beliefs about nature are consistent with available information and learning processes.The above definition extends the notion of subjective equilibrium, as introduced in Kalai and Lehrer [2, 3], in that uncertainty about nature is added. The point of the paper is to show that, even when facing this type of uncertainty, Bayesian players will choose (in finite time) a behavior described by a Nash equilibrium.


## 2.1. Realized Play Paths

The concept ofinfinite play path is now defined. (What follows is described in Kalai and Lehrer [3].)  This notion of infinite (or realized) play path represents the actual actions chosen by the players over time, in the following sense.Consider a(
n
+
1
)-vector of behavioral strategies f
=
(
ν
,
(
f
i
)
i
=
1
,
…
,
n
). The null history h
0 leads to the realized action combination z
1 in the support of f
(
h
0
). Defined recursively, in period t
+
1, the players will choose the randomizations f
(
z
(
t
)
), which will result in the action combination z
t
+
1. The vector (
z
1
,
z
2
,
z
3
,
…
) is called the realized play path.A realized play path, finite or infinite, will be denoted by the letter z.Denote byA
f the support of f; that is, the set of infinite play paths was assigned strictly positive probability by f.


## 2.2.  Beliefs

The beliefs of the players about others’ strategies and the realizations of the states of nature are now formally described.Every player is assumed to have subjective prior beliefs about both other players’ strategies and nature. Those prior beliefs are formed before the first period of the game, and they will be updated in every subsequent period in a Bayesian manner, according to available information (see Kalai and Lehrer [2, 3] for a formal definition, as we use the same approach here).Formally, the beliefs of playeri
(
i
=
1
,
…
,
n
) regarding the strategies of the other players are represented by a n-vector of strategies f
i
=
(
f
j
i
)
j
=
1
,
…
,
n. The belief f
j
i represents the belief of player i about player j’s strategy. Moreover, player i knows her own strategy (i.e., f
i
i
=
f
i for every i).The belief of playeri about nature is represented by a behavioral strategy ν
i
:
H
¯
→
Δ
(
𝒮
), for every i
(
i
=
1
,
…
,
n
).We consider the following probabilistic representation of beliefs. We associate an-vector of strategies f and a choice of nature ν to a unique probability measure μ
f
,
ν on the set on infinite play paths, as follows.First, the measureμ
f
,
ν is defined inductively on the set of finite play paths and then uniquely extended to the set of infinite play paths.Defineμ
f
,
ν to be 1 for the null history. Consider now a finite history h
∈
H
¯ whose corresponding realized play path is given by the vector z, a vector of actions a
∈
Σ, and a state of nature s
∈
𝒮. The value μ
f
,
ν
(
z
,
a
,
s
) is inductively defined to be
(4)
μ
f
,
ν
(
z
)
·
ν
(
h
)
(
s
)
·
∏
i
‍
f
i
(
h
)
(
a
i
)
.So defined, we now uniquely extend this measure to(
Σ
×
𝒮
)
∞. Any finite history h
∈
H
¯ is now interpreted as the cylinder C
(
h
), which is by definition the set of infinite paths whose initial segment is h.Define the probability measureμ
~
f
,
ν as μ
~
f
,
ν
(
C
(
h
)
)
≡
μ
f
,
ν
(
h
) for every such cylinder, and consider its unique extension to (
(
Σ
×
𝒮
)
∞
,
Γ
) given by Caratheodory’s theorem. The extension of the probability measure μ
~
f
,
ν to (
(
Σ
×
𝒮
)
∞
,
Γ
) is the unique extension of μ
f
,
ν on (
(
Σ
×
𝒮
)
∞
,
Γ
). See for instance Kalai and Lehrer [2] for more details.The above representation implicitly requires that the belief of every player about nature is independent (in a probabilistic sense) of the actions chosen by other players. Moreover, it is also that every player believes that other players choose their actions independently of each other.In Section5.1, an example is given showing that none of the current results hold without those last two assumptions. The reader is also referred to Section 5.2 for a discussion of those assumptions on beliefs and their behavioral implications.For sake of notational convenience, we shall denote by the same symbol(
f
i
,
ν
i
) the prior belief about the nature and others’ strategies of player i and her updated beliefs obtained by iterated applications of Bayes’ formula.


## 2.3.  Payoffs

The intertemporal payoff functions of the players are now described. Every player has the utility function over the set of infinite histories(5)
u
i
:
(
Σ
×
𝒮
)
∞
⟶
ℝ
.We assume that, for every playeri,(1)
the functionu
i is continuous with respect to the sup-norm topology on (
Σ
×
𝒮
)
∞, and
(2)
u
i is uniformly bounded above and below.For any(
n
-
)vector of strategies f, player i
(
i
=
1
,
…
,
n
), whose belief about the states of nature is ν
i, receives the expected payoff
(6)
U
i
(
f
,
ν
i
)
=
E
f
,
ν
i
[
u
i
(
z
)
]
,
where E
f
,
ν
i is the expected value with respect to the probability measure μ
f
,
ν
i induced by the strategies f and nature’ choices ν
i.Moreover, every player is assumed to maximize the above expression, namely, her (subjective) expected payoff given her subjective belief about nature’ drawings and against her subjective belief about other players’ strategies.The above specification of payoffs encompasses the case treated in Kalai and Lehrer [2, 3] and Sandroni [7], where the payoff over infinite histories takes the form of expected discounted sum of one-period payoff.


## 2.4.  Equilibrium Concepts

This section is devoted to defining the solution concepts that will be used throughout.First, the concept of best-response against others’ strategies, given a belief about nature, is defined. Pick any playeri
(
i
=
1
,
…
,
n
) and consider her belief about nature ν
i and a (
n
-
1
)-vector strategies f
-
i (this last vector can represent either beliefs about others’ strategies or actual strategies). For every α
≥
0, a strategy f
i is a α-best response to
(
f
-
i
,
ν
i
) if
(7)
U
i
(
g
,
f
-
i
,
ν
i
)
-
U
i
(
f
i
,
f
-
i
,
ν
i
)
≤
α
,
for every other strategy g available to player i.Fix nowα
>
0. A Nash
α
-equilibrium is a n-vector f of strategies such that f
i is an α-best responseto
(
f
-
i
,
ν
) for every i
(
i
=
1
,
…
,
n
), where ν is the true probability of the states of nature. In particular, in any (almost) Nash equilibrium, beliefs about nature and others’ strategies are exact.The next notion allows us to specify a concept of closeness, in a probabilistic sense, between two vectors of strategies and for two particular choices of nature. Define first, forψ and ψ
′ probability measures on the same measurable space (
Ω
,
ℱ
), the sup-normto be
(8)
∥
ψ
-
ψ
′
∥
∞
=
sup
⁡
A
∈
ℱ
|
ψ
(
A
)
-
ψ
′
(
A
)
|
.Definition 1.
Fixɛ
>
0. The strategy profile (
f
,
ν
1
) plays ɛ-like the strategy profile (
g
,
ν
2
) if
(9)
∥
μ
f
,
ν
1
-
μ
g
,
ν
2
∥
∞
≤
ɛ
.The concept of “playingɛ-like” for two given strategies measures how distant those strategies are from each other in a probabilistic sense. It is preferable to approach this issue from a probabilistic standpoint, as explained in detail in Kalai and Lehrer [2, 3], even though the authors use a different concept.With the above definitions, it is now possible to introduce the concept ofstochastic subjective equilibrium (up to some constants), which generalizes the concept of subjective equilibrium introduced in Kalai and Lehrer [2, 3] and the concept of self-confirming equilibrium introduced in Fudenberg and Levine [5, 11]. This notion will play an important role in the proof of the main result of this paper.Definition 2.
Fixɛ
>
0. A stochastic ɛ-subjective equilibrium is a matrix of beliefs (
f
j
,
ν
j
)
j
=
1
,
…
,
n, satisfying for every i
(
i
=
1
,
…
,
n
) that(i)
the strategyf
i
i is a best-response to (
f
-
i
i
,
ν
i
), and
(ii)
the strategy profile(
f
j
j
,
ν
)
j
=
1
,
…
,
n plays ɛ-like (
f
i
,
ν
i
).In other words, in any stochastic subjective equilibrium, the following requirements hold: (i) every player maximizes her intertemporal utility function against her beliefs about others’ strategies and given her beliefs about nature, and (ii) the beliefs about others’ strategies and nature are realization-equivalent (up toɛ) to actual plays. No particular condition on beliefs about nature is required in such equilibrium; for instance there is no need at this point for requirement ensuring that beliefs about nature are consistent with available information and learning processes.The above definition extends the notion of subjective equilibrium, as introduced in Kalai and Lehrer [2, 3], in that uncertainty about nature is added. The point of the paper is to show that, even when facing this type of uncertainty, Bayesian players will choose (in finite time) a behavior described by a Nash equilibrium.


## 3.  The Main Result

In this section, the main result of the paper is stated and discussed. That is, the set of sufficient conditions leading to convergence toward the Nash equilibria in finite time is given.We first introduce a definition, which captures the concept ofinduced strategy resulting from a given strategy after a particular finite history.Definition 3.
Consider an-vector of strategies f, a period t
∈
ℕ, and a finite history h
∈
H
t. The induced strategy f
h is defined as
(10)
f
h
(
h
′
)
=
f
(
h
h
′
)
for
any
h
′
∈
H
r
(
r
∈
ℕ
)
,
where h
h
′ is the history of length t
+
r resulting from the concatenation of the history h (first) and (followed by) the history h
′.
For anyp-vector of strategies f
~
=
(
f
1
,
…
,
f
p
) (with 1
≤
p
≤
n
+
1), the induced p-vector of strategies f
~
h are defined as
(11)
f
~
h
=
(
(
f
1
)
h
,
…
,
(
f
p
)
h
)
.Before stating the main result of this paper, a notion in Measure Theory is first defined. Consider two measuresλ and λ
~ on the same measurable space (
Ω
,
ℱ
). The measure λ is said to be absolutely continuous with respect to λ
~, denoted by λ
≪
λ
~, if for every A
∈
ℱ such that λ
(
A
)
>
0 it is true that λ
~
(
A
)
>
0.Finally, for any realized play pathz and time t
>
0, denote by z
(
t
) the truncation of z to its t first elements (thus z
(
t
)
∈
H
t).Theorem 4.
Consider an-vector of strategies f representing actual plays and for every player j the belief (
f
j
,
ν
j
) with f
j
j
=
f
j such that, for every i,(i)
the strategyf
i is a best-response to (
f
-
i
i
,
ν
i
),
(ii)
the beliefs are such thatμ
f
,
ν
≪
μ
f
i
,
ν
i,
(iii)
playeri updates her beliefs in a Bayesian manner, and
(iv)
the belief of playeri about nature is not correlated with observations of actions taken by other players.
Fix now any arbitraryα
>
0. For μ
f
,
ν-almost every path z, there exists a time T such that, for every t
≥
T, there exists a strategy profile f
¯ such that(1)
f
¯ is a Nash α-equilibrium, and
(2)
f
¯ plays 0-like f.The above theorem says that, if (1) players maximize their intertemporal utility functions against their own beliefs, and if (2) beliefs are updated in a Bayesian manner, as long as the independence requirement is satisfied and the grain of truth holds, actual plays are realization-equivalent to an almost Nash equilibrium in finite time.One of the keys to proving the above result is that, when Assumptions (i)–(iv) are satisfied, along the realized play path actions satisfy the properties of a stochastic (almost-) subjective equilibrium in finite time. Since also any (almost) Nash equilibrium is an almost stochastic subjective equilibrium, and since also any (almost) Nash equilibrium trivially satisfies Assumptions (i)–(iv) above, Theorem4 implicitly establishes some form of equivalence between those three different concepts.The assumptions used in Theorem4 are discussed next.Assumptions (ii) and (iv) above are tight; for instance the reader is referred to Kalai and Lehrer [2] for counterexamples violating any of those assumptions, in the case where beliefs about nature are correct.When all assumptions in Theorem4 but (iv) above are satisfied, Bayesian players may not be able to learn anything about others’ strategies and/or nature. In this case, resulting plays can become chaotic and convergence is not to be expected. In Section 5.1, such an example is presented. The example is taken from an early study by Jordan [12], and it is very similar to the framework under study. The only difference is that players have now private and partial information about the realizations of the states of nature. Using this example, Kalai and Lehrer [2] show that, when n
≥
3, convergence toward a Nash equilibrium is not obtained even when players have exact beliefs about nature. A counterexample, matching exactly the current framework, can be easily derived from Jordan’s example.In terms of possible extensions to Theorem4, it is conjectured that Bayesian learning is not the only (non-trivial) learning process for which the above result holds. The characterization of all learning processes for which convergence toward a Nash equilibrium obtains is an open problem.The proof of Theorem4 is given in the next section.


## 4. Proof and Intermediary Results

This section is devoted to giving the main line of the proof of Theorem4. Since the proof is technical, only the main intermediary results are presented here.The strategy of the proof of Theorem4 goes as follows. First, it is shown that beliefs and strategies satisfying Assumptions (i)–(iv) become, in finite time, identical to an almost subjective stochastic equilibrium. Second, almost subjective stochastic equilibria are shown to be realization-equivalent to an almost Nash equilibrium when beliefs are accurate enough. Finally, it is shown that beliefs become accurate enough, in finite time. Overall, this leads to the approximation of initial strategies and beliefs by an almost Nash equilibrium, as in Theorem 4.The first proposition makes the link between strategies and beliefs satisfying Assumptions (i)–(iv) in Theorem4 and the concept of (almost-) stochastic subjective equilibrium. Its proof is given in the Appendix.Proposition 5.
Consider an-vector of strategies f representing actual plays and for every player j the belief (
f
j
,
ν
j
) with f
j
j
=
f
j such that, for every i,(i)
the strategy
f
i
is a best-response to
(
f
-
i
i
,
ν
i
)
,
(ii)
the beliefs are such that
μ
f
,
ν
≪
μ
f
i
,
ν
i
,
(iii)
player
i
updates her beliefs in a Bayesian manner, and
(iv)
the belief of player
i
about nature is not correlated with observations of actions taken by other players.
For everyɛ
>
0 and for μ
f
,
ν-almost every play path z, there exists a time T such that, for every t
≥
T, the strategy profile (
f
z
(
t
)
i
,
ν
z
(
t
)
i
)
i
=
1
,
…
,
n is stochastic ɛ-subjective equilibrium for the repeated game starting after z
(
t
).The above result implies that, as long as Assumptions (i)–(iv) hold, actual plays and beliefs about others’ strategies along almost every path will become, in finite time, an (almost-) stochastic subjective equilibrium.The next proposition makes the link between (almost-) stochastic subjective equilibrium and (almost-) Nash equilibrium. Its proof is given in the Appendix.Proposition 6.
Fix any vector of beliefs(
f
j
,
ν
j
)
j
=
1
,
…
,
n. For every α
>
0, there exists a constant ɛ
¯
>
0 such that for every ɛ
<
ɛ
¯, if (
f
j
,
ν
j
)
i
=
1
,
…
,
n is a stochastic ɛ-subjective equilibrium, then there exists a strategy profile f
¯ satisfying(1)
f
¯
is a Nash
α
-equilibrium, and
(2)
f
¯
plays 0-like
f
.The above result mainly states that, provided that beliefs are accurate enough, every stochastic subjective equilibrium is an (almost-) Nash equilibrium. Given the conclusion of Proposition6, and in order to prove the main result, it is enough to ensure that beliefs become arbitrarily correct.Arbitrary accuracy of beliefs follows from the next proposition, which is the well-known and important result proved by Blackwell and Dubins [6]. It is a convergence result for conditional probabilities, stating that as information increases conditional probabilities of two different measures will convergence, as long as a requirement of absolute continuity is satisfied by those two measures.Before stating the result, let(
Ω
,
ℱ
) be a measurable space and let (
𝒫
t
)
t
∈
ℕ be an increasing sequence of countable partitions of Ω, also called filter. This sequence of partitions represents the information available to an agent in any given period, and the set Ω represents the set of all the choices of nature. For any w
∈
Ω and any period t, let P
t
(
w
) be the unique set in 𝒫
t such that w
∈
P
t
(
w
). Its proof can be found in Blackwell and Dubins [6].Theorem 7 (Blackwell and Dubins [6]).
Consider twoσ-additive measures μ and μ
~ on (
Ω
,
ℱ
) such that μ
≪
μ
~. For μ-almost every w
∈
Ω and for every ɛ
>
0, there exists a time T such that
(12)
|
μ
(
A
∣
P
t
(
w
)
)
-
μ
~
(
A
∣
P
t
(
w
)
)
|
<
ɛ
for every A
∈
ℱ and for every t
≥
T.With all the above intermediary results, we next move to the proof of Theorem4.Proof of Theorem4.
Fix the strategiesf and beliefs (
f
i
,
ν
i
)
i
=
1
,
…
,
n such that f
i
=
f
i
i for every i, satisfying Assumptions (i)–(iv) of Theorem 4. Fix any α
>
0 and consider also ɛ
¯ associated with α and (
f
i
,
ν
i
)
i
=
1
,
…
,
n by Proposition 6 and any ɛ
<
ɛ
¯.
By Proposition5, for μ
f
,
ν-every path there exists a time t
0 after which (
f
j
,
ν
j
)
i
=
1
,
…
,
n is a stochastic ɛ-subjective equilibrium. By Proposition 6, there exists also a Nash α-equilibrium for the repeated game starting after z
(
t
0
) that plays 0-like f.
Thus, we have found a periodt
0 such that the original strategies play 0-like a Nash α-equilibrium in the repeated game starting after z
(
t
0
).
The proof is now complete.


## 5. Concluding Remarks

This section provides some extended discussions of the assumptions in Theorem4.


### 5.1. Independence of Beliefs

In this section, an example is given showing that Assumption (iv) in Theorem4 cannot be relaxed. The game below is taken from Jordan [12], and it is discussed in detail in Kalai and Lehrer [2].Consider two players engaged in an infinitely repeated game. The repeated game is similar to the one studied so far, with the difference that a randomly generated (fixed-size) pair of payoff matrices(
A
i
,
B
j
)
(
i
,
j
)
∈
I
×
J is drawn by nature before the first period (the sets I and J are assumed to be finite). A pair (
i
¯
,
j
¯
)
∈
I
×
J is drawn according to the probability distribution Π. The probability distribution Π is common knowledge among the players; that is, their beliefs about nature are exact.Player1 is told privately the realized value i
¯, and player 2 is told privately the realized value j
¯. Private information is not to be revealed to the other player at any point in the game. In this game, uncertainty about nature faced by any player is on the private information owned by the other player. Thus, the belief about nature of player 1 can be represented by the conditional probability Π
(
·
∣
i
¯
) and similarly for player 2. All other assumptions but Assumption (iv) in Theorem 4 also hold. Assume also that the players maximize the expected sum of discounted one-period payoffs of the same game repeated over time (see Jordan, [12], for more details).Kalai and Lehrer [2] show that, when the number of players is two, convergence toward a Nash equilibrium obtains when players update their beliefs about nature according to realized actions. However, when the number of players is strictly greater than two, convergence fails.The intuition of such a result is that, whenn
≥
3, players’ information sets are no longer filters as more information becomes available, due mostly to strategic attempt to hide private information and mislead others players through their own actions. Such behaviors immediately lead to an impossibility of learning, and convergence as in Theorem 4 does not usually obtain.


### 5.2. Equivalent Representation of Beliefs and Kuhn’s Theorem

Instead of representing the belief of playeri about player j by the behavioral strategy f
j
i, we could have represented instead player i belief by a probability distribution over the set of behavioral strategies available to player j. Kuhn’s theorem (see Aumann, [13], and Kuhn, [14]) applies to our setting and ensures that the two approaches above are equivalent.Of importance is the assumption that every player believes that others’ actions are uncorrelated with each other. Informally, this last assumption ensures that any player’ beliefs are represented by a measure product over beliefs about others’ strategies. When this assumption is not present, it is easy to find examples where convergence toward a Nash equilibrium does not obtain (see for instance Kalai and Lehrer, [2], for a discussion of this issue).


## 5.1. Independence of Beliefs

In this section, an example is given showing that Assumption (iv) in Theorem4 cannot be relaxed. The game below is taken from Jordan [12], and it is discussed in detail in Kalai and Lehrer [2].Consider two players engaged in an infinitely repeated game. The repeated game is similar to the one studied so far, with the difference that a randomly generated (fixed-size) pair of payoff matrices(
A
i
,
B
j
)
(
i
,
j
)
∈
I
×
J is drawn by nature before the first period (the sets I and J are assumed to be finite). A pair (
i
¯
,
j
¯
)
∈
I
×
J is drawn according to the probability distribution Π. The probability distribution Π is common knowledge among the players; that is, their beliefs about nature are exact.Player1 is told privately the realized value i
¯, and player 2 is told privately the realized value j
¯. Private information is not to be revealed to the other player at any point in the game. In this game, uncertainty about nature faced by any player is on the private information owned by the other player. Thus, the belief about nature of player 1 can be represented by the conditional probability Π
(
·
∣
i
¯
) and similarly for player 2. All other assumptions but Assumption (iv) in Theorem 4 also hold. Assume also that the players maximize the expected sum of discounted one-period payoffs of the same game repeated over time (see Jordan, [12], for more details).Kalai and Lehrer [2] show that, when the number of players is two, convergence toward a Nash equilibrium obtains when players update their beliefs about nature according to realized actions. However, when the number of players is strictly greater than two, convergence fails.The intuition of such a result is that, whenn
≥
3, players’ information sets are no longer filters as more information becomes available, due mostly to strategic attempt to hide private information and mislead others players through their own actions. Such behaviors immediately lead to an impossibility of learning, and convergence as in Theorem 4 does not usually obtain.


## 5.2. Equivalent Representation of Beliefs and Kuhn’s Theorem

Instead of representing the belief of playeri about player j by the behavioral strategy f
j
i, we could have represented instead player i belief by a probability distribution over the set of behavioral strategies available to player j. Kuhn’s theorem (see Aumann, [13], and Kuhn, [14]) applies to our setting and ensures that the two approaches above are equivalent.Of importance is the assumption that every player believes that others’ actions are uncorrelated with each other. Informally, this last assumption ensures that any player’ beliefs are represented by a measure product over beliefs about others’ strategies. When this assumption is not present, it is easy to find examples where convergence toward a Nash equilibrium does not obtain (see for instance Kalai and Lehrer, [2], for a discussion of this issue).



---

*Source: 453168-2014-01-19.xml*