minimax theorem

Prisoner's Dilemma: John Von Neumann, Game Theory, and the Puzzle of the Bomb
by William Poundstone
Published 2 Jan 1993

We’ll hear more about biological interpretations of game theory later. THE MINIMAX THEOREM 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. Von Neumann’s position as founder of game theory rests mainly with his proof of the minimax theorem by 1926. Von Neumann considered the theorem crucial. In 1953 he wrote, “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 thought there was nothing worth publishing until the ‘minimax theorem’ was proved.” To put it in plain language, the minimax theorem says that there is always a rational solution to a precisely defined conflict between two people whose interests are completely opposite.

…

Von Neumann demonstrated mathematically that there is always a rational course of action for games of two players, provided their interests are completely opposed. This proof is called the “minimax theorem.” The class of games covered by the minimax theorem includes many recreational games, ranging from such trivial contests as ticktacktoe to the sophistications of chess. It applies to any two-person game where one person wins and the other loses (this is the simplest way of meeting the requirement that the players’ interests are “completely opposed”). Von Neumann proved that there is always a “right” or more exactly, an “optimal” way to play such games. Were this all there was to the minimax theorem, it would qualify as a clever contribution to recreational mathematics.

…

One conclusion was that many potential coalitions can be stable. Then it is difficult or impossible to predict what will happen. Von Neumann hoped to use the minimax theorem to tackle games of ever more players. The minimax theorem gives a rational solution to any two-person zero-sum game. A three-person game can be dissected into sub-games between the potential coalitions. If players A and B team up against player C, then the resulting game (coalition of A and B vs. C) is effectively a two-person game with a solution guaranteed by the minimax theorem. By figuring out the results of all the potential coalitions, the players A, B, and C would be able to decide which coalitions were most in their interests.

The Man From the Future: The Visionary Life of John Von Neumann
by Ananyo Bhattacharya
Published 6 Oct 2021

One could argue that, on the contrary, at the root of the discipline was the naive hope that mathematics could help forge lasting peace. In 1925, the tools to realize Lasker’s grandiose ambitions were not available. The first decisive step towards a ‘science of contest’ would be taken towards the end of the following year. On 7 December 1926, von Neumann unveiled his proof of the minimax theorem to mathematicians at Göttingen. Published in 1928, the paper expounding his proof, On the Theory of Parlour Games,10 would firmly establish game theory as a discipline, framing human cooperation and conflict in truly mathematical terms. Von Neumann had been interested in the scientific principles underlying games and toys since childhood.

…

Von Neumann, who would never forget being beaten to the punch by Birkhoff and Gödel, was in no mood to give up his claim to being game theory’s inventor. He had not seen Borel’s papers when he was formulating his proof, von Neumann said in his response. If he had, the effect would have been ‘primarily discouraging’.17 ‘Throughout the period in question I thought there was nothing worth publishing until the “minimax theorem” was proved,’ he added. ‘As far as I can see, there could be no theory of games on these bases without that theorem. By surmising, as he did, the incorrectness of that theorem, Borel actually surmised the impossibility of the theory as we now know it.’ Outside France, von Neumann’s 1928 minimax paper is today recognized as the founding work of game theory.

…

As Binmore says, ‘The point of bluffing is not so much that you might win with a bad hand, as that you want to encourage the opposition to bet with middle-range hands when you have a good hand.’57 Poker rounds off von Neumann’s exhaustive treatment of zero-sum two-person games. He had laid down the axioms of game theory and given formal definitions of terms such as ‘game’ and ‘strategy’. He also offered a proof of his minimax theorem, which was much more elementary than the original of 1928. In 1938, Jean Ville, a student of Émile Borel, had published a simple algebraic proof of minimax. After Morgenstern chanced upon Ville’s work in the IAS library, he alerted von Neumann, who made Ville’s proof simpler still. For the remainder of Theory of Games, von Neumann tries to extend his results to games with any number of players and to situations where there is the possibility of mutual benefit.

The Pentagon's Brain: An Uncensored History of DARPA, America's Top-Secret Military Research Agency
by Annie Jacobsen
Published 14 Sep 2015

