# Local Interactions andp-Best Response Set

Authors: J. Durieu; P. Solal
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We study a local interaction model where agents play a finiten-person game following a perturbed best-response process with inertia. We consider the concept of minimal p-best response set to analyze distributions of actions on the long run. We distinguish between two assumptions made by agents about the matching rule. We show that only actions contained in the minimal p-best response set can be selected provided that p is sufficiently small. We demonstrate that these predictions are sensitive to the assumptions about the matching rule.


---

## Body

## 1. Introduction

There is an extensive literature on evolutionary game theory which investigates the long-run outcomes when a population of boundedly rational agents uses simple rules of adaptation to recurrently play a game in normal form. These models allow for sharp-equilibrium selection results in some classes of games with multiple equilibria. Such an equilibrium can be interpreted as a convention, that is, a pattern of behavior that is customary and expected and regulates much of economic and social life (for a survey, see, among others, Young [1]). A common assumption in this literature is that interactions among agents are local and not global. Each individual may be matched according to some matching rule with a subgroup of the overall population to play a game (for a survey, see, e.g., Weidenholzer [2]). In this paper, we assume that agents have no information about this matching rule. As a consequence, we elaborate two alternative scenarios corresponding to different assumptions made by agents about the matching rule. This point can be interpreted as a consequence of bounded rationality: agents only have an imperfect representation of their environment. We use the concept of (minimal) p-best response set introduced by Tercieux [3] to make predictions for the long-run behavior of the population of agents (this concept is used by Durieu et al. [4] in a fictitious play model with bounded memory). We establish that such predictions are possible for the whole class of finite n-person games. We also study how assumptions about the matching rule affect these predictions.Precisely, we consider a finite population of agents located at the vertices of a chordal ring, that is, a ring topology in which each vertex has additional links with other vertices. In particular, we focus on chordal rings of degree2
K
,
K
∈
ℕ, constructed by adding at each vertex 2
K
-
2 chords with its closest vertices in a ring network. In order to deal with asymmetric finite n-person games, we distinguish between n classes of agents. A specific role in the game is assigned to every class. Each agent of each class is located at exactly one vertex and two agents of the same class are located in different vertices. In this way, each vertex contains exactly n agents. The game is played recurrently. At each period, one agent of each class is drawn at random to play the game. However, players’ identity is not revealed. At the beginning of every period, each agent of each class observes the actions that the agents of other classes located in vertices linked with its own vertex has chosen in the previous period. He uses this information to estimate the probability distribution on the action profiles played by his potential opponents in the current period. These estimations depend on the assumptions made by agents about the matching rule. Each agent believes that he can be matched with agents located at vertices linked with his own location. Precisely, we consider the following two scenarios. In the first scenario, each agent assumes that his potential opponents are drawn jointly by location. In the second scenario, each agent assumes that his potential opponents are drawn independently. For both scenarios, agents may have the opportunity to choose a best response to their estimation. The concept of p-best response set allows us to study the way in which the distribution of actions that people take in the n classes evolves over time. We show that, for both assumptions about the matching rule, only actions contained in the minimal p-best response set can be selected on the long run provided that p is sufficiently small. For each assumption, an explicit bound of p is given, and we analyze how this critical value evolves when n increases.Ellison [5, 6] considers a similar local interaction structure: agents are arranged on a ring improved by adding chords between vertices in a regular form. However, since Ellison [5, 6] focuses on symmetric two-player games, each vertex is associated with one agent and each agent has full information about the matching rule. Ellison [5] considers a symmetric 2
×
2 coordination game. The model predicts that the risk-dominant equilibrium is selected on the long run. Ellison [6] shows that in a symmetric m
×
m game, the 1
/
2-dominant equilibrium, if it exists, is selected on the long run. Alós-Ferrer and Weidenholzer [7] consider the weakened solution concept of globally pairwise risk-dominant equilibrium and show that this equilibrium, if it exists, is selected in a symmetric 3
×
3 coordination game played by agents arranged on a ring. However, a generalization of this result to a larger class of games is not possible. Indeed, Alós-Ferrer and Weidenholzer [7] present an example of a 4
×
4 coordination game in which the globally pairwise risk-dominant equilibrium is not selected on the long run. From this point of view, the concept of minimal p-best response set is interesting. Since a minimal p-best response exists in every game, it allows us to investigate the long-run outcomes in the whole class of finite n-person games. Moreover, since the concept of minimal p-best response set generalizes the concept of p-dominant equilibrium [8], the result of Ellison [6] is a particular case of our result.The paper is structured as follows. Section2 introduces notations. Section 3 introduces the concept of p-best response set. Section 4 introduces the learning model. In Section 5 we present the main results. Section 6 concludes.


