Mark Newheiser - Game Theory

Introduction

Game theory is a mathematical model used to represent and describe various games, which are simply scenarios in which two or more people can make choices which lead to different outcomes. Ideally, the outcomes can be fully determined by the choices made. In the game of chess for example, if you know all the moves both players will make you know the outcome. And in a game of chicken, if you know what both people will do, you know the outcome as well. Poker isn't a good example of this type because so much is left up to chance--you can describe and reason about a strategies using probability, but because of randomness it can't be described completely.

Decision Trees and Tables

Games can be described in a number of different ways. You can use a decision tree to describe games in which you have a series of sequential choices being made, such as a game like tic-tac-toe, and where the outcome is dependent upon all the choices of both players. If you look all the way down the tree, you can examine all the possible outcomes and reason about what the best moves to make would be, assuming your opponent also makes the best possible moves.

Unfortunately, Tic-Tac-Toe alone has a decision tree with 362,800 elements, so we'd have a hard time reasoning about that one by hand although it's no trouble for a computer. Chess similarly has 10^43 possible board positions in the space of just 40 moves, which is of course roughly equal to the entire lifetime of the universe measured in seconds. I talk some about dealing with this type of complexity elsewhere, but this type of analysis is best reserved for games with only a few choices.

Some of the most interesting applications of game theory come from situations where you're just describing a single choice on the part of both players. This type of problem can usually be described in a single table.

Example

P1, P2	Sell High	Sell Low
Buy High	1, 4	4, 1
Buy Low	0, 0	4, 1

For this table, the blue text represents player one's possible choices and outcomes, and the red text represents player two's possible choices and outcomes. We can consider player one to be a Buyer, and player 2 to be a Seller. The Seller wants to sell something to the Buyer for a high price if he can, and the Buyer wants to get something for a low price if he can. However, the Seller would still rather sell something for a low price rather than not be able to sell something at all, and the Buyer will still rather buy it for a high price than leave with nothing.

There are four possible outcomes, as described in the table:

If the Buyer and Seller both agree on a high price, both go away happy with the Seller happier than the Buyer. (For this table, higher numbers mean a better outcome)
If the Buyer and Seller both agree on a low price, the Buyer walks away happier than the Seller.
If the Buyer isn't willing to pay a high price which the Seller sets, both of them walk away with nothing.
If the Seller offers a low price while the Buyer was willing to willing to pay a higher one, the Buyer still gets it at a low price

One of the interesting things about this scenario is that whoever makes their choice first has the advantage. If the Seller says flat out that he's only willing to accept a high price, the Buyer is better off taking it than walking away. And if the Buyer informs the Seller that he's only willing to pay a low price, the Seller is better off taking it than refusing by demanding a higher price.

Both players are likely to haggle in this situation, since both want to complete the transaction but both also want to convince the other that they're willing to refuse the deal if the price isn't satisfactory. The choice each player makes is based on their estimation of what the other player is likely to do.

Type of Games

The above game is an example of an assymetric game. Both players are in fundamentally different positions, playing different roles. In a symmetric game, both players are in the same position, such as in a game of Chicken, it just matters what choices both of them make. Other varients include specifying that the choices must be made simultaneously or in sequence, and describing whether the players have complete information as to all the different possibilities for the game and the payoffs of the other players. In addition, there may be any number of choices both players can make, and any number of players in the same game.

Just to show how some of these can change the above scenario, if the Buyer/Seller game had to happen simultaneously, with both of them announcing their preference at the same time, the Buyer would have a stronger incentive to make a high offer, since if the Seller makes a low offer he'd still get the low price. However, the Seller knowing this might be much more inclined to make a high offer as well, so it might work to the Buyer's disadvantage.

And if the Buyer and Seller did not have complete information about the payoff table and how much the other player values the item, (as is usually the case in the real world) the transaction would be further complicated. Both parties would be trying to estimate what offer they should make against what they think the other person's payoff table is. In this case the Buyer and Seller might benefit more from not making the first move, and gaining more information about the other player by letting them make an offer before making an offer themselves.

The Games We Play

With all that said, there are a number of interesting games that fit into a very simple form. Just considering all the symmetric two-person games with only two options and played with complete information gives you a very interesting range of problems.

All that description means is that you have a situation that both players understand and which

All the games I just described have the form:

P1, P2	Cooperate	Defect
Cooperate	a, a	b, c
Defect	c, b	d, d

You can name the two options (Cooperate/Defect) anything you want, the key is just that they be the same for both players. Without loss of generality, we're going to assume that "a" will always be of greater value than "d", since otherwise you could flip Cooperate/Defect and have the same game. This leaves 12 unique games of this form, all of which I'll take the time to show here. For notation purposes, I'm going to rank "1" as the best outcome and "4" as the worst, and just assume that whatever the actual values are, that 1 is preferable to 2, which is preferable to 3, etc.

One critical assumption of Game Theory, and economics itself, is that people are both selfish and rational. All this means is that we assume people will generally try to seek whatever outcome gives the most benefit to themselves, and they'll be smart enough to figure out how to do it.

Games with Dominant Strategies

P1, P2	Cooperate	Defect
Cooperate	1, 1	2, 4
Defect	4, 2	3, 3

P1, P2	Cooperate	Defect
Cooperate	1, 1	2, 3
Defect	3, 2	4, 4

