Paper 3, Section II, H

Optimization
Part IB, 2021

Explain what is meant by a two-person zero-sum game with m×nm \times n payoff matrix AA, and define what is meant by an optimal strategy for each player. What are the relationships between the optimal strategies and the value of the game?

Suppose now that

A=(0114102212034230)A=\left(\begin{array}{cccc} 0 & 1 & 1 & -4 \\ -1 & 0 & 2 & 2 \\ -1 & -2 & 0 & 3 \\ 4 & -2 & -3 & 0 \end{array}\right)

Show that if strategy p=(p1,p2,p3,p4)Tp=\left(p_{1}, p_{2}, p_{3}, p_{4}\right)^{T} is optimal for player I, it must also be optimal for player II. What is the value of the game in this case? Justify your answer.

Explain why we must have (Ap)i0(A p)_{i} \leqslant 0 for all ii. Hence or otherwise, find the optimal strategy pp and prove that it is unique.