Iterative Information Update andStability of Strategies
Takuya Masuzawa1 and Koji Hasebe2
1

Faculty of Economics, Osaka University of Economics
2-2-8 Osumi, Higashiyodogawa-ku, Osaka, 533-8533 Japanmasuzawa@osaka-ue.ac.jp
2
Graduate School of Systems and Information Engineering, University of Tsukuba
1-1-1 Tennoudai, Tsukuba-shi, 305-8573 Japan
hasebe@iit.tsukuba.ac.jp

Abstract. In this paper, we investigate processes of iterative information update due to Benthem (International Game Theory Review, vol.9,
pp.13-45, 2007), who characterized existent game-theoretic solution concepts by such processes in the framework of Plaza’s public announcement logic. We reﬁne this approach and make clearer the relationshipbetween stable strategies and information update processes. We ﬁrst extend Plaza’s logic then demonstrate the conditions under which a stableoutcome is determined independently of the order of iterative information
update. This result gives an epistemic foundation for the order independence of iterated elimination of disadvantageous strategies.
Keywords: game theory, epistemic logic, information update, publicannouncement, stable strategy

1

Introduction

Logical analysis of game-theoretic solution concepts is an active trend in studies
on dynamic epistemic logic [8] and its variants (cf. also [4]). In that domain, researchers consider processes of updating each agent’s knowledge, which changes
the epistemic models for a given game. In particular, by means of Plaza’s publicannouncement logic [15], Benthem [2] analyzed game theoretic solution concepts
by considering an information updating process. In his setting, based on a decision criterion every player ﬁrst chooses a strategy as a tentative decision, andthen each player’s information about the situation is iteratively updated depending on the other players’ tentative decisions. The information update may
bring about a failure of the criterion to keep the tentative decision. That is,
the information update may suggest that another choice is preferable to someplayers, and they may change their tentative decisions. In this setting, Benthem
considered a stability of strategy, which we call iterative updatability in this paper. Roughly speaking, a tentative decision is iteratively updatable if no playerchanges it for any number of public announcements that no player has changed
his tentative decision so far. Through this notion, Benthem characterized existent game-theoretic solution concepts.

The purpose of our paper is to reﬁne the approach of [2] and make clearer the
relationship between stable strategies and information update processes. For thispurpose, we also introduce a logic based on Plaza’s public announcement logic[15]. In order to describe game-theoretic components, such as players’ evaluationof a situation and intensions for their choices, we ﬁrst extend Plaza’s logic so that
all the atomic formulas are classiﬁed into three categories: information-invariant(or called invariant), information-monotonic (or called monotonic), and the others. An invariant atomic formula represents a statement whose truth value does
not change after any information update. On the other hand, a monotonic atomic
formula represents a statement whose truth persists after any information update if it is previously true. In this sense, in Plaza’s logic all the atomic formulas
are regarded as invariant. This extension provides an enough expressive power
to describe the game-theoretic components whose truth might change after someannouncement. Then we also introduce an extended Kripke-style possible world
semantics and show the soundness and completeness for this syntax.
Next we formalize the notion of iterative updatability in terms of our logic toinvestigate its properties, especially in relation with information-monotonicity.
We show that if announced statements are information monotonic, then the order of announced statements does not aﬀect the information updatability. This
result explains the order independence of iterated elimination of disadvantageous
strategies. Moreover, we show that the iterative process of information update
preserves logical implication between two statements if one of them is monotonic. This theorem is useful when we compare diﬀerent information updatingprocesses.
Finally, we also demonstrate how to apply our results to game-theoretic situations. The ﬁrst example is an exchange economy with asymmetric information.
By iterative updatability, we explain how the quality of a good, which is initially private information, is revealed to other market participants. As a second
application, following [2], we reexamine iterated elimination of disadvantageous
strategies. By means of our reﬁned framework, we demonstrate properties suchas order independence, comparison of two criteria, and its relation to Nash equilibria.
Paper organization. Section 2 introduces the syntax and semantics of ourlogic. Section 3 formulates the notion of iterative updatability, and then shows
its properties. Section 4 demonstrates how to analyze a game-theoretic situation
by iterative updatability. Finally, Section 5 concludes the paper.

2

Public announcement logic

In this section we introduce our inference system, which is an extension of Plaza’s
public announcement logic [15].
2.1

Language

Let N be a set of players and P be an inﬁnitely countable set of atomic formulas(denoted by the symbols p, q, . . .). Here, we introduce the classiﬁcation of atomic

formulas into the following three types: information-invariant formulas (denotedby Q∗ ), information-monotonic formulas (denoted by Q), and the others, whereQ∗ ⊆ Q ⊆ P . This classiﬁcation is the diﬀerence between our logic and that ofPlaza’s. Throughout the paper, for brevity, Q∗ and Q are often called invariant
and monotonic atomic formulas, respectively.
Formulas (denoted by ϕ, ψ, . . .) are constructed by the following grammar,
which is the same as in Plaza’s logic.
ϕ ::= p | ¬ϕ | ϕ ∧ ϕ | ϕ ∨ ϕ | ϕ ⇒ ϕ | ϕ ↔ ϕ | Ki ϕ | 〈ϕ〉ϕIntuitively, a formula of the form Ki ϕ means that player i knows ϕ, while aformula of the form 〈ϕ〉ψ means that ψ holds after the true statement ϕ has
been publicly announced.
2.2

