Emiliano Lorini
email: emiliano.lorini@irit.fr

On the Epistemic Foundation for Iterated Weak Dominance: An Analysis in a Logic of Individual and Collective attitudes

Keywords: Epistemic logic, Epistemic game theory, Belief revision, Iterated weak dominance

This paper proposes a logical framework for representing static and dynamic properties of different kinds of individual and collective attitudes. A complete axiomatization as well as a decidability result for the logic are given. The logic is applied to game theory by providing a formal analysis of the epistemic conditions of iterated deletion of weakly dominated strategies (IDWDS), or iterated weak dominance for short. The main difference between the analysis of the epistemic conditions of iterated weak dominance given in this paper and other analysis is that we use a semi-qualitative approach to uncertainty based on the notion of plausibility first introduced by Spohn, whereas other analysis are based on a quantitative representation of uncertainty in terms of probabilities.

Introduction

The fundamental concept of game theory is the concept of solution which is, at the same time, a prescriptive notion, in the sense that it prescribes how rational agents in a given interaction should play, and a predictive one, in the sense that it allows us to predict how the agents will play. There exist many different solution concepts both for games in normal form and for games in extensive form (e.g., Nash Equilibrium, iterated deletion of strongly dominated strategies, iterated deletion of weakly dominated strategies, correlated equilibrium, backward induction, forward induction, etc.) and new ones have been proposed in the recent years (see, e.g., [START_REF] Halpern | Beyond nash equilibrium: solution concepts for the 21st century[END_REF]). A major issue we face when we want to use some solution concept in order either to predict human behavior or to build some practical applications (e.g., for computer security or for multi-agent systems) is to evaluate its significance. Some of the questions that arise in these situations are, for instance: given certain assumptions about the agents such as the assumption that they are rational (e.g., utility maximizers), under which conditions will the agents converge to equilibrium? Are these conditions realistic? Are they too strong for the domain of application under consideration? There is a branch of game theory, called epistemic game theory, which can help to answer these questions (see [START_REF] Perea | Epistemic game theory: reasoning and choice[END_REF] for a general introduction to the research in this area). Indeed, the aim of epistemic game theory is to provide an analysis of the necessary and/or sufficient epistemic conditions of the different solution concepts, that is, the assumptions about the epistemic states of the players that are necessary and/or sufficient to ensure that they will play according to the prescription of the solution concept. Typical epistemic conditions which have been considered are, for example, the assumption that players have common belief (or common knowledge) about the rationality of every player, 1the assumption that every player knows the choices of the others, 2 or the assumption that players are logically omniscient. 3The aim of this paper is to propose a new logic, called PDL-A (Propositional Dynamic Logic of individual and collective Attitudes), in which the epistemic conditions of different solution concepts for normal form games can be formally specified. Our logic PDL-A is a combination of van Benthem et al.'s variant of Propositional Dynamic Logic PDL which gives an epistemic interpretation to programs [START_REF] Van Benthem | Logics of communication and change[END_REF] with Spohn's theories of uncertainty and belief change [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF]. The interesting aspect of this logic is that it allows us to describe both the static and the dynamic properties of different kinds of individual and collective epistemic attitudes such as knowledge, belief, graded belief, robust belief and common belief which provide the epistemic foundations of different solution concepts in game theory.

In this work we mainly concentrate on the logical characterization in PDL-A of the epistemic conditions of iterated deletion of weakly dominated strategies (IDWDS) (also called 'iterated weak dominance' or 'iterated admissibility').

Iterated weak dominance is an important solution concept in game theory which is distinguished from iterated strong dominance. Although there have been some works in economics investigating the epistemic conditions of iterated weak dominance, they are far less studied and understood than the epistemic conditions of iterated strong dominance. The fundamental difference between the analysis of iterated weak dominance given in this paper and other analysis is that we use a semi-qualitative approach to uncertainty based on the notion of plausibility introduced by Spohn [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF], whereas existing analysis of the epistemic conditions of iterated weak dominance are based on a quantitative representation of uncertainty in terms of probabilities (see, e.g., [START_REF] Brandeburger | The power of paradox: some recent developments in interactive epistemology[END_REF][START_REF] Brandenburger | Admissibility in games[END_REF][START_REF] Halpern | A logical characterization of iterated admissibility[END_REF][START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF]). Spohn's theory of uncertainty and belief change, generally referred to as 'κ calculus', has been largely used in Artificial Intelligence (AI) (Goldszmidt & Pearl [28] refer to it as 'rank-based system' and 'qualitative probabilities'). It provides an elegant and relatively simple approach designed to reason about both the static aspects and the dynamic aspects of epistemic attitudes. Our approach is semiqualititative in the sense that we assume that beliefs of agents are ranked by a finite number of non-negative integers providing a qualitative scale for degrees of belief. Specifically, each integer corresponds to a linguistic quantifier such as I weakly believe that ϕ,Imildly believe that ϕ,Istrongly believe that ϕ,e t c .H o w e v e r ,o u r approach is not purely qualitative because it allows us to say how much a given agent believes that a certain proposition ϕ is true. The distinction between purely quantitative, semi-qualitative and purely qualitative approaches to uncertainty has been widely discussed in the AI literature (see, e.g., [START_REF] Pearl | From conditional oughts to qualitative decision theory[END_REF][START_REF] Weydert | General belief measures[END_REF]). While in purely quantitative approaches belief states are characterized by classical probabilistic measures or by alternative numerical accounts, such as lexicographic probabilities [START_REF] Blume | Lexicographic probabilities and choice under uncertainty[END_REF][START_REF] Brandeburger | The power of paradox: some recent developments in interactive epistemology[END_REF][START_REF] Brandenburger | Admissibility in games[END_REF]or conditional probabilities [START_REF] Battigalli | Strong belief and forward induction reasoning[END_REF], in semi-qualitative approaches, such as Spohn's theory, belief states are described by rough qualitative measures assigning orders of magnitude. Finally, purely qualitative approaches do not use any numerical representation of uncertainty but simply a plausibility ordering on possible worlds structures inducing an epistemic-entrenchment-like ordering on propositions. Purely qualitative approaches have been used both in the area of belief revision and in the area of logics of belief change (see, e.g., [START_REF] Baltag | A qualitative theory of dynamic interactive belief revision[END_REF][START_REF] Gärdenfors | Revisions of knowledge systems using epistemic entrenchment[END_REF][START_REF] Van Benthem | Dynamic logic for belief revision[END_REF]).

The rest of the paper is organized as follows. Section 2 provides an informal introduction to the concept of iterated weak dominance and to the epistemic conditions of this solution concept. Section 3 presents the syntax and the semantics of the logic PDL-A. Section 4 is devoted to the formalization in PDL-A of the previous different kinds of individual and collective attitudes, which are fundamental building blocks for the analysis of the epistemic conditions of iterated weak dominance. In Section 5 a complete axiomatization as well as a decidability result for PDL-A are given. In Section 6 the logic PDL-A is extended with constructions to describe information about agents' choices and is used to provide an analysis of the epistemic conditions of iterated weak dominance. Related works on the analysis of the epistemic conditions of iterated weak dominance are discussed in Section 7.

Epistemic Conditions of Iterated Weak Dominance: Some Intuitions

Given a game in normal form Ŵ and a player i in this game, a strategy a of player i is a weakly dominated strategy if and only if there is another strategy b of player i such that: [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF] no matter what strategies the other players will choose, playing b is for i at least as good as playing a and (2) there exists at least one strategy profile of the other players such that, if the others play this strategy then playing b is for player i better than playing a. The so-called iterated weak dominance is a procedure that starts with a given game in normal form and, at each step, for every player in the game removes all his weakly dominated strategies, thereby generating a subgame of the original game, and that repeats this process again and again. The strategy profiles that survive Consider the game in Fig. 1 with two players Row and Column (the payoff on the left-hand side being the payoff of Row and the payoff on the right-hand side being the payoff of Column). In the initial game the strategy B of Row is weakly dominated by the strategy A and is deleted from the game. In the resulting game the strategy β of Column is weakly dominated by the strategy α and is also deleted from the game. Therefore, the solution of the game is the strategy profile (A,α).

There are at least two requirements that should be met in order to be able to predict that the players will act according to the prediction of iterated weak dominance. Let us illustrate them with the aid of the example in Fig. 1. Assume that both Row and Column are rational players (i.e., they are utility maximizers) and that they have a common belief about this.

If we assume that Row is rational then his only reason for discarding strategy B and for deciding not to play it is that he envisages the possibility that Column will play β (even though playing β clashes with the hypothesis that Column is rational and that she believes that Row is rational, as we assumed common belief in rationality, and hence that Row will not play B). Thus, the first requirement is that the beliefs of Row and, more generally, the beliefs of every player in the game must be cautious, in the sense that every player must envisage all possible choices of the other players (see, e.g., [START_REF] Mas-Colell | Microeconomic theory[END_REF]Chapter 8] and also [START_REF] Asheim | Admissibility and common belief[END_REF][START_REF] Asheim | Proper rationalizability in lexicographic beliefs[END_REF][START_REF] Börgers | Weak dominance and approximate common knowledge[END_REF][START_REF] Börgers | Cautious utility maximization and iterated weak dominance[END_REF][START_REF] Brandenburger | Lexicographic probabilities and iterated admissibility[END_REF][START_REF] Samuelson | Dominated strategies and common knowledge[END_REF] for further discussion about this requirement).

Moreover, if we assume that Column is rational then her reason for discarding strategy β is that she considers the situation in which Row plays the admissible (i.e., non-weakly dominated) strategy A strictly more plausible than the situation in which Row plays the inadmissible strategy B. More generally, in order to guarantee that the players in a game will act according to the prescription of the solution concept, each of them should believe that the situations in which the other players play an admissible strategy are strictly more plausible than the situations in which they play an inadmissible one. If we assume that a certain strategy of a player is incompatible with the player's rationality if and only if it is inadmissible, the previous observation leads to the following second requirement: every player in a game must have a robust belief about the rationality of the other players, in the sense that he will continue to believe that the others will play rationally as long as he does not learn something which is incompatible with this fact. This concept of 'robust belief' is one of the key elements of Stalnaker's analysis of the epistemic conditions of iterated weak dominance [START_REF] Stalnaker | Knowledge, belief and counterfactual reasoning in games[END_REF][START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF]. 4The previous two requirements will be formally specified in Section 6,i nw h i c h a logical analysis of the epistemic conditions of iterated weak dominance will be provided. But before moving to game theory we present in the next section the logic PDL-A.

Logical Framework

This section presents the syntax and the semantics of the logic PDL-A. Technically, this logic is an extension of the logic E-PDL (Epistemic Propositional Dynamic Logic) proposed by van Benthem et al. [START_REF] Van Benthem | Logics of communication and change[END_REF] with special constructions for representing plausibility orderings over possible worlds and with dynamic operators for representing the effects of an operation of belief conditioning in the sense of Spohn. Generally speaking, PDL-A can be seen as a combination of E-PDL with Spohn's rank-based system.

Syntax

Assume a countable set of atomic propositions describing facts Prop ={p, q,...},a finite set of agents Agt ={i, j,...} and a set of natural numbers Num ={0,...,max}, with max ∈ N \{ 0}. For example, suppose Num ={ 0, 1, 2, 3, 4, 5}. Num can be interpreted as a qualitative scale where 0 means 'null', 1 means 'very low', 2 means 'low', 3 means 'medium', 4 means 'high' and 5 means 'very high'. 5 For the sake of simplicity we assume that Num is finite. This assumption is crucial to be able to provide a complete axiomatization of the logic PDL-A (see Section 5). A generalization of our results to the case where Num is infinite is postponed to future work.

2 Agt * = 2 Agt \∅is the set of all non-empty sets of agents (alias coalitions). Elements of 2 Agt * are denoted by symbols J, H,... For notational convenience, the coalition Agt \{i} is denoted by -i.

The language of PDL-A is defined by the following grammar in Backus-Naur Form (BNF):

π ::= i | π 1 ; π 2 | π 1 ∪ π 2 | π * |?ϕ ϕ, ψ ::= p | exc i,h |¬ϕ | ϕ ∧ ψ |[π ]ϕ |[ * α i ϕ]ψ
where p ranges over Prop, h ranges over Num, i ranges over Agt and α ranges over Num \{0}. The other Boolean constructions ⊤, ⊥, ∨, → and ↔ are defined from p, ¬ and ∧ in the standard way. We define Obj to be the set of all Boolean combinations of atomic propositions in Prop and we call the elements of Obj ontic (or objective) facts in order to distinguish them from 'epistemic facts' about agents' mental states.

