Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum

Monthly Update sign up
Mailing List signup
Search
MENU

Unit 9

Game Theory

9.3 Simple Games

PIECE OF CAKE

Let's start by looking at a simple situation that can be modeled as a game. Suppose that two children at a birthday party both want to have the last piece of cake. If one child gets it, the other will be resentful, and even if an adult intervenes to split the cake in two, one child will inevitably complain that the other's share is larger. This conundrum can be avoided by letting one child cut the cake and letting the other child have first choice of the pieces. This seems to be an intuitively fair way to solve the problem. We can put this intuition on firmer footing, however, using the techniques of game theory.

To model this situation as a game, we have to make a few simplifying assumptions. First, the child who is to cut the cake, who we'll call the "cutter," has a variety of choices of how to make the cut, but we can simplify things by recognizing that the real decision is simply whether or not to attempt to cut the cake fairly. In this model, we reduce the cutter's choices to just two: namely, cut evenly or cut unevenly. The chooser has only two possible actions, of course: choose the piece perceived to be larger or the one that seems smaller. Finally, we must assume that both children are completely selfish, or rational. That is, they always act in a way that gives them as much cake as possible.

We can organize this information into a matrix that enables us to see and analyze the various possible outcomes.

NOTE: The first value in each cell is the cutter's payoff, and the second is the chooser's payoff. We will follow this convention of listing the row player's payoff first throughout the unit.

Cake

In this scheme, the cutter chooses the row of the outcome and the chooser chooses the column. For example, if the cutter chooses to cut evenly and the chooser chooses the larger piece, then the cutter will get "half minus a crumb" and the chooser will get "half plus a crumb," which is the outcome represented in the upper left cell of the table. Allowing for the difference of a "crumb" is simply a way to acknowledge that actually cutting a cake evenly is extremely difficult.

Now, being selfish, the cutter will choose the action that promises to bring him the most cake regardless of what the chooser chooses. Cutting the cake unevenly creates the possibility of getting the larger piece, but it also opens the door for the chooser to thwart this effort. In other words, the cutter's maximum payoff in choosing to cut unevenly is the large piece, and his minimum payoff in this case is the smaller piece.

If the cutter chooses to cut evenly, however, his maximum payoff is about half of the cake, and his minimum payoff is also about half of the cake. So, of the cutter's two choices, the one that has the least downside-or, in other words, the "maximum minimum"-is the one he should choose. Consequently, in this situation, he should choose to cut the piece of cake evenly.

The chooser seeks to do the same thing, make the choice that maximizes her benefit. In this case, if the cutter cuts evenly, the chooser's best option is to pick the "half plus a crumb." Notice that even though both children implement their best strategy, one still comes out slightly advantaged over the other. This common feature of games is summed up in the following statement: "You know, the best you can expect is to avoid the worst." Games do not have to be fair.

The choices that the cutter and chooser had to make in the above example are known as "pure strategies." This simply means that the players play the game using the same strategy every time; deviating from the strategy gains them nothing and could potentially end up harming them. This idea of a "best" strategy-in the sense that deviation from it increases the chance of reaching a less-desirable result-is known as an "equilibrium."

A nice example of equilibrium is the case of a three-way duel (sometimes called a "truel"). Let's say that person A is an excellent shot, able to hit the target 100% of the time; person B is a great shot, with a 90% success rate; and person C is a terrible shot, striking the target a mere 20% of the time.

Three-Way Duel

Assuming that each person can shoot only once, the best strategy for each in this case is basically: "shoot the person most dangerous to you." If each player adopts this strategy, then A should shoot at B and B should shoot at A, as each of them is the other's most imminent threat. Person C should shoot at A, because there is a tiny chance that B will miss, but there is no chance that A will miss. The outcome, if all "players" implement their equilibrium strategies, is that Person C will be the winner of the contest, the one left standing. This example demonstrates how the conclusions of game theory can sometimes be counter-intuitive.

back to top

A PENNY SAVED...

To get a better sense of how equilibrium works, let's look at a game that has no clear "best" strategy: matching pennies. In this game, two players, called "Mixed" and "Matched," simultaneously place one penny each on a table, either heads up or heads down. If the two coins are matching, then Matched gets to keep them both; if the two coins are not matching, then Mixed gets them both. We can summarize the situation with the following payoff matrix:

Payoff Matrix

We can see from this table that if Mixed plays heads and Matched also plays heads, then Mixed loses a penny and Matched gains a penny. Remember, in this game both players put their coins down at the same time, so neither has an advantage in knowing what to pick. Notice also that this is indeed a zero-sum situation-whatever Mixed loses is gained by Matched, and vice versa. If this game were to be played just once, neither Mixed nor Matched would have any clue as to what the other was going to play, so the choice between heads and tails would be completely random. Therefore, unlike the cake game discussed earlier in which each player had a definite "best" strategy, there is no one strategy that beats all others for a single round of matching pennies.

The plot thickens, so to speak, when multiple rounds are played; this is what game theorists call an "iterated game." If the two players were to play multiple rounds, then playing a pure strategy of heads every time or of tails every time would definitely put a player at a disadvantage. For instance, if Matched noticed that Mixed always plays heads, then she should play heads as well and win
every round.

A pure strategy is not the best bet for either side in this situation. Ideally, each player would like to keep the other player guessing as to the next play. The most intuitive, and best, way to accomplish this is to play randomly. Random play is an example of a mixed strategy. Let's look at a modified table that includes this new strategy option. Note that the payoff values in the table also must change a bit in meaning. Whereas previously we were concerned with the payoff of just a single round of play, we are now considering iterated games and mixed strategies, and the payoffs must represent averages per round. Playing randomly results in an average payoff of "zero" per round. Note that, because this is still a zero-sum situation, if one player gets zero, so must the other.

Payoff Matrix

Now, each player has a choice of how to play this iterated game-pure heads, pure tails, or randomly. Using the logic developed in the preceding section, Mixed should choose the strategy that ensures the maximum minimum, and Matched, from his perspective, should do the same. This means that Mixed should choose to play randomly, and so should Matched, and both of them should expect to make nothing from the game. Playing randomly in this case means playing heads and tails with equal probability. Doing this means that the game is at equilibrium: neither player has anything to gain by deviating from the chosen strategy if the other player does not deviate. Not every equilibrium in an iterated game must be composed of equal probabilities, however. The precise probabilities depend on the specific payoffs of the game.

In this analysis, we assume that playing randomly means that the odds of a player playing heads or playing tails are 50/50. If this were not true, then the opposing player could statistically recognize a bias towards either heads or tails and adjust her play accordingly to take advantage of this. In a scenario such as this, the payoffs for playing randomly would no longer be (0,0), but rather the product of the pure strategy payoffs, (-1, 1) for example, and the proportion of heads or tails played. For example, if out of 100 games, Mixed plays 60% heads, then Matched should also play 60% heads and expect to have an average payoff of 0.1 per round as opposed to the zero that would be expected if both players play heads and tails with equal probability. Conversely, Mixed should expect to lose 0.1 per round, on average.

We have until now been concerned with zero-sum games; whatever the winner wins, the loser has to lose. However, many situations in life, and, hence, the games that model these situations, are not zero-sum. These are situations in which the combined outcome can be greater than or less than zero. In other words, some situations are win-win, and some situations are lose-lose. One of the most famous non-zero-sum games is the Prisoner's Dilemma.

back to top

Next: 9.4 Prisoner's Dilemma


HomeVideo CatalogAbout UsSearchContact Us

© Annenberg Foundation 2013. All rights reserved. Privacy Policy