Saturday, December 27, 2014

The Prisoner's Dilemma

Imagine you are a criminal whose life of crime has finally caught up to you.  You and your partner, Al, have been caught by the police for a minor crime and both of you are being interrogated separately.


The police correctly suspect that you and Al have committed larger crimes but have no evidence for a conviction, so they set up a bargain.  If both you and Al confess to your other crimes you will both serve 8 years in prison.  If one of you confesses and the other does not, the confessor will go free and the silent one will serve 20 years in prison.  If both of you are silent, then there is only enough evidence to convict you of the minor crime, and both of you will only serve 5 years in prison.  What do you do?


Al Confesses
Al is Silent
You Confess
You serve 8 years and
Al serves 8 years
You go free and
Al serves 20 years
You Are Silent
You serve 20 years and
Al goes free
You serve 5 years and
Al serves 5 years

This Prisoner’s Dilemma was first conceived by Flood and Dresher in 1950 to illustrate the relationship between competitive and cooperative behavior between two parties in game theory.

A good illustration of the risks and rewards presented in the Prisoner’s Dilemma is a card game described in the dystopian young adult book Matched by Ally Condie.


As one of the characters explains the game, “They each put down a card at the same time.  If they both have an even card, they each get two points.  If they’re both odd, then they each get one point … If one is even and one is odd, the person who puts down the odd card gets three points.  The person who puts down the even one gets zero.”


Player 2 Odd
Player 2 Even
Player 1 Odd
Player 1 gets 1 pt and
Player 2 gets 1 pt
Player 1 gets 3 pts and
Player 2 gets 0 pts
Player 1 Even
Player 1 gets 0 pts and
Player 2 gets 3 pts
Player 1 gets 2 pts and
Player 2 gets 2 pts

Note that in this version of the Prisoner’s Dilemma, the goal is to gain something positive, like receiving points, instead of avoiding something negative, like a prison sentence.  But the dilemma is similar.  On your turn, do you lay down an odd card for 1 or 3 points, or do you lay down an even card for 0 or 2 points?

To help solve these dilemmas, you can use the Nash Equilibrium, which is the solution set of best decisions for each party given that no party has anything to gain by changing his or her decision.   In the card game, you should lay down an odd card, because you would have nothing to gain by changing your mind even if you know what the other player will play.  (If the other player lays down an even card, you will get 3 points, so changing your mind to play an even card to get 2 points would not make sense.  If the other player lays down an odd card, you will get 1 point, so changing your mind to play an even card and get 0 points would also not make sense.)  Similarly, as a prisoner you should confess, because you would have nothing to gain by changing your decision even if you know Al’s decision.  (If Al remains silent, you will be let free, so changing your decision to also remain silent and get a 5 year prison sentence would not make sense.  If Al confesses, you will receive an 8 year sentence, so changing your decision to remain silent and get a 20 year prison sentence would also not make sense.) 

Of course, by symmetry the Nash Equilibrium would be for the other player to also lay down an odd card, and for Al to confess as well.  However, this solution which would not give the best overall result for both parties.  In the card game, the best overall result would be for both players to lay down even cards for 2 points each, for the maximum total reward of 4 pts.


Player 2 Odd
Player 2 Even
Player 1 Odd
Player 1 gets 1 pt and
Player 2 gets 1 pt
1 + 1 = 2 pts total
Player 1 gets 3 pts and
Player 2 gets 0 pts
3 + 0 = 3 pts total
Player 1 Even
Player 1 gets 0 pts and
Player 2 gets 3 pts
0 + 3 = 3 pts total
Player 1 gets 2 pts and
Player 2 gets 2 pts
2 + 2 = 4 pts total

With the interrogated prisoner situation, the best overall result would be for both you and Al to remain silent, which will result in the two of you receiving only a 5 year prison sentence, for the minimum total penalty of 10 years.


Al Confesses
Al is Silent
You Confess
You serve 8 years and
Al serves 8 years
8 + 8 = 16 years total
You go free and
Al serves 20 years
0 + 20 = 20 years total
You Are Silent
You serve 20 years and
Al goes free
20 + 0 = 20 years total
You serve 5 years and
Al serves 5 years
5 + 5 = 10 years total

