2. Game theory and linear programming Consider a zerosum game where Player 1 has re actions and player 2 has p actions. Suppose the payeff to player 1 is A- if player 1 plays action if E {1, . . . , m} and player 2 plays action j E {1, . . . , p}. Since game is zero-sum, the payoff to player 2 is A,:_,-. This is equivalent to assuming that player 2 pays player 1 the amount Ag. For concreteness, suppose m. = 2, p = 3, and the matrix _143 A'iaeai Suppose we allow the players to randomize or mix over their actions, so player 1 chooses a probability mass function a: = (r1, . ..,a:..,,} where 9:,- E 0 denotes the probability with which she plays action 1' E {1, . . . ,m}, and player 2 chooses a probability mass function y = {y1,. . . ,yp), where 3.3 3-; 0 denotes the probability with which she plays action j E {1, , , , , p}. Then the expected reward for player 1 is giyen by m a zzmiAijyj = {FT-fit" i=1 j=l Thus, if player 1 plays a randomized action I. Then the expected value 15(1) if player 2 plays action 3' is given by rig-[:5] = 21:] 5,1445. Let afar) = [131(3), . . . ,ep[a")). (a) The goal of player 2 is to minimize the expected payment she will have to make to player 1. Therefore, the optimal choice for y is given by the solution of the following linear program: D(x) = miny s.t. 2i=y; = 1, y 2 0. Show that the dual of this linear program is given by maxs B, s.t. B