Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

# 9.2 Origins of Game Theory

## GAMES PEOPLE PLAY

• Mathematicians attempt to analyze types of interactions by treating them as games in which players use strategies to obtain payoffs.
• Games like checkers and chess are games of perfect information; the board shows both players all the information needed to make the right decision.
• Games like poker are games of imperfect information; no player has enough information (the other players' cards are hidden) to make a guaranteed right decision.

Games have appeared throughout history, and in many different cultures, as a form of entertainment and education. The first mathematical analyses of certain games occurred in the 1700s, centered around the card game Le Her, but it was not until the mid-1920s that the field of game theory was properly founded by the multi-talented Hungarian mathematician and physicist, John von Neumann.

Von Neumann was an exceptional character and ranks among the brightest minds of the first half of the twentieth century. He was involved in many fields, including quantum physics, topology, computer science, and economics. He also worked on the Manhattan Project, the top-secret effort that built the first atomic bomb. In his leisure time, he was an avid poker player, and his interest in games and how they "work" is said to have stemmed partly from this fascination. Poker is a game in which mathematics and human nature square off. A player must not only be good at calculating odds, but must also be able to read the other players to tell if they are bluffing or not.

Poker players are able to bluff one another because poker is a game of imperfect information. As a player, you know your own cards and you know what the other players have wagered, but you do not know what cards they hold. It is this missing information that brings excitement to the game and makes it challenging. Many of the games we will explore in this discussion present situations similar to those that arise in poker, in that players do not know all of the information available and yet still must make decisions.

Certain games of imperfect information can lead to interesting scenarios in which players unwittingly act against their own best interests.

By contrast, chess is a game with perfect information. In a game of chess, knowledge of the positions (i.e., the pieces and board set-up) and all historical information regarding the moves are available to both players. Players must use this information to formulate and modify strategies and tactics during a match. The challenge of chess lies not in the ambiguity of not knowing what your opponent has to work with, but rather in the extreme complexity of possible scenarios, each requiring a good deal of analysis. Despite their differences, poker and chess have one very important characteristic in common: both are zero-sum games.

## ZERO SUM

• Zero-sum games are games in which a winner's payoff is equal to a loser's loss.
• Utility is an imprecise concept, but biological payoffs are measurable.

Zero-sum games are games in which one player's loss is exactly equal to another player's gain. If you win a hand at poker, your winnings will add up to the sum of your opponents' losses (unless you play at a casino, where the house takes a cut). At the end of the day, poker players (as a group) are no wealthier or poorer than when they started. Likewise, in chess, one person's victory is balanced by the opponent's loss. Even when a chess match ends in a stalemate, then both players are no better off than when they started-neither has gained or lost anything, except perhaps time, but that is not taken into account.

Not all situations in life, or game theory, are zero-sum situations, however. Two notable examples are business transactions and arms races. In an arms race, two or more nations compete to build the most-and the most destructive-weapons possible. This is a situation in which there are many outcomes that leave all "players" worse off than when they started. If they invest heavily in weapons, but then never use them, they have squandered a good deal of their resources and are poorer for it. Also, if the nations use their weapons and go to war, there is much squandering of resources, and all are worse off than before.

In business transactions, both parties exchange something for something that they find more valuable. If you trade ten dollars for a hat, you have obviously decided that the hat is more valuable to you than your ten dollars (or, at least, equally valuable). Likewise, your ten dollars is more valuable than the hat to the hat-seller. This idea of relative value is what economists call "utility." It is through increased or decreased utility that non-zero-sum arrangements are possible.

Utility, however, has proved to be a rather controversial concept. When game theory is applied to biology, or evolution, the concept of utility comes through in the term "biological fitness." In this context, game theory measures payoffs in terms of reproductive success-the objective number of offspring that a "player" leaves behind to carry on a genetic legacy.

## MINIMIZE THE WORST-CASE SCENARIO

• The minimax theorem, attributable to Von Neumann and Morgenstern, states that players seek the strategy that minimizes their maximum loss.

Von Neumann focused the bulk of his research on zero-sum games. He and economist Oskar Morgenstern established the field of game theory with the publication of their book "The Theory of Games and Economic Behavior," which was primarily an analysis of the zero-sum situation. Von Neumann and Morgenstern worked from the fundamental assumption that players always act in a way that increases their utility-that is, they always implement the strategy that they perceive will bring them the greatest reward. This is the classic definition of "rational," in the context of game theory. Furthermore, Von Neumann showed that in any two-player, zero-sum, game, there will always be a best, or optimal, strategy for each player. This will be the strategy that maximizes the minimum possible gain, or utility, dependent on what the other player does.

This theorem, known as the "minimax theorem," set the foundation for the mathematical study of games. It states that there is always a strategy that a player can choose that will lead to their most-favorable worst possible outcome. Depending on the specific rules of the game, that outcome might not be better than that of another player, but it will be better than the alternatives, provided the other player is playing in a similar fashion. For instance, even in a game as complex as chess, there exists an outcome that should happen every time, provided both players play perfectly. This means that, theoretically, one of the three possible outcomes of chess-a white win, a black win, or a draw-should be the "right" outcome if both players play perfectly. The game is so complex, however, that the strategies that each person should employ to produce this ideal outcome are unknown.

An easier example to consider is the game of tic-tac-toe (TTT). A good TTT player can never be beaten. A good player, given the first move, will always take a corner square, and any rational opponent will then take the center square. Play continues from this point, with the players making the moves that ensure that they will not lose, yet that also leave their best winning options open. Because of the layout and the rules of TTT, this means that when two good players play each other, the result will always be a tie. This is the "right" outcome, provided no one makes a mistake.

One way to analyze the game progression is through the use of a "game tree." A game tree provides a systematic way to lay out all sequences of moves in a game in visual format. Each move is represented by a node, whose branches represent all the possible countermoves. Even for a game as simple as TTT, the game tree gets very large, as there are over 300,000 (9!) possible sequences of moves and countermoves that must be taken into account.

Now that we've been introduced to some of the general concepts and terms that will be used in our discussion of game theory, let's turn our attention to a few specific games and analyses.