A Unified Framework for Common Knowledge of Rationality with Sets of Probabilities*

Hailin Liu

Abstract. The notion of imprecise probability can be viewed as a generalization of the traditional notion of probability.Several theories and models of imprecise probability have been suggested in the literature as more appropriate representations of uncertainty in the context of single-agent decision making.In this paper I investigate the question of how such models can be incorporated into the traditional game-theoretic framework.In the spirit of rationalizability,I present three new solution concepts called Γ-maximin rationalizability,E-rationalizability and maximally rationalizability.They are intended to capture the idea that each player models the other players as decision makers who all employ Γ-maximin,E-admissibility or maximality as their decision rules.Some properties of these solution concepts such as existence conditions and the relationships with rationalizability are studied.

1 Introduction

The theory of subjective expected utility (axiomatized by [17]) has become a widely-accepted normative theory for dealing with single-agent decision making under uncertainty.However,the assumption about the representation of uncertainty in this framework has often been criticized for being overly restrictive.In particular,Ellsberg ([5]) has argued that uncertainty,as opposed to risk,cannot be adequately represented by a single personal probability distribution.Inspired by this challenge,various alternative theories of decision making under uncertainty have been developed in the literature,e.g.,Gilboa and Schmeidler’s multiple priors model([7])and Schmeidler’s Choquet expected utility model([19]).In addition,there has been a vast amount of literature on alternative approaches to representing uncertainty in decision problems,such as upper and lower probabilities,sets of probability measures,belief functions,and so on (see [22] for a detailed discussion of the models of imprecise probabilities).

The Ellsberg paradox arises in single-agent decision making situations where uncertainty regarding some exogenous event is involved.Nevertheless,one would expect that similar situations of uncertainty could arise in multi-agent,interactive scenarios,where the considerations underlying uncertainty for each player are the other players’ strategy choices,rather than the state of nature.This naturally suggests a new line of research,which is to incorporate some model of uncertainty using imprecise probabilities into traditional game-theoretic frameworks.New conceptual issues arise in this approach to game under uncertainty,e.g.,how should solution concepts be defined given the new decision theoretic foundations.In recent years,there has been a growing literature on applying the aforementioned theories of imprecise probabilities in the context of games,which can be divided roughly into two categories depending on the way of addressing these conceptual issues.On the one hand there are those that investigate the consequences of allowing players’beliefs to be represented by imprecise probabilities in the framework of Nash equilibrium or its refinements.Dow and Werlang([3])introduce an equilibrium concept for two-player normal form games in which players’beliefs about the opponents’strategy choices are represented by non-additive probabilities and players are Choquet expected utility maximizers.Eichberger and Kelsey([4])extend Dow and Werlang’s equilibrium concept to normal form games withn-players and discuss some nice properties of this concept.By using the multiple priors model to represent players’uncertainty,Klibanoff([9])and Lo([13])provide two equilibrium-type solution concepts for normal form games with any finite number of players.Unlike these researchers,Liu and Xiong([12])present a different solution concept calledrobust equilibriumby extending the framework of the so-calledlinear tracing procedure([8]),to accommodate games with uncertainty where players’initial beliefs are modeled by a set of probability measures rather than a common prior.This concept can be viewed as a refinement of Nash equilibrium.

On the other hand,several studies have attempted to generalize the concept ofrationalizability([2,16]) in normal form games to accommodate notions of rationality other than subjective expected utility maximization.In addition to the idea of equilibrium with uncertainty aversion,another significant innovation introduced by Klibanoff ([9]) is the characterization of common knowledge of rationality under uncertainty for normal form games where each player attempts to maximize the minimum expected utility.Epstein ([6]) also considers normal form games and develops a general framework for discussing the implications of common knowledge of rationality in which the definition of rationality can accommodate different kinds of preference structures including the multiple priors model.

The approach to game theory with uncertainty I present in this paper is very much in the same spirit as Klibanoff’s and Epstein’s approaches,which embraces the essential idea of rationalizability,namely,to assume that each player models the opponents as the same kind of rational decision maker under uncertainty.As noted in previous literature,rationalizability captures the idea that each player attempts to deduce their opponents’rational behavior from the structure of the game by modeling her opponents as expected utility maximizers,where players’uncertainty about their opponents’ strategy choices are fully described by a single probability distribution.This paper explores the possibility of adapting this standard assumption by using a set of probability distributions to model uncertainty in normal form games.However,even in single-agent decision theory,there is no generally accepted criterion for decision making under uncertainty when uncertainty is depicted by a set of probability distributions.In view of this,this paper develops a general theoretical framework to analyze the implications of rationality and common knowledge of rationality in the sense that each player employs the same decision rule to choose the best strategy with respect to a set of probability distributions.In particular,I consider here three generalized decision rules named Γ-maximin([1,7]),E-admissibility([10]),andmaximality([22]).According to the first rule,a decision maker should choose an option that maximizes the minimum expected utility with respect to a set of probability distributions.And the second one constrains the decision maker’s admissible choices to those options that maximizes expected utility for some probability in the set of probabilities.In contrast,the third rule demands the decision maker to choose those options that are not strictly preferred by any other available choices.In analogy with rationalizability,I put forward three distinct but related game-theoretic solution concepts under uncertainty,in which each player is required to model the other players as the same kind of decision makers who use either Γ-maximin,E-admissibility or maximality to make decisions.This gives rise to the three solution concepts that we shall call Γ-maximin rationalizability,E-rationalizabilityandmaximally rationalizabilityrespectively.Just as Γ-maximin,E-admissibility and maximality are extensions of expected utility maximization,Γ-maximin rationalizability,E-rationalizability and maximally rationalizability all turn out to be generalizations of rationalizability.Example 1 in Section 4 illustrates the distinction among these solution concepts.

