Season 11 Episode 2

What happens if you play the same game against the same opponent again and again... for ever? Current student Eddie is on OOMC to break down the probabilities.

Watch on YouTube

Further Reading

The Prisoner's Dilemma

Prof. Robert Axelrod's 1984 book The Evolution of Cooperation sets out lots of the theory for problems like this. There's a lengthy summary on Wikipedia, or if you prefer a video, Veritasium’s video on the prisoner’s dilemma includes clips from Robert Axelrod himself. YouTube | Veritasium | This game theory problem will change the way you see the world

Everyone should try Nicky Case’s interactive web game called Evolution of Trust which is built on this theory (thank you to the anonymous person in Slido who mentioned it!)

Randomness in decision-making

Let's think a bit more about why a random strategy might be better than a deterministic strategy. Here’s another coordination game. There are two players walking down a corridor, and each selects “Left” or “Right” for whether they’re going to walk on the left or the right (as viewed by us, watching this happen down from a safe distance down the corridor). If they pick different sides from each other then they each win 1 point, but if they pick the same side then they both get 0 points... and bump into each other.

In this game, we might imagine some players decide to always pick “Left” and some other players always decide to pick “Right”. They’ll have a terrible time when they meet other people in the same group, so if we're imagining some sort of evolution then perhaps the number of people in each group will balance out. Nothing interesting yet!

But it gets interesting if people play repeatedly against the same opponent, and we let them base their decision on the outcome of their previous game. So now if they both choose left and bump into each other, they will remember that, and when they play again, they could switch.

A deterministic strategy does not work well here, because if their policy is always to switch sides when they bump into someone, and (oh no) if that’s also the other player’s strategy... then both of them will shift from left to right in lockstep, blocking each other forever.

Here's where randomness helps! If everyone's policy after bumping into someone is to change to the other side with probability \(p\), then we might see one of them swap sides and (crucially) the other one not switch sides. That has probability \(2p(1-p)\) if they’re both using this random strategy, and this probability is maximised with \(p=\frac{1}{2}\). So not 0 and not 1. You need a bit of randomness.

Even better, this random-if-we-collided policy works against the “always choose left” players; maybe they bump into each other once or twice, but there’s some probability that the slightly-random player will switch to the other side, getting out of the way of the stubborn “always choose left” player.

For a sillier example of the importance of randomness, imagine turning up to a rock-paper-scissors tournament wearing a T-shirt that says “I always pick rock”.

Share afterwards?

Someone in chat pointed out that, for the game in the episode, if the players agree to share the points afterwards, then they will immediately both cooperate, because 3+3 is more than 5+0. I would now like to recommend this related YouTube clip of someone trying this on a British TV show called Golden Balls. YouTube | spinout3 | golden balls. the weirdest split or steal ever!

Exercises for after you’ve watched the video;

• Given that Nick wants to split the money, why does he keep refusing to commit to choosing the split ball?
• Why does the host keep telling them that the only way to guarantee a split is to select split?

Nash equilibrium

If you’d like to read something, I'll link to Wikipedia again, but this gets very involved very quickly.

If you’d like to watch something, I like this video from Ashley Hodgson (Associate Professor of Economics at St. Olaf Collge in Minnesota); YouTube | Ashley Hodgson | Nash Equilibrium in 5 Minutes (and then if you’d like to see a follow-up video with randomness in the decisions,  YouTube | Ashley Hodgson | Mixed Strategies Nash Equilibrium: Intuition).

Markov chains

Here’s an NRICH activity that gets you to analyse some Markov chains.

This means that given a matrix \(X\), we might be really interested in the behaviour of \(X^n\) for large \(n\), or maybe more precisely we might be interested in the direction that \(X^n v \) points, where \(v\) is some starting vector.

Generally (but not always), what happens for large \(n\) is that the vector tends to point in a predictable direction (given by the eigenvector corresponding to the eigenvalue with the largest real part, if that means anything to you). This is usually one of the main results of a university course or series of courses on matrices and/or Markov chains, and it’s why we can say anything about the long-term behaviour of a system like this.

Three things to check out

UNIQ is a summer school for UK students. Part of the content is matrices and Markov chains.

PROMYS Europe is a summer school for UK / EU / Europe students. There's also the original PROMYS based in Boston and a recently-launched PROMYS Italia. There's a problem set of eight questions that you might like to have a look at, even if you're not going to apply for PROMYS 

We have a mailing list which you can sign up to find out about other Oxford Mathematics outreach events and opportunities.