Tuesday 28 January 2014

Matching pennies in class

Yesterday I took the first class of my new module on Game Theory. I've been very excited about this as I think Game Theory is a really fun subject to learn (and teach).

In class we covered the first two chapters of my notes (Chapter 1: Introduction to Game Theory, Chapter 2: Normal Form Games). Whilst talking about Normal Form Games I showed the students the game called Matching Pennies.

Two players each show a coin with either 'Heads' or 'Tails' showing. If both coins match then the 1st player (the row player) wins, otherwise the 2nd player (the column player) wins.

This can be represented using a 'bi-matrix':

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

Each tuple of that matrix corresponds to a pair of strategies from the set $\{H, T\}$, so if the row player chose $H$ and the column player chose $T$ then they would read the outcome in the first row and second column: $(-1,1)$. The convention used here is that outcomes show the utilities to the first and then the second player. So in this instance the row/first player would get -1 and the column/second player would get 1 (ie the column player wins because the coins where different).

I asked the students to get in to pairs and record five rounds of the game on some paper (forms and all other content for the course available at this github repo).

After that, I modified the game to give this:

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

The row player still wins when the coins match but there is just more to win/lose when $H$ is picked by the row player.

I got the students to once again record the results.

Last night I got home and instead of speaking to my wife I went through and entered all the data.


Here are some of the results.

First of all 'basic matching pennies'. Here are the moving averages of all the games played:


I'm graphing the probability with which players played $H$. As you can see 'we' got to equilibrium pretty quickly and 'on average' players were randomly swapping between $H$ and $T$.

Here is a plot of the equivalent mean score to both players:


First of all we see that the plots are reflections in the $x=0$ line of each other. This is because the game we are considering is called a Zero Sum Game: all the utility doublets sum to 0. Secondly we see that the mean score is coming around to 0. 

All of the above is great and more or less exactly what you would expect.

While playing the second game I overheard a couple of students say something like 'Oh this is a bit more complicated: we need to think'. They were completely right!

Here are the results. First of all the strategies:


It seems like students are once again playing with equal probabilities of picking $H$ or $T$. The outcome for the score is again very similar:



Is this what we expect?

Not quite.

Let us assume row players are playing a 'mixed strategy' $\sigma_1=(x,1-x)$ (ie they choose $H$ with probability $x$) and column players are playing $\sigma_2=(y,1-y)$.

Let us see what the expected utility to the row player is when $\sigma_2=(.5,.5)$ as a function of $x$ (the probability of  playing $H$):

$$u_1((x,1-x),(.5,.5))=.5(2x-(1-x))+.5(-2x+1-x)=0$$

So in fact what the row player does is irrelevant (with regards to his/her utility) as long as the column player plays $\sigma_2=(.5,.5)$.

What about the column player?

Writing down the utility to the column player when $\sigma_1=(.5,.5)$ as a function of $y$ (the probability of playing $H$):

$$u_2((.5,.5),(y,1-y))=1/2(-2y+y+2-2y+y-1)=1/2-y$$

So NOW if $\sigma_1=(.5,.5)$ it looks like the column player has SOME control over his/her utility.

Here is a plot of that $u_2$:



So our plot is that of a decreasing function. Remember $y$ is something that the column player can control. So as the column player wants to increase $u_2$: the best response they should adapt to the row player playing $\sigma_1=(.5,.5)$ is in fact $y^*=0$ because at $y=0$ the utility is at it's highest!

What this implies (for the second game) is that whilst the students were all winning and losing in equal measure (the mean score was around 0). The column player could in fact improve their strategy and take advantage of the fact that the row player was playing $\sigma_1=(.5,.5)$.

The row player can't actually do this (we did the math above and we saw that he/she couldn't really have any effect on his/her utility). What my students and I will see in Chapter 6 of my class is that in fact there is a way to make both players 'unable to improve their outcomes'. When we get there it will also shed light on the dashed lines in some of the plots of this blog post.

Friday 24 January 2014

What happens when I ask students if they have seen 'A Beautiful Mind'

For the past 4~5 years now I've been lucky enough to tag along with +Paul Harper when he does outreach in high schools. I've developed my own little 'roadshow' that introduces students to Game Theory.

On Wednesday there was a cool event at the School of Mathematics where we had 120 odd 17 year olds in to get a taste for the Mathematics at University (some pics: here and here).