The main contribution of this paper is in providing a general game-theoretic framework which enables us to discuss how different decision rules can be incorporated into the framework of rationalizabiity in normal form games when uncertainty is depicted by a non-trivial set of probability distributions.This framework can be easily adapted to accommodate some other decision rules discussed in decision theory such as Maximality([22]).Although it turns out that the concept of Γ-maximin rationalizability coincides with Klibanoff’s and Epstein’s iterative definitions of rationalizability with uncertainty aversion(they used different terms for this concept),the current approach to rationalizability under uncertainty can be regarded as complementary work to their theories,since it provides an alternative way of characterizing the same solution concept.By applying this new definition,it is easier to check whether a strategy of a player is Γ-maximin rationalizable (or uncertainty aversion rationalizable).In a similar way,I define the concepts ofE-rationalizability and maximally rationalizability,which,to my knowledge,has not been explored in any previous study.

The rest of this paper proceeds as follows:Section 2 presents a brief review of the solution concept rationalizability,and discusses some of its properties.Section 3 motivates the idea of using imprecise probabilities to represent uncertainty in games.I then propose two solution concepts called Γ-maximin rationalizability andE-rationalizability,which extend the framework of rationalizability to contexts where a set of probabilities is used to represent uncertainty.Section 4 studies some properties of these solution concepts,and also includes an example to illustrate their difference.Section 6 concludes the paper and suggests possible future work.

2 Rationalizability

In contrast with the concept of Nash equilibrium where each player’s belief is required to coincide with her opponents’ strategies,the concept of rationalizability,proposed independently by[2]and[16],imposes a weaker requirement on players’beliefs.More precisely,it only demands players to obey the requirement of Bayesian rationality and common beliefs in Bayesian rationality.It attempts to account for rational behavior as the consequence of common knowledge of the game structure and the rationality of players,without imposing any further constraints on players’strategy choices.

Let us begin with some formal notations and definitions.Throughout this paper,we consider a finite normal or strategic form gameG ≡〈I,{Si},{ui}〉i∈I,whereI={1,2,...,n}is a finite set of players,Sidenotes a finite set of pure strategies(or actions)available to playeri,andui:S →R denotes playeri’s payoff function.We shall denote the set of playeri’s mixed strategies by Δi,which can be regarded as the set of all probability distribution overSi.For each mixed strategyδi ∈Δi,letδi(si) denote the probability assigned tosi.Recall that a strategy profile is aNash equilibriumif no player can benefit by merely changing her strategy while the other players keep theirs unchanged.More precisely,a mixed strategy profileδ* ∈Δ is a(mixed strategy)Nash equilibrium if for each playeri,for every mixed strategyδiof playeri.An alternative way to characterize the notion of Nash equilibrium is to define it in term of best response.We say that a strategyδi ∈Δiis abest responsetoδ-ifor playeriifuifor all∈Δi.Thus a strategy profile is a Nash equilibrium if each player’s strategy is a best response to the other players’strategies.For an arbitrary setXof strategies,we denote byH(X)the convex hull of the setX,namely,the smallest closed convex set containingX.

It is well known that the concept of rationalizability attempts to characterize rational strategic behavior that are consistent with the assumption that both the structure of the game and the rationality of the players are common knowledge to them.To be more specific,rationalizability in normal form games is defined based on the following assumptions:

·A1:Each player employs a subjective personal probability to express her belief about the other players’ strategy choice,which cannot conflict with any information available to her.

·A2:Each player attempts to maximize expected utility with respect to her subjective probability regarding her opponents’strategy choices.

·A3:The structure of the game,including the strategy space and payoff functions,and the fact that each player satisfies the above two assumptions are common knowledge.

Informally speaking,we can examine a player’s rationality by checking whether the actions chosen by that player are “rational” or not.We say that an action of a player is rational if there exists some belief regulated by the assumptions given above such that it is a best response to that belief.Thus,a strategyδiof playeriisrationalizableif she can justify her choice by explaining that(i)δiis rational,(ii)there exists some beliefμisuch thatδimaximizes her own expected utility with respect toμi,andμiassigns positive probability only to rational actions of her opponents,and(iii)there are beliefs of her opponents that make those actions rational and assign positive probability only to her rational actions,and so on.This suggests an intuitive way of defining rationalizability without invoking the iterative process originally suggested by[16].In order to present this formal definition,we have to make the notion of a belief and what we mean by a strategy being rational explicitly.

Definition 1.In a strategic form gameG,abeliefof playeri ∈I,denoted byμi,about the other players’strategy choices is a probability distribution over the set of the other players’strategies

Here we should draw a clear distinction between the concepts of belief and mixed strategy.A belief about playerihas the same mathematical form as a mixed strategy of playeri,which is normally found in the literature.However,the interpretations of both concepts are different(see[15]for a comprehensive discussion on the interpretations of mixed strategies).A mixed strategy of playeriis usually viewed as an explicit randomization over her pure strategies inSi.If playerichooses to play a mixed strategy,she commits herself to carry out the deliberate randomization.The main criticism of this interpretation of mixed strategy is that for each player there are usually infinitely many mixed strategies that yield her the same expected payoff as her mixed strategy equilibrium does,given her opponents’equilibrium behavior.But we are here concerned with a different solution concept called rationalizability.Thus,interpreting mixed strategies as objects of deliberate choice is appropriate within the current framework.On the other hand,a belief about playeriis a probability distribution on the set of playeri’s mixed strategies,which represents another player’s view about playeri’s strategy choice.It should not be confused with a randomization that is actually carried out by playeri.In that sense,we can say that players’mixed strategies should be understood as the objects of the beliefs about players’strategy choices,and the probability distribution given by a belief about playerimerely represents the likelihood that another player assigns to playeri’s mixed strategies.