Knowledge constructs (or programs) π correspond to the basic constructions of Propositional Dynamic Logic (PDL) [START_REF] Harel | Dynamic logic[END_REF]: sequential composition (;), nondeterministic choice (∪), iteration ( * ) and test (?). A given knowledge program π corresponds to a specific configuration of the agents' epistemic states.

The formula [π ]ϕ has to be read "ϕ is true, according to the knowledge program π ". For the atomic case, the operator [i] represents the standard S5-notion, partitionbased and fully introspective notion of knowledge that is commonly used both in computer science [START_REF] Fagin | Reasoning about knowledge[END_REF] and economics [START_REF] Aumann | Interactive epistemology, I. knowledge[END_REF].

[i]ϕ has to be read "ϕ is true according to what agent i knows" or more simply "agent i knows that ϕ is true", which just means that "ϕ is true in all worlds that agent i envisages". Sequential composition ; allows to represent an agent's knowledge over his knowledge and over other agents' knowledge. For instance, [i; j]ϕ means that "ϕ is true according to what agent i knows about agent j's knowledge". or more simply "agent i knows that agent j knows that ϕ is true". Non-deterministic choice ∪ allows to represent the notion of shared knowledge. For instance, [i ∪ j]ϕ means that "both agent i and agent j know that ϕ is true". By means of iteration * one can represent higher order knowledge of arbitrary depth. For instance, [(i; j) * ]ϕ means that "agent i knows that agent j knows ϕ is true, agent i knows that agent j knows that agent i knows that agent j knows ϕ is true, and so on, ad infinitum". The test operation ? has the usual meaning as in PDL: [?ϕ]ψ means that "if ϕ is true then ψ is true".

As we will show in Section 4.1, the operators [i] captures a form of 'absolutely unrevisable belief', that is, a form of belief which is stable under belief revision with any new evidence. A similar property for the notion of knowledge has been advanced by the so-called defeasibility (or stability) theory of knowledge [START_REF] Klein | A proposed definition of propositional knowledge[END_REF][START_REF] Rott | Stability, strength and sensitivity: converting belief into knowledge[END_REF][START_REF] Stalnaker | On logics of knowledge and belief[END_REF]. According to this theory, a given piece of information ϕ is part of an agent's knowledge only if the agent's justification to believe that ϕ is true is sufficiently strong that it is not capable of being defeated by evidence that the agent does not possess. As pointed out by [START_REF] Baltag | A qualitative theory of dynamic interactive belief revision[END_REF], two different interpretations of the term 'evidence' have been given in the context of this theory, each giving a different interpretation of what knowledge is. The first one [START_REF] Stalnaker | On logics of knowledge and belief[END_REF] defines knowledge as a form of belief which is stable under belief revision with 'any piece of true information', while the second one [START_REF] Rott | Stability, strength and sensitivity: converting belief into knowledge[END_REF] gives a stronger definition of knowledge as a form of belief which is stable under belief revision with 'any piece of information'. The concept formalized by the operators [i] captures the latter notion of knowledge in a stronger sense. In Section 4.1, we will introduce the notion of safe belief which corresponds to the former notion of knowledge.

The formula * α i ϕ ψ has to be read "after agent i has learnt that ϕ is true with a degree of firmness α, ψ will be true" (or "after agent i has revised his beliefs with ϕ and with a degree of firmness α, ψ will be true"). As we will show in Section 3.2, technically an epistemic event * α i ϕ amounts to an operation of beliefs' conditionalization in Spohn's sense [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF], where the parameter α measures the extent to which agent i will believe that ϕ is true after learning that ϕ is true. The epistemic event * α i ϕ is supposed to be public, i.e., if agent i learns that ϕ is true then all other agents know this. This assumption could be easily relaxed by using action models as introduced in [START_REF] Baltag | The logic of public announcements, common knowledge and private suspicions[END_REF][START_REF] Baltag | Logics for epistemic programs[END_REF], which would allow us to model private and semi-private epistemic events.

The language of PDL-A contains special atoms of the form exc i,h which are used to rank the worlds that agent i considers possible at a given world according to their plausibility degree for the agent. Starting from [START_REF] Grove | Two modellings for theory change[END_REF], ranking among possible worlds have been extensively used in belief revision theory. We here use the notion of plausibility first introduced by Spohn [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF]. Following Spohn's theory, the worlds that are assigned the smallest numbers are the most plausible, according to the beliefs of the individual. That is, the number h assigned to a given world rather captures the degree of exceptionality of this world, where the exceptionality degree of a world is nothing but the opposite of its plausibility degree (i.e., the exceptionality degree of a world decreases when its plausibility degree increases). Therefore, formula exc i,h can be read alternatively as "the current world has for agent i a degree of exceptionality equal to h" or "the current world has for agent i a degree of plausibility equal to maxh".

Before turning into semantics, we provide some abbreviations that will be used in the rest of the paper. We define i to be the dual of [i],thatis:

i ϕ def =¬ [ i]¬ϕ
Formula i ϕ means that "ϕ is compatible with agent i's knowledge".

Semantics

The semantics of the logic PDL-A is a possible world semantics with a special function for exceptionality. Definition 1 (Model) PDL-A models are tuples M = W, {E i : i ∈ Agt},κ,V where:

• W is a nonempty set of possible worlds or states;

• every E i is an equivalence relation between worlds in W; • κ : W × Agt -→ Num is a total function mapping worlds and agents to natural numbers in Num such that:

(Constr1)f o r e v e r y w ∈ W and for every i ∈ Agt,thereisv such that wE i v and κ(v, i) = 0;

• V : W -→ 2 Prop is a valuation function.
As usual, p ∈ V (w) means that proposition p is true at world w. The equivalence relations E i , which are used to interpret the epistemic operators [i], can be viewed as functions from W to 2 W . Therefore, we can write

E i (w) ={ v ∈ W : (w, v) ∈ E i }.
The set E i (w) is agent i's information set at world w: the set of worlds that agent i envisages at world w.AsE i is an equivalence relation, if (w, v) ∈ E i then agent i has the same information set at w and v (i.e., agent i has the same knowledge at w and v).

The function κ provides a plausibility grading of the possible worlds for each agent i and is used to interpret the atomic formulas exc i,h . κ(w, i) = h means that, according to agent i the world w has a degree of exceptionality h or, alternatively, according to agent i the world w has a degree of plausibility maxh. (Remember that the degree of plausibility of a world for an agent is the opposite of its exceptionality degree for the agent). The function κ allows to rank an agent's envisaged worlds according to their plausibility degree: among the worlds agent i envisages at world w (i.e., agent i's information set at w), there are worlds that i considers more plausible than others. For example, suppose that E i (w) ={ w, v, u}, κ(w, i) = 2, κ(u, i) = 1a n dκ(v, i) = 0. This means that at world w agent i envisages the three worlds w, v and u. Moreover, according to agent i, the world v is strictly more plausible than the world u and the world u is strictly more plausible than the world w (as max-0 > max-1 > max-2).

(Constr1)isanormality constraint for the plausibility grading which ensures that an agent can always envisage a world with a minimal degree of exceptionality 0. This constraint is important because it ensures that an agent's beliefs are consistent e.g., an agent cannot believe ϕ and ¬ϕ at the same time (see Section 4.1 for more details).

As in PDL, the accessibility relation for atomic knowledge programs is generalized to all kinds of knowledge programs. Given a PDL-A-model M = W, {E i : i ∈ Agt},κ,V we define:

E π 1 ;π 2 = E π 1 • E π 2 E π 1 ∪π 2 = E π 1 ∪ E π 2 E π * = (E π ) * E ?ϕ ={ (w, w) : w ∈||ϕ||} where ||ϕ|| = {w ∈ W : M, w |= ϕ}.
Definition 2 (Truth conditions)G i v e naPDL-A-model M, a world w and a formula ϕ, M, w |= ϕ means that ϕ is true at world w in M. The rules defining the truth conditions of formulas are:

• M, w |= piff p∈ V (w) • M, w |= exc i,h iff κ(w, i) = h • M, w |= ¬ ϕ iff not M, w |= ϕ • M, w |= ϕ ∧ ψ iff M, w |= ϕ and M, w |= ψ • M, w |= [ π ]ϕ iff M, v |= ϕ for all v such that (w, v) ∈ E π • M, w |= [ * α i ϕ]ψ iff M * α i ϕ , w |= ψ
where the updated model M * α i ϕ is defined according to the Definition 4 below.

The epistemic event * α i ϕ (i.e., agent i learns that ϕ is true) updates agent i's information set by modifying the exceptionality degree that i ascribes to his envisaged worlds. Before defining this model update, we follow [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF] and lift the exceptionality of a possible world to the exceptionality of a formula viewed as a set of worlds.

Definition 3 (Exceptionality degree of a formula)G i v e naPDL-A model

M = W, {E i : i ∈ Agt},κ,V ,l e t||ϕ|| w,i ={ v ∈ W : v ∈| | ϕ|| and (w, v) ∈ E i }
be the set of worlds that agent i envisages at w a n di nw h i c hϕ is true. The exceptionality degree of formula ϕ for agent i at world w, denoted by κ w,i (ϕ), is defined as follows:

κ w,i (ϕ) = min v∈||ϕ|| w,i κ(v, i) if ||ϕ|| w,i = ∅ max if ||ϕ|| w,i = ∅
The exceptionality degree of a formula ϕ captures the extent to which ϕ is considered to be exceptional by the agent. As expected, the plausibility degree of a formula ϕ is defined as maxκ w,i (ϕ). The plausibility degree of a formula ϕ captures the extent to which ϕ is considered to be plausible by the agent.

Definition 4 (Update)G i v e naPDL-A-model M = W, E,κ,V , M * α i ϕ
is the model such that for all w ∈ W and for all j ∈ Agt:

W * α i ϕ = W E * α i ϕ j = E j κ * α i ϕ (w, i) = ⎧ ⎨ ⎩ κ(w, i) -κ w,i (ϕ) if M, w |= ϕ Cut(α + κ(w, i) -κ w,i (¬ϕ)) if M, w |= ¬ ϕ ∧ i ϕ κ(w, i) if M, w |= [ i]¬ϕ κ * α i ϕ (w, j) = κ(w, j) if i = j V * α i ϕ = V
where

Cut(x) = xi f 0 ≤ x ≤ max max if x > max
The epistemic event * α i ϕ does not affect the objective world. This is the reason why the valuation function V is not altered by it (see the definition of V * α i ϕ ). Moreover, it modifies agent i's plausibility ordering but does not modify the plausibility orderings of the agents different from i (see the definition of κ * α i ϕ ). In particular, it induces a kind of belief conditioning in Spohn's sense [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF]. Agent i's plausibility ranking over his envisaged worlds is updated as follows.

1. For every world w in which ϕ is true, i.e., M, w |= ϕ, the degree of exceptionality of w for i decreases from κ(w, i) to κ(w, i)κ w,i (ϕ), which is the same thing as saying that, degree of plausibility of w for i increases from maxκ(w, i) to max-(κ(w, i)-κ w,i (ϕ)). (Note that, by Definition 3, we have κ(w, i)-κ w,i (ϕ) ≤ κ(w, i)). 2. For every world w in which ϕ is false:

(a) if at w agent i envisages a world in which ϕ is true, i.e., M, w |= ¬ ϕ ∧ i ϕ, then the degree of exceptionality of w for i changes from κ(w, i) to Cut(α + κ(w, i)κ w,i (¬ϕ)); (b) if at w agent i does not envisage a world in which ϕ is true, i.e. M, w |=

[i]¬ϕ, then the degree of exceptionality of w for i does not change.

The preceding condition 1 ensures the intuitive requirement that belief revision with ϕ leaves the plausibility ranking in the ϕ-part of agent i's information set unchanged.

