John von Neumann and The Minimax Principle

Image via Wikipedia

JOHN VON NEUMANN

John von Neumann was a Hungarian-American mathematician who is widely regarded as the father of game theory (although, a Frenchman named Emile Borel published seven years before von Neumann). He was born in Budapest, Hungary in 1903 and possessed an eidetic memory which allowed him to excel in his studies. Von Neumann's inspiration for developing game theory came from poker, which he played rather unsuccessfully. He quickly realized that poker was not guided by probabilities alone and that one needed to play against the players, not against the cards. Furthermore, he wanted to formalize the notion of deception against the other players in the game. It was in his 1928 paper "Theory of Parlor Games" where he first broached the subject of game theory and proved the minimax theorem. In fact, von Neumann is quoted as saying, "As far as I can see, there could be no theory of games on these bases without that theorem...throughout the period in question I though there was nothing worth publishing until the 'minimax theorem' was proved." Once he proved the theorem, he collaborated with Oskar Morgenstern, an Austrian mathematician, to work on game theory. In 1944, they published their seminal work "Theory of Games and Economic Behavior" which is widely considered one of the most important texts of modern economic theory. To illustrate the point, the intended audience for the book was originally only economists, but it was applied to other subjects such as politics, sociology, psychology, and many others. From that point on, John von Neumann focused much of his work on war and politics. In fact, he would go on to hold several positions within the United States government such as the RAND Corporation and the Atomic Energy Commission under the Eisenhower administration.

John von Neumann would have been considered an extreme hawk by today's standards. He openly advocated preventive war against the Soviet Union. Another famous quote attributed to him, "If you say why not bomb them tomorrow, I say why not today? If you say today at 5 o'clock, I say why not one o'clock?" Of course, by the mid-1950s, the USSR had amassed enough of a nuclear arsenal to sustain a more than credible deterrent against a first strike by the United States.

Unfortunately, von Neumann was diagnosed with bone cancer in 1955. Amazingly, he continued his work as a consultant even while receiving debilitating chemotherapy. In fact, he moved his office to Walter Reed Army Medical Center and received frequent visits from the Secretary of Defense and his colleagues in the U.S. Air Force. John von Neumann succumbed to his cancer on February 8, 1957 and would be remembered as one of the greatest minds of the twentieth century.

His other significant accomplishments include his development of the digital computer, basing computer calculations on binary numbers, and having computers store programs in a coded form instead of punch cards.

THE MINIMAX PRINCIPLE

To quote from William Poundstone, "the minimax theorem proves that every finite, two-person, zero-sum game has a rational solution in the form of a pure or mixed strategy." In other words, when there is a precisely defined conflict between two people whose interests are completely opposite from one another, there is always a rational solution. Essentially, a player is trying to minimize his potential loss while maximizing his potential gain. The solution is rational because each player cannot expect to do any better given the nature of the conflict. The principle is explained using an example of two kids and a cake.

The first kid cuts the cake into two slices and the second kid decides which slice he wants. The cutter expects to get the smaller piece because the chooser will select the larger piece. By cutting the cake as evenly as possible, the cutter guarantees himself almost half the cake. But, if he cuts the cake unevenly, he knows he will get the much smaller piece. Therefore, in order for the cutter to minimize his opponent’s maximum payoff, he will cut the cake as evenly as possible. This is a very basic example of the minimax principle, however, its proof demonstrated that two rational players, whose interests are completely opposed, can agree on a rational course of action confident that the opponent will follow suit (by cutting the cake as evenly as possible, the cutter can be sure that the opponent will leave about half the cake).

Von Neumann thought that the minimax principle could be applied to n-person (two or more) games as well. Take a three-person game for example. The preferences of Player 1 and Player 2 are completely opposed to each other, but Player 1 and Player 3 share similar (or the same) preferences. In that case, they could form a coalition and defeat Player 2. By allying with each other, Players 1 and 3 essentially constitute one player and Player 2 is the other. Now you've got two players with completely opposing preferences (sound familiar?) It doesn't have to stop there; using the minimax principle you could develop n-person games ad infinitum, discover all the possible winning coalitions, and reduce them to zero-sum games. However, the one problem with this line of reasoning is that you're assuming that rational actors would determine the results of every possible coalition and join the one with the maximum payoff. What about games where cooperation is outlawed? As I'll discuss in a later post, John Nash discovered a way to arrive at an equilibrium even when players cannot cooperate with each other.

I researched what the actual minimax proof looks like and found this one from Brigham Young University to be the least challenging (I still have trouble understanding it though). If you're mathematically gifted, I suggest you read it, because it is essentially the foundational principle of game theory.