Nevertheless,an essential feature of this formulation of belief is that it allows a player to believe that the other players choose their strategies according to certain correlated randomization devices,since a beliefμiof playeriis a probability measure overS-iand thus is an element of the setH(S-i).Note that a beliefμiof playeriis not necessarily a product of independent probability distributions on each of the setSjof actions forj ∈N{i}.That is,a beliefμiof playerineed not be identified as an element of the set of mixed strategies of her opponentsS-i.In addition,it is not difficult to see that the setS-iis strictly smaller than the setH(S-i)in games with more than 2 players.Hence we have deliberately used a different notationμifor a belief in the current framework in order to distinguish it from a mixed strategyδ-i.

It is assumed that each player always chooses an action to maximize her own expected payoff with respect to some belief about the opponents’strategies.A strategy being rational can then be defined precisely in terms of maximization of expected utility.

Definition 2.A strategyδiof playeriin a strategic form gameGis arationalstrategy if there exists a beliefμiof playerisuch thatδimaximizes playeri’s expected utility,that is,ui(δi,μi)≥ui()for allΔi.In this case,we say thatδiis abest responseto the beliefμi.

The key idea of the following characterization is to define an action (or pure strategy) to be rationalizable by considering each player’s introspective process of justifying her own strategy choice,based on the analysis of her opponents’ similar reasoning about their rational behavior.

Definition 3.In a strategic form gameG,an actionsi ∈Siof playeriis rationalizable if for each playerj ∈I,there exists a setZj ?Sjof actions such that:(i)si ∈Zi,and(ii)every actionsjinZjis a best response to some beliefμjof playerjwhose support is a subset ofZ-j.

Recall that the support of a beliefμiis defined as the set of pure strategies to whichμiassigns positive probabilities.The second condition above thus says that each player’s actions can be justifiable by some belief about the other players’strategies,which is based on those actions of her opponents that can be justifiable in the same way.As a matter of fact,this is implied by the assumption of common knowledge of the rationality of the players,which is the the essential part of the concept of rationalizability.

Whenever a new solution concept is put forward,a primary theoretical question is whether the proposed concept can give rise to at least one solution for games in general.Regarding the concept of rationalizability,the answer to this question is positive.

Proposition 2.1(Pearce,[16]).For finite normal form games,the set of rationalizable strategies is always nonempty and contains at least one pure strategy for each player.

We have considered above how to define the concept of rationalizability by using the notion of belief and the rationality of the players.As a matter of fact,the set of rationalizable actions can be further characterized for finite strategic games in terms of the familiar idea of dominance relations.As we shall see,this characterization for rationalizability gives rise to an operationalizable method for finding the set of rationalizable actions for finite games.Recall that the concept of rationalizability basically captures the idea that as a rational decision maker each player can only choose those strategies that are best responses to some beliefs regarding the other players’strategies.In other words,a rational player should not adopt a strategy that is not a best response to any belief about her opponents’ strategy choices.In the game-theoretic terminology,such a strategy is called a never-best response strategy.Thus one can see that the concept of rationalizability is closely related to the notion of never-best response strategy as defined below.

Definition 4.In a normal form gameG,an actionsiof playeriis anever-best responseif it is not a best response to any belief of playeri,that is,for every beliefμiof playerithere exists a strategyδi ∈Δisuch thatui(δi,μi)＞ui(si,μi).

In other words,there is no beliefμiof playeriabout her opponents’strategies with respect to which a never-best response actionsimaximizes her own expected payoff.This coincides exactly with the central idea of rationalizability,namely that the players are rational in the sense of maximizing expected utility.As mentioned above,each player should rule out the actions that are not best response to any belief,namely,never-best response actions.

Let us now turn to the familiar notion of strict dominance which will play a crucial role in the characterization of rationalizable actions,as we shall see below.

Definition 5.In a normal form gameG,an actionsiof playeriisstrictly dominatedif there exists a strategyδi ∈Δisuch thatui(δi,s-i)＞ui(si,s-i)for alls-i ∈S-i.

In words,whatever the other players do,playerican benefit from playing some other strategy rather than a strictly dominated strategy.Clearly,a rational player would never use a strictly dominated strategy.Otherwise the player’s choice violates the assumption of rationality in the sense of maximizing expected utility.At this point one may wonder whether the notion of never-best response is equivalent to the conception of strictly dominated action.It turns out that one can establish the equivalence between these two notions within the current framework.

Lemma 2.2(Pearce,[16]).In a strategic form game G,an action of player i is a never-best response if and only if is strictly dominated.

Suggested by the above lemma,we can show that the set of rationalizable actions can be obtained by iteratively deleting strictly dominated actions until we arrive at the stage where no more strictly dominated action can be further eliminated.Let us first formally define the process of iterated elimination of strictly dominated actions.

Observe that after a finite numbers of steps the process of iterated elimination of strictly dominated actions will certainly halt in the sense that there is no action that can be further eliminated,since we restrict our attention to finite games.Moreover,one can show that the procedure of iterated elimination of strictly dominated actions does not depend on the order that we proceed the elimination,that is,it always yields the same surviving set of actions for each player.

With the aid of this procedure,we can thus easily identify the set of rationalizable actions for each player in finite games,which thus provides a nice algorithm for finding rationalizable actions.

Proposition 2.3(Pearce,[16]).For any finite normal game G,the set of profiles of rationalizable actions coincides with the set of profiles that survives the process of iterated elimination of strictly dominated actions.

3 Rationalizability with Sets of Probabilities

Following the tradition of decision making under uncertainty,the concept of rationalizability assumes that each player’s belief regarding the other players’strategies is represented bya single personal probability measure.However,there are many convincing arguments for supporting imprecision in beliefs-even in the context of single-agent decision problems(see[5,22]).A number of alternative models to subjective expected utility theory have been proposed,which advocate the use of imprecise probabilities for dealing with uncertainty in decision problems(see,for instance,[7,10,22]).It is thus natural to incorporate these ideas into the traditional game-theoretic framework.Based on the rules of Γ-maximin,E-admissibility and maximality,we present here a generalized game-theoretic framework as an initial attempt to examine how modeling uncertainty with imprecise probabilities may provide insight into traditional game theory.In analogy with the concept of rationalizability,we propose three new game-theoretic solution concepts that are designed to capture the idea that each player models all the other players as rational decision makers who respects the criterion of Γ-maximin,E-admissibility or maximality.