In other words, if v and u are worlds in which ϕ is true and agent i considers v more plausible (or less exceptional) than u then, after revising his beliefs with ϕ, agent i will still consider v more plausible than u. More formally, for all v, u ∈| | ϕ|| we 6 The degree of firmness α in the preceding condition 2(a) measures the extent to which agent i will believe that ϕ is true after revising his beliefs with ϕ. Indeed, as we will show in Section 4.1, in Spohn's theory of uncertainty the strength of the belief that ϕ is true is defined by the exceptionality degree of the negation of ϕ (i.e., κ w,i (¬ϕ)). Consequently, condition 2(a) guarantees that, if agent i envisages a world in which an objective formula ϕ is true then, after revising his beliefs with formula ϕ and with a degree of firmness α, he will believe ϕ with strength α. This property will become clearer in Section 4.1 in which the concept of graded belief (i.e., believing something with a certain strength) will be formally defined and its logical properties will be studied (see, in particular, Proposition 7).

have that if κ(u, i)>κ ( v, i) and (u, v) ∈ E i then κ * α i ϕ (u, i)>κ * α i ϕ (v, i).
Note that the reason why in Section 3.1 we assumed that α must be different from 0 is to guarantee that if an agent envisages a world in which a given objective formula ϕ is true then, after learning that ϕ is true, he will believe ϕ. Again, this property of the belief revision operation will become clearer in Section 4.1 where the concept of belief will be clearly defined (see, again, Proposition 7).

The function Cut is a minor technical device, taken from [START_REF] Aucher | A combined system for upyear logic and belief revision[END_REF], which ensures that the new plausibility assignment fits into the finite set of natural numbers Num. Finally, the preceding condition 2(b) guarantees that the agent's i plausibility ordering over worlds does not change, if i learns something that he does not envisage. 7Remark 1 It is straightforward to verify that the operation

* α i ϕ preserves the con- straint (Constr1) over PDL-A-models. Therefore, if M is a PDL-A-model then M * α i ϕ is a PDL-A-model too.
In what follows we write |= ϕ to mean that ϕ is valid (ϕ is true in all PDL-Amodels).

Varieties of Individual and Collective Attitudes

In the following two sections a variety of individual and collective attitudes will be defined, and their logical properties and logical relationships will be studied. We consider three kinds of individual attitudes, in addition to the concept of knowledge formalized by the operator [i], namely belief, graded belief and robust belief. Furthermore, we consider three kinds of collective attitudes, namely common knowledge, common belief and common robust belief. Of course, we do not claim that this analysis is exhaustive. For instance, we do not consider the collective counterpart of graded belief, namely the concept common graded belief, as a logical analysis of this concept goes beyond the objectives of the present work.

The concepts of belief, graded belief, robust belief and common belief will be fundamental building blocks for the analysis of the epistemic conditions of iterated weak dominance that we will carry out in Section 6. The concept of graded belief is also essential to understand the meaning of the parameter α in the belief revision operator * α i ϕ ). Finally, the concepts of common knowledge and common robust belief are defined here because we are interested: (1) in comparing them with the concept of common belief and (2) in understanding the similarities between the dynamic properties of robust belief and the dynamic properties of common robust belief, and between the dynamic properties of knowledge and the dynamic properties of common knowledge.

Individual Attitudes

Following [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF], we say that agent i believes that ϕ is true, denoted by Bel i ϕ,i fa n d only if ϕ is true in all worlds that i considers minimally exceptional (or maximally plausible). Let us define the belief operator Bel i as follows:

Bel i ϕ def =[ i](exc i,0 → ϕ)
As the following Proposition 1 highlights, the previous abbreviation correctly characterizes this notion of belief. Given a PDL-A model M = W, {E i : i ∈ Agt},κ,V and aw orldw in M,letB i ={ (w, v) : (w, v) ∈ E i and κ(v, i) = 0} be the accessibility relation for agent i's belief and B i (w) ={ v ∈ W : (w, v) ∈ B i } be the corresponding i's belief state at world w.

Proposition 1 For every PDL-A model M and for every world w in M, M, w |=

Bel i ϕ if and only if M, v |= ϕ for all v ∈ B i (w).
The following concept of 'graded belief' is taken from Spohn. 8 We say that at world w agent i believes that ϕ with strength equal to h, denoted by Bel h i ϕ, if and only if the degree of exceptionality of ¬ϕ for agent i at w (i.e., κ w,i (¬ϕ)) is equal to h.In formal terms we define:

Bel h i ϕ def = i (exc i,h ∧¬ϕ) ∧[i](exc i,<h → ϕ) if h < max [i](exc i,<h → ϕ) if h = max 8
A modal logic analysis of this concept has been given by Aucher [START_REF] Aucher | A combined system for upyear logic and belief revision[END_REF]( s e ea l s o [START_REF] Laverny | From knowledge-based programs to graded belief-based programs, part II: off-line reasoning[END_REF][START_REF] Van Ditmarsch | Prolegomena to dynamic logic for belief revision[END_REF]). A relevant difference between Aucher's approach and our approach is that he introduces graded belief operators in the syntax right away, whereas we build them from the special atomic formulae exc i,h . However, the added value of working with the exc i,h -constructs is that they provide a simple extension of van As we have emphasized above, graded belief is a fundamental concept of Spohn's theory of uncertainty and belief change, as it justifies the definition of belief revision we have given in Section 3.2 (Definition 4). It is worth noting that the graded belief operator Bel h i is an operator of strong necessity (or actual necessity) in the sense of possibility theory [START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF].

For every h ∈ Num, we moreover provide the following definition:

Bel ≥h i ϕ def = k∈Num:k≥h Bel k i ϕ
Bel ≥h i ϕ has to be read "agent believes that ϕ is true with strength at least h". It is worth noting that, when h ≥ 1, the operator Bel ≥h i is a normal operator, as it can be interpreted by means of the following accessibility relation:

B <h i ={(w, v) : (w, v) ∈ E i and κ(v, i)<h}.

In particular, given a

PDL-A model M = W, {E i : i ∈ Agt},κ,V ,w eh a v et h a t M, w |= Bel ≥h i ϕ if and only if M, v |= ϕ for all v such that (w, v) ∈ B <h i .
T h e operator Bel ≥h i will be a key element in the analysis of the epistemic conditions of iterated weak dominance that we will conduct in Section 6.4. Specifically, it will be necessary in order to define the notion of perfect rationality on which the concept of iterated weak dominance is based. For notational convenience, we define Bel ≥h i to be the dual operator of Bel ≥h i ,thatis,

Bel ≥h i ϕ def =¬ Bel ≥h i ¬ϕ.
The following Propositions 3-7 capture some interesting properties of the preceding types of individual attitudes. For instance, the following Proposition 3 highlights that modal operators for belief and graded belief with strength at least h are normal.

Proposition 3 For every ∈{Bel

i : i ∈ Agt}∪ Bel ≥h i : i ∈ Agt, h ∈ Num \{0} we have: |= ( ϕ ∧ ψ) → (ϕ ∧ ψ) (1a) If |= ϕ then |= ϕ (1b)
According to the following Proposition 4, belief is characterized by the normal modal logic system KD45.

Proposition 4

For every i ∈ Agt we have:

|= ¬ (Bel i ϕ ∧ Bel i ¬ϕ) (2a) |= Bel i ϕ → Bel i Bel i ϕ (2b) |= ¬ Bel i ϕ → Bel i ¬Bel i ϕ (2c)
Note that the item (2a) follows from the normality constraint (Constr1) over PDL-A models given in Section 3.2.

The following Proposition 5 highlights some basic relationships between knowledge, belief and graded beliefs with different strengths.

Proposition 5 For every i ∈ Agt we have:

|= Bel h i ϕ →¬Bel k i ϕ if h = k (3a) |= [ i]ϕ → Bel max i ϕ (3b) |= [ i]ϕ → Bel i ϕ (3c) |= Bel i ϕ ↔ Bel ≥1 i ϕ (3d)
According to the item (3a), an agent cannot believe the same thing with different strengths. Moreover, knowing that ϕ implies believing that ϕ with maximal strength max (3b); knowing that ϕ implies believing that ϕ (3c); believing that ϕ coincides believing that ϕ withstrengthatleast1(3d).

The following Proposition 6 captures the basic decomposability properties of the operators of graded belief.

Proposition 6

For every i ∈ Agt we have:

|= Bel h i ϕ ∧ Bel k i ψ → Bel ≥max{h,k} i (ϕ ∨ ψ) (4a) |= Bel h i ϕ ∧ Bel k i ψ → Bel min{h,k} i (ϕ ∧ ψ) (4b)
According to the validity (4a), the degree of belief of ϕ∨ψ is at least equal to the maximum of the degree of belief of ϕ and ψ. According to the validity (4b), the degree of belief of ϕ ∧ ψ is equal to the minimum of the degree of belief of ϕ and ψ. Similar properties for graded belief are given in possibility theory [START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF]. Note that second validity uses the "definite" value min{h, k} while the first validity uses the "at least" construction ≥ max{h, k} because the minimun of the union of two sets is equal to the minimum of the minima of the two sets, while the minimun of the intersection of two sets is at least equal to the maximum of the minima of the two sets but not necessarily equal.

Finally, the following Proposition 7 is about the dynamic properties of belief and graded belief.

Proposition 7

For every i ∈ Agt and for every α ∈ Num \{0} we have:

|= i ϕ → * α i ϕ Bel i ϕ if ϕ ∈ Obj (5a) |= i ϕ → * α i ϕ Bel α i ϕ if ϕ ∈ Obj (5b) |= [ i]ψ → * α i ϕ [i]ψ if ψ ∈ Obj (5c) |= * α i ϕ [i]ψ →[i]ψ if ψ ∈ Obj (5d)
Item (5a) highlights a basic property of belief revision in the sense of AGM theory [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF], namely the so-called success postulate: if ϕ is an objective fact and agent i envisages a world in which ϕ is true then, after learning that ϕ is true, agent i believes that ϕ is true. 9 Note that this property does not hold in general but only for formulas in Obj. Indeed, if we drop the restriction to Boolean formulas, the match to AGM success postulate does not work anymore. For instance, if ϕ is a Moore-like sentence of the form p ∧¬Bel i p, the formula i ϕ → * α i ϕ Bel i ϕ is clearly not valid. Item (5b) clarifies the role of the degree of firmness α in the operation of belief revision: if ϕ is an objective fact and agent i envisages a world in which ϕ is true then, after revising his beliefs with formula ϕ and with a degree of firmness α, agent i believes that ϕ is true with strength equal to α. Finally, item (5c) captures the fundamental property of knowledge that we have discussed in Section 3.1:i fψ is an objective fact and agent i knows that ψ then, after learning a new fact ϕ, he will continue to know that ψ is true. In this sense, knowledge is stable under belief revision with any piece of information. The last item (5d) is a no-learning principle for knowledge: if ψ is an objective fact and agent i will know that ψ after revising his knowledge with ϕ then, it means that i already knows ψ.

Before moving to the analysis of collective attitudes, we follow Stalnaker [START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF]in defining a notion of robust belief relative to as p e c i f i cf o r m u l aϕ, in the sense of belief which is stable under belief revision with ϕ:

RBel i (ϕ, ψ) def = Bel i ψ ∧ * α i ϕ Bel i ψ
where α is any arbitrary value in Num \{ 0} (e.g., α = 1). The construction RBel i (ϕ, ψ) has to be read "agent i has a robust belief that ψ relative to ϕ". One reason why the value of the parameter α can be taken arbitrarily is that we have the following validity, for all α, α ′ ∈ Num \{0} and for all ψ ∈ Obj:

|= * α i ϕ Bel i ψ ↔ * α ′ i ϕ Bel i ψ
Therefore, the definition of relative robust belief RBel i (ϕ, ψ) is independent from the value of α in case of objective formulas (i.e., Bel i ψ ∧ * α i ϕ Bel i ψ is logically equivalent to Bel i ψ ∧ * α ′ i ϕ Bel i ψ for all α, α ′ ∈ Num \{ 0} and for all ψ ∈ Obj). This concept of relative robust belief, as well as the concept of graded belief defined above, will be fundamental in the logical analysis of the epistemic conditions of iterated weak dominance we will carry out in Section 6.