Axiomatic system

The axioms and inference rules of our system are as follows.
Axioms for the propositional tautology and epistemic operators:
A1 Every axiom of the propositional tautology is an axiom.
A2 Ki (ϕ ⇒ ψ) ⇒ (Ki ϕ ⇒ Ki ψ).
A3 Ki ϕ ⇒ ϕ.
Axioms for the public announcement operator:
P1 〈ϕ〉ψ ⇒ ϕ.
P2 〈ϕ〉¬ψ ↔ ϕ ∧ ¬〈ϕ〉ψ.
P3 〈ϕ〉(ψ ∧ χ) ↔ 〈ϕ〉ψ ∧ 〈ϕ〉χ.
P4 〈ϕ〉Ki ψ ↔ ϕ ∧ Ki (ϕ ⇒ 〈ϕ〉ψ).
P5 〈ϕ〉〈ψ〉χ ↔ 〈〈ϕ〉ψ〉χ.
A theorem of our system is inductively deﬁned as follows.
R1 If ϕ is an axiom, then ⊢ ϕ.
R2 Modus ponens: If ⊢ ϕ and ⊢ (ϕ ⇒ ψ), then ⊢ ψ.
R3 Necessitation: If ⊢ ϕ, then ⊢ Ki ϕ.
R4 Substitution of equals for public announcement:
If ⊢ ϕ ↔ ψ, then ⊢ 〈ϕ〉χ ↔ 〈ψ〉χ and ⊢ 〈χ〉ϕ ↔ 〈χ〉ψ.
R5 Invariance for null information: If ⊢ ϕ, then ⊢ ψ ↔ 〈ϕ〉ψ.
Note that the system composed of A1-A3 and R1-R3 is the usual multimodal
propositional logic. On the other hand, axioms P1-P5 and inference rules R4 andR5 are used for reasoning about public announcements.
In addition to all the axioms and inference rules introduced above, Plaza’s
logic includes the axiom that 〈ϕ〉q ↔ ϕ ∧ q for any atomic formula q. Insteadof this axiom, we introduce the following axiom P0 and inference rule R6 toformalize the notions of invariance and monotonicity, respectively.
Axiom for invariance:
P0 〈ϕ〉q ↔ ϕ ∧ q for all q ∈ Q∗ .

Inference rule for monotonicity:
R6 If ⊢ ϕ ⇒ ψ, then ⊢ 〈ϕ〉¬q ⇒ 〈ψ〉¬q for all q ∈ Q.
Axiom P0 means that the truth value of any invariant atomic formula does
not change after any announcement. On the other hand, inference rule R6 meansthat the truth of any monotonic atomic formula is preserved after any announcement if it is initially true.
Here, we make some remarks on this extension of Plaza’s logic. As mentioned
in Section 1, in the framework of Plaza’s logic, the truth value of an atomic
formula does not change after any information update. In other words, Plaza’s
logic is a special case in which Q∗ = Q = P (i.e., any atomic formula is treated as
invariant). To describe our target situation, however, in which the preferences or
intentions of players may change depending on information updates, we require
some distinction between invariant and non-invariant statements. Our logic is aminimal extension to solve this problem.
From the syntactic point of view, Plaza’s formalism allows us to translate any
formula into an equivalent one without the public announcement operator. Plaza
used this property to prove some logical meta-theorems, such as the completenesstheorem [15]. On the other hand, this property does not hold for our logic, but
through semantic extension we can also prove its completeness, which is shownin the next subsection.
Regarding the notion of monotonicity, we can extend it to general formulas.
Let M be a set of formulas, each of which (say, χ) satisﬁes the following condition: if ⊢ ϕ ⇒ ψ, then ⊢ 〈ϕ〉¬χ ⇒ 〈ψ〉¬χ. Clearly, this condition is a naturalextension of R6. For M, the following proposition holds.
Proposition 1. M is closed under the following operations:
1. If χ1 ∈ M and χ2 ∈ M, then (χ1 ∧ χ2 ), (χ1 ∨ χ2 ) are also in M.
2. If χ1 ∈ M, then Ki χ1 is also in M.
These operations do not fully characterize M. For example, we can show thatif χ1 ∈ M and χ2 ∈ M, then ¬χ1 ⇒ 〈¬χ1 〉χ2 are also in M. Further, note that
all theorems are monotonic.
2.3

Semantics

Our language can be interpreted in standard models for epistemic logic, except
for interpretation of invariance and monotonicity.
A Kripke-model M is a triple (W, (R)i∈N , v), where W is a set of states, Rian accessibility relation over W for player i ∈ N , and v : P × W × 2P → {1, 0} is
an assignment function. We assume that Ri is reﬂexive. We impose the following
conditions on v:
Invariance of Q∗ : For any q ∈ Q∗ , v(q ∗ , w, X ′ ) = v(q ∗ , w, X ′′ ) for any w ∈ W ,and for any X ′ , X ′′ ⊆ W .

