But as later commentators noted, von Neumann had led himself into an inconsistency, threatening his theory's internal integrity. A key part of two-person zero-sum games was choosing a strategy that was the best you could do against a smart opponent. Your best bet was to play your optimal (probably mixed) strategy no matter what anybody else did. But if coalitions formed among players in many-person games, as von Neumann believed they would, that meant your strategy would in fact depend on coordinating it with at least some of the other players. In any event, game theory describing many players interacting in non-zero-sum situations— that is, game theory applicable to real life—needed something more than the original Theory of Games had to offer. And that's what John Nash provided.
BEAUTIFUL MATH
The book A Beautiful Mind offers limited insight into Nash's math, particularly in regard to all the many areas of science where that math has lately become prominent.8 But the book reveals a lot about Nash's personal troubles. Sylvia Nasar's portrait of Nash is not very flattering, though. He is depicted as immature, self-centered, arrogant, uncaring, and oblivious. But brilliant.
Nash was born in West Virginia, in the coal-mining town of Bluefield, in 1928. While showing some interest in math in high school (he even took some advanced courses at a local college), he planned to become an electrical engineer, like his father. But by the time he enrolled at Carnegie Tech (the Carnegie Institute of Technology) in Pittsburgh, his choice for major had become chemical engineering. He soon switched to chemistry, but that didn't last, either. Finding no joy in manipulating laboratory apparatus, Nash turned to math, where he excelled.
He first mixed math with economics while taking an undergraduate course at Carnegie Tech in international economics. In that class Nash conceived the idea for a paper on what came to be called the "bargaining problem." As later observers noted, it was a paper obviously written by a teenager—not because it was intellectually naive, but because the bargaining he considered was over things like balls, bats, and pocket knives. Nevertheless the mathematical principles involved were clearly relevant to more sophisticated economic situations.
When Nash arrived at Princeton in 1948, it had already become game theory's world capital. Von Neumann was at the Institute for Advanced Study, just a mile from the university, and Morgenstern was in the Princeton economics department. And at the university math department, a cadre of young game theory enthusiasts had begun exploring the new von Neumann– Morgenstern continent in earnest. Nash himself attended a game theory seminar led by Albert W. Tucker (but also explored game theory's implications on his own).
Shortly after his arrival, Nash realized that his undergraduate ideas about the "bargaining problem" represented a major new game theory insight. He prepared a paper for publication (with assistance from von Neumann and Morgenstern, who "gave helpful advice as to the presentation").
"Bargaining" represents a different form of game theory in which the players share some common concerns. Unlike the two-person zero-sum game, in which the loser loses what the winner wins, a bargaining game offers possible benefits to both sides. In this "cooperative" game theory, the goal is for all players to do the best they can, but not necessarily at the expense of the others. In a good bargain, both sides gain. A typical real-life bargaining situation would be negotiations between a corporation and a labor union.
In his bargaining paper, Nash discussed the situation when there is more than one way for the players to achieve a mutual benefit. The problem is to find which way maximizes the benefit (or utility) for both sides—given that both players are rational (and know how to quantify their desires), are equally skilled bargainers, and are equally knowledgeable about each other's desires.
When bargaining over a possible exchange of resources (in Nash's example, things like a book, ball, pen, knife, bat, and hat), the two players might assess the values of the objects differently. (To the athletic minded, a bat might seem more valuable than a book, while the more intellectually oriented bargainer might rank the book more valuable than the bat.) Nash showed how to consider such valuations and compute each player's gain in utility for various exchanges, providing a mathematical map for finding the location of the optimal bargain—the one giving the best deal for both (in terms of maximizing the increase in their respective utilities).9
SEEKING EQUILIBRIUM
Nash's bargaining problem paper would in itself have established him as one of game theory's leading pioneers. But it was another paper, soon to become his doctoral dissertation, that established Nash as the theory's prophet. It was the paper introducing the "Nash equilibrium," eventually to become game theory's most prominent pillar.
The idea of equilibrium is, of course, immensely important to many realms of science. Equilibrium means things are in balance, or stable. And stability turns out to be an essential idea for understanding many natural processes. Biological systems, chemical and physical systems, even social systems all seek stability. So identifying how stability is reached is often the key to predicting the future. If a situation is unstable—as many often are—you can predict the future course of events by figuring out what needs to happen to achieve stability. Understanding stability is a way of knowing where things are going.
The simplest example is a rock balanced atop a sharply peaked hill. It's not a very stable situation, and you can predict the future pretty confidently: That rock is going to roll down the hill, reaching an equilibrium point in the valley. Another common example of equilibrium shows up when you try to dissolve too much sugar in a glass of iced tea. A pile of sugar will settle at the bottom of the glass. When the solution reaches equilibrium, molecules will continue to dissolve out of the pile, but at the same rate as other sugar molecules drop out of the tea and join the pile. The tea is then in a stable situation, maintaining a constant sweetness.
It's the same principle, just a little more complicated, in a chemical reaction, where stability means achieving a state of "chemical equilibrium," in which the amounts of the reacting chemicals and their products remain constant. In a typical reaction, two different chemical substances interact to produce a new, third substance. But it's often not the case that both original substances will entirely disappear, leaving only the new one. At first, amounts of the reacting substances will diminish as the quantity of the product grows. But eventually you may reach a point where the amount of each substance doesn't change. The reaction continues—but as the first two substances react to make the third, some of the third decomposes to replenish supplies of the first two. In other words, the action continues, but the big picture doesn't change.
That's chemical equilibrium, and it is described mathematically by what chemists call the law of mass action. Nash had just this sort of physical equilibrium in mind when he was contemplating stability in game theory. In his dissertation he refers to "the ‘mass-action' interpretation of equilibrium," and that such an equilibrium is approached in a game as players "accumulate empirical information" about the payoffs of their strategies.10
When equilibrium is reached in a chemical reaction, the quantities of the chemicals no longer change; when equilibrium is reached in a game, nobody has any incentive to change strategies—so the choice of strategies should remain constant (the game situation is, in other words, stable). All the players should be satisfied with the strategy they've adopted, in the sense that no other strategy would do better (as long as nobody else changes strategies, either). Similarly, in social situations, stability means that everybody is pretty much content with the status quo. It may not be that you like things the way they are, but changing them will only make things worse. There's no impetus for change, so like a rock in a valley, the situation is at an equilibrium point.
In a two-person zero-sum game, you can determine the equilibrium point using von Neumann's minimax solution. Whether using a pure strategy or a mixed strategy, neither player has anything to gain by deviating from the optimum strategy that game theory prescribes. But von Neumann did
not prove that similarly stable solutions could be found when you moved from the Robinson Crusoe–Friday economy to the Gilligan's Island economy or Manhattan Island economy. And as you'll recall, von Neumann thought the way to analyze large economies (or games) was by considering coalitions among the players.
Nash, however, took a different approach—deviating from the "party line" in game theory, as he described it decades later. Suppose there are no coalitions, no cooperation among the players. Every player wants the best deal he or she can get. Is there always a set of strategies that makes the game stable, giving each player the best possible personal payoff (assuming everybody chooses the best available strategy)? Nash answered yes. Borrowing a clever piece of mathematical trickery known as a "fixed-point theorem," he proved that every game of many players (as long as you didn't have an infinite number of players) had an equilibrium point.
Nash derived his proof in different ways, using either of two fixed-point theorems—one by Luitzen Brouwer, the other by Shizuo Kakutani. A detailed explanation of fixed-point theorems requires some dense mathematics, but the essential idea can be illustrated rather simply. Take two identical sheets of paper, crumple one up, and place it on top of the other. Somewhere in the crumpled sheet will be a point lying directly above the corresponding point on the uncrumpled sheet. That's the fixed point. If you don't believe it, take a map of the United States and place it on the floor—any floor within the United States. (The map represents the crumpled up piece of paper.) No matter where you place the map, there will be one point that is directly above the corresponding actual location in the United States. Applying the same principle to the players in a game, Nash showed that there was always at least one "stable" point where competing players' strategies would be at equilibrium.
"An equilibrium point," he wrote in his Ph.D. thesis, "is … such that each player's mixed strategy maximizes his payoff if the strategies of the others are held fixed."11 In other words, if you're playing such a game, there is at least one combination of strategies such that if you change yours (and nobody else changes theirs) you'll do worse. To put it more colloquially, says economist Robert Weber, you could say that "the Nash equilibrium tells us what we might expect to see in a world where no one does anything wrong."12 Or as Samuel Bowles described it to me, the Nash equilibrium "is a situation in which everybody is doing the best they can, given what everybody else is doing."13
Von Neumann was dismissive of Nash's result, as it did turn game theory in a different direction. But eventually many others recognized its brilliance and usefulness. "The concept of the Nash equilibrium is probably the single most fundamental concept in game theory," declared Bowles. "It's absolutely fundamental."14
GAME THEORY GROWS UP
Nash published his equilibrium idea quickly. A brief (two-page) version appeared in 1950 in the Proceedings of the National Academy of Sciences. Titled "Equilibrium Points in n-Person Games," the paper established concisely (although not particularly clearly for nonmathematicians) the existence of "solutions" to many-player games (a solution being a set of strategies such that no single player could expect to do any better by unilaterally trying a different strategy). He expanded the original paper into his Ph.D. thesis, and a longer version was published in 1951 in Annals of Mathematics, titled "Non-cooperative Games."
Von Neumann and Morgenstern, Nash politely noted in his paper, had produced a "very fruitful" theory of two-person zero-sum games. Their theory of many-player games, however, was restricted to games that Nash termed "cooperative," in the sense that it analyzed the interactions among coalitions of players. "Our theory, in contradistinction, is based on the absence of coalitions in that it is assumed that each participant acts independently, without collaboration or communication with any of the others."15 In other words, Nash devised an "every man for himself" version of many-player games—which is why he called it "noncooperative" game theory. When you think about it, that approach pretty much sums up many social situations. In a dog-eat-dog world, the Nash equilibrium describes how every dog can have its best possible day. "The distinction between non-cooperative and cooperative games that Nash made is decisive to this day," wrote game theorist Harold Kuhn.16
To me, the really key point about the Nash equilibrium is that it cements the analogy between game theory math and the laws of physics—game theory describing social systems, the laws of physics describing natural systems. In the natural world, everything seeks stability, which means seeking a state of minimum energy. The rock rolls downhill because a rock at the top of a hill has a high potential energy; it gives that energy away by rolling downhill. It's because of the law of gravity. In a chemical reaction, all the atoms involved are seeking a stable arrangement, possessing a minimum amount of energy. It's because of the laws of thermodynamics.
And just as in a chemical reaction all the atoms are simultaneously seeking a state with minimum energy, in an economy all the people are seeking to maximize their utility. A chemical reaction reaches an equilibrium enforced by the laws of thermodynamics; an economy should reach a Nash equilibrium dictated by game theory.17
Real life isn't quite that simple, of course. There are usually complicating factors. A bulldozer can push the rock back up the hill; you can add chemicals to spark new chemistry in a batch of molecules. When people are involved, all sorts of new sources of unpredictability complicate the game theory playing field. (Imagine how much trickier chemistry would become if molecules could think.18)
Nevertheless, Nash's notion of equilibrium captures a critical feature of the social world. Using Nash's math, you can figure out how people could reach stability in a social situation by comparing that situation to an appropriate game. So if you want to apply game theory to real life, you need to devise a game that captures the essential features of the real-life situation you're interested in. And life, if you haven't noticed, poses all sorts of different circumstances to cope with.
Consequently game theorists have invented more games than you can buy at Toys R Us. Peruse the game theory literature, and you'll find the matching pennies game, the game of chicken, public goods games, and the battle of the sexes. There's the stag hunt game, the ultimatum game, and the "so long sucker" game. And hundreds of others. But by far the most famous of all such games is a diabolical scenario known as the Prisoner's Dilemma.
TO RAT OR NOT TO RAT
As in all my books, a key point has once again been anticipated by Edgar Allan Poe. In "The Mystery of Marie Roget," Poe described a murder believed by Detective Dupin to have been committed by a gang. Dupin's strategy is to offer immunity to the first member of the gang to come forward and confess. "Each one of a gang, so placed, is not so much … anxious for escape, as fearful of betrayal," Poe's detective reasoned. "He betrays eagerly and early that he may not himself be betrayed."19 It's too bad that Poe (who was in fact a trained mathematician) had not thought to work out the math of betrayal—he might have invented game theory a century early.
As it happened, the Prisoner's Dilemma in game theory was first described by Nash's Princeton professor, Albert W. Tucker, in 1950. At that time, Tucker was visiting Stanford and had mentioned his game theory interests. He was asked unexpectedly to present a seminar, so he quickly conjured up the scenario of two criminals captured by the police and separately interrogated.20
You know the story. The police have enough evidence to convict two criminal conspirators on a lesser offense, but need one or the other to rat out his accomplice to make an armed robbery charge stick. So if both keep mum, both will get a year in prison. But whoever agrees to testify goes free. If only one squeals, the partner gets five years. If both sing like a canary, then both get three years (a two-year reduction for copping a plea).
Years in prison for Bob, Alice
If you look at this game matrix, you can easily see where the Nash equilibrium is. There's only one combination of choices where neither player has any incentive to change strategies—they both rat each other out. Think abou
t it. Let's say our game theory experts Alice and Bob have decided to turn to crime, but the police catch them. The police shine a light in Bob's face and spell out the terms of the game. He has to decide right away. He ponders what Alice might do. If Alice rats him out—a distinct possibility, knowing Alice—his best choice is to rat her out, too, thereby getting only three years instead of five. But suppose Alice keeps mum. Then Bob's best choice is still to rat her out, as he'll then get off free. No matter which strategy Alice chooses, Bob's best choice is betrayal, just as Poe's detective had intuited. And Alice, obviously, must reason the same way about Bob. The only stable outcome is for both to agree to testify, ratting out their accomplice.
Ironically, and the reason it's called a dilemma, they would both be better off overall if they both kept quiet. But they are interrogated separately, with no communication between them permitted. So the best strategy for each individual produces a result that is not the best result for the team. If they both keep mum (that is, they cooperate with each other), they spend a total of two years in prison (one each). If one rats out the other (technical term: defects), but the other keeps mum, they serve a total of five years (all by the silent partner). But when they rat each other out, they serve a total of six years—a worse overall outcome than any of the other pairs of strategies. The Nash equilibrium—the stable pair of choices dictated by self-interest—produces a poorer payoff for the group. From the standpoint of game theory and Nash's math, the choice is clear. If everybody's incentive is to get the best individual deal, the proper choice is to defect.
A Beautiful Math Page 7