Remark 2 It is worth noting that our concept of relative robust belief, represented by the formula RBel i (ϕ, ψ), is related to the concept of robust (or strong) belief defined by [START_REF] Baltag | Talking your way into agreement: belief merge by persuasive communication[END_REF]. According to Baltag & Smets, ϕ is a strong belief if and only if ϕ is epistemically possible and moreover all epistemically possible ϕ-states are strictly more plausible than all epistemically possible ¬ϕ-states. More formally, we can say that at world w agent i has the robust belief that ψ (in Baltag & Smets's sense), denoted by RBel B&S i ψ, if and only if (i) ||ψ|| w,i = ∅ and (ii) for all v ∈| | ψ|| w,i and for all u ∈ ||¬ψ|| w,i , κ(v, i)<κ( u, i). The operator RBel B&S i ψ can be syntactically expressed in the logic PDL-A. In particular, for every PDL-A model M and for all w ∈ W we have:

M, w |= RBel B&S i ψ if and only if M, w |= Bel i ψ ∧ h∈Num\{0} ( i (¬ψ ∧ exc i,h ) →[i](ψ → exc i,<h )).
Note that for all objective facts ψ ∈ Obj, we have the following validity:

|= RBel B&S i ψ ∧ i (ϕ ∧ ψ) → RBel i (ϕ,ψ).
In other words, if ψ is robust belief in Baltag & Smets's sense and, according to the agent's knowledge, ϕ and ψ are consistent, then the agent has a robust belief that ψ relative to ϕ, that is, the belief that ψ is stable under belief revision with ϕ.Inother words, a robust belief in Baltag & Smets's sense can only be defeated by evidence (truthful or not) that is known to contradict it. Following Baltag & Smets [START_REF] Baltag | A qualitative theory of dynamic interactive belief revision[END_REF] we moreover define the following concept of 'safe belief'. In [START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF] Stalnaker calls it 'absolutely robust belief' in order to distinguish it from the preceding concept of 'relative robust belief', while in [START_REF] Stalnaker | On logics of knowledge and belief[END_REF]h eu s e si tt o formally characterize Lehrer's defeasibility analysis of knowledge [START_REF] Lehrer | Undefeated justified true belief[END_REF]. We say that agent i has the safe belief that ϕ, denoted by SBel i ϕ, if and only if ϕ is true in all worlds that i envisages and that are at least as plausible as the current world. In formal terms, we define:

SBel i ϕ def = h∈Num (exc i,h →[i](exc i,≤h → ϕ))
with exc i,≤h def = k∈Num:0≤k≤h exc i,k . As the following Proposition 8 highlights, the previous abbreviation correctly characterizes this notion of safe belief. Given a PDL-A model M = W, {E i : i ∈ Agt},κ,V and a world w in M,letSB i ={(w, v) : (w, v) ∈ E i and κ(v, i) ≤ κ(w, i)} be the accessibility relation for agent i's safe belief and let SB i (w) ={ v ∈ W : (w, v) ∈ SB i } be the corresponding set of i's SB i -accessible worlds at world w. 10Proposition 8 For every PDL-A model M and for every world w in M, M, w |= SBel i ϕ if and only if M, v |= ϕ for all v ∈ SB i (w).

For notational convenience, we define SBel i to be the dual operator of SBel i ,thatis,

SBel i ϕ def =¬ SBel i ¬ϕ.
As the items (6a)-(6c) in the following Proposition 9 highlight, safe belief is characterized by the normal modal logic system S4.3 which exactly corresponds to Stalnaker's logic S4.3 in his defeasibility analysis of knowledge [START_REF] Stalnaker | On logics of knowledge and belief[END_REF]. The item (6d) in Proposition 9 captures the characteristic property of safe belief: if ψ is an objective fact, agent i safely believes that ψ and ϕ is true then, after learning that ϕ,h e will continue to safely believe that ψ is true. In this sense, a safe belief is stable under belief revision with any piece of true information.

Proposition 9

For every i ∈ Agt and for every α ∈ Num \{0} we have:

|= SBel i ϕ → ϕ (6a) |= SBel i ϕ → SBel i SBel i ϕ (6b) |= SBel i ϕ ∧ SBel i ψ → SBel i ϕ ∧ SBel i ψ ∨ SBel i ψ ∧ SBel i ϕ (6c) |= (ϕ ∧ SBel i ψ) → * α i ϕ SBel i ψ if ψ ∈ Obj (6d)
Note that, differently from knowledge, safe belief is not necessarily stable under belief revision with false information. Indeed, SBel i ψ → * α i ϕ SBel i ψ is invalid even for ψ ∈ Obj.

Collective Attitudes

Given a PDL-A model M = W, {E i : i ∈ Agt},κ,V ,letE J = i∈J E i , B J = i∈J B i and SB J = i∈J SB i . We define a world v to be E J -reachable from world w, denoted by (w, v) ∈ E + J , if and only if there exist worlds w 0 ,...,w n such that w 0 = w, w n = v and for all 0 ≤ k ≤ n-1, there exists i ∈ J such that (w k , w k+1 ) ∈ E i .Inotherwords, for every J ∈ 2 Agt * , E + J is the defined to be the transitive closure of E J . Similarly, we define B + J and SB + J to be the transitive closures of B J and SB J . We define three types of collective attitudes that are interpreted by means of the relations E + J , B + J and SB + J . The first two correspond to the well-known concepts of common knowledge and common belief and are represented, respectively, by the operators CK J and CBel J . The third one, represented by the operator CSBel J , corresponds to the concept of common safe belief that has been rather neglected in the logical literature up to now. 11 We define it here because we are interested in comparing it with the concepts of common knowledge and common belief, in the same way as in Section 4.1 we compared safe belief with knowledge and belief. For all J ∈ 2 Agt * we define:

CK J ϕ def = i∈J i * ϕ CBel J ϕ def = i∈J (i; ?exc i,0 ) * ϕ CSBel J ϕ def = h∈Num,i∈J (?exc i,h ; i; ?exc i,≤h ) * ϕ
As the following proposition highlights, the preceding three abbreviations correctly characterize the concepts of common knowledge, common belief and common safe belief.

Proposition 10 For every PDL-A model M and for every world w in M:

• M, w |= CK J ϕ if and only if M, v |= ϕ for all v such that (w, v) ∈ E + J , • M, w |= CBel J ϕ if and only if M, v |= ϕ for all v such that (w, v) ∈ B + J , • M, w |= CSBel J ϕ if and only if M, v |= ϕ for all v such that (w, v) ∈ SB + J .
The following Proposition 11 highlights the basic logical relationships between common knowledge, common belief and common safe belief.

Proposition 11 For every J ∈ 2 Agt * we have:

|= CK J ϕ → CSBel J ϕ (7a) |= CSBel J ϕ → CBel J ϕ (7b)
According to the item (7a), J's common knowledge that ϕ entails J's common safe belief that ϕ whereas, according to the item (7b), J's common safe belief that ϕ entails J's common belief that ϕ.

Finally, the following Proposition 12 is about the dynamic properties of common knowledge, common belief and common safe belief. Let

[ * J ϕ] ψ def = * α 1 i 1 ϕ ... * α card(J) i card(J) ϕ ψ
where (i 1 ,...,i card(J) ) is any arbitrary ordering of the elements of J,a n d α 1 ,...,α card(J) are any arbitrary values in Num \{0}. The construction [ * J ϕ]ψ has to be read "after every agent in J has learnt that ϕ is true, ψ will be true".

Proposition 12

For every J ∈ 2 Agt * we have:

|= CK J i∈J i ϕ →[ * J ϕ]CBel J ϕ if ϕ ∈ Obj (8a) |= CK J ψ →[ * J ϕ]CK J ψ if ψ ∈ Obj (8b) |= (CSBel J ϕ ∧ CSBel J ψ) →[ * J ϕ]CSBel J ψ if ψ ∈ Obj (8c)
The item (8a) is the collective counterpart of the item (5a) of Proposition 7: if ϕ is an objective fact and the agents in J have common knowledge that each of them envisages a world in which ϕ is true then, after learning that ϕ is true, the agents in J acquire the common belief that ϕ. This principle can be viewed as the collective counterpart of the success postulate of AGM theory [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF]. The item (8b) is the collective counterpart of the inertial principle for knowledge (Proposition 7, item 5c): if the agents in J have common knowledge that the objective fact ψ is true then, after learning that ϕ, they will continue to have common knowledge that ψ. The item (8c)isthe collective counterpart of the inertial principle for safe belief (Proposition 9, item 6d): if the agents in J have the common safe belief that the objective fact ψ is true and that ϕ is true then, after learning that ϕ is true, they will continue to have the common safe belief that ψ. In this sense, common safe belief is stable under belief revision with any piece of information that the agents commonly and safely believe to be true.

Axiomatization and Decidability

In this section, we provide a complete axiomatization as well as a decidability result for the logic PDL-A. This logic has so-called reduction axioms which allow us to eliminate all the dynamic operators of belief revision from formulas. That elimination provides a decidable procedure for checking whether a given formula is PDL-A valid.

Moreover it provides an axiomatics. Let PDL-A -be the fragment of the logic PDL-A without the operators * α i ϕ and PDL-A -be the fragment of PDL-A -without the special atoms exc i,h .T h a ti s ,l e t the language of PDL-A -be the set of formulas defined by the following BNF:

ϕ ::= p | exc i,h |¬ϕ | ϕ 1 ∧ ϕ 2 |[π ]ϕ
and let the language of PDL-A --be the set of formulas defined by the following BNF:

ϕ ::= p |¬ϕ | ϕ 1 ∧ ϕ 2 |[π ]ϕ
where p ranges over Prop, h ranges over Num, i ranges over Agt and π ranges over the set of knowledge programs as defined in Section 3.1.

Proposition 13

The following formulas are PDL-A valid for all h, k ∈ Num and for all i ∈ Agt.

i exc i,0 (NormPlaus) h∈Num exc i,h (ComplPlaus) exc i,h →¬exc i,k if h = k (UniquePlaus)
Proposition [START_REF] Blume | Lexicographic probabilities and choice under uncertainty[END_REF] The following equivalences are PDL-A valid for all p ∈ Atm, h ∈ Num, α ∈ Num \{0},i, j ∈ Agt such that i = j:

* α i ϕ p ↔ p (R1) * α i ϕ exc i,h ↔ ϕ ∧ l,m∈Num\{0}:l-m=h Bel m i ¬ϕ ∧ exc i,l ∨ ¬ϕ ∧ i ϕ ∧ l,m∈Num:Cut(α+l-m)=h Bel m i ϕ ∧ exc i,l ∨([i]¬ϕ ∧ exc i,h ) (R2) * α i ϕ exc j,h ↔ exc j,h (R3) * α i ϕ ¬ψ ↔¬ * α i ϕ ψ (R4) * α i ϕ (ψ 1 ∧ ψ 2 ) ↔ * α i ϕ ψ 1 ∧ * α i ϕ ψ 2 (R5) * α i ϕ [π ]ψ ↔ F * α i ϕ (π ) * α i ϕ ψ (R6)
where for all j ∈ Agt:

F * α i ϕ (j) = j F * α i ϕ (π 1 ; π 2 ) = F * α i ϕ (π 1 ); F * α i ϕ (π 2 ) F * α i ϕ (π 1 ∪ π 2 ) = F * α i ϕ (π 1 ) ∪ F * α i ϕ (π 2 ) F * α i ϕ (?ψ) = ? * α i ϕ ψ F * α i ϕ (π * ) = F * α i ϕ (π )
Theorem 1 Satisfiability in PDL-A is decidable.

Theorem 2 The validities of PDL-A are completely axiomatized by

• all principles of classical propositional logic • axiomatization of PDL for the operators [π ]

([π]ϕ ∧[π ](ϕ → ψ)) →[π ]ψ (K [π] ) [π 1 ; π 2 ]ϕ ↔[π 1 ][π 2 ]ϕ (Seq) [π 1 ∪ π 2 ]ϕ ↔[π 1 ]ϕ ∧[π 2 ]ϕ (Choice) [?ψ]ϕ ↔ (ψ → ϕ) (Test) [π * ]ϕ ↔ (ϕ ∧[π ][π * ]ϕ) (FixPoint) (ϕ ∧[π * ](ϕ →[π ])) →[π * ]ϕ (Induction) ϕ [π ]ϕ (Nec [π] )
• axioms T, 4 and B for the epistemic operators

[i] [i]ϕ → ϕ (T [i] ) [i]ϕ →[i][i]ϕ (4 [i] ) ϕ →[i] i ϕ (B [i] ) • the schemas of Proposition 13
• the reduction axioms of Proposition 14 • rule of replacement of equivalents

ψ 1 ↔ ψ 2 ϕ ↔ ϕ[ψ 1 /ψ 2 ] (REP)
where ϕ[ψ 1 /ψ 2 ] is the formula that results from ϕ by replacing zero or more occurrences of ψ 1 ,inϕ,byψ 2 .

Application to Game Theory

In this section we provide an application of the logic PDL-A to game theory. We first introduce in Section 6.1 two important solution concepts of game theory: the procedure of Iterated Deletion of Strongly Dominated Strategies (IDSDS procedure), and the procedure of n-rounds of Iterated Deletion of Weakly Dominated Strategies followed by Iterated Deletion of Strongly Dominated Strategies (DWDS n -IDSDS procedure). In Section 6.2 we provide an extension of the logic PDL-A with information about agents' behaviors (i.e., which strategy a given agent is currently playing). We call PDL-A + the resulting logic. In Section 6.4 the logic PDL-A + is used to formally characterize different forms of rationality which have been discussed in the field of epistemic game theory: weak rationality, strong rationality and perfect rationality. Section 6.4 is the main contribution of this second part of the paper. Several theorems about the epistemic characterization of IDSDS and DWDS n -IDSDS will be provided. Proofs of these theorems are collected in a technical annex at the end of the paper.

Iterated Weak and Strong Dominance

Let us first introduce the notion of normal form game.

Definition 5 (Normal form game) A normal form game is a tuple Ŵ ={ { S i : i ∈ Agt}, {U i : i ∈ Agt}} where:

• S i is agent i's finite set of strategies; • U i : i∈Agt S i -→ R is agent i's

utility function assigning a real number (the utility value for i) to every combination of agents' actions (alias strategy profiles).

For every agent i ∈ Agt, the elements of S i are denoted by symbols a i , b i ,... For every coalition J ∈ 2 Agt * , we define the set of strategies for the coalition J to be S J = i∈J S i . For notational convenience we write S instead of S Agt . For every coalition J,e l e m e n t so fS J are denoted by s J , s ′ J ,... For simplicity, elements of S are denoted by s, s ′ ,... Given s J ∈ S J and i ∈ J, we note s J [i] the position of s J corresponding to agent i. In what follows we write s ≤ i s ′ instead of U i (s) ≤ U i (s ′ ) and s < i s ′ instead of U i (s)<U i (s ′ ) to mean respectively that "the strategy profile s ′ is for agent i at least as good as the strategy profile s" and "the strategy profile s ′ is for agent i better than the strategy profile s".

Definition 6 (Subgame) Given two games Ŵ ={ { S i : i ∈ Agt}, {U i : i ∈ Agt}} and Ŵ ′ ={{S ′ i : i ∈ Agt}, {U ′ i : i ∈ Agt}}, Ŵ ′ isasubgameofŴ if and only if: • for every i ∈ Agt, S ′ i ⊆ S i ; • for every i ∈ Agt, U ′ i = U i | i∈Agt S ′ i where U ′ i is the restriction of U i to the set of strategy profiles i∈Agt S ′ i .
As t r a t e g ya i of a given player i is a strongly dominated strategy if and only if, there exists another strategy b i of i such that, for all strategies s -i of the other players, playing b i while the others play s -i is for i better than playing a i while the others play s -i . An example of strongly dominated strategy is cooperation in the Prisoner Dilemma (PD) game: whether the opponent chooses to cooperate or defect, defection yields a higher payoff than cooperation. More formally:

Definition 7 (Strongly dominated strategies) Given a game Ŵ ={ { S i : i ∈ Agt}, {U i : i ∈ Agt}},theset SD Ŵ i ={a i ∈ S i :∃b i ∈ S i s.t. ∀s -i ∈ S -i , a i , s -i < i b i , s -i }
is the set of strategies of player i that are strongly dominated in Ŵ.

Astrategya i of a given player i is a weakly dominated strategy if and only if, there exists another strategy b i of i such that, for all strategies s -i of the others, playing b i while the others play s -i is for i at least as good as playing a i while the others play s -i and there is at least one strategy s ′ -i of the others such that playing b i while the others play s ′ -i is for i better than playing a i while the others play s ′ -i . More formally:

Definition 8 (Weakly dominated strategies) Given a game Ŵ ={ { S i : i ∈ Agt}, {U i : i ∈ Agt}},theset WD Ŵ i ={a i ∈ S i :∃b i ∈ S i s.t. ∀s -i ∈ S -i , a i , s -i ≤ i b i , s -i and ∃s ′ -i ∈ S -i s.t. a i , s ′ -i < i b i , s ′ -i }
is the set of strategies of player i that are weakly dominated in Ŵ.

The so-called Iterated Deletion of Strongly Dominated Strategies (IDSDS) (or iterated strong dominance) is a procedure that starts with the original game Ŵ and, at each step, for every player i removes from the game all i's strongly dominated strategies, thereby generating a subgame of the original game, and that repeats this process again and again. The IDSDS procedure can be inductively defined as follows.

Definition 9 (IDSDS Procedure) Given a game Ŵ ={{S i : i ∈ Agt}, {U i : i ∈ Agt}}, Iterated Deletion of Strongly Dominated Strategies (IDSDS) is the procedure defined recursively as follows.

For all i ∈ Agt:l e tS IDSDS i,0

= S i and Ŵ 0 = Ŵ,f o rm ≥ 1, let S IDSDS i,m = S IDSDS i,m-1 \ SD Ŵ m-1 i ,whereŴ m-1 is the subgame of Ŵ with strategy sets S IDSDS i,m-1 . For every m ≥ 0andJ ∈ 2 Agt * ,letS IDSDS J,m = i∈J S IDSDS i,m and let S IDSDS m = S IDSDS Agt,m . Finally, let S IDSDS i = m∈N S IDSDS i,m .ForeveryJ ∈ 2 Agt * ,letS IDSDS J = i∈J S IDSDS i and S IDSDS = S IDSDS Agt .
T h ep r o c e d u r eo fn-rounds of Iterated Deletion of Weakly Dominated Strategies followed by Iterated Deletion of Strongly Dominated Strategies (DWDS n -IDSDS) is a procedure that starts with the original game Ŵ and, at each step, for every player i removes from the game all i's weakly dominated strategies thereby generating a subgame of the original game, and that repeats this process for n rounds. Then, after n rounds it applies Iterated Deletion of Strongly Dominated Strategies starting with the game Ŵ n .TheDWDS n -IDSDS procedure can be inductively defined as follows.

Definition 10 (DWDS n -IDSDS Procedure) Given a game Ŵ ={ { S i : i ∈ Agt}, {U i : i ∈ Agt}}, n-iteration of Deletion of Weakly Dominated Strategies (DWDS n ) followed by Iterated Deletion of Strongly Dominated Strategies (IDSDS) is the procedure defined recursively as follows.

For all i ∈ Agt:l e tS DWDS n -IDSDS i,0

= S i and Ŵ 0 = Ŵ,f o r1 ≤ m ≤ n, let S DWDS n -IDSDS i,m = S DWDS n -IDSDS i,m-1 \ WD Ŵ m-1 i ,f o rm > n,l e tS DWDS n -IDSDS i,m = S DWDS n -IDSDS i,m-1 \ SD Ŵ m-1 i
,w h e r eŴ m-1 is the subgame of Ŵ with strategy sets

S DWDS n -IDSDS i,m-1
.

For every m such that 0 ≤ m ≤ n and J ∈ 2 Agt * ,l e tS DWDS n -IDSDS

J,m = i∈J S DWDS n -IDSDS i,m
and

S DWDS n -IDSDS m = S DWDS n -IDSDS Agt,m . Finally, let S DWDS n -IDSDS i = m∈N S DWDS n -IDSDS i,m
.F o re v e r yJ ∈ 2 Agt * ,l e t

S DWDS n -IDSDS J = i∈J S DWDS n -IDSDS i and S DWDS n -IDSDS = S DWDS n -IDSDS Agt .
Note that, if n = 0, DWDS n -IDSDS is nothing but IDSDS. Moreover, if n =∞ , DWDS n -IDSDS corresponds to the procedure of iterated admissibility or iterated deletion of weakly dominated strategies [START_REF] Brandeburger | The power of paradox: some recent developments in interactive epistemology[END_REF][START_REF] Brandenburger | Admissibility in games[END_REF].

PDL-A with Information About Players' Choices

The logic PDL-A is here extended with special constructions of the form pl i (a i ) whose meaning is "agent i plays (or chooses) the strategy a i ". We call PDL-A + the resulting logic. For every J ∈ 2 Agt * ,w ed e f i n epl J (s J ) ("the agents in J play the collective strategy s J ") as follows:

pl J (s J ) def = i∈J pl i (s J [i])
For simplicity, we write pl(s) instead of pl Agt (s).

For every coalition of agents J ∈ 2 Agt * ,w ed e f i n et h es e tBeh J of information about J's choices:

Beh J = s J ∈s J pl J (s J ) : s J ⊆ S J .
For example, the formula pl J (s J ) ∨ pl J (s ′ J ) in Beh J means that "the agents in J play either the collective strategy s J or the collective strategy s ′ J ".

Definition 11 (PDL-A + model) PDL-A + -models are tuples M ′ = M, {A i : i ∈ Agt} where:

• M is a PDL-A model;

• for every agent i, A i : W -→ S i is a total function mapping each world w to the strategy played by agent i at w.

A i (w) = a i means that at w agent i plays the strategy a i . Functions A i are easily generalized to functions A J : W -→ S J , by postulating that A J (w) = s J if and only if A i (w) = s J [i] for every i ∈ J.

Given a PDL-A + model M and a world w, the truth condition of pl i (a i ) is:

M, w |= pl i (a i ) iff A i (w) = a i
PDL-A + models are assumed to satisfy the following two constraints. For every w, v ∈ W, i ∈ Agt, a i ∈ S i and s -i ∈ S -i :

(Constr2)i f A i (w) = a i and (w, v) ∈ E i then A i (v) = a i ; (Constr3)t h e r e i s u such that (w, u) ∈ E i and A -i (u) = s -i . 12
According to the Constraint (Constr2), an agent i chooses the strategy a i if and only if he knows this. According to the Constraint (Constr3), for every strategy s -i of the other players an agent i envisages a world in which this strategy is played. This corresponds to the second requirement we have discussed in Section 2, namely the assumption that the beliefs of the players are cautious. The notions of validity and satisfiability in PDL-A + are defined in the usual way. For every PDL-A + formula ϕ, we say that ϕ is valid, denoted again by |= ϕ,ifϕ is true in all PDL-A + -models. We say that ϕ is satisfiable if ¬ϕ is not valid. We moreover say that two PDL-A + formulas ϕ and ψ are compatible, denoted by Comp(ϕ, ψ),if ϕ ∧ ψ is satisfiable.

Note that the logic PDL-A + is completely axiomatized by the axioms and rules of inference of the logic PDL-A plus the following axiom schemas:

a i ∈S i pl i (a i ) (Active) pl i (a i ) →¬pl i (b i ) if a i = b i (UniqueAct) pl i (a i ) →[i]pl i (a i ) (ActAware) i pl -i (s -i ) (PossStr)
The decidability of PDL-A + follows straightforwardly from the decidability of PDL-A and the fact that the set of axioms differentiating PDL-A + from PDL-A is finite (remember that every strategy set S i is assumed to be finite).

Variants of Rationality

The following formula characterizes a notion of weak rationality which is commonly supposed in the epistemic analysis of games (see, e.g., [START_REF] Van Benthem | Rational dynamics and epistemic logic in games[END_REF]):

WRat i (a i ) def = b i =a i ⎛ ⎝ s -i ∈S -i : b i ,s -i ≤ i a i ,s -i Bel i pl -i (s -i ) ⎞ ⎠
This means that the strategy a i is a weakly rational choice for the agent i, i.e., WRat i (a i ), if and only if, for every strategy b i different from a i , there exists a joint strategy s -i of the other agents that he considers maximally plausible such that, playing a i while the others play s -i is for agent i at least as good as playing b i while the others play s -i . This means that weak rationality simply consists in not choosing a strategy that is strongly dominated within the set of worlds that the agent considers maximally plausible. The following abbreviations WRat i and AllWRat J have to be read respectively "agent i is weakly rational" and "all agents in the group J are weakly rational":

WRat i def = a i ∈S i (pl i (a i ) ∧ WRat i (a i )) AllWRat J def = i∈J WRat i
The preceding notion of weak rationality has been distinguished from a slightly stronger notion of rationality, called strong rationality (see, e.g., [START_REF] Bonanno | A syntactic approach to rationality in games with ordinal payoffs[END_REF]). The strategy a i is a strongly rational choice for the agent i, i.e., SRat i (a i ), if and only if, for each strategy b i different from a i either (1) there is a joint strategy s -i of the other agents that i considers maximally plausible such that playing a i while the others play s -i is for i better than playing b i while the others play s -i or (2) there is no joint strategy s -i of the other agents that i considers maximally plausible such that playing b i while the others play s -i is for i better than playing a i while the others play s -i .This means that strong rationality simply consists in not choosing a strategy that is weakly dominated within the set of worlds that the agent considers maximally plausible:

SRat i (a i ) def = b i =a i ⎛ ⎝ ⎛ ⎝ s -i ∈S -i : b i s -i < i a i ,s -i Bel i pl -i (s -i ) ⎞ ⎠ ∨ ⎛ ⎝ s -i ∈S -i : a i ,s -i < i b i ,s -i Bel i ¬pl -i (s -i ) ⎞ ⎠ ⎞ ⎠
The following abbreviations SRat i and AllSRat J have to be read respectively "agent i is strongly rational" and "all agents in the group J are strongly rational":

SRat i def = a i ∈S i (pl i (a i ) ∧ SRat i (a i )) AllSRat J def = i∈J SRat i
Stalnaker has introduced an even stronger notion of rationality, called perfect rationality [START_REF] Stalnaker | Knowledge, belief and counterfactual reasoning in games[END_REF][START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF]. Roughly, Stalnaker's notion expresses that in cases two or more actions maximize utility, the agent should consider, in choosing between them, how he should act if he learned that he was in error. And if the two actions are still tied, the agent considers how he should act if he learned that he was making an error of a higher degree (see also [START_REF] Board | Belief revision and rationalizability[END_REF]). We here consider a slightly different variant of Stalnaker's notion of perfect rationality that can be conceived as a lexicographic refinement of the preceding concept of strong rationality. Our notion of perfect rationality can be inductively defined by means of the preceding notion of strong rationality and of the notion of graded belief introduced in Section 4.1. The basic idea is the following. We say that the strategy a i is a strongly rational choice for the agent i at level 1, denoted by SRat 1 i (a i ), if and only if a i is a strongly rational choice accordingtoagenti's current beliefs. This notion of level 1-strong rationality coincides with the notion of strong rationality defined above. Moreover, for every h ∈ Num such that 1 < h ≤ max, we say that the strategy a i is a strongly rational choice for the agent i at level h, denoted by SRat h i (a i ), if and only if: • a i is a strongly rational choice for the agent i at level h -1, and • strategy a i is an admissible choice according to agent i's graded beliefs with strenght at least h, 13 after having discarded all strategies b i different from a i that are not strongly rational choices at level h -1.

Finally, we say that the strategy a i is a perfectly rational choice for the agent i, denoted by PRat i (a i ), if and only if:

• a i is a strongly rational choice for the agent i at level max,and • strategy a i is an admissible choice according to agent i's knowledge, after having discarded all strategies b i different from a i that are not strongly rational choices at level max.

In other words, a i is a perfectly rational choice for the agent i if and only if: a i is not weakly dominated within the set of epistemic alternatives that i considers exceptional with degree at most 0; and a i is not weakly dominated within the set of epistemic alternatives that i considers exceptional with degree at most 1, after having discarded all weakly dominated strategies within the set of epistemic alternatives that i considers exceptional with degree at most 0; and so on until level max. Formally speaking, we define: 13 Remember from Section 4.1 that the graded belief operator Bel ≥h i can be interpreted by means of the binary relation B <h i ={ (w, v) : (w, v) ∈ E i and κ(v, i)<h}. Thus, strategy a i is an admissible choice according to agent i's graded beliefs with strenght at least h if and only if, strategy a i is a strongly rational choice with respect to agent i's set of envisaged worlds with exceptionality at most h -1.

SRat 1 i (a i ) def = SRat i (a i ) for all h ∈ Num such that 1 < h ≤ max: SRat h i (a i ) def = SRat h-1 i (a i ) ∧ b i =a i ⎛ ⎝ SRat h-1 i (b i ) → ⎛ ⎝ ⎛ ⎝ s -i ∈S -i : b i ,s -i < i a i ,s -i Bel ≥h i pl -i (s -i ) ⎞ ⎠ ∨ ⎛ ⎝ s -i ∈S -i : a i ,s -i < i b i ,s -i Bel ≥h i ¬pl -i (s -i ) ⎞ ⎠ ⎞ ⎠ ⎞ ⎠

Finally:

PRat i (a i ) def = SRat max i (a i ) ∧ b i =a i ⎛ ⎝ SRat max i (b i ) → ⎛ ⎝ ⎛ ⎝ s -i ∈S -i : b i ,s -i < i a i ,s -i i pl -i (s -i ) ⎞ ⎠ ∨ ⎛ ⎝ s -i ∈S -i : a i ,s -i < i b i ,s -i [i]¬pl -i (s -i ) ⎞ ⎠ ⎞ ⎠ ⎞ ⎠
The following abbreviations PRat i and AllPRat J have to be read respectively "agent i is perfectly rational" and "all agents in the group J are perfectly rational":

PRat i def = a i ∈S i (pl i (a i ) ∧ PRat i (a i )) AllPRat J def = i∈J PRat i
The following Proposition 16 highlights the logical relationships between the three notions of rationality (weak, strong and perfect).

Proposition 16

For every i ∈ Agt we have:

|= SRat i → WRat i (9a) |= PRat i → SRat i (9b)
The following Proposition 17 is about properties of positive and negative introspection for the three forms of rationality. If an agent is/is not weakly/strongly/perfectly rational then, he knows this.

Proposition 17

For every i ∈ Agt we have:

|= WRat i →[ i]WRat i (10a) |= SRat i →[ i]SRat i (10b) |= PRat i →[ i]PRat i (10c) |= ¬ WRat i →[ i]¬WRat i (10d) |= ¬ SRat i →[ i]¬SRat i (10e) |= ¬ PRat i →[ i]¬PRat i (10f)

Epistemic Conditions of Solution Concepts

The following Theorem 3 is the qualitative version of a probabilistic-based result of Stalnaker [START_REF] Stalnaker | On the evaluation of solution concepts[END_REF] who has been the first to use probabilistic Kripke structures in order to characterize the IDSDS procedure in terms of common belief of weak rationality (see [START_REF] Board | Knowledge, beliefs, and game-theoretic solution concepts[END_REF][START_REF] Bonanno | A syntactic approach to rationality in games with ordinal payoffs[END_REF] for some recent discussion of Stalnaker's result). A similar result has also been proved, with differing degrees of formality, by Bernheim [START_REF] Bernheim | Axiomatic characterizations of rational choice in strategic environments[END_REF], Pearce [START_REF] Pearce | Rationalizable strategic behavior and the problem of perfection[END_REF], Brandenburger & Dekel [START_REF] Brandeburger | Rationalizability and correlated equilibria[END_REF], Tan & Werlang [START_REF] Tan | The bayesian foundation of solution concepts of games[END_REF] and Lorini & Schwarzentruber [START_REF] Lorini | A modal logic of epistemic games[END_REF]. According to the Theorem 3, if the players have common belief that every agent is weakly rational then the strategy profile which is played must survive IDSDS.

Theorem 3

Let s ∈ S IDSDS . Then:

|= CBel Agt AllWRat Agt →¬pl(s)
According to the following Theorem 4, if the players have common belief that every agent is perfectly rational, then the strategy profile which is played must survive one iteration of DWDS followed by IDSDS. This is called the Dekel-Fudenberg procedure as it appeared for the first time in [START_REF] Dekel | Rational behavior with payoff uncertainty[END_REF]. Characterizations of the epistemic conditions of this solution concept have also been given in a probabilistic setting by Stalnaker [START_REF] Stalnaker | Knowledge, belief and counterfactual reasoning in games[END_REF] as well as by Brandenburger [START_REF] Brandenburger | Lexicographic probabilities and iterated admissibility[END_REF]andBörgers [START_REF] Börgers | Weak dominance and approximate common knowledge[END_REF]. 14 Theorem 4 Let s ∈ S DWDS 1 -IDSDS . Then:

|= CBel Agt AllPRat Agt →¬pl(s)
According to the following Theorem 5, if the players have common belief that every player (1) is perfectly rational and (2) has a robust belief that all other players are perfectly rational relative to any compatible information about their choices, then the strategy profile which is played must survive two iterations of DWDS followed by IDSDS. A similar theorem has been stated before by Stalnaker [START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF], even though he did not provide a formal proof for it. The main difference between Theorem 5 and Stalnaker's result is that Stalnaker's analysis is given in quantitative setting based on probabilities whereas the representation of uncertainty used here is semi-qualitative (see Section 7 for further discussion). Theorem 5 Let s ∈ S DWDS 2 -IDSDS . Then:

|= CBel Agt AllPRat Agt ∧ AllRBelPRat Agt →¬pl(s)
where for every J ∈ 2 Agt * : 14 Börgers' characterization uses the concept of approximate common knowledge by Monderer & Samet [START_REF] Monderer | Approximating common knowledge with common beliefs[END_REF] instead of common belief. (Roughly speaking ϕ is approximate common knowledge if and only if, everybody assigns high probability to ϕ, everybody assigns high probability to the fact that everybody assigns high probability to ϕ, and so on).

AllRBelPRat J def = i∈J ⎛ ⎜ ⎜ ⎝ χ -i ∈Beh -i : Comp(χ -i ,AllPRat -i ) RBel i (χ -i , AllPRat -i ) ⎞ ⎟ ⎟ ⎠
AllRBelPRat J has to be read "every player in J has a robust belief that all other players are perfectly rational relative to any compatible information about their choices". It is worth noting that the hypothesis CBel Agt (AllPRat Agt ∧ AllRBelPRat Agt ) of Theorem 5 requires that, for every player i ∈ Agt and for every strategy s -i of the other players, if the strategy s -i is admissible (i.e., it is not weakly dominated) then i envisages a world in which the other agents play the strategy s -i a n dt h e ya r ea l l perfectly rational. In particular, we have the following validity: 15

|= CBel Agt (AllPRat Agt ∧ AllRBelPRat Agt ) → i∈Agt s -i ∈S -i :s -i ∈S DWDS 2 -IDSDS -i,1 i (pl -i (s -i ) ∧ AllPRat -i )
Therefore, the model in which the formula CBel Agt (AllPRat Agt ∧ AllRBelPRat Agt ) is satisfied must be 'sufficiently rich', as for every player i and for every admissible strategy of the other players there must be a world envisaged by i in which this strategy is played and the other players are perfectly rational. This richness condition, which is called by Brandenburger et al. [START_REF] Brandeburger | The power of paradox: some recent developments in interactive epistemology[END_REF][START_REF] Brandenburger | Admissibility in games[END_REF] the 'completeness assumption', has been explicitly spelled out in [START_REF] Perea | Epistemic game theory: reasoning and choice[END_REF]Definition 7.11,page 304]. 16 The preceding Theorem 5 can be generalized to n-iteration of deletion of weakly dominated strategies. But before generalizing Theorem 5, we need to introduce the concept of k-order robust belief about perfect rationality. For the case k = 1, we define:

AllPRatRBelPRat J,1 def = AllPRat J ∧ AllRBelPRat J
and for all k > 1: 15 This validity can be proved by using Proposition 2 given in the technical annex at the end of the paper (Section A.3). 16 It is worth noting that the completeness assumption together with the fact that there is common belief that every player is perfectly rational and has a robust belief à la Baltag & Smets [START_REF] Baltag | Talking your way into agreement: belief merge by persuasive communication[END_REF] (see Section 4.1) about the perfect rationality of the other players are also sufficient conditions for two iterations of DWDS followed by IDSDS. Indeed, in a way similar to the proof of Theorem 5, one can prove the following validity for all s ∈ S DWDS 2 -IDSDS :

AllPRatRBelPRat J,k def = AllPRat J ∧ i∈J ⎛ ⎜ ⎜ ⎝ χ -i ∈Beh -i : Comp(χ -i ,AllPRatRBelPRat -i,k-1 ) RBel i (χ -i , AllPRatRBelPRat -i,k-1 ) ⎞ ⎟ ⎟ ⎠
|= ⎛ ⎝ ComplAss ∧ CBel Agt ⎛ ⎝ AllPRat Agt ∧ i∈Agt RBel B&S i AllPRat -i ⎞ ⎠ ⎞ ⎠ →¬pl(s) with ComplAss def = i∈Agt s-i∈S-i:s-i∈S DWDS 2 -IDSDS -i,1 i (pl -i (s -i ) ∧ AllPRat -i ).
AllPRatRBelPRat J,k has to be read "every player in J is perfectly rational and has a k-order robust belief that all other players are perfectly rational relative to any compatible information about their choices".

According to the following Theorem 6, if the players have common belief that every player is perfectly rational and has a k-order robust belief that all other players are perfectly rational relative to any compatible information about their choices, then the strategy profile which is played must survive k + 1 iterations of DWDS followed by IDSDS. Theorem 6 Let s ∈ S DWDS k+1 -IDSDS and k > 0. Then:

|= CBel Agt AllPRatRBelPRat Agt,k →¬pl(s)
Note that, when k = 1, Theorem 6 and Theorem 5 coincide.

Before concluding, note that, because every A i is a total function, the epistemic conditions given in the antecedents of Theorems 3, 4, 5 and 6 are respectively sufficient conditions of the equilibria IDSDS, DWDS 1 -IDSDS, DWDS 2 -IDSDS and DWDS n -IDSDS. In particular,

|= CBel Agt AllWRat Agt → s∈S IDSDS pl(s) |= CBel Agt AllPRat Agt → s∈S DWDS 1 -IDSDS pl(s) |= CBel Agt (AllPRat Agt ∧ AllRBelPRat Agt ) → s∈S DWDS 2 -IDSDS pl(s) |= CBel Agt AllPRatRBelPRat Agt,k → s∈S DWDS k+1 -IDSDS pl(s) for k > 0 7 Related Work
As pointed out in the introduction, the main difference between the present approach and alternative epistemic characterizations of iterated weak dominance is that we use a semi-qualitative approach to uncertainty based on the notion of plausibility introduced by Spohn [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF], whereas existing epistemic analysis of iterated weak dominance are based on a quantitative representation of uncertainty in terms of probabilities. In this sense, the representation of uncertainty used in this paper is relatively more simple than the representation of uncertainty used in other approaches. For instance, in [START_REF] Stalnaker | Knowledge, belief and counterfactual reasoning in games[END_REF] Stalnaker presents a result similar to the preceding Theorem 4 whereas in [START_REF] Stalnaker | Belief revision in games: forward and backward induction[END_REF] he discusses a result similar to the preceding Theorem 5. Differently from the present approach, Stalnaker uses rich semantic structures combining probability measures over possible worlds, representing the uncertainty of players, with plausibility orderings over epistemic alternatives, in order to model belief revision policies.

Brandenburger et al. [START_REF] Brandenburger | Admissibility in games[END_REF]( s e ea l s o [START_REF] Brandeburger | The power of paradox: some recent developments in interactive epistemology[END_REF]) provide an epistemic characterization of iterated admissibility where uncertainty is represented using lexicographic probability systems (LPSs). An LPS assigns to every player a finite sequence of probability measures (p 1 ,...,p n ) with non-overlapping supports. The probability p 1 corresponds to a player's initial hypothesis about the behavior of the others, p 2 corresponds to the player's secondary hypothesis, and so on. The interpretation given to this sequence of probability measure is that for any 1 ≤ k < n the hypothesis at level k is infinitely more likely than the hypothesis at level k + 1. In their analysis of the epistemic conditions of iterated weak dominance based on LPSs, Brandeburger et al. define a concept of 'assumption' that is similar to the concept of robust belief used here and in Stalnaker's analysis. The idea is that a given player assumes that an event (or state of affairs) ϕ is true if and only if, according to the player, ϕ is infinitely more likeky than ¬ϕ.

In their logical characterization of iterated admissibility based on the concept of "all the agents know" [START_REF] Halpern | Multi-agent only knowing[END_REF], Halpern & Pass [START_REF] Halpern | A logical characterization of iterated admissibility[END_REF] consider probability structures of the form , s, F, PR 1 ,...,PR n ,whereŴ is a set of states, s is a function associating each state in to a strategy profile of a given game Ŵ, F is a -algebra over ,and for each player i in the game Ŵ, PR i associates with each state ω in a probability distribution PR i (ω) on ( , F).

Battigalli & Siniscalchi [START_REF] Battigalli | Strong belief and forward induction reasoning[END_REF] analyze the epistemic conditions of the concept of forward induction, that has been shown to be tightly related to the concept of iterated admissibility. Their analysis is based on conditional probability systems, a generalization of classical Bayesian probabilities that allow them to model the update and/or the revision of the players' beliefs, in the course of an extensive game. The fundamental concept of Battigalli & Siniscalchi's analysis is "strong belief" that is tightly related to our and Stalnaker's concept of "robust belief" and to Brandeburger et al.'s concept of "assumption". (See [START_REF] Asheim | Preference-based belief operators[END_REF] for a comparison between these three concepts).

A work that is similar in spirit to our approach is Baltag et al.'s analysis of the epistemic conditions of backward induction based on a purely qualitative notion of plausibility [START_REF] Baltag | Keep 'hoping' for rationality: a solution to the backward induction paradox[END_REF]. There are two main similarities between our approach and theirs. First of all, we share with them the idea of analyzing the epistemic conditions of solution concepts by using a relatively simpler representation of uncertainty based either on a purely qualitative approach or on a semi-qualitative one. Secondly, although Baltag et al.'s analysis and our analysis are focused on two different solution concepts, they employ a similar conceptual apparatus. For instance, Baltag et al.'s characterization of the epistemic conditions of backward induction employs a concept of "robust belief" that, as shown in Section 4.1, is closely connected to our concept of "relative robust belief". 17

Conclusive Remarks

In this paper we have developed a logical analysis of the epistemic conditions of iterated weak dominance in a semi-qualitative framework based on Spohn's theory of uncertainty and belief change. One might wonder whether the same kind of analysis could be made by using purely qualitative structures M = W, {E i : i ∈ Agt}, { i : i ∈ Agt}, V which result from replacing the plausibility grading function κ with a family of total preorders i over possible worlds, where w i v means that v is for agent i at least as plausible as w,a n dw ≡ i v and w ≺ i v mean respectively that (w i v and v i w)a n d( w i v and v i w). Let us consider this issue in more detail. Our analysis is mainly based on the notion of perfect rationality, as defined in Section 6.4, which is based on the notion of graded belief when max > 1. 18In order to define the concept of graded belief, it is necessary to rank the possible worlds that an agent envisages according to their degree of exceptionality (or plausibility) so that we can identify the set of worlds of rank 0, the set of worlds of rank 1, the set of worlds of rank 2, and so on. The total preorder i over possible worlds would be sufficient to make such a kind of ranking, as from a total order over a set of elements we can build a corresponding ranking over the elements in that set. Specifically, for all i ∈ Agt we could define:

Rank 0 i ={v ∈ W : ∃u ∈ E i (v) such that v ≺ i u}
and for all h ≥ 1:

Rank h i ={v ∈ W \ k<h Rank k i : ∃u ∈ E i (v) \ k<h Rank k i such that v ≺ i u}.
Given the preceding ranking over possible worlds, the plausibility grading function κ is definable as follows: for all i ∈ Agt and for all w ∈ W, κ(w, i) = h if and only if w ∈ Rank h i . Thus, while in our semi-qualitative approach the plausibility ranking is directly given by the function κ in the definition of a PDL-A model, in a purely qualitative approach, such as the one presented in [START_REF] Baltag | A qualitative theory of dynamic interactive belief revision[END_REF][START_REF] Van Benthem | Dynamic logic for belief revision[END_REF], it would be induced by the plausibility ordering i over the set of possible worlds.

Although from a semantic point of view, it seems clear that the same kind of analysis could be made after replacing the plausibility grading function κ with a family of total preorders i , it is not clear at all what the resulting logic would look like. More generally, it is not clear how to build a decidable logic with a complete axiomatization which is interpreted by means of purely qualitative structures of the form M = W, {E i : i ∈ Agt}, { i : i ∈ Agt}, V and which allows us to represent in the object language the epistemic conditions of iterated weak dominance, namely the concept common belief, the concept of robust belief about perfect rationality and the concept of graded belief on which the definition of perfect rationality is based. However, another important reason for choosing a semi-qualitative approach to uncertainty rather than a purely qualitative one is that the graded belief operator Bel h i ϕ, on which our analysis of the epistemic foundation of iterated weak dominance is based, is traditionally interpreted by means of the plausibility grading function κ (see the seminal work by Spohn [START_REF] Spohn | Ordinal conditional functions: a dynamic theory of epistemic states[END_REF]andalso [START_REF] Aucher | A combined system for upyear logic and belief revision[END_REF][START_REF] Laverny | From knowledge-based programs to graded belief-based programs, part II: off-line reasoning[END_REF][START_REF] Van Ditmarsch | Prolegomena to dynamic logic for belief revision[END_REF]). It would be a non-standard and unnatural choice to intrepret it via the total preorder i .

Another issue we intend to study in future research is a generalization of the approach to belief change presented in Section 3.2. Due to space restrictions, we only considered in this work an operation of belief change based on Spohn's concept of belief conditioning (Definition 4). We believe that our approach is flexible enough to allow us to model or at least to approximate other kinds of belief revision operation such as, e.g., the concepts of lexicographic upgrade and conservative upgrade in the sense of [START_REF] Van Benthem | Dynamic logic for belief revision[END_REF].

Appendix: Some Proofs

A.1 Proof of Theorem 1 Satisfiability in PDL-A is decidable.

Proof First of all note that the logic PDL-A --is nothing but the variant of PDL where each atomic knowledge program i is interpreted by an equivalence relation E i . This logic can be embedded into PDL extended with converse, by simulating every atomic knowledge programs i with a composite program (a ∪ a -1 ) * ,w h e r ea is an arbitrary atomic program interpreted by a binary relation R a (not necessarily an equivalence relation!) and a -1 is the converse of a. PDL with converse is decidable [START_REF] Harel | Dynamic logic[END_REF]. It follows that PDL-A --is decidable too.

Moreover, note that the problem of satisfiability in PDL-A -is reducible to the problem of global logical consequence in PDL-A --, where the special atoms exc i,h are just elements of the set of propositional variables Prop and the set of global axioms Ŵ is the set of all formulas of Proposition 13. That is, we have |= PDL-A -ϕ if and only if Ŵ |= PDL-A --ϕ. Observe that Ŵ is finite (because Num is finite). It is a routine task to verify that the problem of global logical consequence in PDL-A -- with a finite number of global axioms is reducible to the problem of satisfiability in PDL-A --. In particular, if Ŵ ={ χ 1 ,...,χ n },w eh a v eŴ |= PDL-A --ϕ if and only if |= PDL-A --CK Agt (χ 1 ∧ ... ∧ χ n ) → ϕ,w h e r eCK Agt is the common knowledge operator defined in Section 4.2. As the problem of satisfiability checking in PDL-A -- is decidable, it follows that the problem of satisfiability checking in the logic PDL-A - is decidable too.

Proposition 15 ensures that red provides an effective procedure for reducing a PDL-A formula ϕ into an equivalent PDL-A -formula red(ϕ).A sPDL-A -is decidable, PDL-A is decidable too.

Fig. 1

 1 Fig. 1 Example of iterated deletion of weakly dominated strategies

  :0≤k<h exc i,k for all h ∈ Num such that h ≥ 1, and exc i,<0 def =⊥ . The following proposition highlights that the preceding definition of the graded belief operator is indeed correct. For every PDL-A model M, for every world w in M and for every h ∈ Num, M, w |= Bel h i ϕ if and only if κ w,i (¬ϕ) = h.

	Proposition 2

Benthem et al.'s logic presented in

[START_REF] Van Benthem | Logics of communication and change[END_REF]

. This simple extension allows us to formalize a variety of individual and collective epistemic attitudes that have been studied in the literature (see Section 4) and that are not expressible in Aucher's logic. (For instance, Aucher's logic does not incorporate the concepts of common belief and common knowledge).