Monotonicity of Q : If X ′ ⊆ X ′′ ⊆ W and v(q, w, X ′′ ) = 1, then v(q, w, X ′ ) =1 for any w ∈ W .
Here, remember that Q∗ and Q are the sets of information-independent andinformation-monotonic atomic formulas, respectively.
The diﬀerence between usual Kripke semantics and ours lies in the interpretation of atomic formulas. In usual Kripke semantics, the truth value of an
atomic formula is determined for each state. By means of this assignment function, however, we cannot treat a situation in which the truth value of an atomic
formula in a certain state may change after some public announcement. In orderto formalize such dynamism, our idea is to extend the assignment function sothat the truth value of an atomic formula in a state is determined by a set ofstates X ⊆ W . Then, we deﬁne the truth values of atomic formulas for such sets
X, X ′ , X ′′ , . . . ⊆ W , which are obtained after public announcements.
Deﬁnition 1 (Truth conditions). The truth value of a formula in state w of
M = (W, (R)i∈N , v) is deﬁned as follows. Here, (w, M ) |= ϕ denotes that ϕ istrue in state w of model M .
1. For an atomic formula q ∈ P , (w, M ) |= q iﬀ v(q, w, W ) = 1.
2. For all ψ and ϕ, each of ¬ψ, ψ ⇒ ϕ, ϕ ∧ ψ, ϕ ∨ ψ, and ϕ ↔ ψ is true in w
of M iﬀ it is true in the truth table of ψ and ϕ.
3. For all ψ and i ∈ N , (w, M ) |= Ki ψ iﬀ for all w′ such that wRi w′ , (w′ , M ) |=ψ.
4. For all ψ and ϕ, (w, M ) |= 〈ψ〉ϕ iﬀ (w, M ) |= ψ and (w, M |ψ) |= ϕ, where
M |ψ = (W |ψ, (Ri |ψ)i∈N , v|ψ), W |ϕ = {w′ ∈ W : (w, M ) |= ψ}, and Ri |ψ
and v|ψ are the restrictions of Ri and v to W |ψ, respectively.
We also deﬁne that ϕ is valid (denoted by |= ϕ) iﬀ (w, M ) |= ϕ for any model
M and for any state w.
For the syntax and semantics introduced so far, we can prove the following
soundness and completeness theorem by similar argument as in [15].
Theorem 1 (Soundness and Completeness). For any formula ϕ, ⊢ ϕ iﬀ|= ϕ.
Proof. Due to space limitations, we only show the completeness. It suﬃces toshow that for all ϕ, if 0 ¬ϕ then ϕ is satisﬁable. Let S(ϕ) be the set of all subformulas of ϕ and we say that a set U of formulas is S(ϕ)-maximal consistent if(1) for all ϕ′ ∈ S(ϕ) either one of ϕ′ and ¬ϕ′ is in U , (2) for all ϕ1 ∈ U there
exists ϕ2 ∈ S(ϕ) such that either ϕ1 = ϕ2 or ϕ1 = ¬ϕ2 , (3) if ϕ1 , ϕ2 , . . . , ϕm ∈ Uthen 0 ¬(∧mi ϕi ). Let M = (W, (Ri ), v) be a Kripke-model such that
– W = {U : U is a S(ϕ)-maximal consistent set.},– U Ri U ′ iﬀ ϕ is in U ′ for all ϕ such that Ki ϕ ∈ U ,– for all p ∈ P , v(p, U, X) = 1 iﬀ p ∈ U ,– for all Y ̸= X and all p ∈ (P \Q), v(p, U, Y ) = 1 iﬀ Y = {U ′ ∈ W : ϕ1 ∈ U ′ },〈ϕ1 〉p ∈ U for some 〈ϕ1 〉p ∈ S(ϕ),– for all Y ̸= X and all q ∈ Q, v(q, U, Y ) = 1 iﬀ either q ∈ U or Y ⊂ {U ′ ∈X|ϕ1 ∈ U ′ }, 〈ϕ1 〉q ∈ U for some 〈ϕ1 〉q ∈ S(ϕ).
For this model, by induction on ϕ we can show that ϕ ∈ U iﬀ (U, W ) |= ϕ forall ϕ.
¤As an application, we have the following result:
Proposition 2. If Q = ∅, for any formula ϕ ∈ M, either ⊢ ϕ or ⊢ ¬ϕ.
Proof. Suppose to the contrary that there exists ϕ ∈ M such 0 ϕ, 0 ¬ϕ.
First, we consider the case where for any Kripke-model whose set of thestates is singleton, ϕ is false. By the completeness theorem, we have a ﬁnite
model M1 = (W1 , (Ri,1 ), v1 ) and w ∈ W1 such that for some state w, (w, M1 ) |=ϕ. We can assume |W1 | is minimal. Then, we can ﬁnd a literal p such that
(1) (w, M1 ) |= p and (2) |W1 | > |W1 |p|. Thus, (w, M1 ) |= ϕ ∧ 〈p〉¬ϕ, which
contradicts the monotonicity of ϕ.
Now, consider the second case where there exists a Kripke-model M2 suchthat the set of states is singleton and that ϕ is true. By the completeness theorem,
we have a ﬁnite model M3 = (W3 , (Ri,3 ), v3 ) and w ∈ W3 such that (w, M3 ) |=¬ϕ. Without any loss of generalities, assume that the number of state is minimal.
If v(q, w, W3 ) ̸= v(q, w′ , W3 ) for some q and w′ ̸= w then W3 |q ̸= W3 andwe have, from the minimality, w, M3 |q |= ϕ, which contradicts the monotonicity of ϕ. Then we can assume that v(q, w, W3 ) = v(q, w′ , W3 ) for all q andw′ ̸= w. Then in any state of W3 , the truth-value of any formula is equivalent. From the minimality, |W3 | = 1. Let us construct a model M4 as follows:
W4 = {a1 , a2 , . . . , an }; xRi,4 y iﬀ x = y. Let Xk denote {a1 , a2 , . . . , ak }. If l < kthen v3 (q, al , Xk ) is determined as M2 ; otherwise it is determined as M3 . In thismodel, inductively we can prove that for all deg(ψ) ≤ k − l, (al , Xk ) |= ψ if
(w, M2 ) |= ψ. (Here, deg stands for the number of logical connectives.) Thus,in the case of n = deg(ϕ) + 1, (a1 , Xn ) |= ϕ. On the other hand, there exists
a literal formula q such that it is true in M2 but is false in M3 . Let us deﬁne
qk = 〈qk−1 〉q. Then, Xn |qn−1 = X1 . Thus, a1 , M4 |qn−1 |= ¬ϕ.
¤3