A poker player needs to predict what his opponent thinks he might do. In 1926, when von Neumann was twenty-three years old, he wrote a paper called “Theory of Parlor Games.” The paper, which examined game playing from a mathematical point of view, contained a soon-to-be famous proof, called the minimax theorem. Von Neumann wrote that when two players are involved in a zero-sum game—a game in which one player’s losses equal the other player’s gains—each player will work to minimize his own maximum losses while at the same time working to maximize his minimum gains. During the war, von Neumann collaborated with fellow Princeton mathematician Oskar Morgenstern to explore this idea further.

…

The book was considered so groundbreaking that the New York Times carried a page one story about its contents the day it was published. But von Neumann and Morgenstern’s book did more than just revolutionize economic theory. It placed game theory on the world stage, and after the war it caught the attention of the Pentagon. By the 1950s, von Neumann’s minimax theorem was legendary at RAND, and to engage von Neumann in a discussion about game theory was like drinking from the Holy Grail. It became a popular pastime at RAND to try to present to von Neumann a conundrum he could not solve. In the 1950s, two RAND analysts, Merrill Flood and Melvin Dresher, came up with an enigma they believed was unsolvable, and they presented it to the great John von Neumann.

…

If both men refuse the deal, they will each be given only one year in jail for parole violation—clearly the best way to minimize maximum losses and maximize minimum gains. But the deal is on the table for only a finite amount of time, the police say. Von Neumann could not “solve” the Prisoner’s Dilemma. It is an unsolvable paradox. It does not fit the minimax theorem. There is no answer; the outcome of the dilemma game differs from player to player. Dresher and Flood posed the Prisoner’s Dilemma to dozens of RAND colleagues and also to other test subjects outside RAND. While no one could “solve” the Prisoner’s Dilemma, the RAND analysts learned something unexpected from the results.

Darwin Among the Machines
by George Dyson
Published 28 Mar 2012

“The main achievement of the [von Neumann-Morgenstern] book lies, more than in its concrete results, in its having introduced into economics the tools of modern logic and in using them with an astounding power of generalization,” wrote Jacob Marschak in the Journal of Political Economy in 1946.5 Von Neumann’s central insight was his proof of the “minimax” theorem on the existence of good strategies, demonstrating for a wide class of games that a determinable strategy exists that minimizes the expected loss to a player when the opponent tries to maximize the loss by playing as well as possible. This conclusion has profound but mathematically elusive consequences; many complexities of nature, not to mention of economics or politics, can be treated formally as games.

…

; consciousness; intelligence; logic; neural networks and brain, 5, 45–48, 72, 87, 89, 109–110, 136, 155–59, 168, 176, 204, 214–15, 219, 225 composite, 34, 168, 172, 199–200, 203–204, 209–210, 217–18, 224, 227–28 and computability, 5–7, 36, 39, 43, 50, 58, 59, 70, 72, 73, 157 and electrons, 109, 198 emergence of, 9, 222–24 Hobbes on physical nature of, 3–5, 39, 51 Hooke on operation and capacity of, 136 human, capacity of, 136, 217 and incompleteness, 50, 70, 72 Leibniz on, 35–36, 38, 51 and mechanism, 3–9, 25–26, 35, 47, 50–51, 59, 70, 73, 87, 108–110, 168, 211, 214, 227 and music, 222–24, 225 origins and evolution, 81–82, 172, 211, 219, 222–25 robustness of, 176 unpredictability of, 9, 35, 45, 72–73, 109–110 minimax theorem, defined, 154 Minsky, Marvin, 7, 72, 111 MTT (Massachusetts Institute of Technology), 80, 98, 144, 179, 180 Mivart, St. George Jackson (1827–1900), 18 “Model of General Economic Equilibrium” (von Neumann), 155 modeling. see also self-organizing systems; weather prediction; vision of air defense, 178–82 computational, 62, 83, 85, 86–88, 110, 196–97 of evolution, 27, 29, 111–19, 125–26 and evolution of consciousness, 10, 82 and evolution of control, 179, 183–84 of intelligence, 71, 72, 89, 175–76, 184–85 modems, wireless, 208 molecules. see also DNA; RNA as code, 19, 144 evolution of, 12 as parts, 173 and self-replication, 29, 113, 118, 123, 129 Monadology (Leibniz), 35, 51 money and cryptography, 62, 165, 167 and cost of decreasing entropy, 170 electronic, 165, 167–70 evolution of, 162–68, 170 and intelligence, 165–71 velocity of, 164, 167 Moore School of Electrical Engineering (Philadelphia), 80–81, 90, 98, 99, 104 Morgenstern, Oskar (1902–1977), 146, 153, 154, 158, 167, 168, 171 morphogenesis, 70, 160, 175 Morrison, Philip, v, 11, 192 Morse code, 142, 175, 184, 225 Morse, Samuel (1791–1872), 142 mouse (computer input), origins of, 226 MS-DOS (operating system), 121 multiplexing (telecommunications), 8, 148, 152 frequency-division, 208 time-division, 143, 205 music, 35, 204, 218–20, 221–26 mutation, and evolution, 20, 113–17, 120 My Garden; its Plan and Culture (Smee), 48 Myers, Frederic W.

