Consider a game in which player X may select any one of m moves, and player Y may select any one of n moves. If X selects i and Y selects j, then X wins aij from Y. After repeating the game many times, player X develops a mixed strategy where the various moves are played according to probabilities presented by the components of the vector x=(x1,,xm), where xi0,i=1,2,,m and i=1mxi=1. Likewise, player Y develops a mixed strategy y= (y1,,yn), where yi0,i=1,2,,n and i=1nyi=1. The average payoff to player X is P(x,y)=xTAy, where A=a11am1a1namn. (a) Suppose that player X selects x as the solution to the linear program: MaximizeZSubjecttoi=1mxi=1i=1mxiaijz,j=1,2,,nxi0,i=1,2,,m. Show that player X is guaranteed a payoff of at least z no matter how player Y manages its strategy. (3 marks) (b) Show that the dual of the program above is as follows: MinimizeqSubjectto:j=1nyj=1j=1naijyjq,i=1,2,,myj0,j=1,2,,n. (2 marks) (c) Prove that maxz=minq. The common value is called the value of the game. Hint: This is not a straightforward statement (3 marks) (d) Consider a matching game. Each player selects either 1, 2, or 3. The player with the highest number wins $1 unless that number is exactly 1 higher than the other player's number, in which case he loses $3. When the two players select the same number, there is no payoff. Find the value of this game and the optimal mixed strategies