ai is weakly dominated for Player i iff there exists a; E A(Ai) such that va-;∈A & s ui(a a-i)ai(ai)>ui(ai, a-i and there exists a-i E A-i such that al2∈Aa It is (relatively) easy to see that a strictly dominated strategy cannot be a best reply gainst any belief. The converse is also true Proposition 0.3 Fix a finite game G=(N, (A, ui)ieN)and a player i E N. An action Ai is strictly dominated for Player i iff there is no belief a-i E A(A-i) such that a1∈r(a-i) Proof: Number the actions in Ai except ai from 1 to Ail, and the action profiles in A-i from 1 to A-iI. Define aA:l x IA-il matrix U by letting Umn=ui(an, ami-ui(ai, am) where a' is the n-th action in Ai\ai1, and am is the m-th action profile in A Consider the problem max0·xs.toU·x≤0,1x=1 x>0 where is a A-il-dimensional column vector. If such a vector exists, then it represents a belief for i, and ai E ri(a. The dual problem is min a S.toy.U+u1≥0 where y is a Ai-1l-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 a 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. Supposeai 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