《博弈论》（英文版） lect 2 (Iterated)Best Response Operators.pdf_大学文库

Definition 1 Fix a finite normal-form game G=(N, (Ai, Lien), a player i E I and a probability measure a_i E A(A-i. An action ai E Ai is a best reply to the belief a-i iff ∑a-(a-)u(an,a-)≥∑a-(a-)u1,a-)1∈A In finite games, expected payoffs are always well-defined. Not so for games with infinite action spaces: even assuming a nice measure-theoretic structure, it is not hard to construct (mildly pathological) examples in which payoff functions are not integrable Thus, a better definition for infinite games is the following. Assume that, for every player i E N, the set of actions(Ai, Ai) is a measure space. Endow the product sets A and A-i with the natural product sigma-algebras, denoted A and A_i. Finally, assume that ui is A- measurable. The sigma-algebras on the set of actions will be indicated explicitly for infinite Definition 2 Fix a normal-form game G=(N, (Ai, Ai, uiieN), a player i E N and a belief a-i E A(A-i, A-i). An action a; E Ai is a best reply to the belief a-i iff the Lebesgue integralS ui(ai, a-i)a-i(da )exists, and moreover u(4,a-)a-()2/a(0,a-)a-()∈A whenever the right-hand side integral exists I emphasize that integrals are taken(here and in the following) in the Lebesgue sense Even if expected payoffs are well-defined, the very structure of the game might lead to the non-existence of best replies. An obvious example arises in the Bertrand price competition game. Example. Two firms produce and sell the same good, facing a market of size Q, and zero fixed and marginal cost; finally, the two firms compete by posting unit prices pi, i=1, 2. Assume that consumers have unit demand and buy from the cheapest producer; if P1= P2 buy from each firm with probability 2 Suppose that Firm 1 expects Firm 2 to post a price equal to p2= 2; this corresponds to a degenerate belief, concentrated on 2. Then any price p1 >2 yields 0, any price p1 2 yields Qpl, and P1=P2=2 yields 22=Q. Clearly no price pi satisfies our definition of a best reply The conditions for the existence of best replies are related to those which guarante the existence of an optimum. We need to specify a topology Ti on every action space A 2

Definition 1 Fix a finite normal-form game G = (N,(Ai , ui)i∈N ), a player i ∈ I and a probability measure α−i ∈ ∆(A−i). An action ai ∈ Ai is a best reply to the belief α−i iff X A−i α−i(a−i)ui(ai , a−i) ≥ X A−i α−i(a−i)ui(a 0 i , a−i) ∀a 0 i ∈ Ai . In finite games, expected payoffs are always well-defined. Not so for games with infinite action spaces: even assuming a nice measure-theoretic structure, it is not hard to construct (mildly pathological) examples in which payoff functions are not integrable. Thus, a better definition for infinite games is the following. Assume that, for every player i ∈ N, the set of actions (Ai , Ai) is a measure space. Endow the product sets A and A−i with the natural product sigma-algebras, denoted A and A−i . Finally, assume that ui is Ameasurable. The sigma-algebras on the set of actions will be indicated explicitly for infinite games. Definition 2 Fix a normal-form game G = (N,(Ai , Ai , ui)i∈N ), a player i ∈ N and a belief α−i ∈ ∆(A−i , A−i). An action ai ∈ Ai is a best reply to the belief α−i iff the Lebesgue integral R A−i ui(ai , a−i)α−i(dai ) exists, and moreover Z A−i ui(ai , a−i)α−i(dai ) ≥ Z A−i ui(a 0 i , a−i)α−i(dai ) ∀a 0 i ∈ Ai whenever the right-hand side integral exists. I emphasize that integrals are taken (here and in the following) in the Lebesgue sense. Even if expected payoffs are well-defined, the very structure of the game might lead to the non-existence of best replies. An obvious example arises in the Bertrand price competition game. Example. Two firms produce and sell the same good, facing a market of size Q, and zero fixed and marginal cost; finally, the two firms compete by posting unit prices pi , i = 1, 2. Assume that consumers have unit demand and buy from the cheapest producer; if p1 = p2, consumers buy from each firm with probability 1 2 . Suppose that Firm 1 expects Firm 2 to post a price equal to p2 = 2; this corresponds to a degenerate belief, concentrated on 2. Then any price p1 > 2 yields 0, any price p1 < 2 yields Qp1, and p1 = p2 = 2 yields 2Q 2 = Q. Clearly no price p1 satisfies our definition of a best reply. The conditions for the existence of best replies are related to those which guarantee the existence of an optimum. We need to specify a topology Ti on every action space Ai ; 2

furthermore, we assume that the relevant sigma-algebra in the definition of a best reply is the corresponding Borel sigma-algebra B(Ti)(hence, ui ()is Borel-measurable if it is continuous). Finally, we assume product sets are endowed with the product topology and the induced Borel product sigma-algebra Proposition 0.1 Consider a game G=(N, (Ai, Ii, uiieN) and fix a player i E N. If ui ( is bounded and continuous, and Ai is a compact metrizable space, then for every measure a-i∈△(A-a,B(T) there exists a best reply a;∈A Proof: We need to show that the map p: A,HJA ui(ai, a-i)a-i(da-i) is continuous Since A; is a metric space, sequences characterize continuity. Thus, fix a sequence ai-ai in A;. By assumption, ui(ah, a-i)ui(ai, a-i)for every a_i E A-i, and ui is bounded Thus, by Lebesgue's Dominated Convergence theorem, p(ai-p(ai).B Observe that, in the above proof, it is essential that expectations be defined in the Lebesgue sense: otherwise, stronger conditions are required on the payoff functions and action spaces There are two reasons why we are interested in infinite games. First, for Nash equilibria to exist one must enlarge the players' action spaces to include all mixtures of strategies thus, effectively, one is looking at an infinite game, in which every strategy set is a simplex, hence a compact subset of Euclidean space, and every payoff function is continuous(because the expected payoff from a mixed strategy profile is linear in the probabilities). Thus, the preceding result applies Second. several interesting economic models lend themselves to a formulation involving infinite strategy spaces. Thus, getting some exposure to the issues that arise in such settings can be useful The Best Reply Correspondence Recall that a correspondence is a set-valued function. Since, in general, Player i may have more than one best reply to a belief a-i E A(A-i, A-i), we use correspondences to describe the mapping from beliefs to best replies Definition 3 Fix a game G=(N, (Ai, AieN) and a player i E N. The best-reply corre- spondence for player i, ri: A(A-i, A-i)= Ai, is defined by va-∈△(A-,A-),a1∈ra(a-)台a; is a best reply given a- The preceding proposition then gives conditions under which the best-reply correspon- dence is nonempty

furthermore, we assume that the relevant sigma-algebra in the definition of a best reply is the corresponding Borel sigma-algebra B(Ti) (hence, ui(·) is Borel-measurable if it is continuous). Finally, we assume product sets are endowed with the product topology and the induced Borel product sigma-algebra. Proposition 0.1 Consider a game G = (N,(Ai , Ti , ui)i∈N ) and fix a player i ∈ N. If ui(·) is bounded and continuous, and Ai is a compact metrizable space, then for every measure α−i ∈ ∆(A−i , B(Ti)) there exists a best reply ai ∈ Ai . Proof: We need to show that the map ϕ : Ai 7→ R A−i ui(ai , a−i)α−i(da−i) is continuous. Since Ai is a metric space, sequences characterize continuity. Thus, fix a sequence a k i → ai in Ai . By assumption, ui(a k i , a−i) → ui(ai , a−i) for every a−i ∈ A−i , and ui(·) is bounded. Thus, by Lebesgue’s Dominated Convergence theorem, ϕ(a k i ) → ϕ(ai). Observe that, in the above proof, it is essential that expectations be defined in the Lebesgue sense: otherwise, stronger conditions are required on the payoff functions and action spaces. There are two reasons why we are interested in infinite games. First, for Nash equilibria to exist one must enlarge the players’ action spaces to include all mixtures of strategies; thus, effectively, one is looking at an infinite game, in which every strategy set is a simplex, hence a compact subset of Euclidean space, and every payoff function is continuous (because the expected payoff from a mixed strategy profile is linear in the probabilities). Thus, the preceding result applies. Second, several interesting economic models lend themselves to a formulation involving infinite strategy spaces. Thus, getting some exposure to the issues that arise in such settings can be useful. The Best Reply Correspondence Recall that a correspondence is a set-valued function. Since, in general, Player i may have more than one best reply to a belief α−i ∈ ∆(A−i , A−i), we use correspondences to describe the mapping from beliefs to best replies. Definition 3 Fix a game G = (N,(Ai , Ai)i∈N ) and a player i ∈ N. The best-reply correspondence for player i, ri : ∆(A−i , A−i) ⇒ Ai , is defined by ∀α−i ∈ ∆(A−i , A−i), ai ∈ ri(α−i) ⇔ ai is a best reply given α−i The preceding proposition then gives conditions under which the best-reply correspondence is nonempty. 3

Correlated Rationalizability and Iterated Dominance Having disposed of all required technicalities, let us go back to our "informal equation Rational Behavior Assumptions about Beliefs= Solution Concepts Fix a game G=(N, (Ai, Ti, uiieN) and assume that each(Ai, Ii) is a compact metrizable space(you can also assume that each Ai is finite, as far as the substantive arguments are concerned) and that payoff functions are continuous We begin by asking: what is a plausible outcome of the game, if we are willing to assume that players are(Bayesian) rational? The answer should be clear: we can only expect an action profile(alien to be chosen iff, for every player i E N, ai E rila_i)for some a-∈△(A-2B() That is: if we think that players are "good Bayesians, " we should expect them to formu- late a belief about their opponents choice, and play a best reply given that belief. equiva- lently, we should expect a rational player to choose an action only if it that action is justified by some belief This exhausts all the implications of Bayesian rationality: in particular, we do not pos talate any relationship between the beliefs justifying the actions in any given profile In very simple games, Bayesian rationality is sufficient to isolate a unique solution: for instance, this is true in the Prisoner's Dilemma. However, in Matching Pennies, the Row player(who wants to match) may choose H because she expects the Column player to also choose H, whereas the Column player (who wants to avoid matches) actually chooses T because he(correctly, it turns out)expects the Row player to choose H. Indeed, it is easy to see that any action profile is consistent with Bayesian rationality in Matching Pennies However one might reason as follows If I, the theorist, am able to rule out certain actions because they are never best-replies, perhaps the players will be able to do so, too. But, if so, it seems easonable to assume that their beliefs should assign zero probability to the col- lection of eliminated actions. This entails a further restriction on the collection of actions that they might choose That is, in addition to assuming that players are Bayesian rational, we may be willing to assume that they believe that their own opponents are also Bayesian rational. This is precisely the type of assumption about beliefs referred to in our "informal equation. It is also a very powerful idea

Correlated Rationalizability and Iterated Dominance Having disposed of all required technicalities, let us go back to our “informal equation” Rational Behavior + Assumptions about Beliefs = Solution Concepts. Fix a game G = (N,(Ai , Ti , ui)i∈N ) and assume that each (Ai , Ti) is a compact metrizable space (you can also assume that each Ai is finite, as far as the substantive arguments are concerned) and that payoff functions are continuous. We begin by asking: what is a plausible outcome of the game, if we are willing to assume that players are (Bayesian) rational? The answer should be clear: we can only expect an action profile (ai)i∈N to be chosen iff, for every player i ∈ N, ai ∈ ri(α−i) for some α−i ∈ ∆(A−i , B(Ti)). That is: if we think that players are “good Bayesians,” we should expect them to formulate a belief about their opponents’ choice, and play a best reply given that belief. Equivalently, we should expect a rational player to choose an action only if it that action is justified by some belief. This exhausts all the implications of Bayesian rationality: in particular, we do not postulate any relationship between the beliefs justifying the actions in any given profile. In very simple games, Bayesian rationality is sufficient to isolate a unique solution: for instance, this is true in the Prisoner’s Dilemma. However, in Matching Pennies, the Row player (who wants to match) may choose H because she expects the Column player to also choose H, whereas the Column player (who wants to avoid matches) actually chooses T because he (correctly, it turns out) expects the Row player to choose H. Indeed, it is easy to see that any action profile is consistent with Bayesian rationality in Matching Pennies. However, one might reason as follows: If I, the theorist, am able to rule out certain actions because they are never best-replies, perhaps the players will be able to do so, too. But, if so, it seems reasonable to assume that their beliefs should assign zero probability to the collection of eliminated actions. This entails a further restriction on the collection of actions that they might choose. That is, in addition to assuming that players are Bayesian rational, we may be willing to assume that they believe that their own opponents are also Bayesian rational. This is precisely the type of assumption about beliefs referred to in our “informal equation.” It is also a very powerful idea: 4

Example: Consider a two-firm version of the Cournot quantity competition game, with action spaces A;=0, 1] and payoffs ui( ai, a_i)=(2-ai-a-i)ai: that is, marginal costs are zero, and inverse demand is given by P(a)=2-q Notice that Player i's expected payoff depends linearly on Player -i's expected quantity thus, our analysis can be restricted to degenerate (point)beliefs without loss of generality For any a_i E A-i, Player i's best reply is found by solving Inax so Tila Then notice that no a; E[0, 2)is ever a best reply: after all, even if a-i=l, there would still be residual demand in the market, and consumers would be willing to pay 1 dollar for an dditional marginal unit of the good. That is, Player i is actually facing the residual inverse demand curve P(ai)=1-ai, so setting ai=,(the corresponding monopoly quantity)is optima This is true for i= 1, 2. Thus, assume that Player i understands that a-iE 1]: that is, Player i believes that, since her opponent is rational, he will never produce less than units of the good. But then, producing ai E(, 1] units cannot be a best reply against a belief satisfying this restriction. Since, moreover, we have already concluded that quantities ai E0, 5)must be discarded on the basis of rationality considerations alone, the assumptions Bayesian rationality Belief in the opponent,s Bayesian rationality already imply that only action profiles(a1, a2) with ai E [, i should be expected to Once we are willing to make this assumption about the players beliefs, it becomes natural at least conceive the possibility that the players themselves might contemplate it. This leads to a hierarchy of hypotheses about mutual belief in rationality. That is, we might think that players are Bayesian rational (2) players believe that their opponents are also Bayesian rational (3)players believe that their opponents believe that their own opponents are Bayesian rational: and so on The following definition captures the implications of these assumptions Definition 4 Fix a game G=(N, (Ai, Ti, ui)iEN ) For every player iE N, let A9=Aj.For k≥1 and for every i∈I, let ai∈ A' iff there exists a-∈△(A-,B(T-) such that

Example: Consider a two-firm version of the Cournot quantity competition game, with action spaces Ai = [0, 1] and payoffs ui(ai , a−i) = (2−ai −a−i)ai : that is, marginal costs are zero, and inverse demand is given by P(q) = 2 − q. Notice that Player i’s expected payoff depends linearly on Player −i’s expected quantity; thus, our analysis can be restricted to degenerate (point) beliefs without loss of generality. For any a−i ∈ A−i , Player i’s best reply is found by solving max ai∈[0,1] (2 − ai − a−i)ai , so ri(a−i) = 1 − 1 2 a−i Then notice that no ai ∈ [0, 1 2 ) is ever a best reply: after all, even if a−i = 1, there would still be residual demand in the market, and consumers would be willing to pay 1 dollar for an additional marginal unit of the good. That is, Player i is actually facing the residual inverse demand curve P R(ai) = 1 − ai , so setting ai = 1 2 (the corresponding monopoly quantity) is optimal. This is true for i = 1, 2. Thus, assume that Player i understands that a−i ∈ [ 1 2 , 1]: that is, Player i believes that, since her opponent is rational, he will never produce less than 1 2 units of the good. But then, producing ai ∈ ( 3 4 , 1] units cannot be a best reply against a belief satisfying this restriction. Since, moreover, we have already concluded that quantities ai ∈ [0, 1 2 ) must be discarded on the basis of rationality considerations alone, the assumptions of Bayesian rationality + Belief in the opponent’s Bayesian rationality already imply that only action profiles (a1, a2) with ai ∈ [ 1 2 , 3 4 ] should be expected. Once we are willing to make this assumption about the players’ beliefs, it becomes natural to at least conceive the possibility that the players themselves might contemplate it. This leads to a hierarchy of hypotheses about mutual belief in rationality. That is, we might think that: (1) players are Bayesian rational; (2) players believe that their opponents are also Bayesian rational; (3) players believe that their opponents believe that their own opponents are Bayesian rational; and so on. The following definition captures the implications of these assumptions. Definition 4 Fix a game G = (N,(Ai , Ti , ui)i∈N ). For every player i ∈ N, let A0 i = Ai . For k ≥ 1 and for every i ∈ I, let ai ∈ Ak i iff there exists α−i ∈ ∆(A−i , B(T−i)) such that 5

(1)a;∈r(a-) 2)a-i(∏ An action ai E Af is said to be k-correlated rationalizable; an action ai E nk>1 Af is said to be correlated rationalizable Part(2)in the above definition captures the idea that, at each step k we are willing to impose the assumption that players are able to perform k-l steps of eductive reasoning about their opponents. Although this is not explicitly required in the definition, this corresponds to progressively more stringent assumptions about rationality; if action sets are finite, this implies that correlated rationalizable strategies exist(why?) Proposition 0. 2 Fix a game G=(N, (Ai, Ti, uiieN). Then, for every i E N and k>1 AFCA Proof: The claim is true for k= 1. Assume it is true for some k, fix i E N and pick ∈A by definition, there exists △(A-a,B(T ch that a;∈r(a a-i(Aki)=1. Since by the induction hypothesis Ak C A-, this implies a_i(Ak- )=1 hence,a;∈A, as claimed.■ Independent rationalizability, or(in keeping with standard terminology)"rationalizabil ity" tout-court, incorporates the additional restriction that players beliefs are actually in- dependent product measures on their opponents'action profiles; that players believe that their opponents' beliefs are independent; that they believe that their opponents believe that their respective opponents' beliefs are independent; and so on and so forth Definition 5 Fix a game G=(N, (Ai, Ti, uiieN). For every player i E N, let r=A;. For k≥1 and for every i∈l,leta;∈ Ri iff there exists a-a∈△(A-,B(T-) such that (2)a-(I≠:B-1)=1 (3)a-i is a product measure on A-i, BT-i) An action a,E Rk is said to be k-rationalizable; an action a; E nk>I Ri is said to be rationalizable I conclude this section with two notes pertaining to the interpretation of (correlated) ationalizability First, I emphasize that, although we have motivated(correlated )rationalizability with informal assumptions about rationality and beliefs, we have been quite vague in definin what we mean by statements such as, "Player i believes that Player -i is rational. We have claimed that this "implies"that Player i's beliefs should assign positive probability only to those strategies of Player -i which can themselves be justified by some belief

(1) ai ∈ ri(α−i); (2) α−i( Q j6=i A k−1 j ) = 1. An action ai ∈ Ak i is said to be k-correlated rationalizable; an action ai ∈ T k≥1 Ak i is said to be correlated rationalizable. Part (2) in the above definition captures the idea that, at each step k, we are willing to impose the assumption that players are able to perform k−1 steps of eductive reasoning about their opponents. Although this is not explicitly required in the definition, this corresponds to progressively more stringent assumptions about rationality; if action sets are finite, this implies that correlated rationalizable strategies exist (why?). Proposition 0.2 Fix a game G = (N,(Ai , Ti , ui)i∈N ). Then, for every i ∈ N and k ≥ 1, Ak i ⊂ A k−1 i . Proof: The claim is true for k = 1. Assume it is true for some k, fix i ∈ N and pick ai ∈ A k+1 i . By definition, there exists α−i ∈ ∆(A−i , B(T−i)) such that ai ∈ ri(α−i) and α−i(Ak −i ) = 1. Since by the induction hypothesis Ak −i ⊂ A k−1 −i , this implies α−i(A k−1 −i ) = 1; hence, ai ∈ Ak i , as claimed. Independent rationalizability, or (in keeping with standard terminology) “rationalizability” tout-court, incorporates the additional restriction that players’ beliefs are actually independent product measures on their opponents’ action profiles; that players believe that their opponents’ beliefs are independent; that they believe that their opponents believe that their respective opponents’ beliefs are independent; and so on and so forth. Definition 5 Fix a game G = (N,(Ai , Ti , ui)i∈N ). For every player i ∈ N, let R0 i = Ai . For k ≥ 1 and for every i ∈ I, let ai ∈ Rk i iff there exists α−i ∈ ∆(A−i , B(T−i)) such that (1) ai ∈ ri(α−i); (2) α−i( Q j6=i R k−1 j ) = 1; (3) α−i is a product measure on A−i , B(T−i). An action ai ∈ Rk i is said to be k-rationalizable; an action ai ∈ T k≥1 Rk i is said to be rationalizable. I conclude this section with two notes pertaining to the interpretation of (correlated) rationalizability. First, I emphasize that, although we have motivated (correlated) rationalizability with informal assumptions about rationality and beliefs, we have been quite vague in defining what we mean by statements such as, “Player i believes that Player −i is rational.” We have claimed that this “implies” that Player i’s beliefs should assign positive probability only to those strategies of Player −i which can themselves be justified by some belief. 6

However,this is an informal statement. Recent contributions have shown how to con- truct formal models(based on the classical decision-theoretic setting) which allow one to formalize ideas such as "rationality"and"belief". In the framework of those models, the "implication"we have used to define rationalizability can actually be proved-i e. it is a theorem. This places rationalizability on very solid methodological ground Second, it might seem rather natural to assume that beliefs should be independent(and that moreover this ought to be "common belief"). After all, the basic model of simultaneous games postulates that players choose their actions independently, without any possibility of coordination. Thus, correlated beliefs might even appear to be unwarranted The debate on"causal vs. epistemic independence, "as the issue is often referred to, is lengthy and beyond the scope of these notes. Let me just invite you to reflect on the subject based on the following example Consider the following three-player "coordination"game: Players 1 and 2 choose L or R, and get 1 if they coordinate and 0 if they do not. Player 3 chooses C or N; C yields 1 if Players 1 and 2 coordinate, and 0 otherwise, while n yields 0 if they coordinate and 1 if they do not. That is, Player 3s choice represents a bet on whether or not Players 1 and 2 manage to coordinate Now suppose that Player 3 is fully aware that Players 1 and 2 choose independently however, she expects them to coordinate, but is unsure as to which action they will choose e. L or R). Thus, she assigns probability 2 to each of the profiles(L, L)and(R, R).This is a correlated belief, but it could be explained with the following simple story: Players 1 and 2 have been playing this game for a long time, and have "learned to coordinate. "Player 3 knows this, but has never observed their actual play--perhaps because she has also been playing the game for a long time, but she has only observed her own payoff in each play of and hence ascertained whether or not there was coordination) I welcome your comments on this issue! Rationalizability and dominance Consider the following definition Definition 6 Fix a finite game G=(N, (Ai, uiieN) and a player i E N. An action a; E Ai is strictly dominated for Player i iff there exists a; E A(Ai) such that a!∈A

However, this is an informal statement. Recent contributions have shown how to construct formal models (based on the classical decision-theoretic setting) which allow one to formalize ideas such as “rationality” and “belief”. In the framework of those models, the “implication” we have used to define rationalizability can actually be proved—i.e. it is a theorem. This places rationalizability on very solid methodological ground. Second, it might seem rather natural to assume that beliefs should be independent (and that moreover this ought to be “common belief”). After all, the basic model of simultaneous games postulates that players choose their actions independently, without any possibility of coordination. Thus, correlated beliefs might even appear to be unwarranted. The debate on “causal vs. epistemic independence,” as the issue is often referred to, is lengthy and beyond the scope of these notes. Let me just invite you to reflect on the subject, based on the following example. Consider the following three-player “coordination” game: Players 1 and 2 choose L or R, and get 1 if they coordinate and 0 if they do not. Player 3 chooses C or N; C yields 1 if Players 1 and 2 coordinate, and 0 otherwise, while N yields 0 if they coordinate and 1 if they do not. That is, Player 3’s choice represents a bet on whether or not Players 1 and 2 manage to coordinate. Now suppose that Player 3 is fully aware that Players 1 and 2 choose independently; however, she expects them to coordinate, but is unsure as to which action they will choose (i.e. L or R). Thus, she assigns probability 1 2 to each of the profiles (L,L) and (R,R). This is a correlated belief, but it could be explained with the following simple story: Players 1 and 2 have been playing this game for a long time, and have “learned to coordinate.” Player 3 knows this, but has never observed their actual play—perhaps because she has also been playing the game for a long time, but she has only observed her own payoff in each play of the game (and hence ascertained whether or not there was coordination). I welcome your comments on this issue! Rationalizability and Dominance Consider the following definition: Definition 6 Fix a finite game G = (N,(Ai , ui)i∈N ) and a player i ∈ N. An action ai ∈ Ai is strictly dominated for Player i iff there exists αi ∈ ∆(Ai) such that ∀a−i ∈ A−i , X a 0 i∈Ai ui(a 0 i , a−i)αi(ai) > ui(ai , a−i); 7

ai is weakly dominated for Player i iff there exists αi ∈ ∆(Ai) such that ∀a−i ∈ A−i , X a 0 i∈Ai ui(a 0 i , a−i)αi(ai) ≥ ui(ai , a−i) and there exists a−i ∈ A−i such that X a 0 i∈Ai ui(a 0 i , a−i)αi(ai) > ui(ai , a−i). It is (relatively) easy to see that a strictly dominated strategy cannot be a best reply against any belief. The converse is also true: Proposition 0.3 Fix a finite game G = (N,(Ai , ui)i∈N ) and a player i ∈ N. An action ai ∈ Ai is strictly dominated for Player i iff there is no belief α−i ∈ ∆(A−i) such that ai ∈ ri(α−i). Proof: Number the actions in Ai except ai from 1 to |Ai |, and the action profiles in A−i from 1 to |A−i |. Define a |Ai | × |A−i | matrix U by letting Umn = ui(a n i , am −i ) − ui(ai , am −i ), where a n i is the n-th action in Ai \ {ai}, and a m −i is the m-th action profile in A−i . Consider the problem: max x≥0 0 · x s.to U · x ≤ 0, 1 0x = 1 where x is a |A−i |-dimensional column vector. If such a vector exists, then it represents a belief for i, and ai ∈ ri(x). The dual problem is min y≥0,w w s.to y 0 · U + w1 0 ≥ 0 where y is a |Ai − 1|-dimensional column vector and w is a scalar (not sign-constrained). The min problem reads as follows: find a mixture y of actions for i, assigning zero weight to ai , such that the expected payoff to the mixture is at least −w higher than the payoff to ai for any action profile of i’s opponents. Note that w is unconstrained, and the problem seeks to minimize w (hence make −w as large as possible). If the optimal value of the problem is 0, so w = 0, then ai is not strictly dominated. Observe that the max program is always bounded, while the min program is always feasible (take y = 0, w = 0). Thus, suppose ai is a best reply, so the max program is feasible: then, by the Existence-Duality theorem, both problems must have optimal solutions, and the values must coincide. This implies that w = 0, so ai is not strictly dominated. Suppose 8