## 2. Notations and Definitions

Let⊆ denote weak set inclusion and let ⊂ denote proper set inclusion. We denote by ⌈
β
⌉ the smallest integer greater than or equal to β. For any finite set A, Δ
(
A
) denotes the set of all probability distributions on A.LetΓ be a finite n-person strategic-form game. Let X
i be the finite set of pure strategies x
i available to player i
∈
I
=
{
1,2
,
…
,
n
}. We write Δ
(
X
i
) for the set of probability distributions q
i over X
i for each i
∈
I. Let q
i
(
x
i
) denote the probability mass on strategy x
i. Define the product set X
=
∏
i
∈
I
‍
X
i. Let Δ
(
X
) be the set of probability distributions on X. Let X
-
i
=
∏
j
≠
i
‍
X
j denote the set of all possible combinations of strategies for the players other than i, with generic elements x
-
i
=
(
x
j
)
j
≠
i. Let Δ
(
X
-
i
) be the set of probability distributions on X
-
i with generic elements q
-
i. We sometimes identify the element of Δ
(
X
i
) that assigns probability one to a strategy in X
i with this strategy in X
i.In this paper, a player’s belief about others’ strategies takes the form of a probability measure on the product of all opponents’ strategy sets. We assume that each playeri has expected payoffs represented by the function u
i
:
X
i
×
Δ
(
X
-
i
)
→
ℝ.For each playeri and probability distribution q
-
i
∈
Δ
(
X
-
i
), let
(1)
B
r
i
(
q
-
i
)
=
{
x
i
∈
X
i
:
u
i
(
x
i
,
q
-
i
)
≥
u
i
(
x
i
′
,
q
-
i
)
,
∀
x
i
′
∈
X
i
}
be the set of pure best responses of i against q
-
i.LetY
=
∏
i
∈
I
‍
Y
i be a product set where each Y
i is a nonempty subset of X
i. Let Δ
(
Y
-
i
) denote the set of probability distributions with support in Y
-
i. Finally, B
r
i
(
Δ
(
Y
-
i
)
) denotes the set of strategies in X
i that are pure best responses of i against some distribution q
-
i with support in Y
-
i; that is,
(2)
B
r
i
(
Δ
(
Y
-
i
)
)
=
⋃
q
-
i
∈
Δ
(
Y
-
i
)
‍
B
r
i
(
q
-
i
)
.


## 3.p-Best Response Sets

We will now introduce the concept of (minimal)p-best response set. Let p
∈
[
0,1
] and let Y
-
i be a nonempty subset of X
-
i. We write Δ
(
Y
-
i
,
p
)
⊆
Δ
(
X
-
i
) for the subset of distributions q
-
i
∈
Δ
(
X
-
i
) such that ∑
x
-
i
∈
Y
-
i
‍
q
-
i
(
x
-
i
)
≥
p. Let B
r
i
(
Δ
(
Y
-
i
,
p
)
) denote the set of strategies in X
i that are pure best responses by i to some distribution q
-
i
∈
Δ
(
Y
-
i
,
p
) (regardless of probability assigned to other possible combinations of strategies); that is,
(3)
B
r
i
(
Δ
(
Y
-
i
,
p
)
)
=
⋃
q
-
i
∈
Δ
(
Y
-
i
,
p
)
‍
B
r
i
(
q
-
i
)
.
Let us recall the definition of a strict p-dominant equilibrium first introduced by Morris et al. [8] in two-person games and extended to n-person games by Kajii and Morris [9]. A profile x
*
∈
X is a strict p
=
(
p
1
,
…
,
p
n
)-dominant equilibrium if for each player i
∈
I
(4)
{
x
i
*
}
=
B
r
i
(
Δ
(
{
x
-
i
*
}
,
p
i
)
)
.
In the sequel, we focus on the case where p
i
=
p for all i
∈
I. The concept of p-best response set extends the concept of strict p-dominant equilibrium to product sets of strategies. Formally, a (minimal) p-best response set is defined as follows.Definition 1.
Letp
∈
[
0,1
]. A p-best response set is a product set Y
⊆
X, where for each player i
(5)
B
r
i
(
Δ
(
Y
-
i
,
p
)
)
⊆
Y
i
.
A p-best response set Y is a minimal p-best response set if no p-best response set is a proper subset of Y.Let𝒬
p be the collection of p-best response sets for some p
∈
[
0,1
]. The following lemma states some properties of minimal p-best response sets.Lemma 2.
LetΓ be a finite n-person game. (1)
Γ has a minimal p-best response set for any p
∈
[
0,1
].
(2)
Fixp
∈
[
0,1
]. Then two distinct minimal p-best response sets of Γ are disjoint.
(3)
Forp
≤
1
/
2, there exists a unique minimal p-best response set in Γ.
(4)
Letp
≤
p
′
≤
1
/
2. Let Y and Y
′ be the minimal p-best response set and p
′-best response set, respectively. Then, Y
⊇
Y
′.For a proof of this Lemma, we refer the reader to Durieu et al. [4] and Tercieux [3].