Iterative updatability

By the logic introduced in the previous section, we deﬁne the iterative updatability and present useful properties as well as an economic example.
3.1

Deﬁnition

We consider the condition under which players maintain the given tentativedecision. Note that even if the player’s criterion to maintain the tentative decision
is satisﬁed at ﬁrst, the announcement of this fact may bring about a failure of thecriterion and the change of the tentative decision. Thus, additional conditions
are required for the tentative decision to be maintained subsequently.
To see that, consider a situation with two-players where each of them choosesa tentative decision. Let ϕi denote a condition for player i (for i ∈ {1, 2}) to
maintain his tentative decision. The tentative decision may be changed even if ϕiis true for all i at ﬁrst. Suppose that a player, i, observes that the other player,j (for j ̸= i), does not change his tentative decision, namely ϕj . Then, even if
each player does not change his tentative decision at ﬁrst, the observation canchange his information and turn ϕi into a false statement. In terms of our logic,〈ϕj 〉ϕi may be false while ϕj and ϕi are both true. Further, in turn, observing
that i does not change the tentative decision regardless of his observation on j,j might change his tentative decision. That is, 〈ϕj 〉〈ϕi 〉ϕj might be false even
if 〈ϕj 〉ϕi . Similarly, for the tentative decision to be maintained, we also require〈ϕj 〉〈ϕi 〉〈ϕj 〉ϕi , 〈ϕj 〉〈ϕi 〉〈ϕj 〉〈ϕi 〉ϕj , and so on. In summary, for a tentative decision to be unchanged, it is necessary to take such an iterated information updateprocess into consideration. More formally, a tentative decision is stable only if〈ϕi 〉ϕj , 〈ϕj 〉〈ϕi 〉ϕj , 〈ϕi 〉〈ϕj 〉ϕi and similar propositions are all true.
Let us formalize the robustness against information updates, iterative updatability. We mean by C a set of formulas such that each formula, ϕ in C, represents
a given suﬃcient condition for a player to change his tentative decision. Let C −be a set of negations of C: C − = {¬ϕ : ϕ ∈ C}. Then we can formulate our target
condition by C − :Deﬁnition 2 (Iterative Updatability). We say that a set of formulas C −is iteratively updatable in a state of a Kripke model (w, M ) if, for all ﬁnite
sequences of formulas, ψ1 , ψ2 , . . . , ψk ∈ C − ,(w, M ) |= 〈ψ1 〉〈ψ2 〉 . . . 〈ψk−1 〉ψk .
Note that Benthem [2] originally focused on the case when |C| = 1.
If C − is iteratively updatable, then each statement is true and any iterated
announcement maintains the statements’ truth values as true. Then, the condition to discuss is the iterative updatability of C − . We shall discuss properties of
the iterative updatability in the following subsection.
3.2

Basic properties

In this subsection, we show that if C consists of information-monotonic statements, the iterative updatability of C − has useful properties.
First property is related to the order of announced statements. For iterative
updatability, it does not suﬃce to consider only the case when speciﬁc statements
are announced in ﬁxed turns, even if they are iteratively announced. On the other
hand, in the case of C ⊆ M, we can prove the following theorem.
Theorem 2 (Single Sequence Property). Suppose that C is a subset of M.
Then, C − is iteratively updatable if and only if there exists a sequence ψ1 , ψ2 , . . .
in C − such that (1) every ϕ ∈ C − appears in the sequence inﬁnite times and (2)〈ψ1 〉〈ψ2 〉 . . . 〈ψk−1 〉ψk is true for all k = 1, 2, . . . .