where exc i,<h def = k∈Num

This is the typical condition of iterated deletion of strongly dominated strategies (also called iterated strong dominance).

This condition is required in order to ensure that the agents will converge to a Nash equilibrium.

See[START_REF] Zvesper | Playing with information[END_REF] for an interesting analysis of iterated strong dominance after relaxing the assumption of logical omniscience.

Related concepts are the concept of 'assumption'[START_REF] Brandenburger | Admissibility in games[END_REF], 'strong belief'[START_REF] Battigalli | Strong belief and forward induction reasoning[END_REF] and 'full belief'[START_REF] Asheim | Admissibility and common belief[END_REF]. See[START_REF] Asheim | Preference-based belief operators[END_REF] for a comparative analysis of these four concepts.

It has to be noted that Spohn's notion of plausibility is measured on the set of ordinals. Here, for simplicity, it is assumed that plausibility is measured on the integer scale Num.

As for the ¬ϕ-part, due to the fact that Num is finite, we can only say that: if v and u are worlds in which ϕ is false, agent i considers v more plausible than u and, according to agent i, u has a degree of exceptionality equal or lower than maxα then, after revising his beliefs with ϕ, agent i will still consider v more plausible than u. More formally, for all v, u ∈ ||¬ϕ|| we have that if κ(u, i)>κ(v, i) and (u, v) ∈ E i and κ(u, i) ≤ maxα then κ * α i ϕ (u, i)>κ * α i ϕ (v, i).

