Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 6 / b

In the first tableau the basis is $(x_2,s_5,x_1)$, givingThe second basis is $(r_1,y_6,r_3)$, giving $y=(0,0,1/4)$ and $r=(3/4,0,1/4)$. This pair is not yet a Nash equilibrium: label $1$ is missing and label $4$ is duplicated.

Resolve the duplicate by bringing $y_4$ into the second tableau. Its column is $(3/4,1/4,9/4{)}^T$, so the simplex ratio test givesVariable $r_3$ leaves, givingNow label $3$ is duplicated. Bring $x_3$ into the first tableau; its column is $(0,3,1{)}^T$. The positive-entry ratios are $(2/3)/3=2/9$ and $(1/9)/1=1/9$. Thus $x_1$ leaves, givingAll labels are now present and $x_i{r}_i=y_j{s}_j=0$. Each unnormalized strategy has total mass $1/3$, so the Lemke-Howson algorithm produces