# Game Theory

Introduction

Conflict has been a central theme throughout human history. It arises whenever two or more individuals, with different values, compete to try to control the course of events. Game theory uses mathematical tools to study situations involving both conflict and cooperation.

The players in a game, who may be people or organizations, choose from a list of options available to them - these choices are called strategies. The strategies chosen by the players lead to outcomes, which describe the consequences of their choices. We assume that the players have preferences for the outcomes: they like some more than others.
Game theory analyzes the rational choice of strategies - that is strategies that lead to the preferred outcomes.

Game theory has been successfully applied to areas such as the military choices in warfare and in international crises, resource-allocation decisions in political campaigns, bargaining tactics in labor-management disputes, gambling theory, and statistics.

In the next section we present the short history of the subject. Then we present several examples of two-person zero-sum games, in which what one player wins the other player loses, so cooperation never benefits the players. We distinguish two different kinds of solutions to such games. Next we analyze some well-known games of partial conflict, in which the players can benefit from cooperation but may have strong incentives not to cooperate.

History

As early as the seventeenth century, such outstanding mathematicians as Christiaan Huygens (1629-1695) and Gottfried W. Leibniz (1646-1716) proposed the creation of a discipline that would make use of the scientific method to study human conflict and interactions. Throughout the nineteenth century, several leading economists created simple mathematical examples to analyze particular examples of competitive situations. The first general mathematical theorem in this subject was proved by the distinguished mathematician Ernst Zermelo (1871-1956) in 1912. It stated that any finite game with perfect information, such as tic-tac-toe, checkers or chess, has an optimal solution in pure strategies, which means that no randomization or secrecy is necessary. A game is said to have perfect information if at each stage of the play, every player is aware of all past moves by himself and others as well as all future choices that are allowed. This theorem is an example of an existence theorem: it demonstrates that there must exist a best way to play such a game, but it does not provide its construction that is a detailed plan for playing that game.

The mathematician  Emile Borel (1871-1956) introduced the notion of a mixed, or randomized, strategy when he investigated some elementary duels around 1920. John von Neumann  proved in 1928, that every two-person, zero-sum game must have optimal mixed strategies and an expected value for the game. His result was extended to the existence of equilibrium outcomes in  mixed strategies for multiperson games that are either constant-sum or variable-sum by John F. Nash Jr. (1931-), in 1951.

Modern game theory dates from the famous minimax theorem that was proven by von Neumann. He gradually expanded his work in game theory, and with co-author Oskar Morgenstern, he wrote the classic text Theory of Games and Economic Behaviour (1944). They introduced the first general model and solution concept for multiperson cooperative games, which are primarily concerned with coalition formation (economic, voting blocs, and military alliances) and the resulting distribution of gains or losses.

The Nobel Memorial Prize in Economics was awarded to three game theorists in 1994.The recipients were John C. Harsanyi (1920-    ) of the University of California, Berkeley, John F. Nash of Princeton University, and Reinhard Selten (1930-    ) of the University of Bonn, Germany.

Game theory has provided important theoretical foundations in economics, political science especially in the study of voting, elections, and international relations. In addition, game theory has contributed major insights in environmental sciences, particularly in understanding the evolution of species and conditions under which animals fight each other for territory or act cooperatively.

Game Theory - The Minimax Theorem

The starting point of the mathematical theory of games is the situation in which the outcome of the game is determined by the strategies employed by the players. The notion of a minimax point, a set of optimal strategies for all players in the game, is what makes this a theory and not a heuristic. When the payoffs for all players in a game add up to zero, this is called a "zero-sum situation". A payoff matrix is used to express the overall situation. The entries in the matrix are the payoffs to the "row player" and the "column player". A "risk-averse" decision is one that forsakes possible gains in order to avoid incurring unnecessary losses. Examples of payoff matrices will follow.

A combination of actions, in which the maximum of the row minimax equals the minimum of the column maxima is called an equilibrium point of the game. This is because by choosing these actions the two players can guarantee themselves a certain minimal payoff - regardless of what their opponent chooses to do. The equilibrium solution is "bulletproof", or stable, in the sense that either player can announce his choice in advance to the opponent, secure in the knowledge that the opponent cannot make use of this information to get a better payoff. An equilibrium decision point is often termed a saddle point. Such a point is often also known as a minimax point. What's important about a saddle point is that it represents a decision by two players that neither can improve upon by unilaterally departing from it.

