Past exam of the MSc in advanced computer science course of the University of Oxford / 2021 / Computational game theory / 2

Put $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$, so the complementary probabilities are $1-p$ and $1-q$. All four expressions are the row player's expected payoff, including those indexed by a column action. Direct expected value calculations giveThe column player's expected payoff is the negative of the row player's because this is a zero-sum game.

The bold black curve is the pointwise minimum of the two opposing-column expected payoff functions. It is the row player's security level payoff at the specified mixed strategy:The lines meet where $3p-1=1-4p$, hence at $p=2/7$. The first branch increases with slope $3$ and the second decreases with slope $-4$, so their intersection is the unique global maximum of the lower envelope:The endpoint values are $g(0)=-1$ and $g(1)=-3$, both smaller. Since an opposing mixed strategy forms a convex combination of the two pure-column expected payoffs, it cannot make the row player's expected payoff lower than this envelope.

The bold black curve is now the pointwise maximum of the two pure-row expected payoff functions:It measures the largest expected payoff that the row player can achieve against column mixed strategy $q$. The column player minimizes this quantity because its own payoff has the opposite sign. Equality of the two lines gives $5q-3=1-2q$, or $q=4/7$. The envelope decreases before that point and increases afterwards, givingThe endpoint values $h(0)=1$ and $h(1)=2$ are both larger. A row mixed strategy cannot exceed the greatest pure-row expected payoff, because its expected payoff is a convex combination of those two values.

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 $p^{\ast }=2/7$, both opposing pure columns give row expected payoff $-1/7$; at $q^{\ast }=4/7$, both pure rows give row expected payoff $-1/7$. 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 givesThe resulting row expected payoff is $(16-18-20+15)/49=-1/7$. 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.