Turing's Cathedral
by George Dyson
Published 6 Mar 2012

That’s what Johnny could do, and what no one else could do as well.”34 Along with his doctorate in 1926—after an oral examination at which David Hilbert was reported to have asked a single question: “In all my years I have never seen such beautiful evening clothes: pray, who is the candidate’s tailor?”—von Neumann received a Rockefeller Fellowship to work with Hilbert at Göttingen, a lifeline from America at a time when positions in Europe were scarce.35 He published twenty-five papers in the next three years, including a 1928 paper on the theory of games (with its minimax theorem proving the existence of good strategies, for a wide class of competitions, at the saddle point between convex sets) as well as the book Mathematical Foundations of Quantum Mechanics, described by Klári as his “permanent passport to the world of science,” and, eighty years later, still in print.

…

Robert (“Captain”) Maxwell, James Clerk Maxwell’s demon Mayer, Harris, 10.1, 10.2, 11.1, 11.2, 18.1, 18.2 on von Neumann, 1.1, 14.1 on termination of the ECP Mayer, Rosalie McCulloch, Warren S. (1898–1969), 7.1, 15.1 meaning, 6.1, 10.1, 13.1, 14.1, 17.1 topology vs. code, as carrier of mechanical intelligence, 13.1, 17.1 see also artificial intelligence mechanical procedure, 6.1, 13.1, 13.2 “Me’lissende” (Robert Oppenheimer) Melville, Richard W. (1914–1994), 7.1, 7.2, 18.1 memory (storage) acoustic delay line, 5.1, 5.2, 8.1, 13.1 content-addressable, 17.1, 14.1 cost of and ECP, 6.1, 6.2, 6.3 hierarchical iconoscope as inefficiencies of, 14.1, 14.2 read-only (ROM) resistor-matrix, 5.1, 5.2 serial vs. parallel solid state (silicon) as switching problem, 5.1, 6.1, 8.1 von Neumann on scarcity of see also random-access memory (RAM); Selectron; Williams (memory) tubes Mercer, General Hugh Merkelson, Ted meteorology, see numerical weather prediction Metropolis, Nicholas (1915–1999), ack.1, 1.1, 5.1, 5.2, 5.3, 7.1, 10.1, 10.2, 10.3, 10.4, 10.5, 10.6, 11.1, 11.2, 11.3 and computing at Los Alamos, 4.1, 18.1 and the ENIAC, 5.1, 5.2 and Monte Carlo (code), 10.1, 10.2 on von Neumann, 4.1, 4.2 Metropolis-Hastings algorithm Michigan, University of, 14.1, 18.1 microprocessors, 6.1, 7.1, 8.1, 14.1, 15.1, 17.1 Miller, Bernetta (1884–1972), 6.1, 6.2, 7.1, 8.1, 8.2 Mineville, New York minimax theorem (von Neumann) Minitotal (Alfvén) Minsky, Marvin “Model of General Economic Equilibrium” (von Neumann, 1932), 15.1, 15.2 Molotov-Ribbentrop Pact Monadology (Leibniz, 1714) Monte Carlo (code), 10.1, 10.2, 11.1, 11.2, 11.3, 16.1, 17.1, 18.1 Monte Carlo (Monaco), 10.1, 10.2 Montgomery, Deane (1909–1992), 3.1, 3.2 Moore School, 5.1, 5.2, 5.3, 5.4, 5.5, 7.1, 7.2, 8.1, 11.1 Morgenstern, Oskar (1902–1977), 4.1, 4.2, 15.1 on von Neumann, 4.1, 10.1 Morse, Marston (1892–1977), 3.1, 3.2, 5.1, 5.2, 6.1, 6.2, 8.1, 14.1, 14.2, 18.1 on meteorology Moulton, Forest Ray (1872–1952) Mount Holyoke College mulatsag Munk, Walter Nagasaki, atomic bombing of (August 9, 1945), 4.1, 7.1, 10.1, 11.1, 11.2 National Center for Atmospheric Research National Defense Research Committee (NDRC), 4.1, 7.1, 7.2 National Physical Laboratory (NPL), 8.1, 9.1, 13.1, 18.1 Navy, U.S., 3.1, 4.1, 5.1, 5.2, 6.1, 9.1, 9.2, 10.1, 14.1 see also Office of Naval Research (ONR) Nazism, 3.1, 3.2, 4.1, 10.1, 10.2, 11.1 Neumann, Herman Alexander Neurototal (Alfvén) Newark, New Jersey, fm1.1, 2.1, 2.2, 3.1, 3.2, 3.3, 3.4 New Jersey, 2.1, 2.2, 2.3, 2.4 constitution of, 1676 division of, 1683 “New Look, The” (in reliability) Newman, Lyn, 13.1, 13.2 Newman, Maxwell H.

