Game Theory XI: Metagames: The Punishing Prisoner's Dilemma

Now, let us look at another perspective on the Prisoner's Dilemma. Suppose we allow the players to communicate. What happens?

The following material is flagged Green Level. It is intended to reflect material that the author believes to be a matter of consensus among experts in the field. This belief may be incorrect, however; and as the author is not an expert and does not have an expert fact-checking the article, errors may creep in.

Let us suppose that two of the players in the Prisoner's Dilemma make an arrangement. The players decide this: if either defects, that person must make a side payment to the other, equal to the harm inflicted by the defection. While the offer is available, the game looks like this (as again, B>A>F>E and 2A>B+E) and, because A-E>B-A (as proven below), the dominant strategies are highlighted in green:
2A>B+E
2A-E>B
A-E>B-A

	Response to offer: Accept	Response to offer: Reject
Offer	Cooperate Defect Cooperate (A,A) (A,B-[A-E]) Defect (B-[A-E],A) (F, F) =(A,A)	Cooperate Defect Cooperate (A,A) (E,B) Defect (B,E) (F, F) =(F,F)
Do not offer	Cooperate Defect Cooperate (A,A) (E,B) Defect (B,E) (F, F) =(F,F)	Cooperate Defect Cooperate (A,A) (E,B) Defect (B,E) (F, F) =(F,F)

As you can see, applying metagame logic here allows for a rationale for players to cooperate: deterrence. Because a side payment is required for defection, each player benefits more from cooperation than from defection.
Let us examine what happens with pure punishment (no payment is made to someone who is defected against; instead, the defector simply loses the utility in question), with punishments of severity C and D, where C>B-A and D>F-E:

	Response to offer: Accept	Response to offer: Reject
Offer	Cooperate Defect Cooperate (A,A) (E,B-C) Defect (B-C,E) (F-D, F-D) =(A,A)	Cooperate Defect Cooperate (A,A) (E,B) Defect (B,E) (F, F) =(F,F)
Do not offer	Cooperate Defect Cooperate (A,A) (E,B) Defect (B,E) (F, F) =(F,F)	Cooperate Defect Cooperate (A,A) (E,B) Defect (B,E) (F, F) =(F,F)

So, even with no reparations made (or, depending on how one looks at it, no protection against the selfishness of others), each person's interests are served by taking this approach.
Canny readers may note that this is similar to the Hobbesian view of government: that without it, each person would defect (resulting in life being "nasty, brutish, and short" as each person pursues their own gain at the expense of everyone else), but the establishment of a justice system (preferably one as draconian as possible) results in each person cooperating out of self-interest. There are a few problems with this perspective, some of which I will cover here:

1. As a general rule, people who break laws do not do so rationally, or at least with the expectation of being caught. If that were the case, there would be no crime in societies with harsh justice systems and near-universal surveillance.
2. The game only takes place over one turn, or with each turn uninfluenced by previous turns. In the real world, future games are affected by previous ones and the benefits of cooperation especially are impacted by punishment. This will be covered in a future installment of the Topic.
3. The game assumes that justice is perfect: that is, that there is never a false conviction or a false acquittal.

Let us look at the third of these. We will have a probability P(punishment|cooperation), which is the probability of punishment given cooperation (that is, the odds that someone cooperating will be falsely convicted) and a probability P(punishment|defection), which is the probability of punishment given defection (that is, the odds that someone defecting will be convicted).
Remember that C and D are expected utilities. In other words, they are the actual severity of the punishment multiplied by the odds that the punishment will be carried out, or SP(punishment|defection), where S is the true severity of the punishment, or more accurately, S(P[punishment|defection]-P[punishment|cooperation]). So, the true severity of the punishment must be C or D divided by P(punishment|defection)-P(punishment|cooperation). So, for pure deterrence to work, a justice system must hand out stricter punishments if it makes more mistakes, and (assuming a strictest possible sentence), there is a theoretical point of inaccuracy at which the system simply cannot function.

<<Metagames: Extortion | Game Theory | Zero-Sum Metagames: Randomness>>

Game Theory: Part VII: Cyclic Games: The Iterated Prisoner's Dilemma II: (Electric Bogaloo: )The End of the Game

We have seen that sometimes, the choice to cooperate in the hopes of future cooperation outweighs the rewards of defection. But what if there is no reason to cooperate in the future? What if future cooperation is impossible?

