Ordered Kripke Model, Permissibility, and Convergence of Probabilistic Kripke Model
Shuige Liu
econ.EM





[label0]The author would like to thank Andrés Perea and Zsombor Z. Méder for
their valuable comments and encouragements. She gratefully acknowledge the
support of Grant-in-Aids for Young Scientists (B) of JSPS No. 17K13707,
Grant for Special Research Project No. 2017K-016 of Waseda University. 



Faculty of Political Science and Economics, Waseda University, 1-6-1
Nishi-Waseda, Shinjuku-Ku, 169-8050, Tokyo, Japan


shuige_liu@aoni.waseda.jp


We define a modification of the standard Kripke model, called the ordered
Kripke model, by introducing a linear order on the set of accessible states
of each state. We first show this model can be used to describe the
lexicographic belief hierarchy in epistemic game theory, and perfect
rationalizability can be characterized within this model. Then we show that
each ordered Kripke model is the limit of a sequence of standard
probabilistic Kripke models with a modified (common) belief operator, in the
senses of structure and the (ε-)permissibilities characterized
within them.





ordered Kripke model, lexicographic belief, probabilistic
Kripke model, permissibility








§ PRELIMINARIES


In this section we give surveys on lexicographic belief and permissibility
(Section <ref>.1) and on probabilistic Kripke model for games
(Section <ref>.2). These will be preparation for the introduction of
ordered Kripke model in Section <ref>.



 §.§ Lexicographic belief and permissibility


In this subsection we give a survey on lexicographic epistemic model (with
complete information) and the definition of permissibility. For a details,
see Perea <cit.>, Chapter 5. Consider a finite 2-person strategic form
game G=(N,{S_i}_i∈ N,{u_i}_i∈ N) where I=1,2. A finite 
lexicographic epistemic model for G is a tuple M^lex=(Θ
_i,β _i)_i∈ N where(a) Θ _i is a finite set of types, and(b) β _i is a mapping that assigns to every θ _i∈Θ
_i a lexicographic belief over Δ (S_j×Θ _j), i.e., β _i(θ _i)=(β _i1,β _i2,...,β _iK) where β _ik∈Δ (S_j×Θ _j) for k=1,...,K.

Let θ _i∈Θ _i with β _i(θ _i)=(β
_i1,β _i2,...,β _iK). Each β _ik (k=1,...,K) is
called θ _i's level-k belief. For (s_j,θ _j)∈
S_j×Θ _j, we say θ _i deems (s_j,θ
_j) possible iff β _ik(s_j,θ _j)>0 for some k∈{1,...,K}. We say θ _i deems θ _j∈Θ _j 
possible iff θ _i deems (s_j,θ _j) possible for
some s_j∈ S_j. For each θ _i∈Θ _i, we denote by Θ _j(θ _i) the set of all θ _j∈Θ _j deemed
possible by θ _i.Definition <ref>.1 (Caution) Type θ _i∈Θ
_i is cautious iff for each θ _j∈Θ _j(θ
_i) and each s_j∈ S_j, it deems (s_j,θ _j)
possible.

