Paper 3, Section II, H

Optimization
Part IB, 2017

(a) Explain what is meant by a two-person zero-sum game with payoff matrix A=(aij:1im,1jn)A=\left(a_{i j}: 1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n\right) and define what is an optimal strategy (also known as a maximin strategy) for each player.

(b) Suppose the payoff matrix AA is antisymmetric, i.e. m=nm=n and aij=ajia_{i j}=-a_{j i} for all i,ji, j. What is the value of the game? Justify your answer.

(c) Consider the following two-person zero-sum game. Let n3n \geqslant 3. Both players simultaneously call out one of the numbers {1,,n}\{1, \ldots, n\}. If the numbers differ by one, the player with the higher number wins £1£ 1 from the other player. If the players' choices differ by 2 or more, the player with the higher number pays £2£ 2 to the other player. In the event of a tie, no money changes hands.

Write down the payoff matrix.

For the case when n=3n=3 find the value of the game and an optimal strategy for each player.

Find the value of the game and an optimal strategy for each player for all nn.

[You may use results from the course provided you state them clearly.]