Stealing cookies on Christmas Eve: An Introduction to Game Theory & The Nash Equilibrium

Imagine this.

It’s the night before Christmas, you are eight years old and you and your younger sister were caught trying to eat the cookies you set out for santa the evening before.

Your dad, who caught you red handed, takes you by the hand and leads you into a separate room. He sits down, rubs his hands together and asks you if you were going to steal Santa’s cookies.

At first, you are silent. But then (evil genius that all dads are), he tells you this: he’s going to take your sister into another room and ask her the same question.

• If the both of you stay silent, both of you will be denied treats for about a week for staying up past your bedtimes.
• If both of you confess, both of you will be denied treats for 6 weeks.
• If you confess and your sister doesn’t, you will be denied treats for 10 weeks while your sister receives no punishment
• If your sister confesses and you don’t, your sister will be denied treats for 10 weeks, while you receive no punishment.

You have no idea whether or not your sister will confess.

What do you do??

Well, game theory might just hold the answer to our eight year old self’s conundrum.

What is Game Theory?

Game theory is a branch of applied mathematics that derives mathematical models to predict the outcome of competitive interactions between two or more “rational” decision makers.

For game theorists, such competitive interactions are called “games” because like conventional games

• they follow a set of rules and assumptions
• the decisions of the players are interdependent — i.e. the choices of one player will affect the outcome of another.

A game is not limited to things like Fortnight or Poker — in fact they can be as simple as crossing the street or ordering ice cream and as complicated as the stock market or military strategy. They can even be something like your dad offering you an ultimatum when you attempt to steal cookies on Christmas Eve.

There are five main ways of classifying such games

1. Cooperative vs. Non Cooperative: In cooperative games, players are permitted to negotiate and collaborate where as in non cooperative games, they are not.
2. Normal vs. Extensive: In normal form games, you can play any of your moves all the time. In extensive form games, the moves you have available depends on those of your opponent.
3. Sequential vs. Simultaneous: In sequential games, players move one after the other, where as in simultaneous games, they move at the same time.
4. Zero sum vs. non zero sum: In zero sum games, the outcomes achieved by all the different players will sum to zero, whereas in non zero sum games, they do not.
5. Symmetric vs. asymmetric: In symmetric games, the best strategy for each player is the same, whereas in asymmetric games, such strategies will not necessarily be the same.

Let’s return to Christmas Eve. We can see that our current situation is

1. Non cooperative: you are not aloud to talk to your sister.
2. Normal: you can always play any of your moves.
3. Simultaneous: you have no knowledge of what your sister does before making your own decision — you are effectively moving at the same time.
4. Non zero sum: your outcomes don’t sum to zero.
5. Symmetric: as we will come to see in a moment, the best thing both of you can do is the same.

As in many fields, there is some common terminology game theorists love to use.

• Players are those involved in game play (you and your sister)
• Actions are decisions that the players make (staying silent or confessing)
• Strategies are composed of actions. “Pure strategies” constitute playing one single action repeatedly and “mixed strategies” mean playing a bunch of different actions with specific probabilities (unless we try to steal cookies each Christmas eve, we only have the pure strategies of cooperating or confessing)
• Payoffs are the outcomes which players receive as a result of their decisions and those of their opponents (being denied treats only one week vs. being denied treats for 10 weeks). Payoff tables represent all your possible outcomes relative to your possible actions.

Rationality and the Nash Equilibrium

Perhaps one of the most important facts about game theory is this: it assumes that the players are “rational” — i.e. that they are independently motivated to maximize their individual outcomes.

Let’s assume for a second that your eight year old self is rational. Then, according to game theory, we want to maximize your individual outcome (unless you’re actually 8 years old, and your main goal is to minimize your sister’s payoff :)).

How do you do this?

Well, by playing the optimal strategy.

Which is…

Something called the Nash Equilibrium.

The Nash Equilibrium specifies that the optimal outcome of a game is one from which no player can benefit by changing his strategy if none of his opponents do so as well.

So, rational players will inevitably play the Nash Equilibrium.

And once they achieve it, they would not dare switch strategies because unless their opponent does so as well, they will not benefit — they will not maximize their outcome.

For this reason, the Nash Equilibrium is often referred to as the “vortex state” — everything converges to it and once you get there, there is no escaping. John Nash — the economics student who coined this term, was said to have gotten the idea when swirling a cup of coffee and pondering the vortex in the middle.