The Perfect Bet: How Science and Math Are Taking the Luck Out of Gambling
by Adam Kucharski
Published 23 Feb 2016

“Chris Ferguson’s Bankroll Challenge.” 146When Ignacio Palacios-Heurta: Palacios-Heurta, Ignacio. “Professionals Play Minimax.” Review of Economic Studies 70 (2003): 395–415. 147Von Neumann completed his solution: Details of the dispute were given in: Kjedldsen, T. H. “John von Neumann’s Conception of the Minimax Theorem: A Journey Through Different Mathematical Contexts.” Archive for History of Exact Science 56 (2001). 149While earning his master’s degree in 2003: Follek, Robert. “Soar-Bot: A Rule-Based System for Playing Poker” (MSc diss., School of Computer Science and Information Systems, Pace University, 2003). 150Led by David Hilbert: O’Connor, J.

Theory of Games and Economic Behavior: 60th Anniversary Commemorative Edition (Princeton Classic Editions)
by John von Neumann and Oskar Morgenstern
Published 19 Mar 2007

In 1956 when he was already very sick with cancer, fortunately I could tell Johnny that J. G. Kemeny, Gerald L. Thompson, and I had succeeded in removing it, generalizing his model substantially, which pleased him very much. This was to become known as the “KMT model,” which also established firmly the relationship of the model to game theory. In both, the fundamental minimax theorem is of the essence; KMT showed why this had to be the case and—unexpectedly—that game theory can also be used as a mathematical technique, as a calculus, in addition to being a true model. Many further generalizations were possible beyond the KMT model, an indication of the power of Johnny’s original ideas.

…

So we promised we would happily put an elephant in the book: anyone who opens the pages can find a diagram showing an elephant if he knows that he should look for one. At this point I note a curious incident that shows how chance can influence the direction of scientific work. At the time when we were about to write down a new proof for Johnny’s famous minimax theorem, originally developed in 1928, I went out for a walk on a brilliant, snowy cold winter day. I went towards the Institute for Advanced Study and since I was cold, I walked into the library, looking around idly. I picked up E. Borel’s Traité du Calcul des Probabilités, and there I saw in it suddenly a paper by Jean Ville [23, 1938] dealing with Johnny’s 1928 paper.