Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 38 / 5

Let $P$ be the row payoff matrix and $Q=P^T$. For $x$ in the probability simplex $\Delta$, write $u(x)=x^{T}Px$ and define the symmetric Nash gain mapThe map is a continuous function, has nonnegative coordinates, and sums to one. The Brouwer fixed-point theorem states that every continuous self-map of a nonempty finite-dimensional compact convex set has a fixed point. Apply it to $T:\Delta \to \Delta$, and let $x=T(x)$.

Set $G={\sum }_i{g}_i(x)$. The fixed-point equation gives $g_i(x)=G{x}_i$. If $G>0$, every positive $x_i$ has strictly positive gain, so $(Px{)}_i-u(x)=g_i(x)=G{x}_i$. Buta contradiction. Thus $G=0$ and every pure payoff $(Px{)}_i$ is at most $u(x)$. Since their $x$-weighted average equals $u(x)$, every supported action attains that maximum. Consequently $x$ is a best response to itself.

The column player's payoff vector against $x$ is $Q^{T}x=Px$, so exactly the same inequalities establish its best response. ThereforeThis supplies the whole fixed-point construction and fixed-point-to-equilibrium argument, rather than assuming Nash's theorem as a black box.

The matrices obey $Q=P^T$, so both players' pure best response vectors have the form $Px$ against opponent mixture $x$. Against pure actions $1,2,3$, the unique best responses are respectively $3,1,2$. This three-cycle has no mutual best-response pair, so there is no pure Nash equilibrium.

In a game satisfying nondegeneracy of a bimatrix game, the two equilibrium strategy supports have equal cardinality: each support consists of best responses to the other strategy, so each size is at most the other. If both supports have size three, $Px$ must have all coordinates equal. The first-minus-second and second-minus-third equations implyThis has no fully positive simplex solution. Thus both supports have size two.

For full support enumeration for a bimatrix game, denote the three possible supports by $12,13,23$. On equal supports $12$ and $23$, indifference requires respectively probabilities $(-1,2)$ and $(2,-1)$, so those pairs fail. Equal support $13$ gives $x_1=x_3=1/2$, whose omitted-action payoff is $1<3/2$. The cross pair $(12,13)$ yieldswith $Pt=(4/3,4/3,1{)}^T$ and $Ps=(7/3,2/3,7/3{)}^T$. Thus the supported actions are best responses. Its reversed pair is also an equilibrium. The remaining unordered cross pairs fail: for $(12,23)$ the necessary $s=(1/4,3/4,0)$ gives $Ps=(11/4,3/2,3/2{)}^T$, so the opponent has a profitable action outside its support. For $(13,23)$, the necessary opponent mixture on $23$ is $(0,-1,2)$, which is infeasible. Reversing either failed pair cannot rescue it.

Hence all three equilibria areTheir payoffs are respectively $(4/3,7/3)$, $(7/3,4/3)$ and $(3/2,3/2)$. The support-size argument and exhaustion above rule out every other equilibrium.

The equilibrium oddness theorem gives a finite odd number of Nash equilibria in a finite nondegenerate bimatrix game. One way to see the parity is through the endpoint argument underlying the Lemke-Howson algorithm. Add sufficiently large constants to each payoff matrix so all entries are positive; this does not change best responses. Form the bounded convex polytopesLabel an $s_i=0$ facet by row label $i$ and a tight $(Q^{T}s{)}_j=1$ facet by column label $n+j$; in $Y$, label a tight $(Pt{)}_i=1$ facet by $i$ and $t_j=0$ by $n+j$. A completely labelled vertex of a polytope pair has either both vectors zero, or both nonzero and normalizes to a Nash equilibrium. In the latter case the labels express exactly the equilibrium best-response and zero-probability conditions. Nondegeneracy makes each vertex of a polytope have exactly $n$ distinct incident labels and each equilibrium correspond to one such pair.

Fix a label to drop and retain all pairs carrying every other label. Include the product-convex polytope edges that retain those labels. At a completely labelled pair there is one possible outgoing edge, obtained by dropping the fixed label. At any other retained vertex of a polytope, that label is missing and one other label is duplicated; dropping either copy gives the two incident edges. Thus this finite graph consists of paths and cycles, with its endpoints precisely the completely labelled pairs. A finite graph has an even number of degree-one vertices. Since one endpoint is the artificial zero pair, the number of genuine equilibrium endpoints is odd. This proves the required equilibrium oddness theorem and finiteness, without claiming that every equilibrium is reached from the zero pair on the same path.

For a symmetric bimatrix game, swapping players maps $(s,t)$ to $(t,s)$. Every nonsymmetric equilibrium lies in a distinct two-element pair; the fixed points of this involution are exactly the symmetric equilibria. Removing even-sized pairs from an odd total leaves an odd number of symmetric equilibria. In the present game, two equilibria form the swapped pair and the remaining one is $(x,x)$ with $x=(1/2,0,1/2)$. There is exactly one symmetric equilibrium, as required.