In both cases, the only way to achieve the best overall result would be for both parties to cooperate and trust each other.  (In the case of the prisoners which are interrogated separately, a deal between the two prisoners would have to be made beforehand.)  In contrast, the Nash Equilibrium assumes no cooperation, just competition.

The Nash Equilibrium is probably best known by the movie A Beautiful Mind (2001), a biography of the mathematician John Nash.


In this movie, a new dilemma is presented to introduce the viewers to game theory.  A young Nash and his college friends are sitting in a bar, and some girls walk in, including one beautiful blonde girl.
 
  
While Nash’s friends are arguing over who will get the blonde girl, Nash realizes that if they all go for her, they will all cancel each other out and no one will get her, and then no one will get any other girl, either, because none of the other girls will like being the second choice.  But if everyone goes for the other girls, everyone will get a girl, which will result in the best overall result.  For simplicity, the following table shows the dilemma for just two of the guys, Nash and Hansen:


Hansen Goes for the Blonde
Hansen Doesn’t Go for the Blonde
Nash Goes for the Blonde
Nash gets no girl and
Hansen gets no girl
Nash gets the blonde and
Hansen gets a girl.
Nash Doesn’t Go for the Blonde
Nash gets a girl and
Hansen gets the blonde
Nash gets a girl and
Hansen gets a girl

Technically, the movie’s solution for all of them to agree to not go after the beautiful blonde girl is not a Nash Equilibrium.  (If Hansen goes for the beautiful blonde girl, then Nash should go for one of the other girls because then at least he will get a girl.  But if Hansen doesn’t go for the beautiful blonde girl, then Nash should, because then he will get a more beautiful girl.)  However, the solution presented is the best solution if they are allowed to cooperate and trust each other to make a deal (and if it is assumed that no one will agree to the unfair deal of only one guy getting the beautiful blonde girl), just like how in the card game the best cooperative solution would be for both players to lay down an even card, or just like how with the interrogated prisoners the best cooperative solution would be for both prisoners to keep silent.

A real life Prisoner’s Dilemma occurred during the 2014 FIFA World Cup for Germany and the United States.  Both countries were in Group G along with Portugal and Ghana.


By June 22, 2014, each team had played 2 games.  Both Germany and USA were leading the pool with 4 points each, having gained 3 points for a win and 1 point for a tie.  Portugal and Ghana both had 1 point each, 1 point for a tie and 0 points for a loss.

Teams
MP
W
D
L
GF
GA
+/-
Pts
Germany
2
1
1
0
6
2
4
4
USA
2
1
1
0
4
3
1
4
Portugal
2
0
1
1
2
6
-4
1
Ghana
2
0
1
1
3
4
-1
1

There were two games left on June 26, 2014 to finish pool play: Germany vs USA and Portugal vs Ghana.  After these games the top two teams would advance, determined first by points and secondly by goal difference.  The following table shows the possible outcomes for the two games (the outcomes with “or” would depend on the goal difference):


Portugal Wins and
Ghana Loses
Portugal and
Ghana Tie
Portugal Loses and
Ghana Wins
USA Wins and
Germany Loses
USA and (Germany or Portugal) advance
USA and Germany advance
USA and (Germany or Ghana) advance
USA and
Germany Tie
USA and Germany advance
USA and Germany advance
USA and Germany advance
USA Loses and
Germany Wins
Germany and (USA or Portugal) advance
USA and Germany advance
Germany and (USA or Ghana) advance

As you can see, as long as game the game between Germany and USA was close in score, both Germany and USA would advance.  Some sport commentators jokingly suggested that Germany and USA should agree to tie, because then both teams would have the certainty of advancing.  Setting this situation up in a simplified Prisoner’s Dilemma, you can give both teams the option of either trying to win or taking it easy.  If both teams take it easy, the result will be a 0-0 tie, and both teams will advance.  If one team tries to win and the other team takes it easy, the team that is trying to win will win by a wide margin of goals and advance, and the other team that is taking it easy will lose by a wide margin of goals and not advance.  Finally, if both teams try to win, the game will likely be close in score (unless one team is much better than the other), so both teams will probably (but not certainly) advance.


Germany Tries to Win
Germany Takes It Easy
USA Tries
to Win
USA probably advances and
Germany probably advances
USA advances and
Germany does not advance
USA Takes
It Easy
USA does not advance and Germany advances
USA advances
Germany advances

