Game Theory Introduction
Game Theory can help us find the ...
- best decision in a competitive situation, or
- fairest decision in a cooperative situation
... where the outcome for each player depends on their decision and the decisions of other players.
It is useful in business, military, sports, finance, personal life, games and more.
Let's have a look at an example to see how Game Theory can help us find the best decision.
Prisoner's Dilemma
Casey and Dana are arrested after a burglary. They are in separate rooms and cannot cooperate.
Casey has been told:
- if you both stay quiet you both get 1 month in prison for trespass
- if you accuse Dana: you go free, Dana gets 10 months
- if Dana accuses you: you get 10 months, Dana goes free
- if you both blame each other you both get 6 months
What do you advise Casey to do?
... think about it for a bit ...
So maybe both Casey and Dana should keep quiet, right? They get only 1 month each that way..
But that outcome is called unstable.
Because either side can do better by making the "I go free, you get 10 months" decision.
So what to do?
Well, sadly, Casey is better off blaming Dana.
We can see it in a table like this:
| Dana | |||
| Stay Quiet | Blame Casey | ||
| Casey | Stay Quiet | -1, -1 | -10, 0 |
| Blame Dana | 0, -10 | -6, -6 | |
Casey risks getting 10 months by staying quiet!
So they will most likely get 6 months each.
Strategy is a player's action or series of actions to complete the game.
- Can be as simple as "Blame Dana"
- Or something like "Kick left 60% randomly"
- Or more complex like a system to play a multi-player game.
Nash Equilibrium
The set of player's strategies where Casey and Dana both blame each other (-6,-6) is a Nash Equilibrium, named after John Nash (the subject of the movie "A Beautiful Mind").
It is when no player is better off by changing only their own strategy.
In the above example: at (-6,-6) Casey is not better off by changing to "quiet", and Dana is also not better off by changing to "quiet", so this is a Nash Equilibrium.
(If they both changed to "quiet" they would both be better off, but we are only looking at individual choices here.)
Another way of viewing it: if any player is better off changing then it is not a Nash Equilibrium.
Example: Jade and Page travel by train to new places to earn money
- if Jade takes a camera and Page a printer they can take people's portraits and earn $300 each.
- or they can take their own cleaning gear and clean windows for $200 total.
- but they can't carry two lots of things.
The strategies look like this:
| Page | |||
| Printer | Cleaning | ||
| Jade | Camera | 300, 300 | 0, 200 |
| Cleaning | 200, 0 | 100, 100 | |
At (300,300) Jade is not better off changing to (200,0). And Page is not better of changing to (0,200). So this is a Nash Equilibrium.
At (0,200) Jade is better off changing to (100,100). So it is not a Nash Equilibrium, and we don't need to check any more.
At (200,0) Page is better off changing to (100,100). So it is not a Nash Equilibrium.
At (100,100) Jade is not better off changing to (0,200). And Page is not better of changing to (200,0) So this is a Nash Equilibrium.
So in this example there are two Nash Equilibria!
The previous example shows that players can end up stuck in a less effective strategy (100,100) vs (300,300) that can be more about habit than anything else.
No Police Needed
One way of thinking about Nash Equilibria is that (for rational players!) no police are needed to keep the rules. The players will naturally "self-police".
Example: Intersection
Imagine two people arrive at an intersection from different sides.
- If they both go they crash, with $9,000 worth of damage each
- If one stops, the other goes with a benefit of $1
- But if they both stop they will be sitting there a long time and cost them $10
| Driver B | |||
| Go | Stop | ||
| Driver A | Go | -9000, -9000 | -1, 0 |
| Stop | 0, -1 | -10, -10 | |
So it is better to stop and wait for the other driver rather than risk a bad day.
But an important point:
This assumes that players are rational.
In the real world some people do stupid things and cause accidents, so we need police to help keep us safe.
Strictly Dominant
When a player is better off switching away from a choice (no matter what the other player chooses) then we can eliminate that choice.
See Strictly Dominated Strategies to learn more.
Thinking Clearly
By now you will be getting the idea: we set up a table listing the options for each player, then estimate the benefit (or cost) for each entry, and then use logic to work out our player's best strategy.
Pure vs Mixed Strategies
What we have seen so far are "Pure Strategies": we end up with a clear choice.
But when chance is involved we may need a "Mixed Strategy": a combination of choices with probabilities.
Read Game Theory Mixed Strategies for more.
Big Subject
This has just been an introduction, there is much more to learn about Game Theory.
Learn more to become a master strategist.