I've blogged many times (and +Dana Ernst has as well: here) about the activity that I run which involves a Prisoners dilemma tournament and 2 rounds of a 2/3rds of the average game, here is my updated set of results over all the times I've played it (the second guess is after we all discuss rational behaviour):

(if any of my student are reading this the above could help them win a box of chocolates on Monday)


This is not the purpose of this post.

Something terrible happened on Wednesday.

During my activity I always show this clip from A Beautiful Mind (awesome movie about John Nash):


Before showing the clip I always ask: "How many of you have seen the movie 'A Beautiful Mind'?".

Now, I've been doing this for 4~5 years and the response I get to this question has made me realise that I'm not cool anymore. I guess there's a point in everyone's life where that realisation hits them. I've been in denial until Wednesday when for the first time ever: not one student had seen the movie :'(. This makes me sad because I think this is probably one of my favourite movies and one I've always thought was pretty cool.

Here's a little plot showing what I've been telling myself over the past few years (the fact that xkcd style graphs is now native to matplotlib is cool, my previous attempt at one of these: 'probability of saying yes to academic responsabilities'):



When I first asked and had about a quarter of the room know what I was talking about I thought that it was kind of cool and a sign of no longer being a kid...

When in twenty years time I embarrass my daughter by opening the door to her boyfriend/girlfriend wearing pyjamas; inviting him/her inside for a talk and reading him/her passages of my PhD thesis or whatever else I can think of, I'll be able to say that it's revenge for not being cool any more and that I made this decision on the 22nd of January 2014.

Thursday 23 January 2014

My Game Theory YouTube Playlist and other resources

I just added Graham Poll's awesome +YouTube playlist (http://goo.gl/UZ1Ws) to my "reading" list for my Game Theory course that I'm teaching on Monday and thought that I should also include the humble videos related to Game Theory that I have on my channel:



I also thought I could get away with making a blog post about this. The playlist above has them in 'last in first out' order but here they are in the order that I made them:

1. "An introduction to mixed strategies using Sage math's interact page."

A video that looks at the 'battle of the sexes' game and also shows of a +Sage Mathematical Software System interact.

2.  "Selfish Behaviour in Queueing Systems"

A video close to my research interests which look at the intersection of Game Theory and Queueing Theory. This video is actually voiced by +Jason Young who was doing his first research internship at the time with me and will be starting his PhD at the beginning of the 2014/2015 academic year.

3. "Pigou's Example"

A video describing a type of Game called a 'routing game'. Pigou's example is a particular game that shows the damaging effect of selfish (rational) behaviour in a congestion affected system. This video also comes with a bit of +Sage Mathematical Software System code.

4. "Calculating a Tax Fare using the Shapley Value"

This is one of my most popular videos despite the error that +Brandon Hurr pointed out at 3:51. It describes a basic aspect of Cooperative Game Theory and uses the familiar example of needing to share a taxi fare as an illustration.

5. "Using agent based modelling to identify emergent behaviour in game theory"

This video shows off some Python code that I've put online that allows the creation of a population of players/agents that play any given normal form game. There are some neat animations showing the players choosing different strategies as they go.

6. "OR in Schools - Game Theory activity"

This isn't actually a video of mine. It is on +LearnAboutOR 's channel but it's a 1hr video of one of the outreach events I do which gets kids/students using Game Theory.

7. "Selfish behaviour in a single server queue"

I built a simulation of a queue (Python code here) with a graphical representation (so you see dots going across the screen). This video simply shows what it can do but also shows how selfish behaviour can have a damaging effect in queues.

I'm going to be putting together (fingers crossed: time is short) a bunch more over the coming term.

Sunday 19 January 2014

Is being a pro athlete like being an academic?

This academic year is a very busy one for me and I spent most of Christmas working (this isn't unusual at all amongst academics) . This didn't feel strange or 'hard': it was simply what I did.

When one of my brothers in law pointed out that writing code on Christmas morning was a bit 'strange' it reminded me of the fact that Jonny Wilkinson (one the best rugby players of all time) supposedly/famously practices on Christmas day (fact #3 here). 

This post is going to be some thoughts about the similarity between professional athletes and academics...

I watched this great +TEDx talk the other day about a kid who describing his 'hackschooling' and in particular discusses 'what he wants to be when he grows up' (the answer is 'happy'):



As a young kid all I ever wanted to be was a professional rugby player (reality set in at about 13-14) . I more or less always had a ball with me, here's a picture of me (I'm the one with my head down) when I was 12ish (I think):


I went to a rugby boarding school when I was 16 and had the best time of my life there. I was never athletically good enough to ever 'be what I wanted to be' (a pro rugby player). A nasty roller blading accident when I was 18 more or less finished off my rugby 'career' anyway. 

From the age of about 15 though I think I realised that I needed a more realistic plan and when people would ask me what I wanted to be I'd always say: 'I want a PhD in mathematics and to be a mathematics researcher'. I don't think I really knew what that was, but that's what I would say.

15 years later that's what I am and I consider myself very lucky to be what I wanted to be when I was a kid.

1. Passion

I think that's probably the first similarity between athletes and academics, it's such a competitive environment. Kids who play pro anything most probably invested (as did their families) a lot of time and effort in to getting there.

Similarly for academics. You have to work extremely hard, to get in to a good University, to do well, to get a PhD and then to finally get a 'pro contract' in the form of post-doc or similar.

2. Luck

For every good pro athlete (I don't mean great), there are probably a bunch that were never 'discovered' (or who themselves never discovered that they were/could be great).

I think this is similar to academics, with less and less funding available for research positions and the extremely competitive job market, there are probably quite a few talented people who never even think of pursuing a career in academia.

A lot of it is probably about being in the right place at the right time. Playing a game when a scout happens to be watching is quite similar to how I got my first post-doc: there happened to be some funding available when I was coming to the end of my PhD and my current employers where open minded enough to appreciate my ability to change fields.

3. Hard Work

Academia is hard. Ridiculously hard. You have to juggle various things: teaching, research, outreach, admin (I really hate admin...) and you have to be good at all of them.

Being a pro athlete is (probably) hard. You have to juggle various things: athletic ability, injuries, athletic IQ, press/media and you have to be good at all of them.

The thing is you do all these things, whether or not that's why you got in to the field in the first place. That's probably because of the passion or the pay (I'll get back to the pay later...).

As a rugby player I was not a good tackler, I was terrible. It was something I had to work on a lot harder than on my vision and fitness for example. I used to spend more time than most working on tackling. 

In academia it took me quite a while to get 'ok' at writing (my PhD supervisor and +Paul Harper who proof read a lot of my early drafts will no doubt agree with that). This was something that I had to work quite hard at (and still do!).

Ultimately athletes and academics are faced with the same 'problem'/'opportunity'. We can work as hard as we want to. There's always further to go (more weights to lift, another training session to have, more tape to watch, more recovery techniques to try...). Here's a good +PHD Comics that was published today illustrating what I mean:



4. Competitiveness

I love competition. I don't really mind losing, but I love competing (I have a rant that I repeat fairly often about the difference between being a bad loser and being competitive but I'll leave that for another time).

When I was in the running for my permanent post I loved knowing that I was working as hard as I possibly could to get it. If someone was going to get appointed ahead of me it was not going to be because I did not push myself hard enough.

The analogous holds immediately with pro athletes and it's a part of my job that I love.

5.  The pay

Ok this is where my analogy perhaps breaks down as the pay is pretty much incomparable but I think there are some parallels to be drawn.

In the press a lot of athletes apparently 'fall out of love with the game' (recently an England cricketer for example was told to go home and remember why he liked cricket), I guess that they sometimes (understandably given how much money comes their way) play for money and it becomes about contracts etc...

For a lot of Academics it's probably the same thing. After a while (snowed under by a pile of admin) it just becomes a job. There's nothing wrong with that of course (a lot of people perhaps end up in Academic 'by mistake' also).

Personally, I think I have the coolest (second to being a pro rugby player) job in the world and am just ridiculously grateful to be able to do it.

The bad sides of this are that I am a workaholic and don't see my wife very often (she sometimes +1s my G+ posts so we do interact), but ultimately I get to do what I wanted to do when I was a kid (if I had been bigger, stronger and faster I'd be writing a flipped version of this on Toulouse's website right now...). In particular I have found teaching to perhaps be one of the most rewarding experiences one can have.

I'm sure there is a lot wrong with my analogy and a huge amount of differences between 'us' and pro athletes... Perhaps this comparison is just a young boys way of coping with his workload and believing that it's actually what he wants to do and that he made it as a 'pro athlete'... ;)