The Nash Equilibrium is for both teams to try to win, because each team would have nothing to gain by changing their strategy even if they know the other team’s strategy.  (If Germany tries to win, USA also needs to try to win as well so they can probably advance, as opposed to taking it easy and not advancing.  If Germany takes it easy, USA will advance no matter what, so changing the USA’s strategy makes no difference.)  However, the best overall result would be for both teams to have the certainty of advancing, which means cooperating and trusting each other on a deal to purposely tie.

As is usually the case, history shows that the Nash Equilibrium based on competition won over the solution based on cooperation.  It appeared that Germany and USA both used the strategy to try to win, and on June 26, 2014 Germany beat USA by a close score of 1-0.  Portugal beat Ghana, but only by a score of 2-1, so both Germany and USA advanced.

The Prisoner’s Dilemma has application in other areas of life, too, especially in economics.  Let’s say that there is a shopping plaza on the outskirts of town with a fitness center and a sports bar.  Both businesses would benefit by having a cable line installed to the shopping plaza; the fitness center would attract more customers if its customers can watch cable TV while running on the treadmill, and the sports bar would attract more diners if its diners can watch their favorite sports teams play while eating.  The cable company offers to run a cable line out to the shopping plaza for a cost of $1000.  Once the cable line is installed, any business can hook into the cable line at $100.  (Also for our example, we’ll say that both businesses value the cable line at $700, in other words, neither business will pay more than $700 to have the cable line installed.)  Each business can either choose to have the cable line installed or to not have the cable line installed.  If both businesses decide to install the cable line, they can split the cost of the cable line at $500 each, and sign up for cable for another $100 each, and receive cable television for a total cost of $600 each.  On the other hand, if both businesses decide not to install the cable line, neither will pay anything but then neither will have cable television.  Finally, if one business decides to install the cable line and the other does not, the one business would pay $1000 for installing the cable line and another $100 for signing up for cable (for a total of $1100), whereas the other business would pay nothing for installing the cable line and $100 for signing up for cable.


Sports Bar No
Sports Bar Yes
Fitness Center No
FC no cable and
SB no cable
FC $100 cable later and
SB $1100 cable
Fitness Center Yes
FC $1100 cable and
SB $100 cable later
FC $600 cable and
SB $600 cable

The Nash Equilibrium would be for both businesses to say no to cable.  (If the sports bar says yes to installing the cable line, the fitness center should say no because it can then receive the benefit of cable television for $100 instead of $600.  If the sports bar says no to installing the cable line, the fitness center should still say no because the cost of installing the cable line would be $1100, which is over the value of $700.)  However, the best overall result would be for both businesses to have cable television, which means they should cooperate and trust each other and make a deal.

The Prisoner’s Dilemma illustrates how two different economic systems have two different solutions.  In a society based on cooperation or socialism, a cable deal may be able to be reached (perhaps with government intervention through tax money).  However, in society based on competition or capitalism, the Nash Equilibrium in this situation says that there will be no progress concerning cable television.  There are several solutions to this problem, but the most obvious is that the cable company needs to decrease its price on installing a cable line and increase its price for signing up, or it will soon be out of its own business.  (This is one of the reasons why it is important for the government not to fix costs in capitalistic society.)  For example, if the prices change to $0 for installing the cable line and $600 for signing up, the Nash Equilibrium changes to both businesses saying yes to cable, because it will cost less than the value of $700 to receive it, and the cable company will still make its $1200.


Sports Bar No
Sports Bar Yes
Fitness Center No
FC no cable and
SB no cable
FC no cable and
SB $600 cable
Fitness Center Yes
FC $600 cable and
SB no cable
FC $600 cable and
SB $600 cable

The Prisoner’s Dilemma can also be applied to similar economic situations, such as building roads or train tracks, installing lighthouses, launching satellites, and much more.  In each case, a socialistic or a capitalistic solution can be reached, each with its own pros and cons.  However, a capitalistic solution will only work if there are no fixed costs that restrain private companies from withholding its services.

In conclusion, the Prisoner’s Dilemma started out as a fun exercise in game theory in 1950.  But like many mental exercises, theory turned into practice, and the Prisoner’s Dilemma had applications in the economic realm as well.

1 comment:

  1. This was interesting and I actually understood it! Yay me!

    ReplyDelete