The following material is flagged Green Level. It is intended to reflect material that the author believes to be a matter of consensus among experts in the field. This belief may be incorrect, however; and as the author is not an expert and does not have an expert fact-checking the article, errors may creep in.

Let us revisit the Iterated Prisoner's Dilemma. We have seen that, eventually, the benefits of cooperation with retaliation against defectors outweigh the benefits of constant defection. But let us look at what happens when rational individuals are told that the game will be ending on the current turn.

Let us look at the reasons any such individual would have for cooperating throughout the game. Past cooperation does not apply, because it has already happened. Future cooperation does not apply, because there is no future. And there is no way to influence what one's partner will do on the current turn. Therefore, the rational way to play this turn is to treat the game as though it were the simple dilemma, and defect.

So, on the final turn (assuming both players know it is the final turn), both players will defect.

Now, let's see what happens if the players are told that the game will be ending after the next turn.

Both players know the proof above that the plays for next turn will be two defections. There is nothing that either player can do to prevent it. So, the rational thing to do is to ignore that turn, and treat this turn as though it were the last.

And we can carry this back to infinity. If both players know how long the game is going to last, or even that they will know when the game is going to end, from the start, neither player has any reason to cooperate with the other! Sometimes, ignorance truly is bliss.

Tune in... sometime... for a somewhat-unfair solution to this.

<<Cyclic Games: The Iterated Prisoner's Dilemma I | Game Theory | Metagames: The Battle of the Sexes>>

Game Theory: Part VI: Cyclic Games: The Iterated Prisoner's Dilemma I: Reciprocal Relationships

First of all, I know you're out there. I can hear you breathing. Especially you in Russia. And you, the one who reads this in Chrome. Please start saying something. Go ahead and comment; go ahead and follow the blog with the thing in the upper right corner. I promise I don't bite unless bitten.

The following material is flagged Green Level. It is intended to reflect material that the author believes to be a matter of consensus among experts in the field. This belief may be incorrect, however; and as the author is not an expert and does not have an expert fact-checking the article, errors may creep in.

So far, we have only looked at games that happen in one turn. But the world does not work that way. We rarely ever meet someone just once. What someone may think of us in the future must be taken into consideration, as must what someone has already done to us.

Let us explore what happens when we run through the Prisoner's Dilemma again and again.

First, when playing an iterated game, it is possible to change one's strategies in response to what one's opponent has done on the last round. For instance, if I have a tendency to make a particular move, you might adjust your moves to cope with that.
But for our understanding of how a game works to make sense, we should define rules for how we will change our strategies. A few possible ways of handling the Prisoner's Dilemma are listed below:

• Altruistic: Always cooperate.
• Sociopathic: Always defect.
• Tit-For-Tat: Start with cooperate, afterward repeat opponent's last move.
• Cynical Tit-For-Tat: Start with defect, afterward repeat opponent's last move.
• Grim Trigger: Cooperate until opponent defects, always defect afterward.
  

So, we have a few ways of doing this. Let's see how they work out, by running each of them against the others and putting together their totals (Total so far for a given pair is listed in parentheses, using the column only. The row's player is listed first, then the column's.).
Also, this time around we will be using a general version of the Prisoner's Dilemma:

	Cooperate	Defect
Cooperate	(A,A)	(E,B)
Defect	(B,E)	(F, F)

where B>A>F>E
and 2A>B+E (this is in place to ensure that two mutual cooperations are better than exchanging between cooperation and defection)
First pass:

	Altruistic	Sociopathic	Tit-For-Tat	Cynical Tit-For-Tat	Grim Trigger
Altruistic	C,C (A)	D,C (B)	C,C (A)	D,C (B)	C,C (A)
Sociopathic	C,D (E)	D,D (F)	C,D (E)	D,D (F)	C,D (E)
Tit-For-Tat	C,C (A)	D,C (B)	C,C (A)	D,C (B)	C,C (A)
Cynical Tit-For-Tat	C,D (E)	D,D (F)	C,D (E)	D,D (F)	C,D (E)
Grim Trigger	C,C (A)	D,C (B)	C,C (A)	D,C (B)	C,C (A)
Totals:	3A+2E	3B+2F	3A+2E	3B+2F	3A+2E

Second pass:

	Altruistic	Sociopathic	Tit-For-Tat	Cynical Tit-For-Tat	Grim Trigger
