Solution

ID: past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2021/computational-game-theory/2/d/solution

The unique Nash equilibrium uses row probabilities on and column probabilities on . The value of a zero-sum game to the row player is ; the column player receives .
The first graph solves the row player's max–min optimization: choose a mixed strategy guaranteeing the greatest possible worst-case expected payoff. The second solves the column player's min–max optimization: choose a mixed strategy placing the smallest upper bound on the row player's expected payoff. Their optimal heights agree, illustrating the minimax theorem.
There is also a direct Nash equilibrium certificate, so the conclusion does not depend on reading coordinates from a plot. At , both opposing pure columns give row expected payoff ; at , both pure rows give row expected payoff . By linearity, every unilateral deviation, including an arbitrary mixed strategy, leaves the deviator's expected payoff unchanged against the fixed opposing equilibrium mixture. Neither player can improve it. This is a mixed-strategy optimality certificate for a matrix game.
The equilibrium outcome is a probability distribution over cells, rather than one deterministic cell. Independent randomization gives
The resulting row expected payoff is . Finally, each envelope has a unique optimum, so any Nash equilibrium must use the displayed optimal mixed strategies. In particular there is no pure strategy Nash equilibrium.

New to topics? Read the docs here!