Note that the three conditions 1, 2(a) and 2(b) cover all cases. Indeed, the third condition [i]¬ϕ is equivalent to ¬ϕ ∧[i]¬ϕ, because [i]¬ϕ →¬ϕ is valid.

The only difference with AGM theory is the condition i ϕ. AGM assumes that the new information ϕ must incorporated in the belief base, whereas we here assume that ϕ must incorporated in the belief base only if agent i envisages a world in which ϕ is true.

Note that the relation SB i matches exactly to the plausibility relation in the pure qualitative accounts on belief revision in Dynamic Epistemic Logic (DEL)[START_REF] Baltag | A qualitative theory of dynamic interactive belief revision[END_REF][START_REF] Van Benthem | Dynamic logic for belief revision[END_REF].

The only exception is Baltag et al.[START_REF] Baltag | Keep 'hoping' for rationality: a solution to the backward induction paradox[END_REF] who study a notion of "common stable true belief" which similar to our notion of "common safe belief".

Note that, when max = 1, the notion of perfectly rationality as defined in Section 6.4 and, consequently, our analysis of the sufficient condition for iterated weak dominance only require the operators of knowledge [i] and belief Bel i . However, this does not mean that the graded belief operator Bel h i is useless in general. It only means that it becomes unnecessary in the binary case, i.e., when it is assumed that agents rank possible worlds according to a two-value scale Num ={0, 1} for degrees of belief.