So, let’s find the Nash Equilibrium!

This is the payoff table for you and your sister

After crunching some numbers, much to the confusion of your tired father, you figure out that the Nash Equilibrium is when both you and your sister confess.

Why?

Well, keep in mind the definition of the Nash Equilibrium: … no player can benefit by changing his strategy if none of his opponents do so as well.

• If you switch strategies and don’t confess, but your sister confesses — you go from 6 weeks without treats to 10 weeks without treats.
• If your sister switches strategies and doesn’t confess, but you confess — your sister goes from 6 weeks without treats to 10 weeks without treats.

Neither of you can benefit if you switch strategies alone, so this is a Nash Equilibrium.

Another way of looking at it is if your sister confesses, the best thing you can do in response is confess (you’d get a payoff of -6 rather than -10). But if your sister doesn’t confess, again the best thing you can do in response is confess (you’d get a payoff of 0 over -1). In either case, confessing is the best thing to do.

So, what should you do? Confess. Confess confess confess confess confess (much to your father’s delight).

The situation you and your sister so perfectly got yourselves into is known as a game called the Prisoner’s Dilemma.

How to find the Nash Equilibrium?

So, how do we actually find the Nash Equilibrium — it kind of seems like we were just guessing and checking.

Well, you are correct.

For simple games like this, guess and check is actually the most effective way to solve for the Nash Equilibrium. In fact, there is not a universally defined method to find the Nash Equilibrium for any situation! Game theorists have developed analytic methods to figure it out for a few games — most notably linear programming and minimax analysis.

Let’s say that the following day (Christmas!), your dad tasks you and your sister with cleaning up the wrapping paper, bows and streamers that you manically ripped through in an effort to get your presents.

You guys decide to settle who is going to take out the garbage with a (seemingly infinite) game of rock-paper-scissors.

Again, we want to find the Nash Equilibrium.

Minimax analysis can help you to find the Nash Equilibrium when it is a pure strategy Nash Equilibrium — i.e. a Nash Equilibrium that comes when each player plays one specific action.

Consider your payoff table for rock paper scissors:

Take the minimum value of each row and the maximum of each column.

When the row maximin (maximum of the minimums) is equal to the column minimax (minimum of the maximums), the pure strategy equilibrium will be at the intersection of these two values. However in this case, the row maximin does not equal the column minimax, so there is no pure strategy Nash Equilibrium for rock paper scissors.

But maybe we can find a mixed strategy Nash Equilibrium. Let’s try linear programming.

Say you play a rock with probability x, paper with probability y and scissors with probability 1-x-y.

Your expected value when your opponent plays

• Rock is (0)(x) + 1(y)-1(1-x-y) = x + 2y -11
• Paper is (-1)(x) + (0)(y) + 1(1-x-y) = 1–2x-y
• Scissors (1)(x)-1(y) + (0)(1-x-y) = x-y

Since the Nash Equilibrium specifies that no player will have an incentive to change strategies, we can set all these expressions to be equal to each other. So, we get that x+2y-1=1–2x-y=x-y.

Solving the system of equations yields that x = y = ⅓. So, the Nash Equilibrium for rock paper scissors is (somewhat unsurprisingly) when you play each option ⅓ of the time.

Applications of Game Theory

While Game Theory does apparently lend itself useful to negotiating cookie ultimatums and garbage take out, it does have many (perhaps more) useful applications.

Game theory can be applied to basically any interaction involving rational beings. Some interesting problems it can be used to solve are

• what is a military’s optimal missile strategy?
• how can one most effectively bid at an auction?
• how can an advertising firm maximize their sales?
• what is a politician’s best possible campaign strategy?
• what is a product’s competitive sales price?
• how can an insurance company price their deals?
• what is the optimal placement of telecommunication towers?
• how could one negotiate labour management?

just to name a few.

Key Takeaways

1. Game theory studies “games” — competitive interactions between rational decision makers which follow a set of rules and has actions which are interdependent.
2. A rational player will play the Nash Equilibrium — the optimal outcome of a game from which no player can benefit by changing strategies if none of his opponents do so as well.
3. There is not a universally defined way of finding the Nash Equilibrium for a game — but there are techniques which are effective in certain situations such as minimax analysis and linear programming.
4. Game theory has a many varied applications — ranging from the pricing a commodity to navigating war.