Thursday, 27 February 2014

Iterated Prisoner's Dilemma with a twist in Class

In my last blog post I described the iterated prisoner's dilemma tournament that my students played in class: 'Iterated Prisoner's Dilemma Tournament in Class'. This was great fun and one team even got the idea of how to define a strategy in a repeated game.

That class activity corresponded to this chapter of my class during which we looked at subgame perfect Nash equilibrium.

Let us look at the Prisoner's dilemma that we played:

$\begin{pmatrix} (2,2)&(5,0)\\ (0,5)&(4,4) \end{pmatrix}$

If both players cooperate for 3 rounds then they both get a utility of $2\times3=6$.

The next chapter of my class looks at what is called 'infinitely repeated games', in this it is assumed that players play an infinite number of rounds. We use the usual mathematical trick to handle infinite sums so that we can compute finite utilities.

For example the utility to both players for always cooperating is given by:

$\sum_{t=1}^{\infty}\delta^{t-1}2=\frac{2}{1-\delta}$

Where $0 < \delta < 1$.

The utility to both players always defecting is given by:

$\sum_{t=1}^{\infty}\delta^{t-1}4=\frac{4}{1-\delta}$

The 'discounting factor' $\delta$ allows us to compare these two strategies: if both players defect they do worse then if they both cooperated.

There are various interpretations for $\delta$, one of which is the probability with which a game continues (ie we allow for the possibility for the game to end at each round), thus the above calculation become an expected value calculation.

To illustrate this I brought a dice in to class and had +Jason Young run a tournament during which the game could end based on a chosen probability.

Here are the first set of results (we played with $\delta=.75$ so we carried on as long as my d20 < 16):

Team Laurence got pretty lucky (players are here trying to reduce the 'amount of time they spend in prison') with their roles and twice only had to play one round!

Here's the overall standings (as well as some other details):

Team Cymru's huge score can be explained by two factors: lack of luck with the dice and they also formed a coalition with team Laurence.

After this we still had 30 minutes spare in the class so I offered ending there or playing another round. My students made me smile by mostly staying and playing another round. In fact they even pointed out that technically they shouldn't be able to watch the progression of the game (ie seeing how other teams were acting). So they suggested that the teams who weren't playing would go stand in the corridor (I thought this was cool to come from them).

We also changed the value of $\delta$ to $.25$ (so games only continued 25% of the time). Here are the results:

This is the last round (they're on separate boards because I had to hide/erase/etc...):

The outcome was team Roy and Cymru both tied for the win at 8 (Roy did this with well timed defections and Cymru managed to cooperate successfully a couple of times).

At this point I wasn't really sure what to use as a tie breaker but someone in class yelled: 'Rock, Paper, Scissors, Lizard, Spock'. We actually played this in class a while back when we started looking at mixed strategies, I blogged about it here: 'A Rock, Paper, Scissors, Lizard, Spock Tournament in class'

Here's the outcome of that:

Joe won it for team Roy.

This was great fun and will hopefully be useful to help my students contextualise one of the ideas of this chapter: it's actually possible to find a value of $\delta$ for which students should cooperate. I'm not sure this was made evident by the activity but we did see more cooperation for lower values of $\delta$.