P1, P2	Cooperate	Defect
Cooperate	1, 1	3, 2
Defect	2, 3	4, 4

P1, P2	Cooperate	Defect
Cooperate	2, 2	1, 3
Defect	3, 1	4, 4

P1, P2	Cooperate	Defect
Cooperate	2, 2	1, 4
Defect	4, 1	3, 3

All of these games have one interesting property in common-- no matter what the other player does, the best stragegy is always to pick the cooperate option. Whether or not you know the other player's choice or not, you'll always be better off picking the first option. In the first game, if the second player cooperates, you'll get 1 if you cooperate and 4 if you don't, so you're better off taking the 1. If the second player doesn't cooperate, you'll get 2 if you cooperate and 3 if you don't, so again you're better off taking the 2 and cooperating. And if you look at each table you'll see that the blue numbers are always higher for the top row, and the red numbers are better for the left row.

To illustrate how this works, take an example for the first game. Assume you're assigned to a project with another person. If both of you help complete the project, you both come out looking great. If neither one of you helps complete the project, you both come out looking badly, but neither one looks worse than the other. And if one of you works on the project while the other doesn't, the person who didn't comes out looking terrible, while the person who tried to do the work probably won't be able to finish the whole thing, but he looks better than the other guy.

The point to this whole example is that no matter what the other person does, you're better off "doing the work" and picking that option. The second game follows a similar form, while the third game is slightly different in that the person who defects does better than the person who cooperated, but both still could have done better by cooperating. And in the last two games the best case is for the other person to defect while you cooperate, although there's no real reason to expect that.

All of these games to be equivalent strategy-wise, although they can have their own subtle variations. In all of these games both players should be able to understand the situation and come to a mutual understanding easily enough, and have an easy time determining their own strategy and the expected strategy of the other player. And since they're all easily solvable, they aren't very interesting to analyze.

(As one last side note, the third game is the only one where one player can do better than the other by going against the dominant strategy, since the person who defects does better than the one who doesn't defect in that case. You could make the case that one player might prefer that outcome if they wanted to do better than the other player, although strictly speaking both players are still both better off co-operating)

The Prisoner's Dilemma

P1, P2	Cooperate	Defect
Cooperate	2, 2	4, 1
Defect	1, 4	3, 3

This is probably the classic problem in game theory, and one of the most studied. But let's put it into a different form to make it easier to understand.

P1, P2	Stay Silent	Rat
Stay Silent	3 years, 3 years	life sentence, 0 years
Rat	0 years, life sentence	20 years, 20 years

Two prisoners have been busted on a minor charge, but they're part of a bigger mob. The police are interrogating them separately, and present a choice to both of them. They're up against a three year sentence minimum, and if their partner rats them out they'll get life in prison. However, if they rat out their partner and their partner doesn't do the same to them, they got off scot-free, and if both of them rat each other out, they both get 20 years.

Both prisoners have a dominant strategy. No matter what the other guy does, you're better off ratting your partner out. If he is going to rat you out, it saves you from life in prison, and if he isn't going to rat you out, it saves you from having to go to prison at all. And so assuming neither of the prisoners trust each other enough to keep their mouths shut, they're likely to end up with the worst outcome for the both of them, at twenty years each.

Another example would be for a nuclear arms race. If no one builds nuclear weapons, everyone is collectively safer. But everyone would also prefer being the only guy on the block with a nuclear bomb, and not to have your neighbor be the only guy. So everyone is likely to end up in the least desirable situation of everyone having weapons and no one wanting to use them. Still another situation is in the case of a trust, or when a bunch of businesses collude to keep prices artificially high. It's in their collective interest to limit the supply, but it's in their individual interest to sell as much as possible. This is also why the countries in OPEC have been known to cheat on each other by selling more than they're supposed to.

The reason this game is interesting is because if both players trusted each other and stuck to an agreement, they could reach a better outcome than they would playing selfishly. But it would be in both player's interests to betray that agreement as well, particularly if they're afraid of the other guy doing the same to them. It's in their collective interest to work together, but in their individual interests to cheat on each other.

Stag Hunt/The Dating Game

P1, P2	Cooperate	Defect
Cooperate	1, 1	4, 2
Defect	2, 4	3, 3

P1, P2	Cooperate	Defect
Cooperate	1, 1	4, 3
Defect	3, 4	2, 2

P1, P2	Cooperate	Defect
Cooperate	1, 1	3, 4
Defect	4, 3	2, 2

So far all the games we've discussed have a dominant strategy, or a strategy which represents the best possible move no matter what the other player does. In all of those cases, you don't even have to know what your opponent is going to do before deciding the best course of action. In all of the remaining cases, you do. These games have what is called nash equilbria. What that means is that there's an outcome in the game, such that given that you know what your opponent chose, you have no regrets about what you chose. In other words, for a particular outcome there's a stable solution where everyone feels like they made the right choice, given what all the other players chose.

Chicken

P1, P2	Cooperate	Defect
Cooperate	2, 2	3, 1
Defect	1, 3	4, 4

Blackmail, calling a strike, assuming someone else will handle a problem.

Stalemate Game

P1, P2	Cooperate	Defect
Cooperate	3, 3	1, 2
Defect	2, 1	4, 4

P1, P2	Cooperate	Defect
Cooperate	3, 3	2, 1
Defect	1, 2	4, 4

Two cars attempting to leave an intersection.