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\).

Iterated Prisoner's Dilemma Tournament in Class

On Friday my students and I played an iterated Prisoner's Dilemma tournament in class.

This is something that I've run many times before with +Paul Harper during outreach events and I've blogged about it here and +Dana Ernst ran something similar and blogged about it here (both those posts also talk about 2/3rds of the average games).

The way I do this is to split the class in to 4 teams and play a round robin of a set of 5 to 8 repetitions of the Prisoner's Dilemma:

The particular version of the game I usually use is given below:

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

The utilities represent 'years in prison' and over the 3 matches that each team will play (against every other team) the goal is to reduce the total amount of time spent in prison.

This is always good fun and my final year students were no exception (more so that +Paul Harper leant me a sidekick who was allowed to use a Nerf gun when the opposite team defected - more about that here):

In this particular instance we played 8 rounds per 'duel' and it was very helpful to have +Jason Young assist me with writing down the scores etc...

Here's the overall scores which show that the team named: 'Cymru' acquired the least total score (and won a box of chocolate):

Here's all the 'duels':

The 3rd game was the most interesting (from an educators point of view).

Team 'Roy' at the very beginning of the duel stated:

'We will cooperate until you defect, once you defect we will only defect'

Both teams cooperated fully and in the final round Roy defected (whilst their opponent continued to cooperate). This all happened with no prompting from myself which is great because team Roy in effect discovered how strategies had to be defined in repeated games which must take in to account the entire history of the game.

What's also quite cool is that they described 'Tit for Tat' the strategy that won Axelrod's tournaments.

+Michael Trick pointed out that that is completely incorrect and that Roy almost described 'Tit for Tat', they in fact played what's called 'grudger' (which did not win Axelrod's tournaments).

What happened in the last two rounds of the game was also pretty interesting as some coalitions formed to try and share the box of chocolates. Some of my students showed some great game theoretical reasoning: 'we will give you all but enough chocolates for each one of us on the team'...

