Peter Bickel taught me a nifty, little, literally, proof of the minimax theorem. Peter says it was inspired by his reading of David Blackwell‘s vector generalization of the same. Here goes.
Let be the
payoff matrix of zero-sum game. Here
is the payoff to the row player from playing
when the column player plays
. Let
be $k$-simplex.
For each , let
This is the set of payoffs that the row player can achieve when playing mixed strategy
. By convexity, it must be an interval whose endpoints depend on
. We will only be interested in the left most endpoint, call it
. Thus, we can assume that (strictly speaking should be subset)
Similarly, for each
, let
. By the same observations we may suppose that
For any and
we have
Now, choose
which exists by continuity and compactness. Similarly, choose
Then,
is the value of the game.
No Farkas or separating hyperplane. Now, minimax is equivalent to duality. So, one might wonder whether such a proof could be used to obtain the duality theorem of linear programming. Assuming that the primal and the dual had optimal solutions, yes. However, the case where one is infeasible or unbounded would cause this kind of proof to break.
PS: Then, Olivier Gossner pointed out that perhaps because I wanted to believe so much that it was true, that I had overlooked something. See the comments. He was right. I tried to make the proof work but could not. A proof of minimax that avoids Farkas and/or the separating hyperlane is not outlandish. There is Guillermo Owen’s proof, via induction, for example. By the way this was not the first such elementary proof. There was a flurry elementary proofs of the minimax in the 40s and 50s in response to a challenge of von Neumann. Indeed, Peck (1958) writes in the introduction to his paper:
“There are so many proofs of this theorem in the literature, that an excuse is necessary before exhibiting another. Such may be found by examining the proof given below for the following: it uses no matrices, almost no topology and makes little use of the geometry of convex sets; it applies equally well to the case where only one of the pure strategy spaces is finite; also there is no assumption that the payoff function is bounded.”
That an induction proof should exist is unsurprising given David Gale’s inductive proof of the Farkas lemma. In fact, Gale’s proof can be seen as an instantiation of Fourier’s method for solving linear programs, again, no Farkas or separating hyperplane.
4 comments
September 27, 2022 at 7:16 am
Ben Golub
O. Gossner and E. Lipnowski were discussing this on Twitter. We can’t figure out why the v* found in the last step is the value of the game. Lipnowski says that the same argument would apply to PURE strategies of a two-person zero-sum game: you get a b(p) maximizing over a finite set, and similarly d(q). And then that shows the existence of a v* as here.
It seems like in the last step one needs to use the hard direction of the separating hyperplane theorem to show that v* is actually the value of the game.
September 27, 2022 at 9:25 am
rvohra
Yes, Olivier is right. At the time it seemed so clear to me (fevered dream). Noodling it over to see if it can be salvaged.
September 27, 2022 at 2:01 pm
Ben Golub
It certainly can using a separating hyperplane theorem!!
September 27, 2022 at 5:40 pm
Anonymous
sigh, yes……….but one can dream a little……rv