Game Theory: The Great Game
Despite its influence on economics and political science, game theory remained unknown and unremarked on in public circles until a recent film portrayed a mathematical theorem as a means of picking up a date in a bar. Since the film A BEAUTIFUL MIND, loosely based on economics Nobelist John Nash, interest in game theory has resurfaced. But beyond the entertaining story, what was all the mathematical fuss about?
The study of how best to play simple games has directly influenced the role of regulation in preventing environmental collapse, the design of a "doomsday strategy" to prevent nuclear war, and, in the opinion of some, to the rise and subsequent fall of the corporate giant Enron, famously accused of "gaming the system." Its origins may be traced to another figure, even more cinematic than John Nash, a mathematician and Cold Warrior who enjoyed strong drink, fast cars, and beautiful women. All this from a study of "rock, scissors, paper."
Game theory began with the study of games of chance and competition -- card games like blackjack, guessing games like penny matching and games of strategy like tic-tac-toe. Games in which two opponents compete, not by arm wrestling, but by outguessing, outplaying, and outthinking each other.
These games mix chance and choice. Chance, in the draw of a shuffled card or the roll of a die. Choice, in the selection of a card to play or a call of "heads" or "tails." Probability theory, begun with a gambler's dispute in 1654, calculates the chances -- odds -- that various events may occur in the face of uncertainty. But despite early hints, the corresponding study of the mathematics of choice -- of which card to play, considering your opponent's choices -- lay fallow for the next 250 years. Not until the 20th century did mathematicians ask clear questions that took into account the interests of both players. Game theory is the result: the mathematics of choice in interactions among players with shared or competing interests.
Our flamboyant mathematician, John von Neumann, first began asking these questions in the 1920s. He wanted to take into account an opponent's thinking as well as his own in choosing the best move for a game. Though not a skilled poker player, Johnny loved the game; for him, it was emblematic of game theory. With a poker face, concealing your intentions while discerning your opponents, you can win with a losing hand. His task was to capture the intentions and outcomes of play in mathematical terms.
John von Neumann summarized game theory in a famous book he co-authored with Oskar Morgenstern in 1944, THE THEORY OF GAMES AND ECONOMIC BEHAVIOR. The heart of the work was the analysis of games where my gain is your loss, and vice versa. These so-called zero sum two person games include the games of our childhood, like penny matching and rock-scissors-paper.
A coin matching game illustrates the basic elements of game theory. You and I each have a nickel and a quarter. We each chose one and compare our coins. Two quarters? You get to keep my quarter. Otherwise, I keep your coin, whether nickel or quarter. Ready to play?
Notice that some choices are more profitable than others. I can win 25 cents if I play a nickel and you play a quarter. If we both play quarters, I lose 25 cents. So which is my best strategy -- which coin is best to play -- and which is yours? We can show each outcome in a table of possibilities, what game theorists call a payoff matrix that shows my gains (and your losses).
This shows "nickel" is a better bet for me than "quarter." No chance of loss, and I could win a quarter. Knowing that I will always play nickel, you always play nickel to avoid losing 25 cents. A single strategy -- nickel, nickel -- dominates the game.
Now match pennies instead. We each show a penny, heads or tails up. If they match, I take your penny. If they don't, you take mine. Each of us has a choice, H or T, and the play of the other affects whether we win or lose.
The payoff matrix becomes:
Now which do I choose? Are you a tails-type person? Or a "heads man"? The last three rounds, you offered H, then T, then H. Will you go for T on the next round? Suddenly my strategy, my rational choice of the best move, isn't clear. But I do notice that if my choice is predictable, you can beat me by going the other way.
von Neumann realized that the intuitive strategy -- choose H or T randomly -- represented a special kind of dominant strategy that both players could agree upon, and that produced a stable outcome. He discovered that every two person zero sum game, regardless of how many choices there were, or what payoffs, had a specific rational strategy that mixed choice and chance. Choice, in order to maximize your results, and chance to insure that your opponent could not defeat your strategy. For penny matching, the von Neumann strategy is to pick H and T randomly, half the time each. Over time, you and I will break even by following this strategy, and neither of us can do better. Every two person zero sum game, no matter what the payoff matrix, will have its own best mix of choice and chance, and no player can consistently beat this strategy. For Johnny, this solved the problem of the two person zero sum game. And poker? He continued to lose. Poker, it turned out, was far too complex to be aided by game theory.
Few adult experiences are as simple and tidy as the games of childhood. Real world exchanges are often mixtures of collaboration and competition. Many win-win situations share gains rather than trade wins for losses, while wars generate losses for everyone. But little progress was made on extending the certainty of zero sum game solutions to multiple players and to non-zero payouts until John Nash's groundbreaking results in 1950, the year he turned 21.
Nash, whose brilliant and poignantly tragic career was portrayed in A BEAUTIFUL MIND, generalized von Neumann's famous "Minmax theorem," proving that equilibrium solutions exist for many multiple player non-zero sum games. He showed that when such a solution existed, that it would be stable; that it would never pay for any single participant to deviate from the equilibrium strategy. Among the real world consequences of his work is that, because deals that make rational sense to the participants are known to exist, it is worth it to find them. This knowledge can make such deals happen.
In the same year, one of Nash's mentors, A. W. Tucker (fact check this!) told a story at Stanford to illustrate a non-zero sum game called the Prisoner's Dilemma. The following simple puzzle shook the foundations of game theory. Its consequences are still controversial.
Once upon a time … two burglars, Bob and Al, are captured by police and interrogated separately. Each has to choose whether or not to confess and implicate the other. If neither confesses, both will serve one year in prison -- they were carrying concealed weapons. If each confesses to burglary and implicates the other, both will go to prison for 10 years. However, if one burglar confesses and implicates the other, and the other burglar does not confess, the one who has collaborated with the police will go free, while the other burglar will go to prison for 20 years on the maximum charge.
Straightforward payoff matrices capture the possible outcomes for Bob and Al.
The strategies are confess or stay silent and the payoffs (penalties, actually) are the sentences served. What choice should each make? Bob reasons as follows: "If Al confesses, then I get 20 years if I don't confess, 10 years if I do. So if he confesses, so should I. If Al doesn't confess, then I go free if I do confess, and get a year if I don't. Either way, I'm better off if I confess." But Al, in exactly the same boat, comes to the same conclusion. They do the only rational thing … and go to prison for 10 years each. Yet, if each had acted "irrationally," and kept quiet, they could have gotten off with one year each. The depressing conclusion is that rational behavior is not rational!
Though many criticisms have been leveled at this simple interpretation, none have laid it to rest. Its theme of individual irrationality was applied to communities some years later in a now famous essay by Garrett Hardin, "The Tragedy of the Commons." In it, he argued that in many environmental situations, individual self-interest would override the common good, leading to worse outcomes for all, unless the common good were enforced, not by individual reason, but by societal machinery. These negative consequences of game theory thinking echo in the dilemmas of the modern world: arms races, road congestion, overfishing, and global warming, are only a few.
The influence of game theory reaches far beyond card room or casino. Anywhere an understanding of human choice, conflict, or cooperation is an issue, the concepts and techniques of game theory come into play. It informs the design of auctions of broadcast spectrum licenses. It undergirds many complex financial transactions. It has shaped the structure of both nuclear arms races and disarmament agreements. But ultimately, human aspirations and human failings are more complex than any solvable game, more subtle than any payoff matrix. We have found no shared strategy that can avoid the tragedy of the commons, resolve the prisoner's dilemma, or even win us a hand of poker. The ultimate lesson of game theory may be that life is far more than a game.
-- Michael Templeton
|© 2003 Educational Broadcasting Corporation. All rights reserved.