An immediate question that is crucial to this investigation is:which model of imprecise probabilities should be assumed as representation of players’beliefs in strategic situations? There are a variety of mathematical models proposed in the literature to represent uncertainty in single-agent decision problems.For instance,lower previsions,upper and lower probabilities,sets of probabilities,non-additive probabilities,and belief functions(see[22]).Among these widely-discussed models of imprecise probabilities,a plausible method is to usea convex set of probability distributions,also called a credal set([11]),to represent a decision maker’s beliefs when confronted with uncertainty.A great advantage of this approach is that it allows us to deal with any state of insufficiencies in our information,including complete ignorance,in a unified way.Here we adopt this representation of uncertainty as the intended model for the players’beliefs regarding the other players’strategy choices.In order to distinguish it from the previous way of modeling beliefs,we will hereafter refer to a belief as a conjecture.Slightly modifying the formulation of belief in the framework of rationalizability,we define a conjecture of a player as follows:

Definition 7.In a strategic form gameG,aconjectureof playeri,denoted byCi,about the other players’ strategy choices is a (nonempty) convex set of probability measures over the opponents’actionsS-i.

Note that this way of representing players’beliefs is a natural generalization of using a single probability distribution,as discussed earlier in the context of rationalizability.Moreover,this representation of beliefs admits the possibility of a correlated conjecture in the sense that,a player’s conjecture may contain a probability distribution that cannot be obtained by independent mixtures over her opponents’strategies,for the elements of a conjecture are probability measures defined overS-i.

One can interpret each member in a player’s conjecture as the frequency of the strategy choices by her opponents,each of which is randomly drawn from a large population.More precisely,each player thinks that each of her opponents stands for a large set of players and has the same set of feasible choice.In this context,the probability distributions in playeri’s conjecture are viewed as the frequencies with which the members of the setS-iare used by those large populations.In light of this,a probability distribution in a conjecture of a player has a completely different meaning from a mixed strategy,even though they may look the same from a mathematical point of view.

Under the preceding interpretation,it is reasonable to consider the cases where the set of strategies for some player is not convex,but players’conjectures are required to be convex.We understand that it is standard practice in game theory to consider the mixed extensions of games,that is,to include all the mixed strategies.Nevertheless,we may want to model circumstances where only the pure strategies are available to the players,which can be suitably described in the current framework with our interpretation.

In the context of single-agent decision making,several decision rules such as Γmaximin([1,7]),E-admissibility([10]),andmaximality([22])have been discussed in the literature of imprecise probabilities(for a detailed comparison between these criteria see [18,20,21]).There is,however,no general agreement among decision theorists as to which is the right rule for judging rational decisions when uncertainty is expressed by a convex set of probability functions.Among these suggested criteria,the rule of Γ-maximin generalizes the principle of maximizing expected utility by simply taking the lower expected utility,thereby inducing a complete order on the decision set.More precisely,according to Γ-maximin,a rational decision maker should choose an option to maximize the minimum expected value with respect to a convex set of probabilities.This rule for decision making under uncertainty seems suitable for describing decision makers who areuncertainty averse,as it always takes the worst possible expected value as the base for maximization.Nevertheless,it has already been noted in[20]that the rule of Γ-maximin fails to distinguish between open and closed,convex and non-convex sets of probabilities,since choices based on this decision rule essentially reduces to binary comparisons which share the same supporting hyperplanes.It thus implies that the properties of closure and convexity concerning players’conjectures regarding their opponents’strategy choices are indistinguishable by Γ-maximin rationalizability.

The other decision criterion that we shall discuss below is often calledE-admissibility,which was implicitly mentioned in[17]and extensively advocated by Issac Levi([10]).According to this decision rule,an option isE-admissible if it maximizes expected utility relative to some probability distribution in the convex set of probabilities.In contrast with Γ-maximin,E-admissibility does not generate an order of options,but it does avoid the above-mentioned limitation,since it cannot be characterized by pairwise comparisons.As shown in the context of decision making,these two rules are not equivalent in the sense that they may recommend different sets of admissible options.Thus it is not surprising that the game-theoretic solution concepts defined based on these rules are not equivalent either,as illustrated by an example in the next section.

Another distinct way of extending the expected utility criterion is to require the set of optimal decisions to be those options that are not strictly preferred by any other available options.This generalization is commonly known asmaximality([22]) in the literature.More precisely,we say that an option is maximal relative to a set of possible choices if there does not exist any other available choice that has greater expected utility than it does for every probability distribution in the convex set of probabilities.

Under strategic situations,players are usually assumed to be uncertain about the other players’strategy behavior,and can only attempt to deduce their opponents’rational actions from the structure of the game and available information about their opponents’preferences.In most games,it is impossible for players to ascertain their opponents’ actual behavior.Due to the insufficient information about preferences and irreducible strategic considerations,any level of uncertainty revealed by the imprecision in the set of probabilities may occur in situations of strategic interaction.Since Γ-maximin,E-admissibility and maximality have been often discussed in the literature of decision theory,it is therefore interesting to study the cases where all the players would use the rule Γ-maximin,E-admissibility or maximality to choose their strategies in games.By analogy to the framework of rationalizability,we need to be explicit about what we mean by a strategy being rational under uncertainty.

Definition 8.In a strategic form gameG,a strategyδiof playeriis Γ-rational under uncertaintyif there exists a conjectureCiof playerisuch thatδimaximizes playeri’s minimum expected utility with respect toCi.In this case,we say thatδiis a Γ-maximin admissiblestrategy relative to the conjectureCi.

Likewise,we can define a notion calledE-admissible strategy in a game where players are assumed to useE-admissibility as the criterion for strategy choices.