Proof. Let ϕ1 , ϕ2 , . . . , ϕk be any ﬁnite sequence in C − . Deﬁne Fk by F1 = ψ1 and
Fk = 〈Fk−1 〉ψk . Let ψl1 , ψl2 , . . . , ψlk be a subsequence of ψ1 , ψ2 , . . . such that
ψl1 = ϕ1 , ψl2 = ϕ2 , . . . , ψlk = ϕk . From monotonicity of ¬ϕ1 , we have ⊢ Fl1 ⇒ϕ1 . Thus, by P1, ⊢ Fl2−1 ⇒ ϕ1 . From the monotonicity, ⊢ 〈Fl2−1 〉ψl2 ⇒ 〈ϕ1 〉ϕ2 .
Through repetition, we have ⊢ Flk ⇒ 〈ϕ1 〉〈ϕ2 〉 . . . 〈ϕk−1 〉ϕk .
¤The second property we address is related to logical implication and iterative
updatability. Consider the two sets of criteria for players to change their tentativedecision, C and C ′ . The iterative updatability of C does not imply that of C ′ even
if C consists of stronger conditions than those of C ′ . On the other hand, if they
are information-monotonic then logical implication is preserved.
Theorem 3 (Comparison Theorem). Let ψ1 , ψ2 . . . and ϕ1 , ϕ2 , . . . be twosequences of formulas such that for all i = 1, 2, . . . , n, ⊢ ψi ⇒ ϕi . Assume that
one of {¬ϕi , ¬ψi } is in M for all i = 1, 2, . . . , n,. Then,⊢ 〈ψ1 〉〈ψ2 〉 . . . 〈ψn−1 〉ψn ⇒ 〈ϕ1 〉〈ϕ2 〉 . . . 〈ϕn−1 〉ϕn .
Proof. The theorem trivially holds for n = 1. Let Fn and Gn be inductively
deﬁned by F1 = ψ1 , G1 = ϕ1 , Fk = 〈Fk−1 〉ψk , and Gk = 〈Gk−1 〉ϕk for k > 1.
Suppose that ⊢ Fk−1 ⇒ Gk−1 . Consider the case when ¬ψk ∈ M. From themonotonicity, ⊢ 〈Fk−1 〉ψk ⇒ 〈Gk−1 〉ψk . Since ⊢ ψk ⇒ ϕk , we have ⊢ 〈Gk−1 〉ψk ⇒〈Gk−1 〉ϕk . Then, ⊢ 〈Fk−1 〉ψk ⇒ 〈Gk−1 〉ϕk . For the case of ¬ϕk ∈ M, we can also
prove it by a similar discussion.
¤
Since the monotonicity of only one of two formulas is assumed, this theorem
is applicable to analyzing the case when the target condition is a non-monotonic
statement. It might be unclear how the truth value of the target statement ischanged by information updates, and thus, we sometimes focus on the suﬃcientor necessary condition, which is logically clearer than the target condition. If
the necessary or suﬃcient condition is information-monotonic, then iterative
updatability preserves both suﬃciency and necessity. Note that all the theorems
presented here still hold for any extended axiomatic system.
3.3

An exchange economy

To illustrate our concept and results above, we present an exchange market
model with two buyers B1, B2, and one seller S. Each buyer has money, and theseller has one indivisible good, which might be of high quality or low quality.
The seller’s utility depends only on the money he has. When a buyer knows thequality of the good, he evaluates a high-quality good at $8 and a low-quality goodat $4.3 On the other hand, if he does not know the quality, then he evaluates
the good at $6.
3

This preference is represented by the utility function u(xh , xl , −p) =4 min {2, 2xh + xl } − p, where xh is the quantity of a high-quality good, xl is that ofa low-quality good, and p is the payment.

We consider a two-state model such that W = {h, l} and Ri for i ∈ {S, B1, B2},
deﬁned by– for B1
: hRB1 h, hRB1 l, lRB1 l, lRB1 h,– for S and B2 : hRS h, lRS l, hRB2 h, lRB2 l.
In state h, the good is of high quality, while in state l, it is of low quality. Then,
B2 and S know the quality of the good, while B1 does not know it at ﬁrst.
Let us consider the case when the players are going to do the following
transactions denoted by
T0: S sells to B1; B1 pays $5 to S.
On the other hand, we assume that alternative transactions are possible for eachpair if it can be done by themselves. Especially, the pair of B2 and S can choose
an alternative transaction, denoted by
T1: S sells to B2; B2 pays $6 to S.
Further, each individual can decide not to participate in any transaction.
In each state, T0 is not acceptable to players in the sense that some player
eventually deviates from T0. In state h, B2 and S can increase their payoﬀs from(0, 5) to (2, 6) by changing the tentative decision to T1, and thus, they should
do so. On the other hand, in state l, no player attempts to change the tentativedecision at ﬁrst. By observing that either B2 or S has not changed his tentativedecision, however, B1 deduces that the quality of the good is low. Then, his
evaluation of the good is changed to $4. Paying $5 is no longer proﬁtable forhim, and thus, he attempts to interrupt T0 and does not participate in any othertransaction.
Iterative updatability we introduced is a formalization of the acceptability inthis situation. Let C = {¬qi : i = B1, B2, s}, where qi denotes that ‘i maintains
the tentative decision, namely, agreeing to T0’. Further, let ϕ be the statementthat T1 increases the utilities of B2 and S from T0, and let ψ indicate thatinterrupting T0 increases the utility of B1. We can assume that ⊢ qj ⇒ ¬Kj ϕ
for j = B2, S, and that ⊢ qB1 ⇒ ¬KB1 ψ. Then, in our semantics, C − is notiteratively updatable. To see this, ﬁrst note that 〈¬KB2 ϕ〉¬KB1 ψ is false in any
state. Further, KB2 ϕ and KB1 ψ are all monotonic, and thus, by the Comparison
Theorem, 〈qB2 〉qB1 is also false.

