4/08/2021

Minimax Theorem

 

John von Neumann’s Minimax Theorem

Left: John von Neumann’s 1928 article Zur Theorie der Gesellschaftsspiele (“The Theory of Games”) from Mathematische Annalen 100: 295–320. Right: von Neumann with his later collaborator Oskar Morgenstern (1902–1977) in 1953.


The Theory of Games

The history of game theory can be traced back as far as to 1713, when Earl James Waldegrave (1864–1741) analyzed and provided a minimax mixed strategy solution to the card game “Le Her”:

The "Le Her" Game
To play, the dealer gives one card to the receiver and one to the dealer. The receiver may choose to exchange cards with the dealer, unless the dealer has a king, in which case no exchange occurs. Then, the dealer may choose to exchange with the top card of the deck, unless the top card is a king, in which case no exchange occurs. In the case of the dealer and receiver having same ranked cards, the dealer is the winner.
Peter holds a common pack of cards; he gives a card at random to Paul and takes one himself; the main object is for each to obtain a higher card than his adversary.The order of value is ace, two, three, ..., ten, Knight, Queen, King. Now, if Paul is not content with his card he may compel Peter to change with him. However, if Peter has a King he is allowed to retain it.If Peter is not content with the card which he at first obtained, or which he has been compelled to receive from Paul, he is allowed to change it for another taken out of the deck at random. However, if the card Peter then draws is a King he is not allowed to have it, and must retain the card with which he was dissatisfied. If Paul and Peter finally have cards of the same value, Paul is considered to lose.- Excerpt, 'A History of the Mathematical Theory of Probability from the Time of Pascal to that of Laplace' by Todhunter (1865 p. 106)
  • Peter should exchange cards eight and below, and hold higher cards with probability = 37.5%
  • Paul should hold seven and above with probability = 37.5%

John von Neumann’s 1928 Paper

Two portraits of John von Neumann from the 1920s

MiniMax & MaxiMin

Historically, there were thought to be two approaches to optimizing the outcome of games such as Le Her:

  • The conservatively aggressive approach (called minimax)

The MaxiMin Approach

An agent A whose choices are governed by a maximin criterion looks at each strategy she might follow and, in each case, considers the lowest payoff she can receive by following such strategies.She then chooses to play the strategy whose minimum payoff is the highest.

The MiniMax Approach

Another player, C, taking the minimax approach on the other hand, looks at the payoffs her opponent D can achieve given each strategy of C. C then chooses to play the strategy which will give D the lowest payoff, if D would always plays so to maximize his payoff subject to C's strategy.

von Neumann’s Minimax Theorem (1928)

Left: John von Neumann in the 1920s. Right: von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele (“On the Theory of Games of Strategy”).
Any event may be regarded as a game of strategy if one looks at the effect it has on the participants, given the external conditions and provided the participants are acting of their own free will.- Excerpt, Zur Theorie der Gesellschaftspiele by von Neumann (1928)
  • von Neumann, J. (1928b)Zur Theorie der Gesellschaftsspiele (“The Theory of Games”). Mathematische Annalen 100: 295–320.

“M’étant occupé indépendamment avec le même problème”

As he writes in a footnote:

Later Work

In 1937 — utilizing L. E. J. Brouwer (1881–1966)’s fixed-point theorem on continuous mappings into compact convex sets — von Neumann provided a purely topological proof of the existence of general competitive equilibrium, a much clearer and more elegant proof than that included in his 1928 paper:

Theory of Games and Economic Behavior

Aside from von Neumann’s 1928 and 1937 papers, the brief notes of Borel and the proof of Ville (1938), relatively little formal work on the definition and existence of equilibrium for games was published before von Neumann and Morgenstern’s monumental 1944 book Theory of Games and Economic Behavior (Dimand & Dimand, 1996). The two first met in Princeton in 1938, but didn’t begin discussing theories of games until 1939, before collaborating intensely in the period 1941–44 to develop what became the first extensive book on game theory:

    Jørgen Veisdal

WRITTEN BY

Editor at Cantor’s Paradise. Assistant Professor at the Norwegian University of Science and Technology.


THE VON NEUMANN ESSAYS