Definition 9.In a strategic form gameG,a strategyδiof playeriisE-rational under uncertaintyif there exists a conjectureCiof playerisuch thatδimaximizes playeri’s expected utility for some probability inCi.In this case,we say thatδiis anE-admissiblestrategy relative to the conjectureCi.

Finally,in a similar fashion we can obtain a notion ofmaximally admissiblestrategy when considering maximality as the decision rule in games.

Definition 10.In a strategic form gameG,a strategyδiof playeriismaximallyrational under uncertaintyif there exists a conjectureCiof playerisuch that,there is no other strategyΔ having greater expected utility thanδidoes for each probability inCi.In this case,we say thatδiis amaximally admissiblestrategy relative to the conjectureCi.

Recall that the key idea of the concept of rationalizability is that each player regards the other other players as expected utility maximizers.It requires not only that players are rational in the sense of maximizing expected utility with respect some belief,but also that players’beliefs should be consistent with their opponents being rational in a similar way.The solution concept introduced below extends this idea to contexts,where each player is assumed to model the other players as decision makers who employ Γ-maximin,E-admissibility or maximality as the decision rule with respect to uncertainty.More specifically,we present a new solution concept that is meant to capture the idea that players are required to consider only those strategies that are rational under uncertainty,and that are supported by conjectures that do not contradict with their opponents being rational under uncertainty.

Now we need to specify the condition for a player’s conjecture being consistent with her opponents’rationality in the senses of Definition 8 and Definition 9 rather than in a traditional decision-theoretic sense.A natural suggestion is to require that each element of the conjecture assigns positive probability only to those actions of her opponents that are rational under uncertainty.Putting these ideas together,we can formally define the new solution concept called Γ-maximin rationalizability.

Definition 11.In a strategic form gameG,an actionsi ∈Siof playeriis Γmaximin rationalizable if for each playerj ∈I,there exists a setAj ?Sjof actions such that:(i)si ∈Ai,and(ii)every actionsjinAjis Γ-maximin admissible relative to some conjectureCjof playerjsuch that the support of each element ofCjis a subset ofA-j.

According to the above definition,one only needs to find a set of acts and a conjecture for each player in order to check whether a strategy is Γ-maximin rationalizable or not.Unlike the above formulation,Klibanoff ([9]) has provided an alternative characterization of rationalizability with uncertainty aversion(see the definition before Theorem 4),which is defined as an iterative reduction process on the strategies.We shall see that his definition turns out to be equivalent to the concept of Γ-maximin rationalizability defined above.As noted in[14],there are two distinct ways of defining rationalizability:one depends upon an iterated elimination procedure and the other does not.In the light of this,it seems fair to say that Klibanoff’s characterization and the above formulation follow exactly the two different ways to generalize rationalizability in normal form games to accommodate uncertainty aversion,although they actually correspond to the same solution concept.

Analogously,the other solution concept that we callE-rationalizability can be formally defined as follows.

Definition 12.In a strategic form gameG,an actionsi ∈Siof playeriisErationalizable if for each playerj ∈I,there exists a setAj ?Sjof actions such that:(i)si ∈Ai,and(ii)every actionsjinAjisE-admissible relative to some conjectureCjof playerjsuch that the support of each element ofCjis a subset ofA-j.

Similarly,we can formally define a notion calledmaximally rationalizabilityas follows.

Definition 13.In a strategic form gameG,an actionsi ∈Siof playeriis maximally rationalizable if for each playerj ∈I,there exists a setAj ?Sjof actions such that:(i)si ∈Ai,and(ii)every actionsjinAjis maximally admissible relative to some conjectureCjof playerjsuch that the support of each element ofCjis a subset ofA-j.

4 Properties of New Solution Concepts

The aim of this section is to establish some properties of the solution concepts Γmaximin rationalizability,E-rationalizability,and maximally rationalizability.Among other things,we will see that,Γ-maximin rationalizability can reasonably embrace a broader class of strategy profiles as outcomes under certain circumstances in comparison with rationalizability,whereasE-rationalizability and maximally rationalizability can be distinguished from Γ-maximin rationalizability based on the ideas originated in decision theory.In addition,we will characterize the condition under which these three solution concepts coincide.

4.1 General results

As we have noted,all these three decision rules,namely,Γ-maximin,E-admissibility and maximality,can be regarded as simple extensions of the principle of maximizing expected utility to contexts where uncertainty is modeled by a set of probability measures.It is obvious that these generalized rules lead to the same recommendations as the criterion of expected utility maximization provided that the set of probability measures is a singleton set.This enables us to show that the concepts of Γ-maximin rationalizability,E-admissibility and maximality do generalize the traditional notion of rationalizability to contexts where a set of probabilities is employed to represent uncertainty in games.

Proposition 4.1.For any strategic form game G and each player i,if an action of player i is rationalizable,then it isΓ-maximin rationalizable.This holds for Erationalizability and maximally rationalizability as well.

Proof.Suppose thatis rationalizable.According to Definition 3,we have that there exists a setZjof actions for each playerj ∈Isuch that both conditions specified in the definition are satisfied.SetAj ≡Zjfor every playerj.It immediately follows that.And it is clear that every action inAjis both Γ-maximin admissible,E-admissible and maximally admissible relative to some conjecture of playerjby considering the set containing only one probability distribution overA-j,as in this case Γ-maximin,E-admissibility and maximality are all equivalent to the principle of expected utility maximization.We can thus conclude thatis Γ-maximin rationalizable,E-rationalizable,and maximally rationalizable as well. □

According to Proposition 2.1,the set of rationalizable actions of each player is nonempty for any finite normal form games.By applying this result,we can easily establish the existences of Γ-maximin rationalizable,E-rationalizable and maximally rationalizable action in strategic games.

Corollary 4.2.For any strategic form game,there always exists at least oneΓmaximin rationalizable action for each player i.This holds for E-rationalizable and maximally rationalizable action as well.

4.2 Comparisons