In class we will consider repeated games in a more rigorous setting and before playing infinitely repeated games also play a modified version of this tournament (I'll blog about that when it happens).

(Note that the name of the winning team: Cymru is Welsh for Wales and I think was partly motivated by the fact that I was wearing my French rugby shirt before the Wales France game that evening. Wales played extremely well and thrashed France.)

Best responses to mixed strategies in class

On Monday my Game Theory class and I took a look the connection between extensive form games and normal form games (leading to subgame perfection) which correspond to these two chapters of my course: C7 and C8 but before starting that we took another look at best responses to mixed strategies (this Chapter of my course).

We have been using this game quite a bit in class:

\[\begin{pmatrix}
(2,-2) & (-2,2)\\
(-1,1) & (1,-1)
\end{pmatrix}\]

We played it before and I blogged about it here. This is a slight modification of the matching pennies game where the 1st strategy corresponds to playing Heads (\(H\)) and the second to playing Tails (\(T\))

If player 1 (the row player) is playing a mixed strategy \(\sigma_1=(x, 1-x)\) then the utility to player 2 when playing player 2 plays $H$ (the first column) can be written as:

\[
u_2(\sigma_1,H)=-2x+1-x=1-3x
\]

and when player 2 plays $T$:

\[
u_2(\sigma_1,T)=2x-1+x=3x-1
\]

We can plot these two utilities here (using +Sage Mathematical Software System):

It is immediate to note that when \(x < 1/3\) player 2 should play $T$. In fact we can write down player 2's best response \(s_2^*\) to any \(\sigma_1\):

\[
s_2^*=\begin{cases}
H,&x < 1/3\\
T,&x > 1/3\\
\text{indifferent},&
\end{cases}
\]

Using all this I played the following game in class:

• I handed out sheets asking students to play against 3 separate mixed strategies \(\sigma_1\in\{(.2,.8),(.9,.1),(1/3,2/3)\}\). I will refer to these 3 rounds as R1, R2 and R3;
• Students (acting as player 2) filled in their strategies;
• I then used the following interact to sample mixed strategies according to \(\sigma_1\):

I changed the value of \(x\) as required.

Here are the three row strategies that were sampled:

• R1: TTTTTH 
• R2: HHHTHH 
• R3: TTHTTT 

This is obviously not giving the exact proportions dictated by the mixed strategy \(\sigma_1\) but that's also kind of the point. By round, here are the results.

R1

Here's a plot of the mixed strategy that was played by the entire class during round 1:

This corresponds to \(\sigma_2=(.70,.30)\), so most students seemed willing to 'trust the theory' that one should play $H$ against this mixed strategy.

4 students scored the highest score (\(7\)) and here's the strategy they all played: \(HHHHHT\), in essence they got lucky and maxed out what they could have had. If they had played the theoretical best response (to only play $H$) they would have scored: 3.

The expected value of playing the theoretical best response (always pick \(H\) against this mixed strategy is: \(6(1-3\times.2)=2.4\) (recall that \(\sigma_1=(.2,.8)\) for this round).

The mean score for this round was 1.4 and here's a distribution of the scores:

47 students who 'won' ie scored a positive score (this is a zero zum game) played \(\sigma_2=(.83,.17)\). 18 'lost' (scored a negative score) playing \(.37,.63\).

It's nice to see that there was a large amount of students who did in fact score 3.

R2

Here's a plot of the mixed strategy that was played by the entire class during round 2:

This corresponds to \(\sigma_2=(.12,.88)\), which is again pretty close to the theoretical best response.

2 students scored the highest score: 11. They once again lucked out and played the perfect response: \(TTTHTT\). If they had played the theoretical best response they would have scored 9.

The expected value of playing the theoretical best response (always pick \(T\) against this mixed strategy is: \(6(3\times.9-1)=10.2\) (recall that \(\sigma_1=(.9,.1)\) for this round).

The mean score for this round was  6.9 and here's a distribution of the scores:

60 students 'won' ie scored a positive score (this is a zero zum game) playing \(\sigma_2=(.07,.93)\). 5 'lost' (scored a negative score) playing \(.77,.23\).

R3

The third round had the students playing against a mixed strategy for which they should have been indifferent. Here's how they played:

This corresponded to \(\sigma_2=(0.62,.38)\).

There were 10 winners for this game and they scored 10 (quite a few strategy profile gave this score so I won't list them but they mainly took advantage of the fact that mostly $T$ was sampled). (The theoretical utility is in fact 0 as you can see with one of the plots above).

The mean score for this round was was .4 (which is quite close to the theoretical value of 0). Here's the distribution of the scores:

28 scored positively playing \(\sigma_2=(.64,.36)\) and 37 scored negatively playing \(\sigma_2=(.77,.23)\).

What's nice to see here is that this 3rd round is a bit more random, with an almost (stretching the definition of the word almost) equal distribution between the number of students who won and lost.

Here's a distribution of the overall scores:

The overall winner of the game (who scored the most over the 3 rounds) was Becky who played:

• R1: \(TTHHHH\)
• R2: \(TTTTTT\)
• R3: \(HHTHTH\)

For a cumulative score of: 21

This was good fun to analyse and was hopefully useful to my students to see what is meant by best responses to mixed strategies. It was particularly cool to see an 'indifferent' (again stretching the definition of the word indifferent) response to the third round.

(Like with everything for this course you can find the data, analysis scripts and everything else at this github repo)

My students write about their first Python conference

Last week I wrote about my impressions from my first Open Source Software conference (OSS): https://djangoweekend.org/

It was an awesome conference but the highlight for me was seeing 3 of my students take full advantage of the event. I asked Matt, Alex and James to write a bit of a guest post for this blog about their experiences:

--------------------------------

Here's what Matt had to say:

"Having never been to a conference like this before, and with only a few months of coding experience under my belt, I had no idea what to expect from Django Weekend Cardiff. Despite this I had an incredible weekend. Everyone that I met and talked to was friendly and more than willing to answer my questions. 

While some of the talks went a little over my head, the clinics were very helpful in getting me started with Django. I even felt confident enough to give a lightning talk, that gave me the chance to voice my opinion on computing with regards to education, and how it had helped me over the few months I was leaning it as part of my undergraduate course for maths.


Overall I had a great time, and will definitely be keeping an eye out for Django Weekend Cardiff 2015."

Matt's lightning talk was recorded so as soon as it's online I will be post about it. He did an awesome job.

--------------------------------

Here's what +Alex Carney had to say:

"I first became aware of the open source scene when I was in Year 7 and my dad installed Ubuntu 7.10 on my ancient laptop in a bid to keep it usable. I slowly became more and more fascinated on what software I was able to download for free and have a play with, from creating animations with Blender to messing around in GIMP and to hear him say that it was made by normal people such as ourselves I was blown away thinking how on Earth could people like my dad and myself create such wonders?

Well needless to say it reignited my desire to learn programming, I had dabbled with Pascal and BASIC beforehand but I couldn't get much further than a series of print statements and lost interest. But then to discover Python, a language with syntax that was actually readable to someone just starting secondary school was amazing, slowly I was able to teach myself parts of it in short bursts over the years, before dropping it when I was in Year 11, to learn C++ mostly forgetting about Python.

Fast forward to September 2013, when I started my Maths degree at Cardiff Uni, and I finding out that I would be taught Python as part of the course was like being reunited with an old friend. But this time there was a major difference I was actually using Python. Back when I was teaching myself I never had any concrete goals or deadlines, I would follow one example before swiftly moving on to the next without stopping to apply what I had learnt. So naturally it was hard to maintain focus and I never produced anything worthwhile. 

However being set tasks to complete was great as I was finally applying my knowledge I had gained over the years and was able to appreciate how useful being able to program is, once you start thinking like a programmer the only limit is your imagination - Oh! and of course how powerful your computer is...

I can't thank Vince and the School of Mathematics at Cardiff enough for sponsoring me to go to the conference because it made me realise a lot of things. Firstly is that there really is a thriving welcoming community on the open source scene. I was always vaguely aware that it existed as I trawled through forums and mailing lists looking for solutions to problems I was having, but something always stopped me from joining in. I was thinking that even though it was open there was some mystical entry barrier that you had to pass before you would be accepted.

However by going to the conference I was shown the complete opposite. Nobody so much batted an eyelid when they saw me, some student only just able to scratch the surface of Python's power and knowing absolutely nothing about Django. Moreover they wanted to speak to me, they wanted to hear about it from a beginner's perspective, they wanted to know what it was like learning Django for the first time, what could they do to make it easier for me to learn? While having a chat with one of the core Django developers I pointed out that I didn't find certain steps in a tutorial that clear and afterwards he went away and amended the tutorial clearing up the confusion that I had!

It was incredibly interesting to hear how other people have used Python in their work and I was blown away at the power of not only the programming language itself but the community as well. An example from a particular talk was the Astronomy community, how Python was able to help the community create a common standard for sharing data and how all the tools developed by individuals went on to benefit the community as a whole. Leaving researchers able to concentrate more on the science than the technical difficulties and headaches of having to deal with fragmented standards and datasets.

I want to finish by saying how truly inspired attending the conference made me and I not only want to thank Vince and the School of Mathematics for giving me the opportunity, but to thank Daniele Procida for making the conference a reality in the first place. I will definitely want to attend next year's and I'm even thinking of going to  PyConUK in September. I am yet to contribute to an open source project but I'm hoping that's an issue I can fix sooner rather than later."

Alex was one of the students in the class with the most starting knowledge; in fact he helped me win a bet with +Jason Young (that I would be able to get a student to use Vim before the end of the year: Alex used Vim from the start...). It's really nice to read that he found the whole conference interesting and more importantly inspiring.

--------------------------------

The final post is from +James Campbell but he has his own blog that I'd really recommend you taking a look at (James is also a rugby referee so he blogs about that as well). Here's the post he wrote about the conference: http://www.jamescampbell.org.uk/?p=417

If it's too much effort to click over to there here's a bit I stole:

"Today they were working on fixing bugs and reviewing code for the upcoming Django 1.7 release. However, despite how busy they were, whenever I needed a hand someone was happy to help. At one point I had Django core developers discussing the best way to solve one of my problems. These guys are some of the best in the world at what they do, yet they still found time to help a complete newcomer, and I’m really grateful to all those who did so."

A Rock, Paper, Scissors, Lizard, Spock Tournament in class

I just taught mixed strategy Nash equilibria to my students (http://goo.gl/evmerJ and  http://goo.gl/wMxAoY).

I thought I could use this as an excuse to play a Rock, Paper, Scissors tournament and then someone suggested I play a Rock, Paper, Scissors, Lizard, Spock tournament:

Most students had seen the game but to help us along with the rules I put this up on the board (source: wikipedia):

We then proceeded to play a 16 player knockout tournament that +Jason Young kindly helped run. Student were matched up and played best of 3 rounds with sudden death.

Here are the results (open the image in it's own tab to view it in detail):

Here's a plot of the strategies played during the 1st, 2nd and 3rd rounds:

The overall strategy profile played is here:

We're not quite playing at Nash equilibrium (which would imply a uniformly distributed choice of strategies) but it's not too far off.

Here are the strategy profiles of all matches that won a game:

Thus it looks like a response to these winning strategies would be to play strategies that beat Spock, Rock and/or Lizard. Paper would seem to be an ok bet. 

Here are the losing strategies:

It looks like Scissors was being played a bit too much and losing to Spock and Rock.

This was good fun and hopefully help the students understand what a mixed strategy is.

If it's of interest here is the dirty Python script I wrote to analyse all this.

My students and my first PyCon

A couple of months ago an email somehow found it's way in to my inbox mentioning a new user group that was setting up in Cardiff. This was from some guy called Daniele Procida. As a Python coder really enthusiastic to be part of the Open Source Software (OSS) community I thought this would be awesome so I've been along to the monthly meetings where all things Python and Django are discussed.

However many months later I got to attend my first PyCon (in fact a DjangoCon): https://djangoweekend.org/

Here's the programme that I carried around in my back pocket:

Professor Tim Phillips, the head of the School of Mathematics kindly agreed to sponsor 3 tickets for students on my Computing for Mathematics course. I gave 3 tickets to students as a reward for their individual coursework (James wrote about Markov chains and Snakes and Ladders, Alex about Fractals and Matt about prime numbers).

+Jason Young who has been my research undergraduate student for a couple of years now (and is a very able coder) attended and +Izabela Komenda (a post-doc) also presented some of her PhD work.

Here's a picture of my Cardiff students, Daniele and I:

It was great that so many sponsors contributed to the conference (full list here) and also that +Cardiff University supported the event wholeheartedly, Roger Whitaker (the dean of research for the physical sciences) even opened the scientific talks on Friday.

Frankly:

It was the best conference I've ever been to.


The atmosphere cultivated by the OSS community is really amazing. Everyone is really encouraging, understanding and just plain ol' nice.

From the scientific talks on the Friday where usages for Python in Science were discussed to witnessing what a 'code sprint' was on the Sunday: everyone was just exceptionally nice.

I learnt Django over christmas and the help people were willing to give (not once making my mistakes more than they were) was really cool.

For example this morning I sat down with Baptiste, one of the core Django developers and he really kindly answered all the (noobish) questions I had (before leaving today he actually gave me his card and told me to get in touch if I had any further problems with a particular thing).

That is just one example of the awesome atmosphere that was cultivated during the conference. The event brilliantly mixed advanced programming for one of the most popular web frameworks with accessible topics for every attendee. I think that this is something that is kind of inherent to the OSS community, you are encouraged to put yourself out there and potentially make mistakes.

For this reason alone I'm extremely glad that the 3 undergraduates got to attend the event. 

Fear of failure and mistakes is something that sometimes really holds students back. As educators it's very important for us to make sure students learn to embrace mistakes.

During one of the talks on Saturday a particular particularity of Django was being discussed and I thought to myself:

I wonder if my students will be put off by "how much they don't understand" and perhaps this will end up being a negative experience for them...

I could not have been more wrong, their attitudes were perfect. They realised that they were very much at the beginning of the road (some of them had not coded before October) and just took advantage of everything around them.

James gave a talk on the Friday which was great and Matt gave a lightning talk (less than 5mins):

They all spoke to the experts around them constantly and by Sunday were themselves writing Django apps. It was great to have +Robert Dragan of learnium help some of them debug their code on the Sunday.

In fact towards the end of Sunday James even had Daniele (a core Django developer) and Charlie (a super-duper really helpful and nice Django developer/person) helping him work on a site:

I won't write much more about the whole event but I'll just repeat something that Matt said during his lightning talk.

He started by saying that he was a bit dismayed when at the beginning of his degree he was told that he was going to have to learn how to code (my course is brand new), he then talked about how he thought +Sage Mathematical Software System helped him gain a better understanding of the prime number theorem but it was what he said last that was really awesome (a lot of other attendees commented on it):

"Why did I have to wait until coming to University to learn to code?"

(All the talks on Saturday were recorded so I really look forward to sharing his talk, it was very well delivered.)

This whole event was a really great experience for me but more importantly my students.

The conference will be running again next here which is awesome for my future students. Next time Daniele, (who is one of the most impressive human beings I've ever met) will have (at least) me to help organise the it.

I've already signed up for my next PyCon (http://pyconuk.org/) and more importantly I've asked myself:

"Why did I have to wait till now to attend an OSS conference?"

An attempt at Golden Balls in class

Today I introduced my students to the concepts of Dominance and Best responses in my new game theory class (Chapters 3 and 4 of my class notes).

To re-affirm ideas we saw previously (normal form representation of games) and also talk about Dominance I tried to set up a kind of Golden Balls game.

Golden Balls is a game show that aired in the UK a while ago and I've never actually seen an episode but the premise is that two players cooperate during the game to come up with a total sum of money that must then be 'shared' using a Prisoner's Dilemma.

If you haven't seen this video before, it's a great example of the end game of the show:

I always show this video to students when talking about Game Theory as I reckon it's pretty awesome.

Here's what I did in class:

I got two students to play the game: A and S. They were to compete against me (as the row player, I was the column player) in the following 5 normal form games (their utility corresponded to the number of chocolates I would owe them):

1. Just a plain old matching pennies game (we played this in class last week and I blogged about it here):

$$\begin{pmatrix}
(1,-1)&(-1,1)\\
(-1,1)&(1,1)
\end{pmatrix}$$

2. A modification of this game with a weakly dominated strategy:

$$\begin{pmatrix}
(1,-1)&(-1,1)\\
(1,-1)&(1,-1)
\end{pmatrix}$$

A and S were both quick to realise  that they should play the second row strategy.

3. A modification of the matching pennies game:

$$\begin{pmatrix}
(2,-2)&(-1,1)\\
(-1,1)&(2,-2)
\end{pmatrix}$$

4. A game with a strategy at which they would definitely win something:

$$\begin{pmatrix}
(2,-2)&(1,-1)\\
(-1,1)&(2,-2)
\end{pmatrix}$$

5. The same game as 4, again (when I play this next year I'll change this game slightly).

This ended up with A and S having about 6 chocolates between them. I then split the team up and told them to play:

$$\begin{pmatrix}
(2,2)&(0,3)\\
(3,0)&(1,1)
\end{pmatrix}$$

If they cooperated (choosing the first strategy) I would double the 6 chocolates and they would have 12 chocolates each. If 1 defected, the defector would have 18 chocolates and the other none. If they both defected they would just have 6 chocolates each.

I asked if they'd like to talk to each other. S, tried but A confidently said: 'no need, I know what you are going to do'. S cooperated and A defected.

There were 1 or 2 'oooos' that were swiftly ended when A proceeded to immediately share his chocolates with A. I in fact ended up just giving the whole box of chocolates I bought:

After this we moved on to talk about best response strategies. 

I asked for a volunteer to player tic-tac-doe with me and we used this as a discussion about best responses:

'Right, now that she has played there, where should I play?'

I put up a picture of +Randall Munroe's tic-tac-toe solution.

All in all it was good fun I think and hopefully helped make the class a bit more 'alive'. I have a (what I think is a) cool idea about a game I'll try and play with my students next week when talking about mixed strategy equilibrium. This could involve a bracket of 16 volunteers...

If you liked the video above, take a look at this one which is pretty awesome too: