Though it would only become famous after World War II, John von Neumann published his first work on game theory, “Zur Theorie der Gesellschaftsspiele,” in 1928. “Gesellschaftsspiele” translates colloquially to “board games,” but it also refers to “party games” or “parlor games.”1 This parlor-game theory paper is related to this blog series because von Neumann conceptualizes ideal humans as random. While Ramsey suggested that human belief could be quantified as probabilities, von Neumann showed that human actions were optimally probabilistic.
How did he get there? For anyone who has studied game theory, the 1928 development should be familiar. Based on an open problem of Borel, von Neumann tried to mathematically determine the best strategies for parlor games. von Neuman abstracts the parlor game into a series of discrete moves by players and random draws that might correspond to chance, like the rolling of dice or the drawing of cards. Each player has a finite number of moves available to them at any turn. They choose their moves using strategies. von Neumann defines a strategy to be a deterministic rule book. A strategy gives a unique move based on the current game history. This history includes the moves of the other players and all of the random draws.
Given two players’ deterministic strategies and the randomness of draws, each player will receive an associated payout. The only constraint von Neumann adds is that the game is zero-sum, meaning the sum of the players’ payouts is zero. You can think of this as whoever loses pays the winner.
Which strategy should Player One choose? Their payout depends on the strategy of Player Two and the randomness of the draws. Because he’s more interested in the interactions between the players, von Neumann casually removes the randomness of the draws by averaging over them. Instead of considering payouts, he considers the expected value of payouts.
Once we turn to expected values and assume zero-sum, the problem of choosing a strategy has a simple form. The rest of the paper develops a landmark result in optimization theory: the minimax theorem.
Let me introduce a teeny bit of notation to make the presentation compact. Let R be the expected value of the payout function, x the strategy chosen by Player One, and y the strategy chosen by Player Two. Then Player One receives the expected payout R(x,y), and Player Two receives the expected payout -R(x,y). von Neumann posits that the goal of Player One is to maximize the payout no matter what strategy Player Two chooses. That is, they have to maximize against the worst possible counterstrategy of Player Two. If Player One declares that their strategy is x, then Player Two will pick a y that minimizes Player One’s payout. Hence, the goal of Player One is to
maximize with respect to x the minimum with respect to y of R(x,y)
Similarly, the goal of Player Two is to
maximize with respect to y the minimum with respect to x of -R(x,y)
But, just by switching the minus to a plus, we can equivalently write the goal of Player Two as to
minimize with respect to y the maximum with respect to x of R(x,y)
There is a beautiful symmetry in these objectives. Player One is maximizing a minimum. Player Two is minimizing a maximum. How do the optimal values compare? We can think of the two different formulations as declaring which player goes first. One player announces their strategy to the other, and the next player uses this information to their advantage. What you can see immediately is that whoever declares their strategy potentially has a significant disadvantage. In terms of some math:2
maxx miny R(x,y) ≤ miny maxx R(x,y)
von Neumann concedes that the rules of the game don’t require players to divulge their strategies to each other. He says “According to the rules of the game [Player Two] was not supposed to know how [Player One] was going to play, he would have to infer it some other way… Everything depends on finding the adversary out.”
The players have to keep their strategies secret somehow. But von Neumann wants a solution so that “It makes no difference which of the two players is a better psychologist.” For von Neumann, randomness is the key to mathematically rigorous, psychologically impermeable deception. He introduces an idea: what if Player One samples a strategy at random from some probability distribution of their possible strategies. They can tell Player Two the distribution in advance. Player Two can do the same. In this way, neither Player One nor Player Two really know how each other will react. The “artifice” (his words) of a random strategy lets us get around the “finding out problem.” Player One can reveal their probabilistic strategy, but Player Two can’t predict what Player One will actually do. All they can do is bet against it.
With the introduction of randomly selected strategies, something miraculous happens. Let p be the distribution of Player One, and q be the distribution of Player Two. von Neumann proves
maxp minq R(p,q) = minp maxq R(p,q)
By introducing an element of randomness, there is no longer a disadvantage to declaring your strategy outright. The payout is the same even if both players know the other’s strategy in advance.
Is this just cute mathematics? von Neumann is just proving something fundamental about convex hulls. The identification of convex combinations of points with probability distributions is purely a formal one. Interpreting the probability as randomness is part of von Neumann’s contribution.
Is he getting to the core of parlor game strategy? It’s notable that the only examples von Neumann works out here are matching penning and rock-paper-scissors. In these cases, picking a strategy uniformly at random is optimal. But von Neumann is pretty clear that he thinks we’re onto something fundamental about behavior. He writes this remarkable passage after proving the minimax theorem.
“The following point should be emphasized: Although in Section 1 chance was eliminated from the games of strategy under consideration (by introducing expected values and eliminating "draws"), it has now made a spontaneous reappearance. Even if the rules of the game do not contain any elements of "hazard" (i.e., no draws from urns) - as e.g., the two examples in 2. - in specifying the rules of behavior for the players it becomes imperative to reconsider the element of "hazard.” The dependence on chance (the "statistical" element) is such an intrinsic part of the game itself (if not of the world) that there is no need to introduce it artificially by way of the rules of the game: even if the formal rules contain no trace of it, it still will assert itself.”
In games, randomness plays a cryptographic role of concealing information from an adversary. von Neumann spends no time discussing how a rational actor might generate such cryptographically secure randomness. If Player Two knew that Player One was using Tippett’s Random Sampling Numbers to choose their random strategy, Player One would be out of luck.
Regardless, von Neumann was entranced by the idea that winning strategies needed randomness to achieve deception. The optimal strategist is a random actor. This equating rationality with mercurial avarice would be made explicit once von Neumann teamed with Oskar Morgenstern to write “Theory of Games and Economic Behavior.” That they changed the title from “A Theory of Parlor Games” to “A Theory of Games” is very telling. von Neumann and Morgenstern were after something more serious, after all: they hoped to solve all of social science and economics. And yet, as Herbert Simon immediately noted at the time, all of the examples in the 1944 book remain parlor games.
Shout out to Ludwig Schmidt for verifying my translation.
I love the purely algebraic proof of this inequality. It’s one of my favorite things to verify in an optimization class. By definition, for any a and b, R(a,b) ≤ maxx R(x,b). Now, fix a and minimize both sides with respect to b to see miny R(a,y) ≤ miny maxx R(x,y). Since this is true for all a, you can maximize with respect to a to prove the inequality. This inequality is called weak duality in optimization.
This is such a cool article, Professor! I love the idea of "randomness [playing] a cryptographic role of concealing information". Is there a way of quantifying the security of this source of randomness in a game of perfect information (when the opponent knows the random number generator strategy in addition to your strategy). I'm guessing that knowing your opponent is getting their random numbers from a quantum process does not give you any information on their next move because it is (from my understanding) a truly random process. However, as you mentioned, knowing that your opponent is using Tippett’s Random Sampling Numbers could give you much more information to predict their next move.
A bit of an aside, but I think the constraint of "zero-sum" is something that doesn't map onto human behvaior/social science. Is there clean/elegant theory on cooperative non-zero sum games?