At this point,the reader may wonder whether the sets of Γ-maximin rationalizable andE-rationalizable actions are in fact identical to the set of rationalizable actions.It has already noted in[6]that the concepts of Γ-maximin rationalizability and rationalizability are not equivalent when the analysis is restricted to only pure strategies.He also includes a generic game(see the game of Figure 1 in[6])that is designed to illustrate the difference.Yet he offers no explicit demonstration of such a difference.

It has been pointed out in[20]that an option that is Γ-maximin(or maximally)admissible may not be Bayes admissible.Inspired by this result,I show by the following example that the solution concepts defined based on Γ-maximin or maximality may induce a larger set of solutions compared to rationalizability.It also serves the purpose of illustrating how these newly proposed solution concepts work.

Example 1.Consider the 3×2 game shown in Figure 1.Unlike the usual setting which includes mixed strategies,we assume here that both players’feasible options are pure strategies only,that is,explicit randomization is excluded? no non-trivial mixed strategy is available to any player.

Figure 1 :A normal form game

It is easy to verify that only the pure strategiesDandRare rationalizable for player 1 and 2 respectively.The previous argument basically relies on the fact that player 1’s actionMis strictly dominated when mixed strategies are taken into account.As a matter of fact,in this game the set of rationalizable action is the same,regardless of whether we allow explicit randomization or not.To see this,note that the actionMis a never-best response,and thus does not belong to the support of any belief of her opponent.Therefore,the restriction imposed on the feasible options of the players does not alter the set of rationalizable actions for both players.

Nevertheless,I claim that all the actions of both players are Γ-maximin rationalizable in the sense of Definition 11.The crucial part for establishing the claim is to see that the actionMof player 1 is actually Γ-maximin rationalizable,even though it is not rationalizable.This can be shown by considering the following construction:(i)let the sets of actions for both players be specified as follows:A1={U,M}andA2={L,R},and (ii) assume that player 1’s and player 2’s conjecture is depicted respectively by the following convex sets:C1={P1(·):{L,R}→[0,1]|P1(·)is a probability and 0.2≤P1(R)≤0.6}andC2={P2(·):{U,M,D}→[0,1]|P2(·)is a probability,P2(D)=0,and 0.45≤P2(U)≤0.95}.

Under the specifications above,it is obvious that the first condition in Definition 11 is directly satisfied,since the actionMbelongs to the setA1specified for player 1.And it can be seen from Figure 2 and Figure 3 that the second condition is also satisfied,since player 1’s lower expected payoff given by the actionsUandMis the same with respect to the setC1,and the actionsLandRalso yield the same lower expected payoff to player 2 with respect to the setC2.We can thus say that every action inA1andA2is Γ-maximin admissible relative to the conjecturesC1andC2respectively.In addition,note that every probability distribution inC1andC2assigns positive probability only to those action inA2andA1respectively.We can therefore conclude that the actionMis Γ-maximin rationalizable.OnceMcan be Γ-maximin rationalized,it is then straightforward to verify that the other actions of both players are Γ-maximin rationalizable as well.

Figure 2 :Expected utility to player 1

Figure 3 :Expected utility to player 2

Furthermore,it is not difficult to see that all the actions of both players are maximally rationalizable as well,since all the three actions of player 1 are maximally rationalizable by considering the conjecture set consisting of all the probability distributions over{L,R}.

The above example illustrates that the set of Γ-maximin and maximally rationalizable actions may differ from the set of rationalizable actions in some cases.In particular,the former two solution concepts admit the actionMas a candidate for the outcome of the game,which is ruled out by the concept of rationalizability.Intuitively,if player 1 is completely ignorant about player 2’s strategy choices,it seems quite reasonable for player 1 to selectM,as it has the highest security level.AndMis not strictly preferred by the other two available actions for player 1.Thus one may say that the concept of Γ-maximin rationalizability and maximally rationalizable does capture our intuition in some games.

The result suggested by the above example is not surprising,since the concept of Γ-maximin rationalizability in fact employs a richer representation of uncertainty than that assumed by rationalizability.More precisely,Γ-maximin rationalizability allows each player to model her opponents as Γ-maximin decision makers under uncertainty,which in fact includes the expected utility model considered by rationalizability as a special case.Hence,the concept of Γ-maximin rationalizability gives rise to a broader class of solutions under certain circumstances.

Nevertheless,it has been shown in[20]that the criterion ofE-admissibility actually behaves rather differently from the rule of Γ-maximin and maximality in the context of individual decision making.It is therefore natural to expect that the solution concept ofE-rationalizability would not be equivalent to the notions of Γ-maximin rationalizability and maximally rationalizability in the game-theoretic context.In order to see this,consider again the game in Example 1.It is easy to see that player 1’s optionMis notE-admissible for any probability distribution overL,R.Based on this fact,we can then conclude thatMis notE-rationalizable,which is both Γmaximin rationalizable and maximally rationalizable as established above.Therefore,E-rationalizability are not generally equivalent to Γ-maximin rationalizability and maximality in the sense that they may lead to rather different sets of admissible actions for players.It is worthwhile pointing out thatE-rationalizability prescribes the same set of admissible actions as the one recommended by rationalizability in this example.It is not difficult to show that this holds for all finite normal form games.In this sense,the concept ofE-rationalizability has a more intimate relationship with the traditional notion of rationalizability compared to Γ-maximin rationalizability and maximally rationalizability.

Furthermore,there is another subtle difference betweenE-rationalizability and Γ-maximin rationalizability,which is based on some idea in decision theory.As mentioned before,in the context of individual decision making,Γ-maximin fails to distinguish among different convex sets of probabilities,whileE-admissibility is capable of distinguishing between any two closed convex sets of probabilities.Putting this into a game-theoretic context,we can show thatE-rationalizability and Γ-maximin rationalizability may lead to different sets of admissible options for a player given the same conjecture about opponents’strategy choices.In other words,even though the player holds the same belief model of the other players,E-rationalizability may recommend a different set of admissible options from the other suggested by Γmaximin rationalizability.To see this,consider Example 1 again.Suppose that player 1’s belief about player 2’s strategy choice is represented by the conjectureC1={P1(·):{L,R}→[0,1]|P1(·)is a probability and 0.4＜P1(R)≤0.6}.Under this belief model,bothMandDhave the same infimum of expectation,and thus they are Γ-maximin admissible.However,onlyDisE-admissible,sinceDstrictly dominatesMwith respect toC1.In this case,E-rationalizability and Γ-maximin rationalizability give rather different recommendations to player 1.