For each s_i∈ S_i, let u_i(s_i,θ _i)=(u_i(s_i,θ
_i1).,..,u_i(s_i,θ _iK)) where for each k=1,...,K, u_i(s_i,θ _ik):=Σ _(c_j,t_j)∈ C_j× T_jβ
_ik(s_j,θ _j)u_i(s_i,s_j), that is, each u_i(s_i,θ _ik) is the expected utility for s_i over θ
_ik and u_i(s_i,θ _i) is a vector of expected utilities. For
each s_i,s_i^'∈ S_i, we say that θ _i 
prefers s_i to s_i^', denoted by u_i(s_i,θ
_i)>u_i(s_i^',θ _i), iff there is k∈{0,...,K-1}
such that the following two conditions are satisfied:(a) u_i(s_i,θ _iℓ)=u_i(s_i^',θ _iℓ)
for ℓ =0,...,k, and(b) u_i(s_i,θ _i,k+1)>u_i(s_i^',θ _i,k+1)
.We say that θ _i is indifferent between s_i and s_i^', denoted by u_i(s_i,θ _i)=u_i(s_i^',θ _i), iff u_i(s_i,θ _ik)=u_i(s_i^',θ
_ik) for each k=1,...,K. It can be seen that the preference relation on 
S_i under each type θ _i is a linear order. s_i is 
rational (or optimal) for θ _i iff θ _i does not
prefer any choice to s_i.Definition <ref>.2 (Primary belief in the opponent's
rationality) Let θ _i∈Θ _i with β _i(θ
_i)=(β _i1,β _i2,...,β _iK). θ _i 
primarily believes in j's rationality iff θ _i's
primary belief θ _i1 only assigns positive probability to those (s_j,θ _j) where s_j is rational for θ _j.Definition <ref>.3 (Common full belief in a property) Let P be an arbitrary property of lexicographic types.(a) θ _i∈Θ _i expresses 0-fold full belief
in P iff θ _i satisfies P;(b) For each n∈ℕ, θ _i∈Θ _i expresses 
(n+1)-fold full belief in P iff θ _i only deems
possible j's types that express n-fold full belief in P.θ _i expresses common full belief in P iff it expresses n
-fold full belief in P for each n∈ℕ.Definition <ref>.4 (Permissibility). Given a lexicographic
epistemic model M^lex=(Θ _i,β _i)_i∈ N for a game G=(N,{S_i}_i∈ N,{u_i}_i∈ N), s_i∈ S_i is 
permissible iff it is optimal to some θ _i∈Θ _i which
expresses common full belief in caution and primary belief in
rationality.Example <ref>.1 Consider the game G as follows (Myerson 
<cit.>):

    u_1\ u_2   C   D
    A   1,1   0,0
    B   0,0   0,0

and M^lex=(Θ _i,β _i)_i∈ N for G where Θ
_1={θ _1}, Θ _2={θ _2}, and

    β _1(θ _1)=((C,θ _2),(D,θ _2)),
    b_2(t_2)=((A,θ _1),(B,θ _1)).

It can be seen that A is permissible since it is optimal to t_1 which
expresses common full belief in caution and primary belief in
rationality.

It is shown by Proposition 5.2 in Asheim and Dufwenberg <cit.> that a
strategy is permissible if and only if it survives an algorithm called 
Dekel-Fudenberg procedure (Dekel and Fudenberg <cit.>). Given a game G, by Dekel-Fudenberg procedure we mean the process that (1) at first round
we eliminate all weakly dominated strategies in G, and (2) then iteratedly
eliminate dominated strategies until no strategies can be eliminated.




 §.§ Probabilistic Kripke model for games


In this subsection we give a survey of the probabilistic Kripke model for
games which is a generalization of the standard Kripke model that is able to
capture both pure and mixed strategies. For details, see Bonanno <cit.>, 
<cit.>. Let G=(N,{S_i}_i∈ N,{u_i}_i∈ N) be a 2-person
strategic form game. A probabilistic Kripke model of G is a tuple ℳ=(W,{R_i}_i∈ N,{p_i}_i∈ N,{σ _i}_i∈
N) where (1) W≠∅ is the set of states (or possible worlds
), sometimes called the domain of ℳ and is denoted by 𝒟(ℳ);(2) For each i∈ N, R_i⊆ S× S is the accessibility
relation for player i. For each w∈ W, we use R_i(w) to denote the
set of all accessible states from w, i.e., R_i(w)={w^'∈
W:wR_iw^'};(3) For each i∈ N, p_i is a mapping from W to Δ (W)
satisfying (a) for each w∈ W, supp p_i(w)⊆ R_i(w), and (b)
for each w^'∈ R_i(w), p_i(w^')=p_i(w);(4) For each i∈ N, σ _i is a mapping from W to S_i such
that for each w^'∈ R_i(w), σ _i(w^')=σ
_i(w)

(W,{R_i}_i∈ N,{σ _i}_i∈ N) is a standard Kripke
model of G. ℳ^o=(W,{R_i}_i∈ N) is called the 
Kripke frame of ℳ. Here we follow the literatures and assume
that ℳ^o is a KD45 frame, i.e., each R_i is serial,
transitive, and Euclidean. For each i∈ N, a semantic belief
operator is a function 𝔹_i:2^W→ 2^W such that
for each E⊆ W,

    𝔹_i(E)={w∈ W:R_i(w)⊆ E}.

A semantic common belief operator is a function ℂ𝔹
:2^W→ 2^W such that for each E⊆ W,

    ℂ𝔹(E)={w∈ W:∪ _i∈ NR_i(w)⊆ E}.

It can be seen that 𝔹_i and ℂ𝔹 correspond to Aumann 
<cit.>'s standard concept “knowledge”and “common knowledge”.

At w∈ W the strategy s_i∈ S_i with s_i is at least as
prefered to s_i^' iff u_i(s_i,Σ _w^'∈
R_i(w)p_i(w)(w^')σ _j(w^'))≥
u_i(s_i^',Σ _w^'∈ R_i(w)p_i(w)(w^')σ _j(w^')). s_i is prefered to s_i^'
at w iff the strict inequality holds. s_i is optimal at w iff
there is no strategy preferred to s_i at w. A state w is 
rational for i iff σ _i(w) is optimal at w. We use RAT_i
to denote the set of all rational states for player i, and define RAT=∩ _i∈ NRAT_i.

The following statement connects iterated elimination of pure dominated
strategies (an algorithm) to rationality (an epistemic concept). Its proof
can be found in Bonanno <cit.>, p.452.Theorem <ref>.1 (Iterated elimination of dominated
strategies and Kripke model). Let G=(N,{S_i}_i∈ N,{u_i}_i∈
N) and S^IEDS be the set of strategy profiles surviving iterated
elimination of dominated strategies. Then(1) given an arbitrary probabilistic Kripke model of G, if w∈ℂ𝔹
(RAT), then σ (w)∈ S^IEDS;(2) for each s∈ S^IEDS, there is a probabilistic Kripke model of G
and a state w such that σ (w)=s and w∈ℂ𝔹(RAT).



§ ORDERED KRIPKE MODEL OF GAMES AND PERMISSIBILITY