The best choice for each player is at the saddle point, which is called a "solution" to the game in pure strategies. The optimal choice for each player is to always take his/her saddle point decision, if such an option exists.

A game of "pure strategy" consists of three interrelated components:

• Players: A game involves a minimum of two players who have differing interests.

•

Actions: At each stage of play the players choose their course of action from a set of possible decisions, which are not usually the same for each player. Often, the players must make their decisions without knowledge of the actions chosen by the other players. We will assume that each player has only a finite number of possible decisions, although some interesting and important games make use of decisions sets, which are infinite.

Payoffs: After the decisions have been made, each player receives a certain payoff measured in a common unit for all players.

A rule for choosing an action is termed a strategy. If the rule says to always take the same action it's called a pure strategy; otherwise the strategy is known as mixed. A game involving a sequence of choices by each player is called a multistage or iterated game. Games where there are only two players whose interests are directly opposed are termed two-person, zero-sum games.

In game theory, the way out of what we might term the "no-saddle point dilemma" is to invent a new notion of what we mean by rational behavior. Without a saddle point all bets are off, since we have then lost our notion of what it means to be "rational". It turns out that the way to recapture this kind of "immunity from disclosure" is to act in such a way that you don't even know yourself what you're going to do until you do it ("no-knowledge")!

The pivotal result in the mathematical theory of games was John von Neumann's Minimax Theorem in 1928. It asserts that for every two-person, zero-sum game there is an optimal strategy for each player. The Minimax Theorem says that the way to recapture rationality is to use strategies that randomize a player's choice over all possible actions. The value of the game is the optimal payoff. Von Neumann's Minimax Theorem makes the strong assertion that there always exists at least one mixed strategy for each player, such that the average payoff to each player is the same when he uses these strategies.

Minimax Theorem: For every two-person, zero-sum game there exists a mixed strategy for each player such that the expected payoff for both is the same value V when the players use these strategies. Furthermore, V is the best payoff each can expect to receive from a play of the game; hence these mixed strategies are the optimal strategies for the two players to employ.

"As far as I can see, there could be no theory of games… without that theorem… I thought there was nothing worth publishing until the 'Minimax Theorem' was proved," remarked von Neumann.

The Minimax Theorem expresses the idea of "rational action". A view of rationality we might colloquially describe as "hope for the best, prepare for the worst." John Nash proved a theorem that generalizes the Minimax Theorem to the case of nonzero-sum games involving two or more players when all the players are in direct competition - noncooperative games.

Nash's Theorem: Any n-person, uncooperative game (zero-sum or nonzero-sum) for which each player has a finite number of pure strategies has at least one equilibrium set of strategies.

There are three important aspects of this theorem: (1) it generalizes the Minimax Theorem in the sense that it establishes the existence of an equilibrium solution for both zero-sum and nonzero-sum games, (2) it shows that there may be more than one such solution, and (3) it extends to the case of any finite number of players.

The Minimax Theorem defines how to proceed rationally in what were previously seen as irrational situations. If nothing else, game theory has cut one of the major Gordian knots of philosophy: the barrier between rational and irrational behavior. Numerical analyst Richard W. Hamming said, "the purpose of game theory is insight, not solutions."

Games

"The Prisoner's Dilemma": This is a classic two-player nonzero-sum game, which illustrates many points of game theory.

In this game, the two players are partners in a crime who have been captured by the police. Each suspect is placed in a separate cell and offered the opportunity to confess to the crime.

We will now set up the payoff matrix (as discussed earlier). In this case, the actions of the first player form the rows and the actions of the second player form the columns. The entries in the matrix are two numbers representing the payoff to the first and second player respectively.

 Not Confess Confess Not confess 5, 5 0, 10 Confess 10, 0 1, 1
If neither suspect confesses, they go free, and split the proceeds of their crime, which we represent, by 5 units of payoff for each suspect. However, if one prisoner confesses and the other does not, the prisoner who confesses testifies against the other in exchange for going free and gets the entire 10 units of payoff, while the prisoner who did not confess goes to prison and gets nothing. If both prisoners confess, then both are convicted but given a reduced term, which we represent by giving 1 unit of payoff: it's better than having just the other prisoner confess, but not so good as going free.