So far,we have shown how the notion of imprecise probabilities sheds light on the traditional game-theoretic framework,by illustrating the difference among Γmaximin rationalizability,maximally rationalizability and rationalizability,and further by examining the distinction betweenE-rationalizability and Γ-maximin rationalizability.However,it is also interesting to investigate when these solution concepts turn out to be equivalent.In other words,we want to give the conditions under which these newly developed solution concepts would reduce to the traditional notion of rationalizability given that we represent uncertainty by a closed and convex set of probabilities.

Some basic notation and definitions are necessary for the following discussion.We are concerned here with finite decision problems where uncertainty is modeled by a closed convex set of probability functions.We let Ω denote a finite state space and letOdenote a finite set of outcomes.An option (or act)fis a mapping from the state space Ω to the set of outcomesO.LetAbe a set of options available to the decision maker.As before,we will use the notationH(A)to denote the convex hull ofA.For sake of simplicity,we assume that the decision maker’s values for outcomes are determinate and are represented by a cardinal utility function.

Definition 14.LetAbe a set of options and letPbe a convex set of probability distributions on the underlying state space Ω.An optionf ∈AisBayes admissiblewith respect toPif there exists P∈Psuch thatfmaximizes the expected utility under P,that is,EP(f)≥EP(g)for allg ∈A.

The above criterion recommends selecting those options inAthat maximizes expected utility for at least one P∈P,which corresponds exactly to the idea ofEadmissibility.We can now present the classic result(see Corollary 3.9.6 in[22]and Theorem 1 in[18])in decision theory,which plays a crucial role in establishing the central result of this section.

Proposition 4.3.If the option set A is convex,then every option that is maximal admissible with respect to a closed convex set P of probability distributions is Bayes admissible with respect to P.That is,if f ∈A is not Bayes admissible,then there exists some g ∈A different from f such thatEP(g)＞EP(f)for allP∈P.

We can now characterize the condition under which the concepts of Γ-maximin rationalizability,E-rationalizability and maximally rationalizability are indeed equivalent to rationalizability.

Proposition 4.4.For any strategic form game G,if each player’s choice set is convex and each player’s conjecture regarding her opponents’ choices is represented by a closed convex set of probabilities,then the set ofΓ-maximin rationalizable actions is equal to the set of rationalizable actions.This holds for E-rationalizability as well.

Proof.(?):It follows directly from Proposition 4.1.

(?):Consider an arbitrary playeri ∈I.Suppose thatsiis not rationalizable.Then it follows from Proposition 2.3 thatsiis strictly dominated,which,by Lemma 2.2,implies thatsiis a never-best response.It thus follows thatsiis not a Bayes admissible action,since it is not a best response to any belief of playeri.Note that each player’s choice set is assumed to be convex.Hence,by Proposition 4.3,we have thatsiis not maximal admissible,that is,there exists someδiin playeri’s choice set such that playeri’s expected payoff toδiis strictly greater than her expected payoff tosiwith respect to any correlated belief regarding the other players’strategic behaviors.Accordingly,siis not Γ-maximin admissible relative to any conjecture,as any conjecture of playeriis a subset of the set of correlated beliefs about her opponents’strategy choices.We can therefore conclude that the actionsiis not Γ-maximin rationalizable,as required.

The result concerningE-rationalizability and maximally rationalizability can be established in a similar fashion. □

Klibanoff([9])also establishes the equivalence between Γ-maximin(or uncertainty aversion)rationalizability and iterated strict dominance(see Theorem 4),whose proof depends heavily on the equivalence of the iterative definitions of uncertainty aversion rationalizability and rationalizability.By contrast,the proof I present here uses essentially Proposition 4.3,and thus has a decision-theoretic flavor.To some extent,the above proof makes explicit why such an equivalence holds by providing an alternative justification based on an important result in decision theory.

The above result implies that Γ-maximin rationalizability,E-admissibility,maximally rationalizability and rationalizability all recommend the same set of strategies for each player as rational decisions for games,provided that players are allowed to consider the convex extensions of their choice sets.And it is quite standard in game theory to examine all the mixtures of the pure strategies.In view of this,we may say that the current framework provides a more general theoretical foundation for the concept of rationalizability.That is,the solutions suggested by rationalizability can be supported by a more general decision theory based on weaker assumptions.In that sense,rationalizability is a quite robust solution concept,which is implied merely by the assumption of common knowledge of players being Γ-maximin rational,Erational or maximally rational.

5 Discussion

In the preceding section,we established several central results concerning Γmaximin rationalizability,a concept which is based on the traditional solution concept of rationalizability.Recall that the concept of rationalizability can be fully characterized by the procedure of iterated elimination of strictly dominated actions,which furnishes us with an algorithm for finding rationalizable actions.A related question is whether there is any efficient procedure for identifying the set of Γ-maximin rationalizable actions for each player.Of course,we are concerned with the more general case where it is not assumed that each player’s choice set is convex,as we have already proved that Γ-maximin rationalizability coincides with rationalizability when the choice sets for the players are convex.So far we have not found the corresponding algorithm for the concept of Γ-maximin rationalizability.This section is mainly devoted to some discussions regarding the analogous algorithm.