A.2 Proof of Theorem 4

Let s ∈ S DWDS 1 -IDSDS . Then:

Proof The proof is by induction.

Base case For all s ∈ S DWDS 1 -IDSDS 1 we prove that:

To prove (A1), it is sufficient to prove the following validity (B1), as CBel Agt AllPRat Agt → AllPRat Agt is valid by the item (10f) in Proposition 17. 19 For all s ∈ S DWDS 1 -IDSDS 1 we have that:

And to prove (B1), it is sufficient to prove that if s[i] ∈ S DWDS 1 -IDSDS i,1 then:

Let us prove (C1) by reductio ad absurdum. We assume that s[i] ∈ S DWDS 1 -IDSDS i, [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF] and M, w |= PRat i and M, w |= pl i (s [i]) for some arbitrary model M and world w in M. We are going to show that these three facts are inconsistent.

implies that: (D1) there is b i ∈ S i such that: (1) for all s ′ -i ∈ S -i we have s[i], s ′ -i ≤ i b i , s ′ -i and (2) there is s ′′ -i ∈ S -i such that s[i], s ′′ -i < i b i , s ′′ -i . M, w |= PRat i and M, w |= pl i (s[i]) together imply:

By the Constraint (Constr3), (D1) implies that: (F1) there is b i ∈ S i such that: (1) for all s ′ -i ∈ S -i we have