This game is a simple representation of a variety of important aspects of game theory. No matter what a suspect believes his partner is going to do, it is always best to confess. If the partner in the other cell is not confessing, it is possible to get 10 instead of 5 as a payoff. If the partner in the other cell is confessing, it is possible to get 1 instead of 0. Yet the pursuit of individually sensible behavior results in each player getting only 1 as a payoff, much less than the 5 which they would get if neither confessed. This conflict between the pursuit of individual goals and the common good is at the heart of many game theoretic problems.

"Weebles vs. Wobbles": The following is an example of a zero-sum game and illustrates how what seems "rational behavior" is not always so. It is a simplified model of price competition as can be studied in economics.

Let us imagine two companies that sell widgets, the Weeble Co and Wobble Inc. Each company has a set cost of \$5,000 per year, regardless of how many widgets they sell or if they sell any at all.

The two companies are competing for the same market and each firm must choose a high price (\$2 per widget) or a low price (\$1 per widget). Here are the rules of the game:

1) At a price of \$2 - 5,000 widgets can be sold for a total revenue of \$10,000. (These numbers represent the entire widget industry, both companies).

2) At a price of \$1 - 10,000 widgets can be sold for a total revenue of \$10,000.

3) If both companies charge the same price, they split the sales evenly between them.

4) If one company charges a higher price, the company with the lower price sells the whole amount and the company with the higher price sells nothing.

5) Payoffs are profits - revenue minus fixed cost (\$5,000 as mentioned).

Here is the payoff matrix for these two companies:

Weeble Co

 Price = \$1 Price = \$2 Wobble Inc. Price = \$1 0, 0 5000, -5000 Price = \$2 -5000, 5000 0, 0
For two-person, zero-sum games, there is a clear concept of a solution. The solution to the game is the maximum criterion - that is, each player chooses the strategy that maximizes his/her/its minimum payoff. In this game, Weeble Inc's minimum payoff at a price of \$1 is zero, and at the price of \$2 it is -5000, so the \$1 price maximizes the minimum payoff. The same reasoning applies to the fine people at the Wobble Co, so both will choose the \$1 price. Here is the reasoning behind the maximin solution: Weeble Inc knows that whatever it loses, the Wobble Co gains; so, whatever strategy it chooses, the Wobble Co will choose the strategy that gives the maximum payoff for that row. Again, the Wobble Co reasons conversely.

"Head Over Tails": This game is another example of a zero-sum game but, unlike the Weeble-Wobble example, does not lend itself to a pure strategy. Rather, its solution is a mixed-strategy, which we discussed earlier.

The two players of this game are Jack and Jill just prior to their trip on the hill. Each has a sack of pennies. On each turn of the game, they will reveal pennies simultaneously, and each player may show either a head (Abraham Lincoln's head, to be precise) or a tail (the Lincoln monument). If both show the same side, Jill wins the penny from Jack; or, if they show different sides, Jack wins the penny from Jill. Here is the payoff matrix for this game:

Jack

 Head Tail Jill Head 1, -1 -1, 1 Tail -1, 1 1, -1
If we add up the payoffs in each cell, we find 1-1=0. That's what makes this a zero-sum game.

It would at first appear that this game does not have a dominant strategy (or unique solution). The minimum payoff for each of the two pure strategies is the same: -1. But this is not the whole story. This game actually has more than two strategies. In addition to the two obvious strategies (always showing a head or always showing a tail), a player can "randomize" his/her strategy by offering either a head or a tail, at random, with specified probabilities. Such a randomized strategy is called a mixed-strategy and was explained in von Neumann's Minimax Theorem.

The solution for this particular game is to offer heads or tails with the random probability of 0.5 each way. Here is the reasoning: if Jack offers heads with any probability greater than 0.5, then Jill can have better than even odds of winning by offering heads with probability of 1 (i.e. always) and guaranteeing that more than half the time the two coins will match. On the other hand, if Jack offers heads with any probability less than 0.5, then Jill can guarantee statistical success by offering tails with probability 1. The only way Jack can get even odds of winning is to choose a randomized strategy with probability 0.5, and there is no way Jill can get better than even odds. The 0.5 probability maximizes the minimum payoff over all pure or mixed strategies (and there are an infinite number of mixed strategies with every probability between 0 and 0.5).

Jack and Jill will necessarily reason the same way and so both players will choose 0.5. This sort of game presents the unique situation, as discusses above, in which the opponents can announce their strategy in advance and suffer no ill consequences (that is, this is a "no-knowledge" strategy).