Recall that the concept of Γ-maximin rationalizability may lead to a different set of solutions than the notion of rationalizability,as we have shown through an example in the previous section.In that example,all actions of both players,including the actionM,are Γ-maximin rationalizable,despite the fact that the actionMis not a best response to any precise belief regarding the other player’s strategy and thus is not rationalizable.An interesting point is that all of these Γ-maximin rationalizable actions are not strictly dominated by anyaction availableto the players,for it is assumed that both players can only select from the pure strategies.In light of this,a natural conjecture for the algorithm for Γ-maximin rationalizability is to restrict the application of strict dominance to the players’choice sets.More specifically,the set of Γ-maximin rationalizable actions is identical to the set of actions that survive the process of iterated elimination of strict dominated actions restricted to players’choice sets.In analogy with the regular notion of strict dominance,we can define the concept of restricted strict dominance as follows.

Definition 15.Consider a normal form gameG.LetAi ?Δidenote the set of strategies available to playeri.An actionsiof playeriisrestricted strictly dominatedinAiif it is strictly dominated by some strategy inAi,that is,there exists a strategyδi ∈Aisuch thatui(δi,δ-i)＞ui(si,δ-i)for allδ-i ∈H(A-i).

By utilizing this restricted version of strict dominance,the conjecture mentioned above can then be formulated as follows.

Conjecture 5.1.For a normal form gameGwith each playeri’s choice set denoted byAi,an actionsi ∈Aiis Γ-maximin rationalizable if and only if it is not restricted strictly dominated inAi.

Unfortunately,it turns out that the equivalence between the concept of Γ-maximin rationalizability and the notion of restricted strict dominance does not hold in general.The following slight modification of the game in Figure 1 refutes the conjecture formulated above.Likewise,the game shown in Figure 4 has two players denoted by player 1 and 2 as before.We assume that each player can only select from their pure strategies,that is,no randomized mixture is available for both players.

Figure 4 :A Counterexample

Figure 5 :EU for the Counterexample

We claim that in this game player 1’s actionsU,M,andDare Γ-maximin rationalizable,and player 2’s actionsLandRare Γ-maximin rationalizable.To see this,note that these actions are those strategies that survive the process of iterated elimination of strictly dominated actions formulated in Definition 6,and thus are rationalizable actions,which implies,by Proposition 4.1,that they are Γ-maximin rationalizable.To rebut the above conjecture,let us consider player 1’s actionE.On the one hand,we can verify that the actionEof player 1 isnotΓ-maximin rationalizable,as there is no conjectureC1of player 1 such that the actionEis Γ-maximin admissible relative toC1.On the other hand,it is not difficult to see that the actionEisnotrestricted strictly dominated with respect to player 1’s choice set{U,M,D,E}.Hence,there is an action of a player that is not restricted strictly dominated,but is not Γ-maximin rationalizable in the sense of Definition 11.This contradicts the equivalence result stated above.

Now let us reconsider the definition of Γ-maximin rationalizability.For an actionsiof playerito be Γ-maximin rationalizable,it is necessary to identify a convex setCiof probability distributions over the other players’ strategies,such thatsiis Γmaximin admissible relative toCi.It is then logically possible to check whether an actionsiis Γ-maximin rationalizable,by examining all the possible convex sets of probabilities over her opponents’ strategy choices.Of course,this method seems unfeasible,for it may require us to check infinitely many convex sets.It would be nice if we could impose some constraints on those convex sets so as to narrow the scope of the examination.A possible method is to consider only those convex sets that include some“critical”probabilities as their boundaries.Let us make clear what we mean by“critical probabilities”.

Definition 16.Consider a normal form gameG.LetAi ?Δidenote the set of strategies available to playeri.A probability distribution P onH(A-i)is critical for playeriif it assigns probability 0 to some pure strategy profiles-1∈A-i,or some of the strategies inAiyield playerithe same expected payoff with respect to P.

Observe that there are only 6 critical probability distributions for player 1 in the game shown in Figure 5.With the aid of the above definition,we can now formulate the idea just mentioned precisely as follows.

Conjecture 5.2.For a normal form gameGwith each playeri’s choice set denoted byAi,an actionsi ∈Aiis Γ-maximin rationalizable if and only if there exists a convex setCiof probability distributions onH(A-i)such that its boundaries are some of the critical probability distributions andsiis Γ-maximin admissible relative toCi.

It is not difficult to verify that this conjecture is indeed correct for the game in Figure 5,as there are only 15 convex sets that use some of the 6 critical probabilities as boundaries.Nevertheless,whether the above conjecture holds in general needs further investigation.If this can be proved to be true,then we have a relatively efficient way for finding Γ-maximin rationalizable actions in games,since to identify the critical probability distribution only requires us to solve some linear equations.

6 Concluding Remarks

A variety of mathematical models have been discussed in the literature to deal with decision making under uncertainty in single-agent decision problems.In contrast with canonical Bayesian decision theory,which uses just one probability function to represent a decision maker’s uncertainty,these models use imprecise probabilities,such as a nontrivial set of probability functions,to represent uncertainty.Based on this idea,I have developed in this paper a general theoretical framework for analyzing how different decision rules can be incorporated into the framework of normal-form rationalizability when uncertainty is represented by imprecise probabilities.

More precisely,I extended the notion of rationalizability to the case where players’ conjectures about opponents’ strategy choices are represented by a convex set of probability measures,instead of a unique probability function.In the spirit of rationalizability,I introduced a solution concept called Γ-maximin rationalizability,which captures the idea that each player models the other players as Γ-maximin decision makers with respect to sets of probabilities representing uncertainty?similarly,I also defined another solution concept namedE-rationalizabilityandmaximally rationalizability.It is easy to see that all of these three new solution concepts include the concept of rationalizability as a special case when the set of probability measures contains only a single probability function.In addition,I have shown by an example that these concepts are not equivalent.I have also identified the conditions under which these solution concepts coincide with each other.

One natural project for future work is to apply some other decision rules like maximality to interactive situations,in a way similar to the framework developed in this paper.And it also seems natural to extend the current framework to the context of extensive form games in which sequential decisions are involved.In this way,one can develop a general theory of games under uncertainty.