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 s be a pure strategy of player 1 which is never a best response to any mixed strategy of player 2. Suppose player 1 has M pure strategies and player 2 has N pure strategies. Let u be the payoff function of player 1. We then define the M × N matrix B with entries Bij = u(s,a2j) − u(a1i,a2j).
Let I be the identity matrix of order N. Then the fact that s is never a best response means that the system Bx ≧ 0, Ix ≥ 0 has no solution. Here x is to be interpreted as an unnormalized mixed strategy of player 2.
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 A, the systems Ax ≧ 0 and [A′y = 0, y ≧ 0 possess solutions satisfying 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 x which forms an acute angle with all the rows of A while the second system requires us to express the origin as a nonnegative linear combination of the rows of A, with the coefficients of the respective rows being given by y. In both the problems we are offered an “escape route”: in the first problem we can make x merely orthogonal to a row of A 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 A 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 A 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 A by stacking the rows of the matrix I below the matrix B defined in the first section.
By the theorem of Tucker in the last section there is a x such that Bx ≧ 0, Ix ≧ 0. But we argued in the first section that there is no solution to Bx ≧ 0, Ix ≥ 0. Therefore it must be the case that for the x given by Tucker theorem it is the case that x = Ix = 0 and therefore Ax = 0
Let y be the other vector promised to us by Tucker’s result. Let’s denote its first M components by y1 and the next N components by y2. Then we have from the last two equations in Tucker’s result and the fact that Ax = 0 that B′y1 + Iy2 = 0, y1 ≧ 0, y2 ≧ 0 and y1 > 0, y2 > 0.
This in turn implies B′y1 = − y2 < 0. Writing it out in terms of components we have $$\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 s is strictly dominated by the mixed strategy given by the vector y1 (since y1 > 0 we can normalize it into a true vector of probabilities).
This proves our result.