4

Iterated elimination of strategies

In this section, as an application of our results in the previous section, we examine
iterated elimination (IE) of disadvantageous strategies in our framework.
4.1

Deﬁnition∏
Let X i be a ﬁnite strategy set of i ∈ N . We abbreviate i∈S X i by X S for
all S ⊆ N . By xS we denote a typical element of X S for all S ⊆ N , and by

(xS , xN \S ) we denote an element in X N such that the projections into X S and
X N \S are xS and xN \S , respectively. Further, let ui : X N → ℜ be the utility
function of i ∈ N .
We introduce three base criteria for elimination of disadvantageous strategies. A strategy xi ∈ X i is strictly dominated iﬀ ∃y i ∈ X i ∀xN \{i} ∈ X N \{i} :ui (y i , xN \{i} ) > ui (xi , xN \{i} ). It is weakly dominated iﬀ ∃y i ∈ X i ∀xN \{i} ∈X N \{i} : ui (y i , xN \{i} ) ≥ ui (xi , xN \{i} ) with at least one strict inequality. Moreover, it is a never best response iﬀ ∀xN \{i} ∈ X N \{i} ∃y i ∈ X i : ui (y i , xN \{i} ) >ui (xi , xN \{i} ). The survivors of iterated elimination (SIE), X ∗N , is deﬁned by
the following algorithm for any of the base criteria for elimination:
begin for all i ∈ N , X ∗i := X i ;while there exist j ∈ N and xj ∈ X ∗j thatmeets the base criterion for elimination in the reduced game,the strategy set of which is restricted to X ∗N
begin for such j and xj do X ∗j := X ∗j \ {xj } end
end
The SIE of strictly or weakly dominated strategies can be traced back toGale, et al.[6], Gale [7], and Luce and Raiﬀa [13]. Bernheim [3] and Pearce [14]independently discussed IE of never best response strategies4 .
4.2

Epistemic characterization

These strategies have been characterized by static epistemic models. First, Pearce[14] characterized SIE of never best response as those chosen in a situation inwhich it is common knowledge that each player maximizes his utility with respect
to his prior belief about other players’ strategy choices as well as the structure of
the game. Tan and Werlang [17] reﬁned this conjecture and gave a formal proof
in a Bayesian framework. Samuelson [16] considered a situation in which every
player chooses a subset of strategies as admissible ones. He pointed out that it
is impossible to characterize the set of SIE of weakly dominated strategies as
those chosen in a situation in which it is common knowledge that each player’s
admissible strategies are weakly non-dominated strategies with respect to his
belief.
Benthem [2] initiated an approach by public announcement logic to theseconcepts. Let xN ∈ X N be a given status quo in which each player j chooses
xj as a tentative decision. For all y i ∈ X i , let f (y i ) denote the statement ‘forall xN ∈ X N , ui (y i , xN \{i} ) > uj (xi , xN \{i} ) if xN is the tentative decision’.
Further, we denote by g(y i ) the statement ‘for all xN ∈ X N , ui (y i , xN \{i} ) >uj (xi , xN \{i} ) if xN is the tentative decision’. Here, we do not assume any change
in the utility function. Thus, both f (y i ) and g(y i ) are information invariant.
Let us consider three classes of criteria for a player to change their tentativedecision:4

If correlated strategies are taken into consideration, SIE of never nest response isequivalent to SIE of strictly dominated strategies

C1 = {Ki f (y i ) : i ∈ N, y i ∈ X i }.
C2 = {Ki (∨yi f (y i )) : i ∈ N, y i ∈ X i }.
C3 = {Ki (f (y i ) ∨ g(y i )) ∧ ¬Ki ¬f (y i )) : i ∈ N, y i ∈ X i }.
Each of them represents condition which a player adopts as a criterion for him
to change his tentative decision. A typical sentence, Ki f (y i ), in C1 implies that iknows a speciﬁc alternative plan to increase his payoﬀ, while a typical sentence,
Ki (∨yi f (y i )), in C2 says that he merely knows of the existence of such a plan.
Obviously, the conditions in C1 are stronger than those in C2 . A formula in C3means that i knows a speciﬁc alternative plan that does not decrease his payoﬀ(i.e., Ki (f (y i ) ∨ g(y i ))), and that it is possible that it will increase his payoﬀ(i.e., ¬Ki ¬f (y i )).
Benthem [2] considered iterative updatability of the conjunction of Ci− (i =1, 2), ∧ϕ∈Ci (¬ϕ). He focused on a Kripke-model, in which any state is identiﬁed by a strategy proﬁle chosen by the players, and every player knows only
his own strategy. Then, he demonstrated the equivalence between the eliminatedstrategies and the states of the Kripke-model eliminated by information updates.
According to his observation, the elimination of states involved by the announcement of a sentence in C1 (resp. C2 ) is equivalent to elimination of strictly (resp.
weakly) dominated strategies. Similarly, we can easily show that the counterpartof C3 is weak domination.
Note that the dynamic information update process is applicable to any given
epistemic state. Thus, the dynamic reformulation provides a solution concept for
epistemically diverse situations, rather than an artiﬁcial situation to characterize
existent solution concepts that Benthem [2] discussed.
4.3

