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

Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfyingThus its two polytopes are $\{x\ge 0:Q^{T}x\le 1\}$ and $\{y\ge 0:Py\le 1\}$. A label $i\le m$ occurs when $x_i=0$ or $r_i=0$; a label $m+j$ occurs when $y_j=0$ or $s_j=0$. The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.

Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slacknessA nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=1$ forces $y=0$, and the converse is analogous. Normalize to mixed strategiesThe inequalities $Py\le 1$ imply that every row payoff against $q$ is at most $1/(1^{T}y)$, with equality on every row receiving positive probability in $p$. Thus $p$ is a best response to $q$. Likewise $q$ is a best response to $p$ using $Q^{T}x+s=1$. Hence $(p,q)$ is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.

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

Row operations multiply each original tableau equation by an invertible matrix. The slack variable block therefore records that matrix and allows the original payoff matrix to be recovered without guessing.

From the first tableau, let $X$ be the coefficient block of $x$ and $S$ that of $s$. Since its original equations were $Q^{T}x+s=1$, we have $Q^T=S^{-1}X$. HeresoFor the second tableau, writing its $y$ and $r$ blocks as $Y,R$, the original equations $Py+r=1$ give $P=R^{-1}Y$. We obtainThus a representative pair of payoff matrices isBoth reconstructed right-hand sides are $1$, as a check on the tableau normalization. Independent transformations $P\mapsto aP+b11^T$, $Q\mapsto cQ+d11^T$, with $a,c>0$, preserve best responses and hence identify the same strategic solution up to positive affine payoff transformations.

Directly,The supports of $x^{\prime }$ and $y^{\prime }$ lie entirely among their respective best-response coordinates, confirming the Nash equilibrium found above. Since this representative is a symmetric bimatrix game, swapping the players' strategies preserves the Nash equilibrium conditions. Explicitly, $P{x}^{\prime }=(3,2,3{)}^T$ is maximized on the support of $y^{\prime }$, and $Q^T{y}^{\prime }=P{y}^{\prime }=(1,3,3{)}^T$ is maximized on the support of $x^{\prime }$. Therefore