Altruistic	C,C (2A)	D,C (2B)	C,C (2A)	C,C (B+A)	C,C (2A)
Sociopathic	C,D (2E)	D,D (2F)	D,D (E+F)	D,D (2F)	D,D (E+F)
Tit-For-Tat	C,C (2A)	D,D (B+F)	C,C (2A)	C,D (B+E)	C,C (2A)
Cynical Tit-For-Tat	C,C (2E)	D,D (2F)	D,C (B+E)	D,D (2F)	D,C (B+E)
Grim Trigger	C,C (2A)	D,D (B+F)	C,C (2A)	C,D (B+E)	C,C (2A)
Totals:	6A+4E	8F+2B	6A+B+2E+F	A+3B+2E+4F	6A+B+2E+F

Third pass:

	Altruistic	Sociopathic	Tit-For-Tat	Cynical Tit-For-Tat	Grim Trigger
Altruistic	C,C (3A)	D,C (3B)	C,C (3A)	C,C (B+2A)	C,C (3A)
Sociopathic	C,D (3E)	D,D (3F)	D,D (E+2F)	D,D (3F)	D,D (E+2F)
Tit-For-Tat	C,C (3A)	D,D (B+2F)	C,C (3A)	D,C (2B+E)	C,C (3A)
Cynical Tit-For-Tat	C,C (3E)	D,D (3F)	C,D (B+2E)	D,D (3F)	D,D (B+E+F)
Grim Trigger	C,C (3A)	D,D (B+2F)	C,C (3A)	D,D (B+E+F)	C,C (3A)
Totals:	9A+6E	5B+10F	9A+B+3E+2F	2A+4B+2E+7F	9A+B+2E+3F

Fourth pass:

	Altruistic	Sociopathic	Tit-For-Tat	Cynical Tit-For-Tat	Grim Trigger
Altruistic	C,C (4A)	D,C (4B)	C,C (4A)	C,C (B+3A)	C,C (4A)
Sociopathic	C,D (4E)	D,D (4F)	D,D (E+3F)	D,D (4F)	D,D (E+3F)
Tit-For-Tat	C,C (4A)	D,D (B+3F)	C,C (4A)	C,D (2B+2E)	C,C (4A)
Cynical Tit-For-Tat	C,C (4E)	D,D (4F)	D,C (2B+2E)	D,D (4F)	D,D (B+E+2F)
Grim Trigger	C,C (4A)	D,D (B+3F)	C,C (4A)	D,D (B+E+2F)	C,C (4A)
Totals:	12A+8E	6B+14F	12A+2B+3E+3F	3A+4B+3E+10F	12A+B+2E+5F

And since this looks stable, we can get a general state for the Xth pass:

	Altruistic	Sociopathic	Tit-For-Tat	Cynical Tit-For-Tat	Grim Trigger
Altruistic	C,C (XA)	D,C (XB)	C,C (XA)	C,C (B+[X-1]A)	C,C (XA)
Sociopathic	C,D (XE)	D,D (XF)	D,D (E+[X-1]F)	D,D (XF)	D,D (E+[X-1]F)
Tit-For-Tat	C,C (XA)	D,D (B+[X-1]F)	C,C (XA)	C,D/D,C ([X/2]B+[X/2]E)	C,C (XA)
Cynical Tit-For-Tat	C,C (XE)	D,D (XF)	D,C/C,D ([X/2]B+[X/2]E)	D,D (XF)	D,D (B+E+[X-2]F)
Grim Trigger	C,C (XA)	D,D (B+[X-1]F)	C,C (XA)	D,D (B+E+[X-2]F)	C,C (XA)
Totals:	3XA+ 2XE	[2X+2]B+ [3X-2]F	3XA+ [X/2]B+ [X/2+1]E+ [X-1]F	[X-1]A+ [X/2+2]B+ [X/2+1]E+ [3X-2]F	3XA+ B+ 2E+ [2X-3]F

So, let's compare these totals. Let's start by comparing the Tit-For-Tat ruleset to the sociopathic one.

1. (2X+2)B+(3X-2)F ? 3XA+(X/2)B+(X/2+1)E+(X-1)F
2. 2XB+2B+3XF-2F ? 3XA+XB/2+XE/2+E+XF-F
3. 2XB+2B+3XF-2F ? 3XG-XB-XE+E+XF-F(substitute B+E+G for A, where G=[2A-B-E]/2)
4. 3XB+2B+XE-E+2XF-F ? 3XG
5. (B-E)+(B-F)+X(B+E)+2X(B+F) ? 3XG
6. (B-E)+(B-F) ? X(3G-3B-E-2F)