Properties

Our ﬁrst contribution here is to clarify the order independence of the elimination
process from a dynamic viewpoint, which Benthem [2] did not address. It is wellknown that the set of SIE of strictly dominated strategies as well as the neverbest response strategies is uniquely determined while the algorithm above is
non-deterministic. On the other hand, SIE of weakly dominated strategies isnot. Gilboa, et al.[9] stated suﬃcient conditions for the order independence in
non-epistemic terms.
According to Theorem 2, the order of information update does not matterat all, since all the sentences in C1 or C2 are information-monotonic. On theother hand, any sentence in C3 is information-monotonic, and thus, the set of
SIE of weakly dominated strategies is order dependent. In summary, the wellknown properties of order independence and dependence can be ascribed to
information-monotonicity.
Second contribution is to clarify the role of information-monotonicity in comparison of the conditions generated by C1 , C2 , and C3 . Obviously, C1 is stronger
than C2 in the sense that Ki f (y i ) ⇒ Ki (∨yi f (y i )). It is, however, not trivial thatthe iterative updatability of C1− implies that of C2− . Benthem [2] demonstrated
this relation by a ﬁxed-point method on Kripke-models. On the other hand, it isalso a direct consequence of Comparison Theorem in the previous section since
all sentence in C1− are monotonic. Further from Comparison theorem we obtainthe same relation between C1− implies that of C3− .
Third contribution is related to Nash equilibrium and the iterative updatability of Ci− . Consider the formula q ∗ = ∨i∈N (∨yi f i (y i )), which translates to‘the tentative decision is not a Nash equilibrium’. We focus on a sentence,E = ¬(K1 q ∗ ∨ K2 q ∗ ∨ · · · ∨ Kn q ∗ ), which can be translated into the following:‘No one knows that the tentative decision is not a Nash equilibrium’.
First, if E is true then it is iteratively updatable. Formally, we obtain the following lemma.
Lemma 1 (Idenpotency Lemma). Assuming that q ∗ ∈ Q∗ , if E = ¬(K1 q ∗ ∨K2 q ∗ ∨ · · · ∨ Kn q ∗ ), then ⊢ E ↔ 〈E〉E.
Proof. ⊢ 〈E〉E ⇒ E is trivial. We show that ⊢ E ⇒ 〈E〉E. It suﬃces to show that⊢ E ⇒ 〈E〉¬Ki q ∗ for all k.
From invariance of q ∗ , ⊢ 〈E〉q ∗ ↔ E ∧ q ∗ . Further, ⊢ E ⇒ q ∗ and, thus,⊢ (¬E ⇒ 〈E〉q ∗ ) ⇒ q ∗ . By A2 and R2 we have that
⊢ ¬Ki q ∗ ⇒ ¬Ki (¬E ⇒ 〈E〉q ∗ ). Then ⊢ E ⇒ ¬Ki (¬E ⇒ 〈E〉q ∗ ) since⊢ E ⇒ ¬Ki q ∗ . Further, ⊢ 〈E〉¬Ki q ∗ ↔ E ∧ ¬Ki (¬E ⇒ 〈E〉q ∗ ) by P2. It follows
that ⊢ E ⇒ 〈E〉¬Ki q ∗ .
¤Further, E means the iterative updatability of Ck− (k = 1, 2). That is, if none
knows that the tentative decision is not a Nash equilibrium, then every player
who changes the tentative decision only if he knows that the deviation to anotherstrategy increases his payoﬀ does not do so regardless of iterative information
updates.
Theorem 4. Let q ∈ Q∗ and E := ¬(K1 q ∗ ∨ K2 q ∗ ∨ · · · ∨ Kn q ∗ ). Assume thatfor all k = 1, 2, . . . , n, there exists some i ∈ N such that ⊢ ¬ϕk ⇒ Ki q. Then,⊢ E ⇒ 〈ϕ1 〉〈ϕ2 〉 . . . 〈ϕm−1 〉ϕm .
Proof. ¬E is in M, and ⊢ E ⇒ ϕl for all l. Deﬁne Fk and Gk by F1 = E;
Fk = 〈Fk−1 〉E; G1 = ϕ1 ; Gk = 〈Gk−1 〉ϕk . Then by Theorem 3, ⊢ Fk ⇒ Gk .
Further, by the previous lemma, we have ⊢ E ↔ 〈E〉E, and thus, ⊢ E ⇒ Fk .
Therefore, ⊢ E ⇒ Gk .
¤In sum, the notion, ‘none knows that the tentative decision is not Nashequilibrium’, is, in our view, a noteworthy concept for analyzing epistemicallydiverse situations.
4.4

Information-variant utilities

