ADVERTISEMENT
latest stories:

What is game theory and what are some of its applications?

Saul I. Gass, professor emeritus at the University of Maryland's Robert H. Smith School of Business, explains.

Game: A competitive activity involving skill, chance, or endurance on the part of two or more persons who play according to a set of rules, usually for their own amusement or for that of spectators (The Random House Dictionary of the English Language,1967).

Consider the following real-world competitive situations: missile defense, sales price wars for new cars, energy regulation, auditing tax payers, the TV show "Survivor," terrorism, NASCAR racing, labor- management negotiations, military conflicts, bidding at auction, arbitration, advertising, elections and voting, agricultural crop selection, conflict resolution, stock market, insurance, and telecommunications. What do they have in common?

A basic example helps to illustrate the point. After learning how to play the game tick-tack-toe, you probably discovered a strategy of play that enables you to achieve at least a draw and even win if your opponent makes a mistake and you notice it. Sticking to that strategy ensures that you will not lose.

This simple game illustrates the essential aspects of what is now called game theory. In it, a game is the set of rules that describe it. An instance of the game from beginning to end is known as a play of the game. And a pure strategy--such as the one you found for tick-tack-toe--is an overall plan specifying moves to be taken in all eventualities that can arise in a play of the game. A game is said to have perfect information if, throughout its play, all the rules, possible choices, and past history of play by any player are known to all participants. Games like tick-tack-toe, backgammon and chess are games with perfect information and such games are solved by pure strategies. But whereas you may be able to describe all such pure strategies for tick-tack-toe, it is not possible to do so for chess, hence the latter's age-old intrigue.

Games without perfect information, such as matching pennies, stone-paper-scissors or poker offer the players a challenge because there is no pure strategy that ensures a win. For matching pennies you have two pure strategies: play heads or tails. For stone-paper-scissors you have three pure strategies: play stone or paper or scissors. In both instances you cannot just continually play a pure strategy like heads or stone because your opponent will soon catch on and play the associated winning strategy. What to do? We soon learn to try to confound our opponent by randomizing our choice of strategy for each play (for heads-tails, just toss the coin in the air and see what happens for a 50-50 split). There are also other ways to control how we randomize. For example, for stone-paper-scissors we can toss a six-sided die and decide to select stone half the time (the numbers 1, 2 or 3 are tossed), select paper one third of the time (the numbers 4 or 5 are tossed) or select scissors one sixth of the time (the number 6 is tossed). Doing so would tend to hide your choice from your opponent. But, by mixing strategies in this manner, should you expect to win or lose in the long run? What is the optimal mix of strategies you should play? How much would you expect to win? This is where the modern mathematical theory of games comes into play.

Games such as heads-tails and stone-paper-scissors are called two-person zero-sum games. Zero-sum means that any money Player 1 wins (or loses) is exactly the same amount of money that Player 2 loses (or wins). That is, no money is created or lost by playing the game. Most parlor games are many-person zero-sum games (but if you are playing poker in a gambling hall, with the hall taking a certain percentage of the pot to cover its overhead, the game is not zero-sum). For two-person zero-sum games, the 20th century¿s most famous mathematician, John von Neumann, proved that all such games have optimal strategies for both players, with an associated expected value of the game. Here the optimal strategy, given that the game is being played many times, is a specialized random mix of the individual pure strategies. The value of the game, denoted by v, is the value that a player, say Player 1, is guaranteed to at least win if he sticks to the designated optimal mix of strategies no matter what mix of strategies Player 2 uses. Similarly, Player 2 is guaranteed not to lose more than v if he sticks to the designated optimal mix of strategies no matter what mix of strategies Player 1 uses. If v is a positive amount, then Player 1 can expect to win that amount, averaged out over many plays, and Player 2 can expect to lose that amount. The opposite is the case if v is a negative amount. Such a game is said to be fair if v = 0. That is, both players can expect to win 0 over a long run of plays. The mathematical description of a zero-sum two-person game is not difficult to construct, and determining the optimal strategies and the value of the game is computationally straightforward. We can show that heads-tails is a fair game and that both players have the same optimal mix of strategies that randomizes the selection of heads or tails 50 percent of the time for each. Stone-paper-scissors is also a fair game and both players have optimal strategies that employ each choice one third of the time. Not all zero-sum games are fair, although most two-person zero-sum parlor games are fair games. So why do we then play them? They are fun, we like the competition, and, since we usually play for a short period of time, the average winnings could be different than 0. Try your hand at the following game that has a v = 1/5.

The Skin Game: Two players are each provided with an ace of diamonds and an ace of clubs. Player 1 is also given the two of diamonds and Player 2 the two of clubs. In a play of the game, Player 1 shows one card, and Player 2, ignorant of Player 1¿s choice, shows one card. Player 1 wins if the suits match, and Player 2 wins if they do not. The amount (payoff) that is won is the numerical value of the card of the winner. But, if the two deuces are shown, the payoff is zero. [Here, if the payoffs are in dollars, Player 1 can expect to win $0.20. This game is a carnival hustler¿s (Player 1) favorite; his optimal mixed strategy is to never play the ace of diamonds, play the ace of clubs 60 percent of the time, and the two of diamonds 40 percent of the time.]

The power of game theory goes way beyond the analysis of such relatively simple games, but complications do arise. We can have many-person competitive situations in which the players can form coalitions and cooperate against the other players; many-person games that are nonzero-sum; games with an infinite number of strategies; and two-person nonzero sum games, to name a few. Mathematical analysis of such games has led to a generalization of von Neumann¿s optimal solution result for two-person zero-sum games called an equilibrium solution. An equilibrium solution is a set of mixed strategies, one for each player, such that each player has no reason to deviate from that strategy, assuming all the other players stick to their equilibrium strategy. We then have the important generalization of a solution for game theory: Any many-person non-cooperative finite strategy game has at least one equilibrium solution. This result was proven by John Nash and was pictured in the movie, A Beautiful Mind. The book (A Beautiful Mind, by Sylvia Nasar; Simon & Schuster, 1998) provides a more realistic and better-told story.

By now you have concluded that the answer to the opening question on competitive situations is "game theory." Aspects of all the cited areas have been subjected to analysis using the techniques of game theory. The web site www.gametheory.net lists about 200 fairly recent references organized into 20 categories. It is important to note, however, that for many competitive situations game theory does not really solve the problem at hand. Instead, it helps to illuminate the problem and offers us a different way of interpreting the competitive interactions and possible results. Game theory is a standard tool of analysis for professionals working in the fields of operations research, economics, finance, regulation, military, insurance, retail marketing, politics, conflict analysis, and energy, to name a few. For further information about game theory see the aforementioned web site and http://william-king.www.drexel.edu/top/eco/game/game.html.

Scientific American Holiday Sale

Limited Time Only!

Get 50% off Digital Gifts

Hurry sale ends 12/31 >

X

Email this Article

X