and (2) there are s ′′ -i ∈ S -i and u ∈ W and h ∈ Num such that (w, u)

But (G1) and (E1) are in contradiction. Inductive case For m > 1, we assume that if s ∈ S DWDS 1 -IDSDS m then:

(Inductive Hypothesis) |= CBel Agt AllPRat Agt →¬pl(s) 19 Indeed, CBel Agt AllPRat Agt implies i∈Agt Bel i PRat i which in turn implies i∈Agt i PRat i . The latter implies i∈Agt PRat i (by the validity (10f) in Proposition 17).

We are going to prove that if s ∈ S DWDS 1 -IDSDS m+1 then:

Let us take an arbitrary model M and world w and assume that M, w |= CBel Agt AllPRat Agt and M, w |= pl(s). We are going to show that s ∈ S DWDS

By the inductive hypothesis, Axiom K and the rule of necessitation for the belief operator Bel i , from (E2) it follows that if s ′ ∈ S DWDS 1 -IDSDS m then:

From (F2), (C2) and M, w |= pl(s) it follows that for every i ∈ Agt and for all b i ∈ S i either there is

. The latter implies that for every i ∈ Agt we have s

which is equivalent to s ∈ S DWDS 1 -IDSDS m+1 .

A.3 Proof of Theorem 5

Let s ∈ S DWDS 2 -IDSDS . Then:

Proof The proof is by induction. The proof of the inductive case goes exactly as the proof of the inductive case in the proof of Theorem 4.

Here we only prove the base case.

Base case For all s ∈ S DWDS 2 -IDSDS 2 we prove that:

To prove (A), it is sufficient to prove the following validity (B), as 20 For all s ∈ S DWDS 2 -IDSDS 2 we have that:

And to prove (B), it is sufficient to prove that if

then:

Let us prove (C) by reductio ad absurdum. We assume that s

and M, w

We are going to show that these three facts are inconsistent.

The rest of the proof makes use of the following Lemma 1.

Proof In order to prove Lemma 1, we first prove the following Lemma 2.

.

Proof (⇐) We first prove the right-to-left direction of the equivalence, after assuming that the set of strategy profiles is S ={ s 1 ,...,s n } for some n ∈ N. Suppose that

The latter implies that

To see this, just note that for any

By the preceding validity and the validity

(⇒) The left-to-right direction of the equivalence can be proved by reductio ad absurdum. We assume that: [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF]

for all s -i ∈ s -i and (2) there exists s ′ -i ∈ s -i such that M, w |= pl -i (s ′ -i ) ∧ AllPRat -i for some PDL-A + model M and world w in M. From the assumption (1), it follows that there is

. From the definition of PRat j , by the Constraint (Constr3) over PDL-A + models, we can prove that if s ′

and M, w |= pl j (s ′ -i [j]) then M, w |= ¬ PRat j . Hence, from the initial assumptions it follows that M, w |= ¬ PRat j . The latter is in contradiction with the assumption [START_REF] Asheim | Admissibility and common belief[END_REF].

Now assume that s

. By Lemma 2, it follows that Comp(pl

From the latter assumption it follows that M, w

it follows that pl -i (s ′ -i )∧¬AllPRat -i is valid. By the Constraint (Constr3) over PDL-A + models and the truth condition of the belief revision operator

. This completes the proof of Lemma 1.

From M, w |= χ -i ∈Beh -i :Comp(χ -i ,AllPRat -i ) RBel i (χ -i , AllPRat -i ), by Lemma 1, it follows that:

implies that:

and

We split the proof in the two subcases: (E1) and (E2).

Proof for the Case (E1) s

implies that:

From (F1) by the Constraint (Constr3) it follows that:

) and ( 4)

Proof for the case (E2) (E2) implies that:

and ( 3)

.

By the Constraint (Constr3), (F2) together with M, w |= PRat i and M, w |= pl i (s[i]) imply that:

and

But (G2) is in contradiction with (D).

A.4 Proof of Theorem 6

Let s ∈ S DWDS k+1 -IDSDS and k > 0. Then:

Proof The proof is by induction. The proof of the inductive case goes exactly as the proof of the inductive case in the proof of Theorem 4.

Here we only prove the base case.

Base case For all s ∈ S DWDS k+1 -IDSDS k+1 we prove that:

To prove (A1), it is sufficient to prove the following validity (B1), as CBel Agt AllPRatRBelPRat Agt,k → AllPRatRBelPRat Agt,k is valid (the proof of this validity is similar to the one given in the proof of Theorem 5 for the validity

For all s ∈ S DWDS k+1 -IDSDS k+1 we have that:

We prove something more general than (B1), namely we prove that for all J ∈ 2 Agt * and for all s J ∈ S DWDS k+1 -IDSDS J,k+1

The proof of (C1) is again by induction.

Base case For all s J ∈ S DWDS 2 -IDSDS J,2

we have to prove that:

In the proof of Theorem 5 we have proved something stronger than (A2), namely we have proved that if

Inductive case Let m be an integer such that m > 1. Let us assume that for all J ∈ 2 Agt * ,ifs J ∈ S DWDS m -IDSDS J,m then:

(Inductive Hypothesis) |= AllPRatRBelPRat J,m-1 →¬pl J (s J )

We are going to prove that if s J ∈ S DWDS m+1 -IDSDS J,m+1

then:

The proof is by reduction ad absurdum. We take an arbitrary PDL-A + model M and a world w in M. We assume that M, w |= AllPRatRBelPRat J,m and M, w |= pl J (s J ) and s J ∈ S DWDS m+1 -IDSDS J,m+1

. We are going to show that these three facts are inconsistent.

The rest of the proof is based on the following Lemma 3.

Lemma 3

Let m be an integer such that m > 1andletχ -i = s -i ∈s -i pl -i (s -i ) for some s -i ⊆ S -i . Then, Comp(χ -i ,AllPRatRBelPRat -i,m-1 ) if and only if there exists s -i ∈ s -i such that s -i ∈ S DWDS m -IDSDS -i,m

.

Proof of Sketch The proof of Lemma 3 is again by induction. We only prove the base case (i.e., when m = 2). (⇐) We first prove the right-to-left direction of the equivalence, after assuming that the set of strategy profiles is S ={ s 1 ,...,s n } for some n ∈ N. Suppose that

with s -i ∈ s -i . We can exhibit the following PDL-A + model M * = W * , {E * i : i ∈ Agt},κ * , {A * i : i ∈ Agt}, V * where:

With the help of Lemma 2 in Section A.3, it is straightforward to ver-

(⇒) The left-to-right direction of the equivalence can be proved by reductio ad absurdum. We assume that: [START_REF] Alchourrón | On the logic of theory change: partial meet contraction and revision functions[END_REF]

for all s -i ∈ s -i and (2) there exists s

RBel j (χ -j , AllPRat -j )) for some PDL-A + model M and world w in M. From the assumption (1), it follows that there is j

. From the definition of PRat j (s ′ -i [j]),b y the Constraint (Constr3) over PDL-A + models and with the help of Lemma 1 in Section A.3, we can prove that if s ′ -i [j] ∈ S DWDS 2 -IDSDS j,2

and M, w |= χ -j ∈Beh -j : Comp(χ -j ,AllPRat -j )

RBel j (χ -j , AllPRat -j ) then M, w |= ¬ PRat j (s ′ -i [j]). Therefore, from the initial assumption that M, w |= pl -i (s ′ -i ) it follows that M, w |= ¬ PRat j . The latter is in contradiction with the assumption (2), namely with M, w |= AllPRat -i .

M, w |= AllPRatRBelPRat J,m is equivalent to:

(B3) M, w |= AllPRat J ∧ i∈J χ -i ∈Beh -i :Comp (χ -i ,AllPRatRBelPRat -i,m-1 ) ×RBel i (χ -i , AllPRatRBelPRat -i,m-1 )

By inductive hypothesis, (B3) implies that for all s ′′ -i ∈ S DWDS m -IDSDS -i,m :

(C3) M, w |= i∈J χ -i ∈Beh -i :Comp ×(χ -i ,AllPRatRBelPRat -i,m-1 )RBel i (χ -i ¬pl -i (s ′′ -i ))

From (C3) and Lemma 3 it follows that for all i ∈ J:

and s -i ′′ ∈ S DWDS m -IDSDS -i,m then κ w,i (pl -i (s -i ′)) < κ w,i (pl -i (s -i ′′)).

(The proof of the preceding item (D3) is similar to the proof of the item (D) in the proof of Theorem 5 in Section A.3).

The rest of the proof proceeds as the proof of Theorem 5 in Section A.3 (starting from item (D)). For this reason, we do not repeat it here.