Our results in the previous subsection depend on the assumption that the players’
utility functions are invariant. To see this, consider a two-person game modelwith two states, a and b, and a variant utility function. An accessible relation
R1 is deﬁned by xR1 y for all x, y ∈ {a, b}, while R2 is deﬁned by xR2 x for allx ∈ {a, b}. Player 1 has two possible strategies, T and B, while player 2 has L
and R.
The utilities are represented in four tables below. They depend on the pair ofstrategies, the state of Kripke-model, and the set of remained states. The upper
two tables represent the utilities when there remains only one state while thelower two represent those when the all states remain. In each square, the lower
left value represents the utility of player 1, and the upper right value represents
that of player 2.

2
L
1

T
2

1

0
0

0

B

1

T
2

1

L

2

1
B

0
1

L
0

0
0

2

10
2
state b in {b}

R
1

R

0

B

0
2
state a in {a}

T

2
L
1

R

1

5
2
state a in {a, b}

R
1

T
2

1
B

2
0

0

1

5
2
state b in {a, b}

All tables diﬀer from each other in the utility of player 1 when (B, L) is
chosen. Then, player 1 enjoys 0 if the state is a and he knows it, while he enjoys
10 if the state is b and he know it. When he does not know which of a and b is
the true state he evaluates his utility as 5, which is a result from the expectation
with probability 1/2 for each state.
Suppose that x = (T, L) is the tentative decision in any state. Let ϕ denotethe statement ‘u2 (T, R) > u2 (x)’, and let ψ denote ‘u1 (B, L) > u1 (x)’. Then,
K2 ϕ, K1 ψ ∈ C. Note that in this case K1 ψ is not information-monotonic.
(L, T ) is not maintained because in any state on {a, b}, K1 ψ is true. In
state a, however, both ¬K1 ψ and ¬K2 ϕ become true after ¬K2 ϕ is publicly
announced. That is, 〈¬K2 ϕ〉〈¬K1 ψ〉 . . . is true. According to the theorems in
the previous section, this phenomenon would not be observable if ψ and ϕ were
information-monotonic.

5

Conclusion

We have discussed the epistemic conditions for the stability of strategies in asituation in which each player chooses a tentative decision under iterative public announcements about the other players’ choices. To analyze these conditions, we extended Plaza’s public announcement logic by adding the notionsof information-invariance and information-monotonicity. By means of these notions, we clariﬁed the conditions for robustness with respect to the order of
information update, that was not investigated in [2].
Our analysis has room for improvement. The applications presented in thispaper are still simple. Moreover, we focused on the case in which any information update is done through public announcement. That is, we did not consider
various types of update process as is discussed in [4]. Our simple logic, however, might open up new approaches to related research issues such as syntactic
analysis.
Acknowledgement
We thank Thomas Ågotnes, Nobu-Yuki Suzuki, and Mamoru Kaneko for theiruseful comments on this work.

References
1. J. van Behthem, J. van Eijck, and B. Kooi. Logics of Communication and Change.
to appear in Information and Computation.
2. J. van Benthem. Rational Dynamics and Epistemic Logic in Games. International
Game Theory Review, vol.9, pp.13-45, 2007.
3. D. Bernheim. Rationalizable Strategic Behavior. Econometrica, vol.52, pp.10071028, 1984.
4. H.P. van der Ditmarsch, W. van der Hoek, and W. B. Kooi. Dynamic Epistemic
Logic, Springer, 2007.
5. R. Fagin, J. Halpern, Y. Moses, and M. Vardi. Reasoning About Knowledge. MITpress, 1995.
6. D. Gale, H.W. Kuhn, and A.W. Tucker. Reduction of game matrices, Lectures on
the Theory of Games, Annals of Mathematics Studies, No. 37, edited by H.W.
Kuhn and A.W. Tucker, Princeton university press, Princeton, 89–96, 1950.
7. D. Gale. A theory of n-person game with perfect information. Proceedings of the
National Academy of Sciences of the United States of America, vol 39, Issue 6, pp.
496-501, 1953.
8. J. Gerbrandy. Dynamic epistemic logic. Logic, Language and Computation, vol.2,
pages 67-84, 1999.
9. I. Gilboa, E.Kalai, and E. Zemel. On the order of eliminating dominated strategies
Operations Research Letters 9, vol 9, pp.85-89, 1990.
10. J.C. Harsanyi. Games with Incomplete Information Played by Bayesian Players:
Part II Bayesian Equilibrium Points, Management Science, vol.14, pp. 320-334,
1968.
11. J. Hintikka. Knowledge and Belief, Cornell University Press, 1962.

12. G. E. Hughes and M. J. Creswell. A New Introduction to Modal Logic, Routledge,
1996.
13. R.D. Luce and H. Raiﬀa. Games and Decisions: Introduction and Critical Survey
Wiley: New York, 1957.
14. D. Pearce. Rationalizable Strategic Behavior and the Problem of Perfection. Econometrica, vol.52, pp.1029-1050, 1984.
15. J. Plaza. Logic of Public Communications. 4th Int’l Symposium on Methodologies
for Intelligent Systems, pp.201-216, 1989. (reprinted version is in Synthese, vol.158,
pp.165-179, 2007.)
16. L. Samuelson. Dominated strategies and common knowledge, Games and Economic
Behavior, vol. 4(2), pp.284-313,1992.
17. T.C. Tan, and S.R. Werlang. The Bayesian foundations of solution concepts ofgames, Journal of Economic Theory, vol.45(2), pp. 370-391, 1988.