Theorems of the alternative to the rescue

Exercise 64.2 in Osborne and Rubinstein’s Course in Game Theory asks:

Show that in a finite strategic game any mixed strategy of a player that is not weakly dominated is a best response to a belief that assigns positive probability to every vector of actions of the other players.

The question also gives a hint following which leads to a solution that make the authors’ solution manual itself remark “This exercise is difficult”.

In this post I want to show that this problem becomes quite easy if one makes use of a ‘Theorem of the Alternative’. Theorems of the alternative present two sets of linear equations or inequalities and claim that of the two exactly one has a solution. They have a geometric interpretation in terms of our ability to separate different convex sets. However, since the convex sets being considered are defined by a finite number of equations and/or inequalities these theorems have simple inductive proofs, unlike the more powerful separating hyperplane theorem.

A very good resource for theorems of the alternatives is Mangasarian’s Nonlinear Programming. For our problem we pick the following:

Tucker’s Theorem of the Alternative

Let $B$, $C$ and $D$ be given matrices, with $B$ being nonvacuous. Then either $$Bx\ge 0,\qquad Cx \geqq 0,\qquad Dx=0$$ has a solution $x$, or, $$B'y_2+C'y_3+D'y_4=0,\qquad y_2>0,\qquad y_3 \geqq 0$$ has a solution $y_2$, $y_3$, $y_4$ but never both.

This is Theorem 2.4.3 in Mangasarian’s book.

The vector inequalities used above have the following meanings: $$\begin{align*} u>v &\Leftrightarrow u_i > v_i, \text{for all $i$}\\ u\geqq v &\Leftrightarrow u_i \ge v_i, \text{for all $i$} \\u\ge v &\Leftrightarrow u_i \ge v_i, \text{for all $i$ but $u \neq v$} \end{align*}$$

The Solution

Now we are in a position to solve Osborne and Rubinstein’s problem, which was:

Show that in a finite strategic game any mixed strategy of a player that is not weakly dominated is a best response to a belief that assigns positive probability to every vector of actions of the other players.

Let $m^*$ be the mixed strategy of player $k$ that we are trying to justify. We define the $p \times n$ matrix $B$ as follows: $$B_{ij}= u_k(a_k^j,a_{-k}^i)-u_k(m^*,a_{-k}^i)$$ where $j$ ranges over all actions of player $k$ with $a_k^j$ being the $j$-th action and $i$ ranges over all tuples of actions of players other than $k$ and $a_{-k}^i$ is the $i$-th such tuple.

Let $I$ denote the $n \times n$ identity matrix.

Since $m^*$ is not weakly dominated, the system $$\begin{equation}\label{eq:nweakly} Bx \ge 0,\qquad Ix \geqq 0 \end{equation}$$ cannot have a solution. The proof is by contradiction. Since $Ix \geqq 0$ we have $x_j \ge 0$ for all $j$. Since $Bx \neq 0$ we have $x \neq 0$. Define $$z=\frac{1}{\sum_j x_j} x.$$ We can interpret $z$ as a vector of probabilities. From $\eqref{eq:nweakly}$ and the definition of $z$ it follows that $Bz \ge 0$. Expanding this using the definition of $B$ above we see that this means that the mixed strategy for player $k$ given by $z$ weakly dominates the mixed strategy $m^*$, something which we have ruled out by assumption.

Now we apply Tucker’s Theorem of the Alternative with $B$ as defined, $C=I$ and $D$ vacuous, to conclude that the system $$B'y_2+I'y_3 = 0,\qquad y_2 > 0, \qquad y_3 \geqq 0$$ does have a solution.

Since $I$ is an identity matrix and $y_3 \geqq 0$ it follows from the equation above that $$\begin{equation}\label{eq:byleq} B'y_2 \leqq 0 \end{equation}$$ We define $$w = \frac{1}{\sum_i y_{2i}} y_2.$$ Then $w$ can be seen as a probability distribution that assigns positive probability to each outcome (since $y_2>0$). From $\eqref{eq:byleq}$ we have by linearity, $$B'w \leqq 0.$$ Expanding this using our definition of $B$ we see that this shows that $m^*$ is a best response to the belief that the tuple $a_{-k}^i$ of opponents’ actions occurs with probability $w_i$. Hence Exercise 64.2 is solved.

One caveat. When the number of players is three or more, the beliefs given by $w$ may imply correlation among the actions of different opponents. Everything is fine as far as the exercise is concerned since Osborne and Rubinstein allow such correlated beliefs, but this convention is not universal in the literature.