A pure strategy that is never a best response is strictly dominated

Jan. 28, 2014

Following my earlier post, here is another example of the use of theorems of the alternative in game theory.

We prove the following result, originally due to Pearce (Econometrica, 52(4), 1029-1050, Lemma 3):

A pure strategy in a two-player finite game which is never a best response to any mixed strategy of the other player is strictly dominated.

The setup

Let ss be a pure strategy of player 11 which is never a best response to any mixed strategy of player 22. Suppose player 11 has MM pure strategies and player 22 has NN pure strategies. Let uu be the payoff function of player 11. We then define the M×NM \times N matrix BB with entries Bij=u(s,a2j)u(a1i,a2j).B_{ij} = u(s,a_2^j)-u(a_1^i,a_2^j).

Let II be the identity matrix of order NN. Then the fact that ss is never a best response means that the system Bx0,Ix0 \begin{equation}\label{eq:never-best} Bx \geqq 0, \quad Ix \ge 0 \end{equation} has no solution. Here xx is to be interpreted as an unnormalized mixed strategy of player 22.

The theorem of the alternative

We can prove our result using Tucker’s Theorem of the Alternative that we used in the last post. But for variety this time we use another result, also due to Tucker, and also discussed in Mangasarian’s book.

For any matrix AA, the systems Ax0Ax \geqq 0 and [Ay=0,y0[A'y = 0,\quad y \geqq 0 possess solutions satisfying Ax+y>0.Ax + y > 0.

One way of giving a geometric intuition to this theorem is that the first system requires us to find a single vector xx which forms an acute angle with all the rows of AA while the second system requires us to express the origin as a nonnegative linear combination of the rows of AA, with the coefficients of the respective rows being given by yy. In both the problems we are offered an “escape route”: in the first problem we can make xx merely orthogonal to a row of AA rather than making it strictly acute and in the second problem we can put zero weight on a row rather than putting a strictly positive weight.

Having the rows of AA pointing in similar directions makes the problem of solving the first system easy but the problem of solving the second system hard, and vice-versa.

This negative correlation between the difficulty of the two problems allows us to solve both the problems simultaneously in a way that is non-trivial. The sense in which the solution is non-trivial is captured by the third system which says that there is no row of AA for which we will have to invoke the “escape route” for both the problems simultaneously.

Strictly speaking this result is not a theorem of the alternative but rather an existence result which can be used to prove theorems of the alternative, as is done in Mangasarian’s book.

Proof of the main theorem

Form the matrix AA by stacking the rows of the matrix II below the matrix BB defined in the first section.

By the theorem of Tucker in the last section there is a xx such that Bx0,Ix0.Bx \geqq 0,\quad Ix \geqq 0. But we argued in the first section that there is no solution to Bx0,Ix0.Bx \geqq 0,\quad Ix \ge 0. Therefore it must be the case that for the xx given by Tucker theorem it is the case that x=Ix=0x = Ix = 0 and therefore Ax=0Ax=0

Let yy be the other vector promised to us by Tucker’s result. Let’s denote its first MM components by y1y_1 and the next NN components by y2y_2. Then we have from the last two equations in Tucker’s result and the fact that Ax=0Ax=0 that By1+Iy2=0,y10,y20B'y_1 + Iy_2 = 0, y_1 \geqq 0, y_2 \geqq 0 and y1>0,y2>0.y_1 >0, y_2 >0.

This in turn implies By1=y2<0.B'y_1 = -y_2 < 0. Writing it out in terms of components we have i=1My1i[u(s,a2j)u(a1i,a2j)]<0,j=1,N\sum_{i=1}^M y_1^i [u(s,a_2^j)-u(a_1^i,a_2^j)]<0, j=1,\ldots N which means that ss is strictly dominated by the mixed strategy given by the vector y1y_1 (since y1>0y_1>0 we can normalize it into a true vector of probabilities).

This proves our result.