Prisoner's Dilemma & Nash Equilibrium
Learning Objectives
Learn basic vocabulary related to the topic
Understand the basics of the Nash Equilibrium
Be able to solve for the Nash Equilibrium in a "game"
Understand the Prisoner's Dilemma as an example of a finite game with a Nash Equilibrium
Learn about real world examples of the Prisoner's Dilemma and the Nash Equilibrium
Vocabulary
Nash Equilibrium: strategy of self-interest that maximizes individual payoff
Players: individuals, organizations, groups, governments, machines, etc.
Outcomes: result of a move or a sequence of moves
Strategy: each player’s decision process about making moves at any stage of the game.
Dominant strategy: a strategy that will always lead to the most payoff, no matter what the other player decides to do.
Dominated strategy: a strategy that will lead to the worse payoff, no matter what the other player decides to do.
Introduction to Game Theory
In our everyday lives, we are almost constantly making decisions.
when to set an alarm
if we should join a club
how to study for a test
We spend a lot of time on these decisions because they're important; they determine how much time we'll have to get ready in the morning, whether we're in a club we enjoy, and how we do on exams. But how do we end up on the decisions that we ultimately make?
There's an area of study that focuses on these decisions in order to understand why we make them and what their consequences are. This study is called game theory.
In game theory, decisions are called strategies. Game theorists might say, for example, that a person's strategy is sleeping in if they set their alarm for the last possible minute.
What happens due to any particular strategy is called a payoff. The payoff to sleeping in, for example, might be missing your bus or not having time to make breakfast.
For this lesson, we will be looking at how we choose between two different strategies when each strategy has a different payoff. To do this, we will organize the strategies and payoffs into a chart called a game matrix
How to read a game matrix
Look to the game matrix to the left. Each of the soccer players has two strategies when someone tries to score a goal. The striker can either kick the ball to the left or the right of the goal. The goalie can then either block the left or block the right. The game matrix shows what the payoffs of each of the outcomes would be. This can help us decide what our best strategies are. For example:
Looking at the matrix, what should the goalie do if the striker kicks left?
We can figure this out by looking only at the rows. Look at the "kick left" row. If the striker kicks left, the goalie has two outcomes. He can either dive left and block the ball (leading to a payoff of 0) or dive right and miss the ball (leading to a payoff of -1). Therefore, we find that the goalie will want to dive left.
Practice this with the next row. What will the goalie do if the striker kicks right? What are his two possible strategies and payoffs?
We can do the same thing with the striker if we look only at the columns.
What will the striker do if the goalie kicks left?
Prisoner's Dilemma
Above, you will see Red and Blue, a criminal duo who the police suspect of stealing the Statue of Liberty.
As soon as they are arrested, the police separate them to try to get them to confess their crime. Because they don't have quite enough evidence, the police set up a deal with each of the culprits to try to get them to rat out their partner. The deal goes like this:
If both say the other committed the crime, they will each serve a year in prison.
If one person accuses the other, but the other person remains silent, the accuser will walk free while the other person serves two years in prison.
If neither of them accuses their partner, they will both walk free.
This is a little difficult to figure out without a game matrix, so let's set one up for this example:
How will the prisoner's dilemma be solved?
Like we did with the first matrix, look at what each culprit will do depending on the strategy that the other picks
First, from Red's perspective:
If Blue stays silent, Red will prefer to accuse, because it will save her from spending a year in jail .
If Blue accuses Red, Red will still prefer to accuse, because she prefers two years in jail to five.
If you look at the matrix, you'll see that if you switch to Blue's perspective, his payoffs are the same as Red's.
Therefore, both Red and Blue will always prefer to accuse. When this happens, we say that each player has a dominant strategy.
A Dominant strategy is a strategy that will always lead to the most payoff, no matter what the other player decides to do.
Both Blue and Red have the same dominant strategy, because like we've shown above, they both will prefer to accuse.
A dominated strategy is a strategy that will lead to the worse payoff, no matter what the other player decides to do. This would be, for example, Red and Blue choosing to stay silent.
A prisoner's dilemma occurs when two things are true:
(1) both players have a dominant strategy, but (2) they prefer the situation in which both of them would have played their dominated strategy.
We can see the prisoner's dilemma play out above.
Both Red and Blue have a dominant strategy to accuse.
If both of them accuse the other, they will end up in the square on the bottom-right, where their payoff will be that they both serve two years.
Even though this should be the outcome that both Red and Blue are happiest with, we can see that if both had chosen to stay silent (their dominated strategy), they would have served only one year!
Practice Problem: Lemonade Stands
Look at the game matrix below. Kate and Riya are both trying to sell lemonade on Claflin Street. They need to decide where to set their prices to make sure they get more customers than their competitor.
What is each lemonade vendor's dominant strategy?
What is their dominated strategy?
Is this an example of the prisoner's dilemma? Explain why or why not.
Solution to this problem can be found below.
Solution
Both Kate and Riya have the same dominant strategy, to defect. This will lead them to the outcomes in the bottom right square below.
Their dominated strategy would be if they cooperated. This is also represented by the top left square.
This is an example of the prisoner's dilemma. Even though both Riya and Kate have a dominant strategy, there is another outome -- their dominated strategy -- that they both would prefer, because it would mean they each make almost twice the amount of money.
Suppose Kate and Riya both have competing lemonade stands on Claflin Street.
Nash Equilibrium
Nash Equilibrium is a cornerstone of Game Theory.
Nash Equilibrium occurs when no player has anything to gain by changing their choice, assuming all other players stay where they are.
Another way to think of it is as the situation with greatest relative payoff for all n players. So if any one person revealed their decision, no one would feel a need to change their choice.
There can be one, multiple, or even no Nash Equilibrium! We'll explore this in some of the examples below.
Prisoner's Dilemma: Take 2
When Blue chooses to accuse, Red's choices are the RED row (to stay silent or accuse within that situation), so they're looking at a -5 vs -2 payoff. -2 (accusing), is their better option here.
With Red defecting, Blue's choices are the BLUE column. They're also deciding between a -5 vs -2 payoff, so their better payoff option here is also to accuse.
Neither player would benefit from changing their individual choice here, so (-2,-2) is a Nash Equilibrium.
Lemonade Stands: Take 2
When Riya chooses to defect, Kate's choices are the PURPLE column (to cooperate or defect based on Blue's decision), so we're looking at her payoffs of 0 and 25. 25 (defecting) is her best payoff here.
When Kate defects, Riya's choices are the BLUE row, also 0 and 25, showing that her best choice is to also defect.
For both, to change their choice away from (25,25) is to decrease their payoff. This is a Nash Equilibrium!
But Wait!
How is (25, 25) different from (40, 40)??
Isn't that also a Nash equilibrium??
Let's have a look . . .
From Kate's perspective, if Riya cooperates, her better option is to defect (60 is better than 40)
From Riya's perspective, the situation is the same! If Kate cooperates, her better payoff is to defect
Soooo, (40,40) is NOT a Nash Equilibrium.
Remember that both players must not want to change their option. So though a situation may have equal benefit for both, like (40, 40), it might not be their best option and therefore not a Nash Equilibrium.
You might've noticed that the Prisoner's Dilemma Example has a similar situation with (-1, -1), but the same is true here. Though this situation has the fairest payoff overall, both Red and Blue have better options for better individual payoff.
Again we see that selfish choices disadvantage both people! And that the best selfish choice for both is what makes a Nash Equilibrium.
Another Example: Game of Chicken
Two pretty bad drivers ( A and B) are in single lanes going opposite directions,
Either can stay in their lane, or get distracted and veer off into the other's lane.
To crash is the worst outcome for both.
The best outcome for each is to stay in their lane while the other swerves, since then the other “chickens out” and the crash is avoided.
So, to assign payoffs . . .
10 points to the driver who does not swerve if the other swerves.
the safest option for one, as they're safest in their own lane
0 points if both swerve.
now they're both in the wrong lane, which is dangerous
-5 points for swerving if the other does not (chickening out).
they're in the wrong lane
-10 points to both for not swerving, i.e. for collision.
obviously crashing is the worst outcome for both
Can you find the Nash Equilibrium(s)?
There are actually TWO! (10, -5) and (-5, 10)
The charts below draw out the answers, but essentially for both A and B, their ideal situations are when they choose to not swerve while the other does.
Note that the "equilibrium" does NOT mean equal numbers for both players.
In the lemonade example above, Nash Equilibrium was (25,25).
But in the Game of Chicken, equal payoffs (-10,-10) and (0,0) are actually the worst situations for both players.
Nash Equilibrium means the best outcome, that both like equally
Last Example: Rock, Paper, Scissors!
We all know it and love it, a game between two players, each choosing to make a symbol with their hands representing rock, paper, or scissors.
Rock crushes scissors, scissors cuts paper, and paper covers rock.
In the game matrix format:
See a Nash Equilibrium?
There are actually NONE! This is becaue of the cyclical nature in the strategies.
If your opponent plays rock, your best response is paper. However, if you play paper, then they should switch to scissors, which in turn means you should switch to rock. And of course, to top it all off, you don’t actually have any way of knowing what strategy your opponent will choose.
Real life examples get even more complicated, with more players and options, but this gives an introduction to how people make everyday, strategic decisions that lead them to choices that may not seem the best.
Important Figures in Game Theory
Real World Examples of the Prisoner's Dilemma & the Nash Equilibrium
- Israeli-Palestinian Conflict
Like the classic example, the "best" outcome is for both parties to coordinate, but there is incentive for both parties (or states, in this case) to not do so. There are four outcomes: the entirety of the land goes to Israel, the entirety of the land goes to Palestine, both sides agree to partition and the land is split between Israel and Palestine (the two state solution) or one side accepts partition, and the other state does not. War will ensue.
- Companies advertising
If a company A doesn't advertise, it can maintain its share of the market and profit from the money that it does not spend on advertising. But because company A fears company B advertising and gaining more market share (and vice versa), both could advertise and lose profit as they are now spending that money on advertising.
- Hiring a lawyer
Suppose two companies would be better off by choosing not to hire a lawyer. But if each company hires a lawyer on the fear/suspicion that the other company might hire a lawyer, they are more likely to benefit in arbitrations by having a lawyer if the other does not. But if both hire lawyers, they are not better off and have incurred unnecessary expense.
- CO2 Emissions
The world as a whole has incentive to lower emissions to protect the planet. However, each country's emissions are generally tied to their industrial production, meaning it is unlikely an individual country will want to lower their emissions. "A Nash equilibrium for this matrix is when both countries decide to not care about carbon emissions. This is an example of getting trapped in the Nash equilibrium because it is impossible for either “player” or country to change their decision without making themselves worse off since the benefits of reducing carbon footprint are not immediate." (blogs.cornell.edu)
More Practice Problems
Click here for more practice problems.
Further Questions & Discussions
What examples of the Prisoner's Dilemma, or Nash Equilibrium, do you have in your everyday life?
Why is understanding the Prisoner's Dilemma important?
Why is understanding the Nash Equilibrium important?
Sources
https://xplaind.com/472079/prisoners-dilemma
https://blogs.cornell.edu/info2040/2019/09/24/nash-equilibrium-and-climate-change/
https://www.nytimes.com/2020/12/20/health/virus-vaccine-game-theory.html
https://www.youtube.com/watch?v=fvEQujUcPv4
https://drive.google.com/file/d/1N1_W9m0APlMRYbk4MQKmNuScsrKXU6tB/view?usp=sharing