In words, u1(al, a2)is the minimum payoff that Player 1 can secure; equivalently, it is the minimum payoff to Player 1 when Player 2 attempts to damage her as much as possible, while keeping into account the fact that Player 1 best-responds Note that since max -f=-min f u2(al, a2)=-u1al, a2)=max min u2(a1, 02) a2∈△(A2)a1∈△(A1) i.e.(ai, a))also yields Player 2 the maximum payoff he can obtain if Player 1 chooses her mixed strategy so as to hold Player 2s payoff down Such a pair of mixed strategies can always be found(why? ) Similarly, one can consider the symmetric problem for Player 2, and define a new pair(af, a2)such that so u2(af, a2)is the minimum payoff that Player 2 can secure; as above u1(ai, a2)= max min u1(a1, a2) the maximum payoff that Player 1 can obtain if Player 2 attempts to hold Player 1s yoff down It may be helpful to think about this as a "pseudo-dynamic"story: in order to define (ai, a2), one imagines that Player 2 chooses first, and Player 1 moves next the latter best-responds to Player 2's choice, and the former, anticipating 1s best response, attempts to minimize Player 1's payoff. On the other hand, to define af, a2), one imagines that Player 1 chooses first, and Player 2 moves next; the latter observes 1's choice and attempts to minimize 1s payoff, while the former, anticipating this, attempts to maximize her own payoff. Of course there is a dual to this story, with 1's and 2s roles inverted It is natural to ask whether Player 1's resulting payoff under the two definitions is the same. The answer is affirmative Theorem0.1(a.ka.“ The minmax theoren”): there exists a pair(ai,a2)∈△(41) △(A2) such that in u1(a1, a2)=min 1(a1,Q 2∈△(A2)a1∈△(A1) The easiest proof of this theorem uses Linear Programming. Let n; be the cardi nality of Ai and number its elements from 1 to ni; define the n1 X n2 matrix U by letting Uke=u(ah, a2), where af and as are the k-th and e-th elements of A1 and A2, respectively. Then Player 1s(2s) beliefs about Player 2 s choices may be represented as nonegative vectors in a2 E R(resp. a1 R")whose elements add up to oneIn words, u1(α 1 1 , α1 2 ) is the minimum payoff that Player 1 can secure; equivalently, it is the minimum payoff to Player 1 when Player 2 attempts to damage her as much as possible, while keeping into account the fact that Player 1 best-responds. Note that since max −f = − min f, u2(α 1 1 , α1 2 ) = −u1(α 1 1 , α1 2 ) = max α2∈∆(A2) min α1∈∆(A1) u2(α1, α2) i.e. (α 1 1 , α1 2 ) also yields Player 2 the maximum payoff he can obtain if Player 1 chooses her mixed strategy so as to hold Player 2’s payoff down. Such a pair of mixed strategies can always be found (why?). Similarly, one can consider the symmetric problem for Player 2, and define a new pair (α 2 1 , α2 2 ) such that u2(α 2 1 , α2 2 ) = min α1∈∆(A1) max α2∈∆(A2) u2(α1, α2) so u2(α 2 1 , α2 2 ) is the minimum payoff that Player 2 can secure; as above, u1(α 2 1 , α2 2 ) = max α1∈∆(A1) min α2∈∆(A2) u1(α1, α2) the maximum payoff that Player 1 can obtain if Player 2 attempts to hold Player 1’s payoff down. It may be helpful to think about this as a “pseudo-dynamic” story: in order to define (α 1 1 , α1 2 ), one imagines that Player 2 chooses first, and Player 1 moves next; the latter best-responds to Player 2’s choice, and the former, anticipating 1’s best response, attempts to minimize Player 1’s payoff. On the other hand, to define (α 2 1 , α2 2 ), one imagines that Player 1 chooses first, and Player 2 moves next; the latter observes 1’s choice and attempts to minimize 1’s payoff, while the former, anticipating this, attempts to maximize her own payoff. [Of course there is a dual to this story, with 1’s and 2’s roles inverted.] It is natural to ask whether Player 1’s resulting payoff under the two definitions is the same. The answer is affirmative: Theorem 0.1 (a.k.a. “The minmax theorem”): there exists a pair (α ∗ 1 , α∗ 2 ) ∈ ∆(A1)× ∆(A2) such that u1(α ∗ 1 , α∗ 2 ) = max α1∈∆(A1) min α2∈∆(A2) u1(α1, α2) = min α2∈∆(A2) max α1∈∆(A1) u1(α1, α2) The easiest proof of this theorem uses Linear Programming. Let ni be the cardi￾nality of Ai and number its elements from 1 to ni ; define the n1 × n2 matrix U by letting Uk` = u1(a k 1 , a` 2 ), where a k 1 and a ` 2 are the k-th and `-th elements of A1 and A2, respectively. Then Player 1’s (2’s) beliefs about Player 2’s choices may be represented as nonegative vectors in α2 ∈ Rn2 (resp. α1 ∈ Rn1 ) whose elements add up to one. 5