So, in other words, as long as 3B+E+2F<3(2A-[B+E])/2 (in this case, at least; and remember that 2A-[B+E]>0), eventually pure greed will lose out to the Tit-For-Tat strategy.
If you like, you can check Tit-For-Tat against other strategies. You can also try putting together something that beats the strategies I gave you.
Next time, a problem with this solution.
<<Non-Zero-Sum Games: The Simple Prisoner's Dilemma | Game Theory | Cyclic Games: The Iterated Prisoner's Dilemma II: (Electric Boogaloo:) The End of the Game>>

Game Theory: Part V: Non-Zero-Sum Games: The Simple Prisoner's Dilemma

Sometimes, we have the option of cooperating with someone else or refusing to cooperate. Sometimes, others have the option of cooperating with us or refusing to cooperate. Elimination of dominated strategies is not always the best option.

The following material is flagged Green Level. It is intended to reflect material that the author believes to be a matter of consensus among experts in the field. This belief may be incorrect, however; and as the author is not an expert and does not have an expert fact-checking the article, errors may creep in.

Let's look at another non-zero-sum game called the Prisoner's Dilemma. The standard setup goes something like this: There are two people who were captured by the police while trying to rob a bank. The police have enough evidence to get them convicted of unlicensed possession of firearms (a crime carrying a sentence of one year in this world), but offer them a deal: each prisoner can turn state's evidence and go free, but if they do, the other will be imprisoned for twenty years. However, if both try this, they will both be imprisoned for five years.

	Cooperate	Defect
Cooperate	(-1,-1)	(-20, 0)
Defect	(0,-20)	(-5, -5)

As you can see, each prisoner does better by snitching (the option labeled "Defect"), but both do better if the other stays silent (the option labeled "Cooperate"). The best solution for each prisoner is to defect while their partner cooperates, and the worst is to cooperate while their partner defects. It is a simple matter to find that the Nash equilibrium (remember that from last time?) is that both prisoners defect.
But the Nash equilibrium is not the best outcome.There are outcomes, called the Pareto optimals, which are outcomes that cannot be moved from without leaving at least one player worse off. In a way, you could think of it as sort of a dominant outcome. As you can see, there are three Pareto optimals, none of which are the Nash equilibrium (the optimals being the outcomes with at least one cooperation).
Incidentally, the Prisoner's Dilemma is something that shows up absolutely everywhere, from the actual prison system to economics to psychology. To give one example, take taxes. No one actually likes paying them, but most people recognize that if no one paid them, the government wouldn't be able to do anything. The best situation for any person is to not pay taxes while everyone else does, but (again, to most people; Libertarians have something of a tendency to disagree with this) everyone paying taxes is a preferable outcome to no one paying taxes, since (yet again, any Libertarians out there will disagree) a small part of one's paycheck/inheritance/dividends/whatever is preferable to a government that is unable to provide roads, police, defense, and so forth.
So how do we solve this? How do we get the prisoners to cooperate?
(Keep your hands down, those of you who already know an answer.)
For one solution, tune in next week. Or maybe the week after that. Same Bat-time, same Bat-channel.
<<Non-Zero-Sum Games: Chicken | Game Theory | Cyclic Games: The Iterated Prisoner's Dilemma I: Reciprocal Relationships>>

Topic: Game Theory

On this blog, I will sometimes discuss ideas over the course of multiple posts. I will call these ideas Topics, and collect them in posts like this one.

Game theory is a branch of mathematics dealing with the interactions between agents capable of making decisions. It provides understanding of how to benefit oneself as well as how to benefit both oneself and others, and can provide interesting insights into society.

1. Notation and Basic Concepts
2. Dominating Strategies
3. Utility Functions 
4. Non-Zero-Sum Games: Chicken 
5. Non-Zero-Sum Games: The Simple Prisoner's Dilemma 
6. Cyclic Games: The Iterated Prisoner's Dilemma I: Reciprocal Relationships 
7. Cyclic Games: The Iterated Prisoner's Dilemma II: The End of the Game.
8. Metagames: The Battle of the Sexes 
9. Coordination and Anti-Coordination 
10. Metagames: Extortion 
11. Metagames: The Punishing Prisoner's Dilemma 
12. Randomness