## 4. Adaptive Processes

Following Samuelson [10], we extend the Darwinian process proposed by Kandori et al. [11] to the multipopulation case. This extension is quite natural to deal with asymmetric n-person games. We think the game Γ as having n roles. For each role i
∈
I, a nonempty class C
i of individuals is eligible to play that role. We assume that each class is composed of M identical agents, where M is a finite integer.We consider the possibility of local interactions. LetG
(
L
,
E
) be a graph where L
=
{
l
1
,
l
2
,
…
,
l
M
} is the set of vertices and E is the set of edges. We assume that vertices are located increasingly in a clockwise direction around a ring. We focus on a chordal ring: vertex l
k
,
k
∈
{
1,2
,
…
,
M
} is adjacent to the vertices (modulo M) l
k
±
1
,
l
k
±
2
,
…
,
l
k
±
K where 2
K
≤
M
-
1. If 2
K
=
M
-
1, then each vertex is adjacent to each other vertex. For each vertex l
∈
L, denote by V
(
l
) the open neighborhood of l, that is, the set of vertices adjacent to l. Since |
V
(
l
)
|
=
2
K for each l
∈
L, G
(
L
,
E
) is regular. The closed neighborhood of l, denoted by V
¯
(
l
), is defined by V
(
l
)
∪
{
l
}.We assume that each class ofM agents is distributed among the set of vertices L. In other words, each agent of each class C
i, i
∈
I, is located at exactly one vertex of L and two agents of the same class are located in different vertices of L. In this way, each vertex contains exactly n agents. From this point of view, each vertex can be interpreted as a location. We denote by x
(
l
)
∈
X the actions profile chosen by agents located in l
∈
L. The collection of action profiles chosen in all locations in L is Θ
=
X
M.Lett
=
1,2
,
… denote successive time periods. The stage game Γ is played once in each period. In period t, one agent is drawn at random from each of the n classes and assigned to play the corresponding role. We assume that, at every period, each agent has no information about who is selected to play each role in the game, only that a given action is played by someone. This lack of information gives rise to two kinds of assumptions made by each agent about his potential opponents, that is, about the matching rule. Fix a location l
∈
L. In a first scenario, each agent in l
∈
L assumes that his potential opponents belong to a unique location in V
¯
(
l
). In other words, opponents would be drawn jointly by location in the closed neighborhood of his location. In a second scenario, each agent in l
∈
L assumes that his potential opponents may belong to different locations in V
¯
(
l
). In other words, opponents would be drawn independently in the closed neighborhood of his location.We give a formal description of both scenarios. Consider a time periodt. Actions chosen in t by the whole population are described by θ
t
=
(
x
t
(
l
1
)
,
x
t
(
l
2
)
,
…
,
x
t
(
l
M
)
)
∈
Θ. Fix an agent i
∈
C
i located in l and an action profile x
∈
X. Denote by ω
l
t
(
x
-
i
) the number of locations in V
¯
(
l
) such that x
-
i
t
(
l
)
=
x
-
i in θ
t. According to the first scenario, at the beginning of period t
+
1, agent i believes that the probability to be matched with agents playing x
-
i is
(6)
q
-
i
L
(
x
-
i
)
=
ω
l
t
(
x
-
i
)
2
K
+
1
.In order to describe the second scenario, it is convenient for each classC
i to identify X
i with the set {
1,2
,
…
,
r
i
}, where r
i
=
|
X
i
|. For each j
∈
C
j such that C
j
≠
C
i, and each x
j
∈
{
1
,
…
,
r
j
}, denote by ω
l
t
(
x
j
) the number of V
¯
(
l
) where x
j is chosen in θ
t. Consider x
-
i
=
(
x
j
)
j
≠
i
∈
X
-
i. According to the second scenario, at the beginning of period t
+
1, agent i believes that the probability to be matched with agents playing x
-
i is
(7)
q
-
i
I
(
x
-
i
)
=
∏
j
≠
i
‍
ω
l
t
(
x
j
)
2
K
+
1
.In periodt, every agent in each class C
i chooses an action x
i
∈
X
i according to the following learning rule. Every agent might receive the opportunity to revise his choice. For the sake of simplicity, we assume that this adjustment probability does not depend on the agent nor on the actions chosen in the whole population. Whenever an agent does not receive a revision opportunity, he simply repeats the action he has taken in the past. Whenever an agent receives a revision opportunity, he switches to a myopic best response. That is, the agent assumes that the action choices of other agents will remain unchanged in the next period and adopts a pure best response against it. Precisely, agent i chooses a pure best response against the probability distribution on X
-
i computed using formula (6) or (7). In other words, we define two myopic best-response dynamics with inertia.If probability distributions are computed using (6), the dynamics results in a Markov chain on the state space Θ, denoted by P
L
0. We refer to it asbest-response process with joint drawing by location. Similarly, if probability distributions are computed using (7), the dynamics results in a Markov chain on the state space Θ, denoted by P
I
0. We refer to it asbest-response process with independent drawing. Let ℛ
L (resp. ℛ
I) be the collection of recurrent sets of P
L
0 (resp., P
I
0). For each i
∈
I and each subset Θ
′
⊂
Θ, let S
i
(
Θ
′
) be the set of actions in X
i that appears in Θ
′. The product set of all actions that appears in Θ
′ is S
(
Θ
′
)
=
∏
i
∈
I
‍
S
i
(
Θ
). Consider a minimal p-best response set Y. Denote by ℛ
Y
L
⊆
ℛ
L (resp., ℛ
Y
I
⊆
ℛ
I) the collection of recurrent sets of P
L
0 (resp. P
I
0) such that Θ
′
∈
ℛ
Y
L (resp., Θ
′
∈
ℛ
Y
I) if and only if S
(
Θ
′
)
⊆
Y. Observe that ℛ
Y
L
≠
∅ and ℛ
Y
I
≠
∅ since Y is a minimal p-best response set and thus a 1-best response set.Following the literature (see, e.g., [11, 12]), the model is completed by adding the possibility of rare mutations or experiments on the part of agents. With fixed probability ϵ
>
0, independent across players and across time, each agent chooses an action at random. The processes with mutations are calledperturbed processes and are denoted by P
L
ϵ and P
I
ϵ. With these mutations as part of the processes, each state of Θ is reachable with positive probability from every other state. Hence, the perturbed processes P
L
ϵ and P
I
ϵ are irreducible and aperiodic finite state Markov chains on Θ. Consequently, for each ϵ
>
0, P
L
ϵ (resp., P
I
ϵ) has a unique stationary distribution μ
L
ϵ (resp., μ
I
ϵ) satisfying μ
L
ϵ
P
L
ϵ
=
μ
L
ϵ (resp., μ
I
ϵ
P
I
ϵ
=
μ
I
ϵ). The limit stationary distribution (as the rate of mutation tends to zero) μ
L
*
=
lim
⁡
ϵ
→
0
μ
L
ϵ (resp., μ
I
*
=
lim
⁡
ϵ
→
0
μ
I
ϵ) exists and is a stationary distribution of the unperturbed process P
L
0 (resp., P
I
0). The states in the support of μ
L
* (resp. μ
I
*) are called stochastically stable states and form a subset of ℛ
L (resp., ℛ
I). The recurrent sets appearing in the support of μ
L
* (or μ
I
*) are those which are the easiest to reach from all other recurrent sets, with “easiest" interpreted as requiring the fewest mutations (cf., Theorem 4 in [12]).We rely on the identification of the set of stochastically stable states developed by Ellison [6]. This identification proceeds as follows. Ellison [6] introduces sufficient conditions to have a collection of recurrent sets that contains all stochastically stable states. The analysis uses three measures: the radius, the coradius, and the modified coradius. To illustrate these concepts, consider a collection of recurrent sets Θ
1
⊆
ℛ
L. Let D
(
Θ
1
) be the basin of attraction of Θ
1, that is, the set of states θ
∈
Θ from which the unperturbed process converges to Θ
1 with probability one. In other words, D
(
Θ
1
) is the set of states θ
∈
Θ such that it is possible without mutation to build a path, that is, a sequence of distinct states, from θ to θ
1
∈
Θ
1. The radius of (the basin of attraction of) Θ
1, denoted by R
(
Θ
1
), is the minimum number of mutations necessary to leave D
(
Θ
1
) from Θ
1, that is, the minimum number of mutations contained in any path from a state θ
1
∈
Θ
1 to a state θ
2
∉
D
(
Θ
1
). The coradius of (a basin of attraction of) Θ
1, denoted by C
R
(
Θ
1
), is the maximum over all states θ
2
∉
Θ
1 of the minimum number of mutations necessary to reach D
(
Θ
1
), that is, the maximum over all states θ
2
∉
Θ
1 of the minimum number of mutations contained in any path from θ
2 to a state θ
1
∈
D
(
Θ
1
). To compute the modified coradius of (the basin of attraction of) Θ
1, consider a state θ
2
∉
Θ
1 and a path from θ
2 to a state belonging to Θ
1. The modified number of mutations of this path is obtained by subtracting from the number of mutations of the path the radius of the intermediate recurrent sets through which the path passes. The modified coradius of (a basin of attraction of) Θ
1, denoted by C
R
*
(
Θ
1
), is the maximum over all states θ
2
∉
Θ
1 of the minimum modified number of mutations necessary to reach D
(
Θ
1
), that is, the maximum over all states θ
2
∉
Θ
1 of the minimum modified number of mutations associated with any path from θ
2 to a state θ
1
∈
D
(
Θ
1
). Note that C
R
*
(
Θ
1
)
≤
C
R
(
Θ
1
) for every Θ
1
⊆
Θ. Ellison [6] establishes the following result.Theorem 3 (see [6]).
Consider a perturbed process and fixΘ
1
⊆
Θ. If R
(
Θ
1
)
>
C
R
*
(
Θ
1
), then the stochastically stable states are contained in Θ
1.SinceC
R
*
(
Θ
1
)
≤
C
R
(
Θ
1
), an alternative condition to have all stochastically stable states contained in Θ
1 is that R
(
Θ
1
)
>
C
R
(
Θ
1
).


