Tag Archive

You are currently browsing the tag archive for the ‘minimax’ tag.

A Lovely Proof (?) of Minimax

September 15, 2022 in linear programming, Operations research | Tags: , , | by | 4 comments

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 A be the m \times n payoff matrix of zero-sum game. Here a_{ij} is the payoff to the row player from playing i when the column player plays j. Let \Delta^k be $k$-simplex.


For each p \in \Delta^m, let R(p) = \{ p^TAq: q \in \Delta^n \}. This is the set of payoffs that the row player can achieve when playing mixed strategy p. By convexity, it must be an interval whose endpoints depend on p. We will only be interested in the left most endpoint, call it b(p). Thus, we can assume that (strictly speaking should be subset) R(p) = [b(p), + \infty). Similarly, for each q \in \Delta^n, let C(q) = \{ p^TAq: p \in \Delta^m \}. By the same observations we may suppose that C(q)= (-\infty, d(q)].

For any p \in \Delta^m and q \in \Delta^n we have R(p) \cap C(q) \neq \emptyset. Now, choose p^* = \arg \max_{p \in \Delta^m}b(p) which exists by continuity and compactness. Similarly, choose q^* = \arg \min_{q \in \Delta^n}d(q). Then, v = (p^{*})^{T}Aq^{*} \in R(p^{*}) \cap C(q^{*}) 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.

Kellogg faculty blogroll