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.
Let be a pure strategy of player which is never a best response to any mixed strategy of player . Suppose player has pure strategies and player has pure strategies. Let be the payoff function of player . We then define the matrix with entries
Let be the identity matrix of order . Then the fact that is never a best response means that the system has no solution. Here is to be interpreted as an unnormalized mixed strategy of player .
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 , the systems and possess solutions satisfying
One way of giving a geometric intuition to this theorem is that the first system requires us to find a single vector which forms an acute angle with all the rows of while the second system requires us to express the origin as a nonnegative linear combination of the rows of , with the coefficients of the respective rows being given by . In both the problems we are offered an “escape route”: in the first problem we can make merely orthogonal to a row of 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 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 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 by stacking the rows of the matrix below the matrix defined in the first section.
By the theorem of Tucker in the last section there is a such that But we argued in the first section that there is no solution to Therefore it must be the case that for the given by Tucker theorem it is the case that and therefore
Let be the other vector promised to us by Tucker’s result. Let’s denote its first components by and the next components by . Then we have from the last two equations in Tucker’s result and the fact that that and
This in turn implies Writing it out in terms of components we have which means that is strictly dominated by the mixed strategy given by the vector (since we can normalize it into a true vector of probabilities).
This proves our result.