In this section we define the ordered Kripke model as a modification of the
standard one and show how it can be used to describe the lexicographic
reasoning in game theory.Definition <ref>.1 (Ordered epistemic model) Let G=(N,{S_i}_i∈ N,{u_i}_i∈ N) be a 2-person strategic form
game. An ordered Kripke model of G is a tuple ℳ
=(W,{R_i}_i∈ N,{σ _i}_i∈ N,{λ _i}_i∈ N)
where(1) (W,{R_i}_i∈ N,{σ _i}_i∈ N) is a standard Kripke
model of G, and(2) For each i∈ N, λ _i assigns to each w∈ W an injection
from a cut {1,...,K} of natural numbers to the set of probability
distributions (with finite supports) over R_i(w), i.e., λ
_i(w):{1,...,K}→Δ (R_i(w)). λ _i(w) can be
interpreted as a linear order on a finite subset of Δ (R_i(w)). We
use 𝒟(λ _i(w)) and ℛ(λ _i(w)) to
denote the domain and the range of λ _i(w), i.e., 𝒟
(λ _i(w))={1,...,K} and ℛ(λ _i(w))={λ
_i(w)(1),...,λ _i(w)(K)}Definition <ref>.2 (Caution). Let G=(N,{S_i}_i∈
N,{u_i}_i∈ N) be a strategic form game and ℳ
=(W,{R_i}_i∈ N,{σ _i}_i∈ N,{λ _i}_i∈ N)
an ordered Kripke model for G. R_i is cautious at w∈ W iff
for any s_j∈ S_j (j≠ i), there exists w^' which is
assigned a possitive probability by some element in ℛ(λ
_i(w)) such that σ _j(w^')=s_j. We say ℳ is cautious iff for each i∈ N, R_i is cautious
at every w∈ W.

The difference between the ordered Kripke model and the standard one is that
the former assigns a linear order λ _i(w) on R_i(w) for each
state w. This order is used to define the preferences in the model. We
have the following defintion.Definition <ref>.3 (Lexicographic preferences) Let G=(N,{S_i}_i∈ N,{u_i}_i∈ N) be a strategic form game and ℳ=(W,{R_i}_i∈ N,{σ _i}_i∈
N,{λ _i}_i∈ N) an ordered Kripke model for G. At w∈ W
the strategy s_i∈ S_i is at least as lexicographically
prefered to s_i^', denoted by s_i≽ _ws_i^', iff ∃ k∈{0,...,|𝒟(λ _i(w))|} such
that(a) u_i(s_i,σ _j(σ _j(λ
_i(w)(t))))=u_i(s_i^',σ _i(λ _i(w)(t))) for
all t≤ k;(b) u_i(s_i,σ _j(λ _i(w)(k+1)))=u_i(s_i^',σ _i(λ _i(w)(k+1))).

Here by σ _j(λ _i(w)(t)) we mean the mixture of stategies
in σ _j(λ _i(w)(t)). Therefore 

    u_i(s_i,σ _j(σ _j(λ _i(w)(t))))=Σ _w^'∈ R_i(w)λ _i(w)(t)(w^')u_i(s_i,σ
    _i(w^')).

It can be seen that when k=|𝒟(λ _i(w))|, s_i and s_i^' generates the same payoff for player i along λ
_i(w). This case is denoted by s_i≃ _ws_i^'. When k≠ |𝒟(λ _i(w))|, we say that s_i is 
lexicographically prefered to s_i^' at w, denoted by s_i≻ _ws_i^'. s_i is optimal at w iff there
is no s_i^'∈ S_i such that s_i^'≻ _ws_i.
We say a state w is lexicographically rational for i iff the
choice σ _i(w) is optimal for i. For each i∈ N, let LRAT_i
be the set of rational states for player i and LRAT=∩ _i∈ NLRAT_i.Example <ref>.1. Consider the following game G in Example 
<ref>.1:

    u_1\ u_2   C   D
    A   1,1   0,0
    B   0,0   0,0

and an ordered Kripke model ℳ as follows:





It can be seen that ℳ is cautious. It can be seen that A and C are optimal in
each state, w_1 and w_2 are rational for player 1, and w_1 and w_3 are rational for player 2. Therefore, LRAT_1={w_1,w_2}, LRAT_2={w_1,w_3}, and LRAT={w_1}. On the other hand, as
mentioned in Example <ref>.1, since both σ _1(w_2)=A and σ _2(w_2)=D are permissible strategies, lexicographic rationality
in the ordered Kripke model here captures the concept of “a
strategy is rational under a lexicographic belief” in the
first order. Now the problem is how to define belief hierarchy and common
belief in this model. It can be seen that we cannot adopt 𝔹_i
and ℂ𝔹 in standard approach. Indeed, in Example <ref>.1 𝔹_i(LART)=ℂ𝔹(LART)=∅ , which is contradictory
to our intention to preserve w_2. Here we give one approach. For each i∈ N and w∈ W, let R_i^1(w)={w^'∈ W:λ
_i(w)(1)(w^')>0} and R^1=∪ _i∈ NR_i^1. A 
semantic level-1 belief operator for player i is a mapping 𝔹
_i^1:2^W→ 2^W such that for each E⊆ W,

    𝔹_i^1(E)={w∈ W:R_i^1(w)⊆ E}.

Similarly, a semantic common level-1 belief operator is a mapping ℂ𝔹^1:2^W→ 2^W such that for each E⊆ W,

    ℂ𝔹^1(E)={w∈ W:∪ _i∈ NR_i^1(w)⊆ E}.

It can be seen that 𝔹_i^1(LRAT)=ℂ𝔹^1(LRAT)={w_1} in Example <ref>.1. In general, we have the follwong
result.Theorem <ref>.1 (Permissibility and semantic common level-1
belief). Let G=(N,{S_i}_i∈ N,{u_i}_i∈ N) be a strategic
form game and S^PER⊆ S be the set of permissible strategy
profiles. Then(1) given an arbitrary cautious ordered Kripke model of G, if w∈ℂ𝔹^1(LRAT), then σ (w)∈ S^PER, and(2) for each s∈ S^PER, there exists a cautious ordered Kripke
model of G such that σ (w)=s and w∈ℂ𝔹^1(LRAT).


To show Theorem <ref>.1, we need the following lemma.Lemma <ref>.1. Let G=(N,{S_i}_i∈ N,{u_i}_i∈
N) be a strategic form game and S^DF⊆ S be the set of strategy
profiles surviving Dekel-Fudenberg procedure. Then given an arbitrary
cautious ordered epistemic model of G, if w∈ℂ𝔹^1(LRAT),
then σ (w)∈ S^DF.Proof. For each n∈ℕ, we use S^DFn to denote the
set of strategy profiles surviving the first n rounds of Dekel-Fudenberg
procedure. Let M=(W,{R_i}_i∈ N,{σ _i}_i∈
N,{λ _i}_i∈ N) be a cautious ordered epistemic model of G
and w∈ W. We show that if w∈ℂ𝔹^1(LRAT), then σ
(w)∈ S^DFn for each n∈ℕ. First, since M is
cautious, it can be seen that σ (w)∈ S^DF1. Indeed, if there is
some i∈ N such that σ _i(w) is eliminated in the first round of
Dekel-Fudenberg procedure, then there is some r_i∈Δ (S_i).
Then it follows from Theorem 5.8.3 in Perea <cit.> (p.215, 221-226) σ _i(w) cannot be optimal to any cauious belief, i.e., it cannot be
optimal on λ _i(w), which is contradictory since w∈ LRAT_i.

Now we show that σ (w)∈ S^DF2. Suppose for some i∈ N, σ
_i(w) is eliminated in the second round of Dekel-Fudenberg procedure,
i.e., there exists r_i∈Δ (S_i^DF1) such that u_i(r_i,s_j)>u_i(s_i,s_j) for all s_j∈ S_j^DF1. On
the other hand, since w∈ℂ𝔹^1(LRAT), σ _i(w) is
optimal to λ _i(w)(1). This implied that some strategies
supporting λ _i(w)(1) has been eliminated in the first round.
However, since w∈ℂ𝔹^1(LRAT), it follows from the definition
that supp λ _i(w)(1)⊆ LRAT, which, from the argument
above, implies that all strategies w^'∈ supp λ
_i(w)(1) should have survived the first round and σ _j(w^') stay in S_j^DF1, a contradiction.

Now suppose that σ (w)∈ S^DF1∩ ...∩ S^DFn but disappeared
in S^DFn+1. This could happen only if some strategies supporting λ _i(w)(1) had been eliminated in the n-th round, which is
because some strategies supporting that strategy in λ _i(w)(1) in (
n-1)-th round, etc. Finally this leads to the second and first rounds,
which, by the argument above, is impossible. Therefore σ (w)∈
S^DFn+1. //Proof of Theorem <ref>.1: (1) Since, by Proposition 5.2 in
Asheim and Dufwenberg <cit.>, any strategy surviving Dekel-Fudenberg
procedure is permissible and vice versa, i.e., S^PER=S^DF, (1)
directly follows from Lemma <ref>.1.(2) Let s∈ S^PER, that is, for each i∈ N, s_i is
optimal to some type expressing common full belief in caution and primary
belief in rationality in a lexicographic epistemic model M^lex=(T_j,b_j)_j∈ N. We construct an ordered Kripke model M=(W,{R_i}_i∈ N,{σ _i}_i∈ N,{λ
_i}_i∈ N) based on M^lex as follows:(1) Let W=T× S, here T=Π _i∈ NT_i;(2) for each w=(t_1,t_2,s_1,s_2), σ _i(w)=s_i;
(3) Connectiong each state in W according to M^lex, i.e., for each w=(t_1,t_2,s_1,s_2),w^'=(t_1^',t_2^',s_1^',s_2^')∈ T× S, w^'=λ
_i(w)(k) iff t_i=t_i^', s_i=s_i^', and (s_j^',t_j^') is the k-th entry in b_i(t_i);
mixed strategy-type pairs are defined in a similar way.Without loss of generality, we can assume that each type in M^lex is
cautious.[
For a state that is not cautious we can extend it into a cautious one. See
Liu <cit.>.] It can be seen that ℳ is also
cautious, and there is w∈ W with σ (w)=s and w∈ℂ𝔹
^1(LRAT). //



§ ORDERED KRIPKE MODEL AS THE LIMIT OF PROBABILISTIC KRIPKE MODELS 



Though the ordered Kripke model is not the first framework combining
standarad Kripke model with an order on (a subset of) each R_i(w) (cf.
Baltag and Smets <cit.>, <cit.>), here we are interested in how
such a model can be connected to the probabilistic Kripke model for games
introduced in Section <ref>. In this section we will first introduce
a probabilistic Kripke model with modified belief operators under which ε-perfect rationalizability can be characterized. Then we will
show that an ordered Kripke model can be seen as a “limit” of a sequence of probablistic Kripke models.



 §.§ Probabilistic belief and ε-perfect
rationalizability


In this subsection we give a survey on probabilitstic epistemic model (with
complete information) and the definition of ε-perfect
rationalizability. See Perea <cit.>, Chapter 2 for the detail of the
former. ε-permissible, which originates from Myerson <cit.>
, is defined in a similar way as ε-proper rationalizability as
in Schuhmacher <cit.> and Perea and Roy <cit.>. Consider a finite
2-person strategic form game G=(N,{S_i}_i∈ N,{u_i}_i∈ N).
A finite probabilistic epistemic model for G is a tuple M^pro=(T_i,b_i)_i∈ N where(a) T_i is a finite set of types, and(b) b_i is a mapping that assigns to every t_i∈ T_i a
probability distribution over Δ (S_j× T_j).

For each s_i∈ S_i and t_i∈ T_i, we define u_i(s_i,t_i)=Σ _(s_j,t_j)∈ S_j×
T_jb_i(t_i)(s_j,t_j)u_i(s_i,s_j). s_i is optimal
(or rational) for t_i iff u_i(s_i,t_i)≥
u_i(s_i^',t_i) for any s_i^'∈ S_i. For each s_i,s_i^'∈ S_i and t_i∈ T_i, s_i is
preferred to s_i^' under t_i iff u_i(s_i,t_i)>u_i(s_i^',t_i). Given t_i∈ T_i,
for each (s_j,t_j)∈ S_j× T_j, we say t_i deems (s_j,t_j) possible iff b_i(t_i)(s_j,t_j)>0. We say t_i deems t_j∈ T_j possible iff t_i deems (s_j,t_j) possible for some s_j∈ S_j. For each t_i∈ T_i,
we denote by T_j(t_i) the set of all t_j's deemed possible by t_i.Definition <ref>.1 (Caution) Type t_i∈ T_i is 
cautious iff for each t_j∈ T_j(t_i) and each s_j∈ S_j, t_i deems (s_j,t_j) possible.Definition <ref>.2 (ε-perfect
trembling condition) Type t_i∈ T_i satisfies ε
-perfect trembling condition iff for any s_j∈ S_j and t_j∈
T_j(t_i) such that t_i deems (s_j,t_j) possible, if s_j
is not optimal under t_j then b_i(t_i)(s_j,t_j)≤ε
.Definition <ref>.3 (Common full belief in a property) Let P be an arbitrary property of probabilistic types.(a) t_i∈ T_i expresses 0-fold full belief in P iff 
t_i satisfies P;(b) For each n∈ℕ, t_i∈ T_i expresses (n+1)
-fold full belief in P iff t_i only deems possible j's types
that express n-fold full belief in P.t_i expresses common full belief in P iff it expresses n-fold
full belief in P for each n∈ℕ.Definition <ref>.4 (ε-Perfect
rationalizability). Given a probabilistic epistemic model M^pro=(T_i,b_i)_i∈ N for a game G=(N,{S_i}_i∈
N,{u_i}_i∈ N), s_i∈ S_i is ε-
permissible iff it is optimal to some t_i∈ T_i which expresses
common full belief in caution and ε-perfect trembling
condition.Example <ref>.1. Consider the following game G (from
Myerson <cit.>):

    u_1\ u_2   C   D
    A   1,1   0,0
    B   0,0   0,0

and M^pro=(T_i,b_i)_i∈ N for G where T_1={t_1}, T_2={t_2}, and

    b_1(t_1)=(1-ε )(C,t_2)+ε (D,t_2),
    b_2(t_2)=(1-ε )(A,t_1)+ε (B,t_1),

where ε∈ (0,1). It can be seen that A is ε
-permissible since it is optimal to t_1 which expresses common full
belief in caution and ε-perfect trembling condition.

Originally, by the definition in Myerson <cit.>, perfect equilibrium is
the limit of ε-perfect equilibrium. Though permissibility is
the concepts in epistemic game theory and is defined in a different manner,
it still holds tha permissibility is the limit of ε
-permissibility. See Schuhmacher <cit.>.



 §.§ Characterizing ε-permissibility in
probabilistic Kripke model


In this subsection, we show how to use probabilistic Kripke model to
describe ε-permissibility. Let G=(N,{S_i}_i∈
N,{u_i}_i∈ N) be a 2-person strategic form game and ℳ
=(W,{R_i}_i∈ N,{p_i}_i∈ N,{σ _i}_i∈ N) a
probabilistic Kripke model for G. We give the following
definitionsDefinition <ref>.5 (Caution). ℳ is 
cautious at w∈ W for i∈ N iff for any s_j∈ S_j (j≠ i),
there exists w^'∈ R_i(w) satisfying p_i(w)(w^')>0
and σ _j(w^')=s_j. We say ℳ is cautious
iff ℳ is cautious at every w∈ W for each i∈ N.Definition <ref>.6 (ε-perfect
trembling condition). ℳ satisfies ε-perfect
trembling condition at w∈ W for i∈ N iff for each w^'∈
R_i(w), if σ _i(w^') (i.e., σ _i(w)) is not
optimal to σ _j(w^'), then p_i(w)(w^')≤ε.

The above two concepts are illustrated in the following example.Example <ref>.1. Consider the game G in Example <ref>.1:

    u_1\ u_2   C   D
    A   1,1   0,0
    B   0,0   0,0

and a probabilistic Kripke model depicted as in Figure 2. 



It can be seen that RAT_1={w_1,w_2}, RAT_2={w_1,w_3}, and RAT=RAT_1∩
RAT_2={w_1}. Since σ (w_1)=(A,C) is a pair of ε
-perfect rationalizable strategies, RAT can still be used in this
framework for the first-order. Now the problem is how to describe higher
orders, i.e., interpersonal belief and common full belief in this framework. 
𝔹_i and ℂ𝔹 in standard probabilistic model do not
work here since 𝔹_i(RAT)=ℂ𝔹(RAT)=∅ , while we
want to keep w_1. Here we provide an approach. Let ℳ
=(W,{R_i}_i∈ N,{p_i}_i∈ N,{σ _i}_i∈ N,) a
probabilistic Kripke model for G satisfying caution and ε
-perfect trembling condition. For each i∈ N, we define R_i^>ε={w^'∈ R_i(w):p_i(w)(w^')>ε}. An upper ε semantic belief
operator is a function 𝔹_i^>ε:2^W→
2^W such that for each E⊆ W,

    𝔹_i^>ε(E)={w∈ W:R_i^>ε(w)⊆
    E}.

An upper ε semantic common belief operator is a
function ℂ𝔹^>ε:2^W→ 2^W such that for
each E⊆ W,

    ℂ𝔹^>ε(E)={w∈ W:∪ _i∈ NR_i^>ε(w)⊆ E}.

When ε <1/2, it can be seen that in Example <ref>
.1, ℂ𝔹^>ε(RAT)={w_1}.

In general, we have the following statement.Theorem <ref>.1 (Characterizing ε
-perfect rationalizability). Let G=(N,{S_i}_i∈ N,{u_i}_i∈
N) be a 2-person strategic form game, ε <1/2,[
It should be noted that ε <1/2 makes sure that R_i^>ε(w)≠ R_i(w), though from the viewpoint of
convergence/limit this is just a technical requirement.] and S^ε PER⊆ S be the set of ε-permissible
strategy profiles. Then(1) given an arbitrary probabilistic Kripke model of G satisfying
caution and ε-perfect trembling condition, if w∈ℂ𝔹
^>ε(RAT), then σ (w)∈ S^ε PER,
and(2) for each s∈ S^ε PER, there exists a
probabilistic Kripke model of G satisfying caution and ε
-perfect trembling condition such that σ (w)=s and w∈ℂ𝔹
^>ε(RAT).Proof. (2) can be proved in a similar way as Theorem <ref>
.1. Here we only prove (1). Since there is no algorithm like Dekel-Fudenberg
procedure that can screen out ε-permissibility, we show how to
construct a type which expresses common full belief in caution and ε-perfect trembling condition. Let ℳ
=(W,{R_i}_i∈ N,{p_i}_i∈ N,{σ _i}_i∈ N) be a
probabilistic Kripke model for G satisfying caution and ε
-perfect trembling condition and w∈ℂ𝔹^>ε(RAT).
For i∈ N, we define a partition 𝔼_i={E_i1,...,E_iℓ
_i} of W and satisfies that for each w^',w^''∈ W, w^' and w^'' belong to the same
equivalent class E_i if and only if R_i(w^')=R_i(w^'') and p_i(w^')=p_i(w^''). For each E_i∈𝔼_i we assign a symble t_i(E_i). Without loss of
generality, we can assume that for each s_i∈ S_i and each E_ik,
there is some w^'∈ E_ik such that σ _i(w^')=s_i.[
This corresponds to caution for probabilistic epistemic model M^pro. It
should be noted that even this condition is not satisfied, we can construct
“ dummies” to make this condition
satisfied without hurt the model.] Let T_i={t_i(E_i)}_E_i∈𝔼_i, and define b_i(t_i(E_i)) with the same probability
as p_i(w^'), where w^'∈ E_i, and the corresponding 
t_j(E_j). It can be seen that b_i(t_i(E_i)) is well-defined
since every state in one E_i has identified distributions. It can be
seen straightforwardly that σ (w)∈ S^ε PER since for
each i∈ N, σ _i(w) is optimal to the type corresponding to w
which expresses common full belief in caution and ε-perfect
trembling condition since ℳ satisfies caution and ε
-perfect trembling condition. //



 §.§ Probabilistic Kripke models converge to ordered Kripke model


In this subsection we show that any ordered Kripke model is the limit of a
sequence of probabilistic Kripke models. This can be intuitively seen by
comparing the two Kripke models in Example <ref>.1 and <ref>
.1: Indeed, Figure 2 can be obtained by replacing 1-ε with 1 and ε with 2 in Figure 1. Also, this can be seen from that perfect rationalizability characterized
by the former is the limit of a sequence of ε-perfect
rationalizabilities characterized by the later. In this section we show how
to formulate this idea.

Let G=(N,{S_i}_i∈ N,{u_i}_i∈ N) be a 2-person strategic
form game and ℳ=(W,{R_i}_i∈ N, {σ
_i}_i∈ N,{λ _i}_i∈ N) be an ordered Kripke model of G. Without loss of generality, we assume that ℳ
satisfies the following two conditions:(Disjoint supports) For each i∈ N, w∈ W, and k,k^'∈𝒟(λ _i(w)), supp λ _i(w)(k)∩ supp λ _i(w)(k^')≠∅ if and only if k≠ k^';[
This condition is adopted in some papers such as Blume et al. <cit.>, 
<cit.> while is not required in some others such as the standard
textbook of Perea <cit.>. Technically, this condition is not necessary
in characterizing rationalizabilities. Here we use it out of simplification.](Surjection) For each w∈ W and each w^'∈ R_i(w),
there is some k∈𝒟(λ _i(w)) such that λ
_i(w)(k)(w^')>0.[
Surjection is different from caution. Caution requires each strategy of the
opponent should appear in the range. When there are multiple states in R_i(w) which are assigned the same strategy, to be cautious only means
that at least one of those state should appear in the range, while
surjection requires that each of these states should appear. On the other
hand, it does not mean that surjection implies caution since surjection has
nothing with strategies assigned to each state in R_i(w). In finite
models, when surjection is not satisfied, we can faithfully extend each
model into one which satisfies surjection without hurting LRAT and ℂ𝔹(LRAT).]

Let ε∈ (0,1). Consider a probabilistic Kripke model ℳ^ε=(W^ε,{R_i^ε}_i∈
N,{p_i^ε}_i∈ N,{σ _i^ε}_i∈ N) of G satisfying(a) W^ε=W, R_i^ε=R_i and σ
_i^ε=σ _i for each i∈ N;(b) for each i∈ N, w∈ W, and w^',w^''∈
supp λ _i(w)(k) for some k∈𝒟(λ _i(w)), it
is satisfied that p_i^ε(w)(w^')/p_i^ε(w)(w^'')=λ _i(w)(k)(w^')/λ
_i(w)(k)(w^'');(c) for each i∈ N, w∈ W, and w^'∈ R_i(w), 0<p_i^ε(w)(w^')≤ε if λ
_i(w)(1)(w^')=0.It can be seen that when ε is small enough, such ℳ
^ε exists (not unique). Let {ε _n}_n∈ℕ be a sequence in (0,1) that converges to 0 such that for
each ε _n, there is some probabilistic Kripke model satisfying
(a) - (c). We choose an arbitrary ℳ^ε _n
satisfying (a) - (c) for each ε _n. It can be seen that the
sequence {ℳ^ε _n}_n∈ℕ
“converges” to ℳ
in the sense that(1) for each i∈ N, w∈ W, and w^'∈ R_i(w) such that p_i^ε _n(w)(w^')→ 0, w^' does
not appear in λ _i(w)(1);(2) for each i∈ N, w∈ W, and w^'∈ R_i(w) such that p_i^ε _n(w)(w^')↛ 0, w^'∈
supp λ _i(w)(1) and p_i^ε _n(w)(w^')→λ _i(w)(1)(w^');(3) The convergence is propotional within each level of λ _i(w).
[
To dealing those “ irrational” choice
which is assigned in probability 0 in any rational belief is one of the
motivation for the introduce of lexicographic belief and studies from
conditional probability. See Blume et al. <cit.>, <cit.>,
Brandenburger et al. <cit.>, Halpern <cit.>.]More formally, this convergence can be seen from the rationalizabilities
they characterize. We have the following statement.Theorem <ref>.2 (Probabilistic models converge to ordered
model). Let G be a 2-person strategic game, ℳ a
cautious ordered Kripke model of G satisfying disjoint supports and
surjection, {ε _n}_n∈ℕ a sequence in (0,1)
converging to 0, and {ℳ^ε _n}_n∈ℕ
be a sequence of probabilistic model of G satisfying condition (a) - (c)
above for each ε _n. Then each w which is commonly believed
to be lexicographically rational in ℳ is commonly
believed to be ε _n-upper rational in ℳ
^ε _n for each ε _n, i.e., ℂ𝔹
^1(LRAT)=∪ _M∈ℕ∩ _n>Mℂ𝔹^>ε
_n(RAT_ε _n).Proof. (⊆) Let w∈ℂ𝔹^1(LRAT). It follows
from Theorem <ref>.1 that σ (w)∈ S^PER, that is, there is
a lexicographic model (Θ _i,β _i)_i∈ N such for each i∈ N, σ _i(w) is optimal to some θ _i∈Θ _i
which expresses common full belief in caution and primary belief in
rationality. Based on each ℳ^ε _n, θ _i
can be accordingly translated into a state t_i^ε _n
“starting” from w in probabilistic
model. Since σ _i(w) is optimal to some θ _i, when ε _n is small enough, σ _i(w) is optimal to t_i^ε _n, and t_i^ε _n expresses common
full belief on caution and ε _n-perfect trembling condition.
This argument holds for each i∈ N. Then by Theorem <ref>.1 σ (w)∈ℂ𝔹^>ε _n(RAT_ε _n), and
consequently w∈∪ _M∈ℕ∩ _n>Mℂ𝔹
^>ε _n(RAT_ε _n).

(⊇) Let w∈∪ _M∈ℕ∩ _n>Mℂ𝔹
^>ε _n(RAT_ε _n), that is, for some M∈ℕ, w∈ℂ𝔹^>ε _n(RAT_ε _n)
for all n≥ M. Since ε _n→ 0, it follows that
for each i∈ N, σ _i(w) is optimal on p_i^ε
_n(w) for infinitely small ε _n. Since each ℳ
^ε _n keeps the propotion between states within each level of 
λ _i(w), this implies that σ _i(w) is optimal to λ
_i(w). Also, the state in the probabilistic model of G corresponding to 
ℳ^ε _n supporting σ _i(w) expresses
common full belief in caution and ε-perfect trembling
condition. Since ℳ is surjective, it follows that the
corresponding type in the lexicographic model for ℳ
expresses common full belief in caution and primary belief in rationality.
Therefore σ _i(w) is perfect rationalizable in ℳ. Since this argument holds for all i∈ N, it follows that w∈ℂ𝔹^1(LRAT). //



§ CONCLUDING REMARKS 




 §.§ Convergence and proper rationalizability


In Section <ref>, we characterized permissibility by ordered Kripke
model. Though it is desirable to characterize other rationalizability
concepts, e.g., proper rationalizability (Asheim <cit.>), in the ordered
Kripke model, we think it is difficult, if not impossible. The reason is
that in this framework, the difference between perfect and proper
rationalizabilities is at what kind of order λ _i(w) gives on R_i(w), which more relies on the interpretation than on the structure. In
other words, by changing the order on accessable states we can characterize
proper rationalizability; but this is attributed to the interpretation we
give to each state, not to any structural properties of the Kripke frame (W,{R_i}_i∈ N) like seriality or transitivity.

On the other hand, using the approach introduced in Section <ref>.3,
proper rationalizability can be discussed as the limit of probabilistic
Kripke models. Let G be a 2-person strategic form game and a cautious
ordered Kripke model ℳ satisfies a condition parallel
to “respecting the opponent's preferences”. For ε >0, consider ℳ^ε=(W^ε,{R_i^ε}_i∈ N,{p_i^ε}_i∈
N,{σ _i^ε}_i∈ N) a probabilistic Kripke model of 
G satisfying conditions (a), (b) in Section <ref>.3 and (c^') for each i∈ N, w∈ W, and w^',w^''∈ R_i(w), 0<p_i^ε(w)(w^')≤ε
p_i^ε(w)(w^'') if λ _i(w)(k^')(w^')>0, λ _i(w)(k^'')(w^'')>0, and k^''>k^'. It can be seen that (1) each
probabilistic Kripke model satisfying (a), (b), and (c^')
characterizes some ε-perfect rationalizable strategies; (2) ℳ is the limit of a sequence {ℳ
^ε _n}_n∈ℕ satisfying (a), (b), and (c^'); and (3) the perfect rationalizable strategies characterized in 
ℳ is limits of ε _n-perfect
rationalizable strategies characterized by {ℳ^ε
_n}_n∈ℕ.



 §.§ Syntactical system


In this paper we have defined the ordered Kripke model to capture the
concept of rationality under lexicographic belief hierarchy by a semantical
approach. It is wondered that whether there exists a syntactic approach
corresponding to that semantic framework, like the one developed in Bonanno 
<cit.> for the standard Kripke model for games. A critical property for
that syntactic system, if exists, is that the change of the criterion for
truth value from the first order to higher orders in the hierarchy, that is,
in the first order we need (at most) to check every accessible state, while
in the second order 𝔹_i^1 we need only to check the first
level states, etc. Works are expected in this direction.





§ REFERENCES




a01 Asheim, G.B., (2001). Proper rationalizability in
lexicographic beliefs. International Journal of Game Theory 30
, 453-478.

ad03 Asheim, G.B., Dufwenberg, M. 2003. Admissibility and common
belief. Games and Economic Behavior 42, 208-234.

a76 Aumann, R., 1976. Agreeing to disagree. The Annals of
Statistics 4, 1236-1239.

bs06 Baltag, A., Smets, A., 2006. Conditional doxastic models: a
qualitative approach to dynamic belief revision. Electronic Notes in
Theoretical Computer Science 165, 5–21.

bs07 Baltag, A., Smets, A., 2007. From conditional probability to
the logic of doxastic actions. Proceedings of TARK XI, Samet, D. ed,
52-61.

b08 Bonanno, G., 2008. A syntactic approach to rationality in
games with ordinal payoffs, In Logic and the Foundation of Game and
Decision Theory (LOFT 7), volumn 3 of Texts in Logic and Games,
Bonanno, D., van der Hoek, W., Wooldridge, M., eds, Amsterdam University
Press, 59-86.

b15 Bonanno, G., 2015. Epistemic foundation of game theory,
Chapter 9 of Handbook of Epistemic Logic, van Ditmarsch, H., Halpern,
J.Y., van der Hoek, W., Kooi, B., eds, College Publications, 443-487.

bbd91a Blume, L., Brandenburger, A., Dekel, E., 1991.
Lexicographic probabilities and choice under uncertainty. Econometrica
59, 61-79.

bbd91b Blume, L., Brandenburger, A., Dekel, E., 1991.
Lexicographic probabilities and equilibrium refinements. Econometrica
59, 81-98.

b92 Brandenburger, A. (1992). Lexicographic probabilities and
iterated admissibility. In Economic Analysis of Markets and Games,
ed. P. Dasgupta, et al. MIT Press, 282-290.

bfk07 Brandenburger, A., Friedenberg, A., Keisler, H.J., 2007.
Notes on the relationship between strong belief and assumption, working
paper.

df90 Dekel, E., Fudenberg, D., 1990. Rational behvaior with payoff
uncertainty. Journal of Economic Theory 89, 165-185.

h10 Halpern, J.Y., 2010. Lexicographic probability, conditional
probability, and nonstandard probability. Games and Economic Behavior 
68, 155-179.

l18 Liu, S. (2018). Characterizing permissibility and proper
rationalizability by incomplete information. EPICENTER Working Paper No.14,
Maastricht University.

m78 Myerson, R.B., 1978. Refinements of the Nash Equilibrium
Concept. International Journal of Game Theory 7, 73-80.

p12 Perea, A., 2012. Epistemic Game Theory: Reasoning and
Choice. Cambridge University Press.

ps17 Perea, A., Roy, S., 2017. A new epistemic characterization of 
ε-proper rationalizability. Games and Economic Behavior 
104: 309-328.

s99 Schuhmacher, F., 1999. Proper rationalizability and backward
induction. International Journal of Game Theory 28, 599-615.