## 5. Selection Results

Fix a minimalp-best response set Y. First, consider the perturbed best-response process with joint drawing by location. We give a sufficient condition to have all stochastically stable states associated with Y.Theorem 4.
LetΓ be a finite n-person game and G
(
L
,
E
) a chordal ring of degree 2
K. Let p
≤
1
/
n and let Y be the minimal p-best response set of  Γ. If K is sufficiently large and ϵ is sufficiently small, the perturbed process P
L
ϵ puts arbitrarily high probability on a subset Θ
*
⊆
Θ such that S
(
Θ
*
)
⊆
Y.Proof.
Observe that ifℛ
Y
L
=
ℛ
L, then the result follows. In the sequel, we assume that ℛ
Y
L
⊂
ℛ
L. We break the proof into three parts.
(
1
) We give a lower bound on R
(
ℛ
Y
L
). Fix a state θ
∈
ℛ
Y
L, a location l
∈
L, and two distinct classes C
i and C
j. Consider agent i
∈
C
i located in l and agent j
∈
C
j located in l
k
∈
V
¯
(
l
). Assume that agent j mutates: he chooses at random a strategy not contained in Y
j. Then, agent i believes that the probability to be matched with agents playing a vector of actions not contained in Y
-
i is ∑
x
-
i
∉
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
1
/
(
2
K
+
1
). Now, assume that α
≤
2
K
+
1 agents in C
j located in locations belonging to V
¯
(
l
) mutate and choose an action outside Y
j. Then, agent i believes that the probability to be matched with agents playing a vector of actions not contained in Y
-
i is ∑
x
-
i
∉
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
α
/
(
2
K
+
1
). Let p
¯ be a probability such that at least one class of agents C
i has an action x
i
∉
Y
i as a pure best response to q
-
i
L, where ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
p
¯. By definition of a minimal p-best response set, we have p
>
p
¯. A transition from Θ
1
∈
ℛ
Y
L to any Θ
2
∉
ℛ
Y
L requires at least z mutations (in locations belonging to V
¯
(
l
) and outside Y
j), where z is such that z
/
(
2
K
+
1
)
≥
1
-
p
¯. Otherwise, agent i’s best-response(s) to q
-
i
L belong(s) to Y
i since ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
≥
p. Hence, R
(
ℛ
Y
L
) is such that R
(
ℛ
Y
L
)
≥
⌈
(
1
-
p
¯
)
(
2
K
+
1
)
⌉.
(
2
) We give an upper bound on C
R
*
(
ℛ
Y
L
). To do this, it is convenient to distinguish between two situations according to the values of p and K. Firstly, consider the cases such that ⌈
p
(
2
K
+
1
)
⌉
≤
K. Fix a state θ
∉
ℛ
Y
L and a class C
i. Assume that, in a location l
k
∈
L, (
n
-
1
) agents j
∉
C
i mutate and choose actions in Y
j. Then, agent i
∈
C
i located in l
∈
V
¯
(
l
k
) believes that the probability to be matched with agents playing a vector of actions contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
1
/
(
2
K
+
1
). Now, consider α
≤
2
K
+
1 consecutive locations in G
(
L
,
E
) denoted by l
k
,
k
∈
{
1
,
…
,
α
}. Assume that in each of these locations (
n
-
1
) agents j
∉
C
i mutate and choose actions in Y
j. Then, agent i
∈
C
i located in l such that l
∈
V
¯
(
l
k
) for each k
∈
{
1
,
…
,
α
} believes that the probability to be matched with agents playing a vector of actions contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
α
/
(
2
K
+
1
). By definition of a minimal p
-best response set, agent i has at least one strategy x
i
∈
Y
i as a pure best response to q
-
i
L after that all agents j
∉
C
i located in α
*
≤
2
K
+
1 consecutive locations in G
(
L
,
E
) belonging to V
¯
(
l
) mutate and choose actions in Y
j if α
* is such that α
*
/
(
2
K
+
1
)
≥
p. Set α
*
=
⌈
p
(
2
K
+
1
)
⌉. Since p
≤
1
/
n, if in α
* consecutive locations, l
1
,
…
,
l
α
*, every agent j
∉
C
i mutates and chooses an action in Y
j, then every agent i
∈
C
i located in each of these locations chooses an action in Y
i. By inertia, it is then possible to reach a state in which an action profile contained in Y is played in α
* consecutive locations, l
1
,
…
,
l
α
*. From such a state, it is possible to reach a state in ℛ
Y
L without additional mutation. Indeed, consider agents located in l
α
*
+
1. Since ⌈
p
(
2
K
+
1
)
⌉
≤
K, every agent of each class, C
i, believes that the probability to be matched with agents playing a vector of actions contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
α
*
/
(
2
K
+
1
)
≥
p. Then, it is possible to reach a state in which an action profile in Y is chosen in α
*
+
1 consecutive locations. Continuing in this fashion, we can reach a state in ℛ
Y
L without additional mutation. Hence, C
R
(
ℛ
Y
L
) is such that C
R
(
ℛ
Y
L
)
≤
(
n
-
1
)
⌈
p
(
2
K
+
1
)
⌉.
Secondly, consider the cases such that⌈
p
(
2
K
+
1
)
⌉
>
K. Observe that since p
≤
1
/
n, we necessarily have n
=
2. Fix a state θ
1
∉
ℛ
Y
L. By the above point, we know that α
*
=
⌈
p
(
2
K
+
1
)
⌉ mutations allow reaching a state, denoted by θ
2, where an action profile in Y is chosen in α
* consecutive locations, l
1
,
…
,
l
α
*. If the number of locations belonging to L
∖
{
l
k
,
k
∈
{
1
,
…
,
α
*
}
} is at most equal to K, then every agent of each class C
i
,
i
∈
{
1,2
}, located in these locations believes that the probability to be matched with an agent playing an action contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
≥
p. A transition from θ
2 to a state in ℛ
Y
L is possible without additional mutation and C
R
(
ℛ
Y
L
) is bounded as above. It remains to deal with situations where the number of locations in L
∖
{
l
k
,
k
∈
{
1
,
…
,
α
*
}
} is strictly greater than K. In θ
2, each agent i
∈
C
i
,
i
∈
{
1,2
}, located in these locations believes that the probability to be matched with an agent playing an action contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
<
p. Thus, it is possible that θ
2 does not belong to ℛ
Y
L nor to the recurrent set containing θ
1. However, an additional mutation is sufficient to reach a state, say θ
3, in which an action profile in Y is chosen in α
*
+
1 consecutive locations. To see this, consider location l
α
*
+
1. If agent j
∈
C
2 located in l
α
*
+
1 mutates and chooses an action in Y
2, then agent i
∈
C
1 located in l
α
*
+
1 believes that the probability to be matched with an agent playing an action contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
≥
p. Using inertia, it is possible that an action profile in Y is chosen in location l
α
*
+
1. By a similar argument, it is possible to establish that one additional mutation may allow reaching a state θ
4 in which an action profile in Y is chosen in α
*
+
2 consecutive locations. This argument can be applied until the number of locations in which an action profile not contained in Y is equal to K. From such a state, it is possible to reach a state in ℛ
Y
L without additional mutation. Hence, the path from θ
1
∉
ℛ
Y
L to a state in ℛ
Y
L passes through a sequence of intermediate recurrent sets whose radius is equal to 1. Thus, the modified coradius of ℛ
Y
L is such that C
R
*
(
ℛ
Y
L
)
≤
⌈
p
(
2
K
+
1
)
⌉.
Finally, sinceC
R
(
ℛ
Y
L
)
≥
C
R
*
(
ℛ
Y
L
), it holds in all cases that
(8)
C
R
*
(
ℛ
Y
L
)
≤
(
n
-
1
)
⌈
p
(
2
K
+
1
)
⌉
.
(
3
) In order to apply Theorem 3, it is sufficient to show that
(9)
⌈
(
1
-
p
¯
)
(
2
K
+
1
)
⌉
>
(
n
-
1
)
⌈
p
(
2
K
+
1
)
⌉
.
A sufficient condition to obtain inequality (9) is that
(10)
1
-
p
¯
>
(
n
-
1
)
p
+
n
-
1
2
K
+
1
.
Inequality (10) is satisfied provided that K is sufficiently large since by hypothesis p
≤
1
/
n, and, by definition of a minimal p-best response set, we have 1
-
p
¯
>
1
-
p.By definition, if a minimalp-best response set is a singleton set, then it is a strict p-dominant equilibrium. The following result is an immediate application of Theorem 4.Corollary 5.
LetΓ be a finite n-person game and G
(
L
,
E
) a chordal ring of degree 2
K. Let x
* be a strict p-dominant equilibrium of Γ, where p
≤
1
/
n. If K is sufficiently large and ϵ is sufficiently small, the perturbed process P
L
ϵ puts arbitrarily high probability on a subset Θ
*
⊆
Θ such that S
(
Θ
*
)
=
{
x
*
}.Observe that ifn
=
2, Corollary 5 is similar to Corollary 2 in Ellison [6] except that it also holds for the class of asymmetric two-player games with a 1
/
2-dominant equilibrium.Second, we consider the perturbed best-response process with independent drawing. We give a sufficient condition to have all stochastically stable states associated with a minimalp-best response set Y.Theorem 6.
LetΓ be a finite n-person game and G
(
L
,
E
) a chordal ring of degree 2
K. Let p
≤
n
1
-
n and let Y be the minimal p-best response set of Γ. If K is sufficiently large and ϵ is sufficiently small, the perturbed process P
I
ϵ puts arbitrarily high probability on a subset Θ
*
⊆
Θ such that S
(
Θ
*
)
⊆
Y.Proof.
Observe that ifℛ
Y
I
=
ℛ
I, then the result follows. In the sequel, we assume that ℛ
Y
I
⊂
ℛ
I. As in the proof of Theorem 4, we break the proof into three parts.
(
1
) We give a lower bound on R
(
ℛ
Y
I
). By the same reasoning as in the proof of Theorem 4, it follows that R
(
ℛ
Y
I
) is such that R
(
ℛ
Y
I
)
≥
⌈
(
1
-
p
¯
)
(
2
K
+
1
)
⌉.
(
2
) We give an upper bound on C
R
*
(
ℛ
Y
I
). Observe that if n
=
2, both processes P
I
ϵ and P
L
ϵ coincide. By the same reasoning as in the proof of Theorem 4, it follows that if n
=
2 then C
R
*
(
ℛ
Y
I
)
≤
⌈
p
(
2
K
+
1
)
⌉. Now, assume that n
>
2. Fix a state θ
∉
ℛ
Y
I and a class C
i. Assume that, in a location l
k
∈
L, (
n
-
1
) agents j
∉
C
i mutate and choose actions in Y
j. Then, agent i
∈
C
i located in l
∈
V
¯
(
l
k
) believes that the probability to be matched with agents playing a vector of actions contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
I
(
x
-
i
)
=
(
1
/
(
2
K
+
1
)
)
n
-
1. Now, consider α
≤
2
K
+
1 consecutive locations in G
(
L
,
E
) denoted by l
k
,
k
∈
{
1
,
…
,
α
}. Assume that in each of these locations (
n
-
1
) agents j
∉
C
i mutate and choose actions in Y
j. Then, agent i
∈
C
i located in l such that l
∈
V
¯
(
l
k
) for each k
∈
{
1
,
…
,
α
} believes that the probability to be matched with agents playing a vector of actions contained in Y
-
i is ∑
x
-
i
∈
Y
-
i
‍
q
-
i
L
(
x
-
i
)
=
(
α
/
(
2
K
+
1
)
)
n
-
1. By definition of a minimal p-best response set, agent i has at least one strategy x
i
∈
Y
i as a pure best response to q
-
i
I after that all agents j
∉
C
i located in α
*
≤
2
K
+
1 consecutive locations in G
(
L
,
E
) belonging to V
¯
(
l
) mutate and choose actions in Y
j if α
* is such that (
α
*
/
(
2
K
+
1
)
)
n
-
1
≥
p. Set α
*
=
⌈
p
1
/
(
n
-
1
)
(
2
K
+
1
)
⌉. Since p
≤
n
1
-
n, if in α
* consecutive locations every agent j
∉
C
i mutates and chooses an action in Y
j, then every agent i
∈
C
i located in each of these locations chooses an action in Y
i. By inertia, it is then possible to reach a state in which an action profile contained in Y is played in α
* consecutive locations in G
(
L
,
E
). From such a state, it is possible to reach a state in ℛ
Y
I without additional mutation. Indeed, since p
≤
n
1
-
n and n
>
2, we necessarily have α
*
≤
K. Hence, C
R
(
ℛ
Y
I
) is such that C
R
(
ℛ
Y
I
)
≤
(
n
-
1
)
⌈
p
1
/
(
n
-
1
)
(
2
K
+
1
)
⌉.
(
3
) In order to conclude, it is sufficient to show that
(11)
⌈
(
1
-
p
¯
)
(
2
K
+
1
)
⌉
>
(
n
-
1
)
⌈
p
1
/
(
n
-
1
)
(
2
K
+
1
)
⌉
.
A sufficient condition to obtain inequality (11) is that
(12)
1
-
p
¯
>
(
n
-
1
)
p
1
/
(
n
-
1
)
+
n
-
1
2
K
+
1
.
Inequality (12) is satisfied provided K is sufficiently large since by hypothesis p
≤
n
1
-
n, and, by definition of a minimal p-best response set, we have 1
-
p
¯
>
1
-
p.The following result is an immediate application of Theorem6.Corollary 7.
LetΓ be a finite n-person game and G
(
L
,
E
) a chordal ring of degree 2
K. Let x
* be a strict p-dominant equilibrium of Γ, where p
≤
n
n
-
1. If K is sufficiently large and ϵ is sufficiently small, the perturbed process P
I
ϵ puts arbitrarily high probability on a subset Θ
*
⊆
Θ such that S
(
Θ
*
)
=
{
x
*
}.


## 6. Conclusion

This paper establishes that the concept of minimalp-best response set is useful to study the long-run outcomes of a process when agents are arranged on a chordal ring and follow a myopic best response rule with inertia. In particular, it allows us to obtain results for the whole class of finite n-person games. Even if predictions are not necessarily sharp (since a minimal p-best response set may become large when p decreases), those results make easier the identification of stochastically stable states. The paper also highlights that predictions depend on the assumptions made by agents about the matching rule. From this point of view, it is possible to establish a connection between these results and the results obtained in Durieu et al. [4]. This paper considers a fictitious play model with bounded memory and sample as in Young’s [12]. Two processes are studied. On the one hand, it is assumed that each agent believes that, in every period, his opponents play independently. On the other hand, each agent believes that, in every period, the play of his opponents is correlated. Durieu et al. show that the concept of p-best response set allows establishing predictions about the long-run outcomes of both processes. Furthermore, as in the present paper, there exists a similar gap between predictions obtained for each process. This conveys the idea that sampling in memory and believing that opponents correlate their actions (play independently resp.) has the same effect as believing that players are drawn jointly (independently resp.) in neighborhood to play the game.



---

*Source: 415686-2014-03-26.xml*