Some analysis of the game shut the box

This Christmas, +Zoe Prytherch and I got my mother a small board game called: "Shut the Box" (also known as "Tric-Trac", "Canoga", "Klackers", "Zoltan Box", "Batten Down the Hatches", or "High Rollers" according to the wiki page). It's a neat little game with all sorts of underlying mathematics.

Here's a picture of us playing:

Here's a close up of the box:

A good description of the game can be found on the wiki page but basically the game can be described as follows:

• It is a Solitaire game that can be played in turns and scores compared (but no strategies arise due to interactions of players).
• The aim is to "shut" as many tiles (each being one of the digits from 1 to 9) as possible.
• On any given go, a player rolls two dice and/or has a choice of rolling one dice if the tiles 7,8,9 are "shut".
• The sum total of the dice roll indicates the sum total of tiles that must be "shut". If I roll 11, I could put down [2,9],[3,8],[1,2,8] etc...
• The game ends when a player can't "shut" tiles corresponding to the dice roll (including the case when all tiles are "shut").

Here's a plot of a game we played with a few of my mother's friends:

You can see that myself and Jean did fairly poorly while Zoë made the difference just at the end to win :)

The game could be modelled as a Markov decision process but over the past few days I decided to code it in Sage and investigate whether or not I could find out anything cool with regards to strategies. If you're not aware of Sage I thoroughly recommend you taking a look, it's an awesome open source mathematics package. In this instance I used the Partitions function to rapidly obtain various combinations of dice rolls and/or tile options to get the results I wanted.

The code is all in a github repo and I feel I've written an ok README file explaining how it works so if you're interested in playing with it please do! The code basically has two parts, the first allows you to play using the program instead of a game board (with prompts telling you what your available plays are).

Here's a quick screencast of me demonstrating some of the code:

The second part of the code allows for strategies to be written that play the game automatically ("autoplay"). I've considered 4 strateges:

• Random (Just randomly pick any potential tile combination)
• Shortest (Choose the tile combination that has shortest length: i.e. [3] instead of [1,2] ~ in case of a tie pick randomly)
• Longest (Choose the tile combination that has longest length: i.e. [1,2] instead of [3] ~ in case of a tie pick randomly)
• Greedy. This chooses the tile combination that ensures the best possible chance of the game not ending on the next go. This is calculated by summing the probabilities of obtaining a dice roll that could be obtained.

I've been leaving my computer run the code in the background for a while now so here are some early results. I've got over 90000 instances for Greedy and Random with over 40000 instances for the other two which I thought of later (EDIT: I know have over 400000 instances...). I've collected (as and when one of my home boxes was ideal) more data since writing this and the file is available for anyone to play with here. If I've made any mistakes with my analysis, I'd love to hear it!.

First of all what does the average score look like:

Greedy_Score   Random_Score     Longest_Score   Shortest_Score  
Min.   : 0.00  Min.   : 0.00    Min.   : 0.00   Min.   : 0.00  
1st Qu.: 6.00  1st Qu.:14.00    1st Qu.:18.00   1st Qu.: 7.00   
Median :11.00  Median :21.00    Median :24.00   Median :11.00
Mean   :11.42  Mean   :20.45    Mean   :24.16   Mean   :12.06  
3rd Qu.:16.00  3rd Qu.:27.00    3rd Qu.:30.00   3rd Qu.:17.00  
Max.   :43.00  Max.   :43.00    Max.   :43.00   Max.   :43.00  

Shortest and Greedy seem to do a fair bit better then the other two. If we take a look at the distribution of the scores that is confirmed:

If we also take a look at the length of the game (i.e. how many total dice rolls there were):

Greedy_Length  Random_Length  Longest_Length  Shortest_Length
Min.   :1.000  Min.   :1.000  Min.   :1.00    Min.   :1.00    
1st Qu.:4.000  1st Qu.:3.000  1st Qu.:2.00    1st Qu.:4.00    
Median :5.000  Median :3.000  Median :3.00    Median :5.00    
Mean   :4.897  Mean   :3.414  Mean   :2.86    Mean   :4.82    
3rd Qu.:6.000  3rd Qu.:4.000  3rd Qu.:4.00    3rd Qu.:6.00    
Max.   :9.000  Max.   :9.000  Max.   :8.00    Max.   :9.00    
                                                             

We see that games last longer when using Greedy and Shortest. If we look at the distribution we see (I've updated this graph since first publishing this post):

It looks like Greedy might allow for slightly longer games than Shortest. Whether or not playing Shortest or Greedy is actually any different seems interesting. A simple analysis of variance (ANOVA) seems to indicate that there is a significant effect:

Df  Sum Sq Mean Sq F value P

stbaov$Method      1   11337   11337   196.3 2e-16 

Residuals     127169 7345725      58

This is all experimental of course and analysing whether or not my suggested greedy strategy is indeed the optimal strategy would require some markov decision process modelling. I might look in to this with an undegraduate project student next year.

The tricky part about using the greedy method whilst actually playing the game with friends is that it requires a fair bit of calculation. Nothing that Sage can't handle in a split second but something that could keep people waiting a fair bit if you were to work it out with a pen and paper. Despite the significant statistical difference between the methods this analysis seems to indicate that choosing the shortest set of tiles is a pretty good strategy so if in doubt I recommend choosing that...

If anyone cares enough about all this to fork the code or suggest a different strategy I'd be delighted :) In case you missed it above, here's the github repo:

https://github.com/drvinceknight/Shut_The_Box

(On a technical note some of the pre analysis is done using python and the actual graphs seen here are done using R)

My experience of G+ as an academic

So Patrick Honner wrote a blog post about twitter for Math teachers. I thought I'd try and do something similar for G+.

DISCLAIMER: I don't know what I'm talking about. I'm in no way a social media expert and/or claim to have any better knowledge on this subject then anyone else. This post will most probably just turn in to a story about how I've used G+ over the past 18 months or so.

My General Philosophy

I've been on G+ for a while now and I'm a really big fan. I joined twitter and got an invite for G+ from an old pal about a month later. As I didn't have any attachement to twitter at that moment I didn't really have a reason to invest in it. I believe that G+ is by far the best designed social platform out there and I was an immediate fan. I thought I'd fully move over to G+ (once I figured out how to get all my photos off facebook I actually quit that). I wrote a blog post about this a while back.

My main rule from the start with G+ was (and pretty much still is apart from one exception that I'll get to in a bit): only post publicly about stuff linked to my "professional life" ~ so "science-y" stuff. I stick to this not because I don't want to share pictures of my holidays with the world but mainly because I think no one would care and I don't want to bore anyone. Having said that, I know a lot of people who share non "science-y" stuff publicly and I certainly enjoy reading it, for example Dana Ernst (a mathematician) often posts about his trail running activities which I always enjoy reading.

I know some people actually do the opposite and use circles to "direct" information. For example they have a math circle and post mathematical content to that circle. I personally don't feel that is the best way to do things as it stops people you haven't circled from finding your posts. 

I use circles for personal things (ie stuff I don't think the world cares about ~ with some friends we communicate via G+ instead of text messages as a bunch of us can follow a single conversation) and also to filter how I read information. For example I have a math circle, a programming circle and a news circle. During the day, depending on my mood I'll read from one of those circles.

That's the very basics of how I use G+ on a day to day basis. 

Some Anecdotes

I really enjoy G+ and have had some great interactions (by all means skip this section as it's just a couple of personal experiences):

- A recent conversation about the teaching of Game theory on one of John Baez's post is a great example of how G+ allows for sharing of knowledge and interaction. I "met" quite a few people on that post and got quite a few ideas for teaching.

- I've learnt a lot about R from Josh Wiley who even took a look at some teaching materials I was putting together. I'm not too sure how Josh and I met (ie on what post) but I guess it was following a series of conversations that I felt comfortable enough to ask him for a hand.

- I've had some students points out typos in my notes :)

- At the very beginning of my time on G+ I spent a while looking for mathematicians and Operational Researchers. One of the early people that I interacted with was Bo Jensen. Paul Harper and myself would chat for ages with Bo about how to use circles (I think we still don't agree :) ). We had a 1 year anniversary hangout:

All of the above are just some small examples of some cool interactions I've had on G+. One of the best things I've done that had some connection to G+ was when I posted about it during the long run my fiancée and I did (160 km over 5 days). This was from Cardiff to Gregynog (where a mathematics colloquium is held every year). This slightly broke with my above "rule" about just posting publicly about "science-y" stuff. Having said that it was a very special experience and I actually posted publicly about it the whole way using the hashtag (oh yeah they work on G+ as well): #jog2nog. On the second day I proposed to Zoe and it was kind of fun to share it.

How I do things

The main point for me about G+ is that you can make it as personal as you want. There is no "right way" to use G+. I've often discussed this on G+ when some people have stated that people "do things the wrong way". I think that's what's great about it, there is no right or wrong way to use it.

Having said that this is how I do things:

• Engage on other people's posts. I think that I enjoy discussions on other people's post far more than on mine. So I often spend time just reading through posts chatting and meeting new people.
• Engage with people on your posts. I'm always flattered when people take the time to post a comment on one of my posts so I always try to enter in to a conversation if there's scope for one. 
• Don't circle everybody. I love the asymmetry of G+. This allows for the possibility that some people might be interested in what I say whilst I might not care for what they say (and obviously vice versa - there are quite a few people I've circled who haven't circled me back and I'm certainly not offended by that). I do my best to take a look at people who engage with me and often circle people who post stuff that interests me.
• Tag wisely. There's a lot going on on G+ (people who call it a ghost town make me giggle but I'll get back to that). So it's tricky to see everything so I often tag people in to conversations if I feel that they might have something to add or might like to listen in. Similarly I always appreciate being tagged in to a conversation that I might be interested in.
• Link to G+ stuff on other sites. Photos are awesome on G+ and a public post can be seen by anyone (whether or not they're on G+) so I often grab the link to a post (by clicking on the date stamp) and share that (that's in fact the only way I currently use twitter).
• Have buffer circles. When large circles get shared I often add the whole circle but put it in a particular circle (eg "Science [to edit]" as opposed to my "Science" circle). I put the noise filter up quite high on that circle (see pic) and slowly move people I'm interested in over to my main "Science" circle.

• NEVER "Also send email to ...". You can post to a particular circle and choose to notify everyone in that circle (see pic). I only ever tag particular people if I want them to seethe post but I never spam an entire circle. I don't recommend doing it as it's an easy way to make people mad...

Find stuff

People who call G+ a ghost town are like people who walk in to a busy bar with their eyes closed, walk out and say that no one was in there. Search for stuff you like (for example "math" and/or "science") and just meet people. If you don't want to meet people then I guess G+ also works, just sit by yourself and don't speak to anybody (I don't think that would be that much fun though).

If you want science take a look at the following:

- Fraser Cain's handpicked  science circle.

- The Science on Google+ Public Database: a bunch of circles on science.

- A small circle of Operational Researchers who post publicly. I put that together while ago so I really should update it.

Something brand new has appeared on G+ in the last couple of days: Communities. I'm still unsure about them as I'm a bit worried that they're compartmentalising information but just search for a community and you'll find people in there to meet :)

Some final thoughts

The one word I always think about when describing G+ to people is "learn". I have learnt so much from G+ (cool programming things, teaching methodologies, general mathematics etc). I am very grateful.

I never really got going with twitter and so I'm sure I'm "not using it right" but I just don't see how it can offer the same level of engagement as G+ does. A while back someone tweeted "at" me (I'm not even sure if I'm saying it right) and I wanted to answer (they complemented me and I wanted to say thanks). After 10 seconds I gave up as I wasn't sure how to get it all down in 140 characters and also I didn't want to confuse my followers on twitter. So I simply went over to G+ and sent them a limited message (i.e. posting to just them). We ended up having a long conversation about G+ and twitter. I don't believe that that would have happened on twitter but again, perhaps I wasn't "using it right".

I've not really mentioned hangouts. They're awesome. Use them.

Importing and Exporting data from and to csv files in python

When I first started using Sage one of the challenges was figuring out how to handle data outside of Sage. I made the terrible mistake of trying to learn Sage without knowing any Python. I've subsequently learnt Python (a language I absolutely love) and thought I'd do a short screencast showing how to manipulate csv files with Python.

Here's the screencast:

I thought I'd put the code I wrote up here as well:

import csv

out=open("data.csv","rb")
data=csv.reader(out)
data=[[row[0],eval(row[1]),eval(row[2])] for row in data]
out.close()

new_data=[[row[0],row[1]+row[2]] for row in data]

out=open("new_data.csv","wb")
output=csv.writer(out)

for row in new_data:
    output.writerow(row)

out.close()

Here's a quick explanation (basically repeating what is in the screencast)

The first line imports the csv module:

import csv

The next few lines open a file for reading (denoted by "rb") and use the csv reader method to import the data (the "eval" function is used to handle the fact that all the data is imported as a string).

out=open("data.csv","rb")
data=csv.reader(out)
data=[[row[0],eval(row[1]),eval(row[2])] for row in data]
out.close()

The next line simply creates a new dataset:

new_data=[[row[0],row[1]+row[2]] for row in data]

We then open/create a file called "new_data" for writing (denoted by "wb") and use the csv writer method to export each row of data:

out=open("new_data.csv","wb")
output=csv.writer(out)

for row in new_data:
    output.writerow(row)

out.close()

Blog/YouTube Channel

I don't post to my blog very often yet I have started making a few more videos on my YouTube channel in one of three categories I guess:

- "Tech" (for want of a better name) how to's (or more exactly how I've figure out how to do stuff which might not be the best way...)
- "Education" (for want of a better name) stuff
- Research presentations

I've decided that I'll also throw those videos on here when I put them together (not too sure why, perhaps the best reason is "why not?"). To get started here are 3 past videos:

- Using GitHub to host a website:

- Simulating a Queue: Basic Discrete Event Simulation

- A game theoretical approach to the EMV ED interface

Playing games with MSc students

This is the fourth post in a series of posts  (see previous posts here, here and here).

I teach the first 4 weeks of the OR Methods module for our MSc in OR and Stats at Cardiff. One of the subjects I teach is game theory and this year I decided to introduce the subject through the use of the same games I've used in outreach events.

We had 31 participants. The first game we played was the 2/3rds of the average game. Here is the first set of guesses (before we discussed rationality and in essence solve the game together).

You can see that the guesses are pretty distributed across the range from 15 to 82. Three students did seem to notice that something was happening around 2/3rds of 100. The winning guess was 26, which is the highest winning first guess I've had so far.

After this we all went through the fact that 0 is the dominating strategy in this game (through iterated elimination of other all other strategies). Once this was rationalised we played again, here's the second set of guesses:

A few weird things happened, for example someone actually guessed 100 (there was no one guessing a 100 before). I suppose this shows some confusion or perhaps someone was just trying to tell me that they thought this was boring (despite the fact that I used a box of chocolats as a participation bribe... :) ). Otherwise the results are as one would expect and the guesses seem to be clustering a bit towards 0. The winning guess was 10 this time around (3 students had to share the chocolats) which is actually a tie for the highest winning second guess I've had so far.

Here's a quick summary of the 4 games I've played so far:

• School kids (13 participants) - First Guess: 17 Second Guess: 2
• Postgraduate students (80 participants) - First Guess: 18 Second Guess: 10
• OR 54 Delegates (10 participants) - First Guess: 23 Second Guess: 3
• MSc 2012 Cohort (31 participants) - First Guess: 26 Second Guess: 10

After this we put the guesses up for everyone to see and discussed what we expect to happen if we played again (and again). I thought this went well and I've had some of the students say they enjoyed it. I certainly enjoy teaching game theory as it's very "easy" to make come alive. After the 2/3rds of the average game we played a prisoner's dilemma tournament but I won't go in to that here. Here are a few photos showing the students discussing strategies and (hopefully) having fun.

Playing games at OR 54

The 54th conference of the Operational Research Society took place in Edinburgh from the 4th till the 6th of September.

Louise Orpin (Education officer of the OR society: http://learnaboutor.com/) was running a stream on education and thought that her and I could give the same talk we gave at SCOR (see previous blog post here) and I've given many times with Professor Paul Harper during high school outreach events (see previous blog post here). This talk is actually designed for school children. It aims to get kids to understand basic ideas of game theory by playing some games.

When asked to give this talk at SCOR I was worried that the audience (PhD students) would be a bit too "mature" for the talk and think it a bit of a waste of their time. The SCOR talk was a great success though and everyone had fun. When it came to giving the talk at OR54 I was also a bit worried as the audience was even more "mature". All these worries were unfounded as it seems that people just like to have fun and play games. It went well. Here are some of the results.

We did not have a huge audience (10) but still had enough to play the games.

The first game we played is the 2/3rds of the average game. Here's the first set of guesses (before discussing rational behaviour):

The guesses were relatively spread out, 2 groups of participants noted that 66 was 2/3 of 100 and also that 43 was 2/3 of 66 but no 1 guessed lower than 5. The winning guess was 23. After explaining the fact that 0 is a dominating strategy we had the participants play again. Here are the guesses second time around:

As you can see 0 was not uniformly picked but the maximum guess was this time 29 and 7 people guessed 3 or lower. The winning guess was this time: 3.

I've run this with 3 types of audiences now and the winning guess on each occasion were (links are to corresponding blog posts):

• School kids - First Guess: 17 Second Guess: 2
• Postgraduate students - First Guess: 18 Second Guess: 10
• OR 54 Delegates - First Guess: 23 Second Guess: 3

We had fun with this and discussed how such a game was a great way to get basic ideas of rationality and dominance across. 

We then proceeded to play a prisoner's dilemma tournament. We split in to 4 teams and the winning team would be the team with the least total score (I've blogged details about this before see here). It was good fun (always) and there was even a coalition that formed to stop the team, that had my undergraduate intern Jason Young, in it from winning. Here are some photos (thanks to Ian Mitchell for the first 2!) from that part of the day:

The cool venue:

Louise starting us out:

Louise and I with the "C" and "D"s used to cooperate or defect...

The scores (if you look carefully you should be able to notice the coalition - Jason chose the name for team D just to make me twitch...):

The above is just 1 example of an outreach event that works really well in schools (and also with more "mature" participants). If you do want more examples please do take a look at http://learnaboutor.com/. I'm writing this the day before teaching game theory to a new cohort of Cardiff MSc students, I'll be playing the same games with them so will probably post about it again at some point. 

(If you'd like more information on the Conference itself take a look at the #OR54 hashtag on G+).

GUEST POST: A Summer Research Internship

During the early part of 2012 I applied for some funds to carry out research on game theoretical behaviour in hierarchical queueing systems. I successfully obtained money from the LANCS initiative (http://www.lancs-initiative.ac.uk/) to hire an undergraduate student to do a 10 week internship. The original goal of the project was to build a simulation model that would be used to aid the research project.

After interviewing half a dozen students I appointed Jason Young. Jason was an absolute pleasure to work with and worked extremely hard. Consequently a lot more was done through this project, Jason and I stil laugh about the fact that originally the plan was "just build a simulation model". As soon as I find some time I'll be writing it up for publication. 

At the end of the project I asked Jason to write up a blog post describing the internship from his point of view. First of all, I thought this might be interesting and second of all, I'll encourage future students to read Jason's thoughts. Here it is:

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

Hello my name is Jason Young and I’ve been working this summer as a research intern. Over the summer I was tasked to build a simulation model of a queuing problem in python, and you can see the results of the project at the end of this post. 

It’s been an interesting experience, and an invaluable insight into the world of mathematical research, and into a working environment. To anyone thinking about or preparing for an internship, this will be the most valuable thing that you take away from the position. It’s a great opportunity to learn and build contacts in your chosen profession, especially if you do well. This is a crucial moment in any undergrads career, and a lot of future employers will look at your experience as a guide to how active you’ve been during your degree, and summer internships are a great way of gaining experience without taking a full year out.

When I first started this project, my attitude was very much that I needed to succeed. My supervisor used to say “Impress or Disappoint”, which is an accurate statement of how the project will go. If you don’t put 100% in, and do an okay job, it’ll make you forgettable  overall. The only way to make a lasting impression is to put as much effort in as possible. It helps in this respect to enjoy your project.

In the week leading up to the internship I did some prep work, learning the basics of python, which was pretty valuable toward the start of the placement. This is also the point where I began to enjoy the challenge of research. As an undergrad with little to no knowledge of how research was carried out, I was quite apprehensive of the whole thing. Once I got started however, I saw that It was something I was very much going to enjoy. The main idea behind research is why. After finishing the model, we began to investigate the problem and I don’t think there was a single occasion that there was a result that we didn’t understand, mainly because after each conclusion had been reached we thought about it. I think if you’re on the fence about a research career this is what you should consider. Personally this is the part I enjoyed most, gaining insights into this mathematical problem, and testing the theory from every angle.

After getting through a significant part of the project, I was told that I’d be able to present my work at a conference. This was a huge honour (I wasn’t told till after, but I was the only undergraduate there) but easily the scariest part of the project. People who researched for years and years would be sitting and watching me talk about my research, which had all of 9 weeks behind it. As you can imagine the weeks leading up to it were a rather stressful affair. I spent an entire week getting the presentation ready, to me and my supervisor’s satisfaction and practicing it in front of some post grad students, who were very kind to stay late and watch, giving some really good feedback. After all this preparation, I was still quite nervous about the whole affair, but once we got to the conference itself, I relaxed quite a bit. Most of the people there were entirely there to learn and question, and didn’t mind me joining in any discussion about research interests. This and the fact that the presentation went really well (One of the questions asked gave us an entirely new train of thought) made it a great experience.

At times it’s been stressful, especially when the work piled up, but with enough persistence there was always enough time and my supervisor was extremely helpful and really pushed me to do the best I could. Overall I’ve loved the work that I’ve done this summer, and really proud of the result.

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

The various outputs of the project can be found here:

• With a few weeks to go Jason did a short screen cast showing the negative effect selfish behaviour can have in queueing systems:

• Jason presented his work at OR54 (the annual meeting of the UK Operational Research society). Here's a screencast of the talk he gave (the sound quality is terrible but there's a blooper at the end):

• The above slides can be found here.
• A version of the program used can be found here (I'm still hoping that Jason and/or I will find time to clean this up a bit).
• Here are a few pics from the project:

Jason had a bunch of computers in a lab running code. This one was Guinevere.

Arthur.

Excalibur. 

Lancelot.

Gaius.

Morgana.

Practicing the talk on the flight to Edinburgh.

This is where we screencast the talk.

Here's a picture of Jason presenting at OR54.

Road cycling and an explanation for cooperation.

I'm a huge Tour de France fan. I would probably follow more road cycling if I could but I just concentrate on the Tour de France which turns up once a year. First of all it is a ridiculous feat of endurance. Secondly (and this holds for road cycling in general) there's so much game theory involved.

The biggest element of this is the effect wind resistance has on cyclists. I heard Chris Boardman commenting on some cycling recently that 80% of a cyclists effort is expended on moving air. There's obviously a lot of research that goes in to this and I found an interesting paper on the subject when planning on writing this blog:

The complex dynamics of bicycle pelotons: http://arxiv.org/pdf/1206.0816v1.pdf

In general road races have many more than just two cyclists but I'm only going to talk about two cyclists for now. This is for two reasons:

1. Firstly this occurs fairly often. At some points in road races groups of cyclists "breakaway" from the main field and have to work together to stay away. 
2. Secondly: the math is nicer with 2 "players".

Let's assume that two cyclists have broken away. Available to each cyclist is two strategies: {Lead, Follow}.  We make the following assumption:

• If both cyclists Lead then it is assumed that they basically work alone (they both suffer the effects of air drag but make the speed of the slowest cyclist). 
• If both cyclist Follow then it is assumed that they don't work at all and are caught by the peleton (their escape is basically over). 
• If one cyclist Leads and the other Follows then they go at the speed of the Leader and the Leader fatigues.

We'll now write out some utilities that correspond to the above assumptions. 

• Let  $v_1,\; v_2$ be the speed for each cyclist. 
• Let $f_1,\;f_2$ be the fatigue felt by each cyclist when suffering the effects of air drag.

We assume the following utilities:

• If both cyclists Lead then cyclist $i$ receives utility:

$$\min(v_1,v_2)-f_i$$

• If both cyclists Follow then they both receive utility:

$$0$$

• If one cyclist Leads and the other Follows then the Leader (w.l.o.g. let it be cyclist $1$) receives utility:

$$v_1-f_i$$

and the Follower receives:

$$v_1$$

This can all be represented in the following bi-matrix:

$$\begin{pmatrix}(\min(v_1,v_2)-f_1,\min(v_1,v_2)-f_2)&(v_1-f_1,v_1)\\(v_2,v_2-f_2)&(0,0)\end{pmatrix}$$


If we assume for now that $v_1=v_2=2$ and $f_1=f_2=1$ (we'll not get our hands messy with units) than our bi-matrix becomes:

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

Let $p$ be the probability with which cyclist 1 Leads and $q$ be the probability with which cyclist 2 Leads. It can be shown (using basic game theory and/or using this Sage interact (http://interact.sagemath.org/node/49)) that there are 3 equilibria for this game:

• $(p,q)=(1,0)$ (Cyclist 1 always Leads)
• $(p,q)=(0,1)$ (Cyclist 2 always Leads)
• $(p,q))=(.5,.5)$ (Both cyclists Lead)

Using 1 of the pure strategies ($(1,0)$ or $(0,1)$) the utility to the Leader is 1 and the utility to the Follower is 2. Using the mixed strategy the expected utility to both cyclists is 1. Let us assume for the rest of this that cyclists use mixed strategies (i.e. neither takes advantage of the other).

In reality cyclists that break away cooperate, they talk and share the load as if they were a team. The mixed strategy above does not correspond to cooperation. It corresponds to a random strategy during which the cyclists will be randomly Leading and Following. Cooperation would be that both cyclists equally share the load (in a coordinated manner), the expected utility to both would then be 1.5 (both cyclists are better off if they cooperate - this is a notion quite close to my research, some screencasts of my talks are available here).

We'll continue to consider the situation in terms of a non-cooperative game as it gives an insight as to why cyclists cooperate.

We now assume that the cyclists are different. Perhaps they have escaped on a mountain stage and one of them is a better mountain rider. Let's take a look at the probabilities of Leading in a mixed strategy equilibria for varying $v_1$ (i.e. how fast the 1st cyclist is):

Basic game theoretical arguments give:

$$p=\begin{cases}1/2,&\text{ if }v_1\leq 2\\1/v_1,&\text{otherwise}\end{cases}$$

and

$$q=\begin{cases}1/2,&\text{ if }v_1\leq 2\\1-1/v_1,&\text{otherwise}\end{cases}$$

We see that as soon as $v_1$ is larger than $v_2=2$ the first cyclist has less of an incentive to lead. He/she basically "brings more" to the 2 cyclists and so the second cyclist must make more of an effort. 

This further emphasises the need for cyclists to work together when they breakaway.  

In reality cyclists would cooperate and the cyclist capable of helping the group stay away would perhaps work more.

A good example of a breakaway was the 2012 Olympic men's road race. The British team has one of the best sprinters of all time: Mark Cavendish. In road cycling, a sprinter is someone who is very good at going very fast over a shirt distance. Mark Cavendish is so good (he has recently been voted the best ever Tour de France sprinter) that no other team wants to be in a bunch finish with him: they'd lose. During this years race, the other teams all tried to put riders in breakaways. Normally other teams left in the peleton would at some point cooperate to accelerate the pace and bring the breakaway back in. In this particular occurrence no other team was good enough to beat Cavendish in a sprint and so no other team wanted to help (i.e. share time riding at the front) team GB. This is a slight over simplification as the Germans have a good sprinter who could have perhaps had a chance but it's not far off the truth. From a game theoretical point of view this make a lot of sense and in essence is exactly what happened. 3 riders formed a final breakaway and they contested the finish (Alexander Vinokourov won gold).

There's so much game theory in road cycling it really is a great sport to watch.

I've written a similar post applying game theory to rugby. For other recent blog posts with an Olympic flavour take a look at Paul Rubin's blog and Laura McLay's blog.

Using Google Docs for a sizeable Mathematics project

This past year I ran a final year project on the subject of the board game Risk (I'll blog about the actual results from the work another time). The main output of an undergraduate project at the school of mathematics at Cardiff university is a report. In my experience these reports can be anything from 70 to 130 pages long.

I've alway been a huge fan of Google docs/drive. If I need to write a letter, write an abstract or anything else gdocs is pretty much my first port of call. If I ever need to write something with someone else then gdocs is again my first port of call (the capacity to have multiple people edit at the same time makes it amazing). Having said all that, my favorite way to write documents (in particular long ones and especially mathematical ones) is to use LaTeX. (I'm not mentioning MS-word which is pretty much ranked last in my list of preferred document editing software - just after 'crayons and pad of paper' and just before 'a rock')

This year I decided to see how Google docs would handle a 'big' mathematical document. I've used google docs for some teaching notes but never anything with a large amount of mathematics.

The student worked very hard and being able to see his project report as he was writing it was very helpful (it was a great way to give him feedback without worrying about which version I'd read).

However there are two major downsides:

1. Limited mathematical notation:

Here's a quick screen shot of the mathematical editor available in google docs:

You can use a basic point and click approach to insert mathematics but it supposedly also renders LaTeX.

As you can see it renders some math (like $x^2+1$) but it won't render relatively simple stuff (like $\mathbb{R}$). It is not capable of writing matrices! My student ended up using this website to LaTeX his equations and input them in to his document as png:

2. Poor rendering of mathematics when printing:

The biggest downside however is that the mathematics written using the in built editor is just not good enough. Here's a picture of the pdf that is rendered from the google doc (the other versions that can be downloaded look just as bad):

As you can see, this just looks terrible...

My summary.

I'm afraid that unless google drastically improves their math editing capabilities I simply would not recommend gdocs for mathematical documents (and I'll continue to use gdocs whenever I know that I don't need any math...). It's a shame because it should be perfectly doable to use mathjax for example and/or replecate something similar to other websites that make use of html5 such as writelatex.

Playing games at SCOR 2012.

The 3rd Student Conference on Operational Research (SCOR 2012) took place in Nottingham in the UK from the 20th to the 22nd of April. (Photos available on the chair of the organising committee's G+ profile).

Louise Orpin (Education officer of the OR society: http://learnaboutor.com/) and I were invited to give a plenary on the last day on the subject of outreach events. The slides we delivered are available here. The talk was in two parts, in the first part I discussed a game theory outreach event (that I have already blogged about here) and in the second part Louise discussed how members of the audience could get involved.

One of the "highlights" (for me anyway) was getting all the students to play the "2/3rds of the average game". We played it twice: once without discussing the rational behaviour and a second time afterwards. 

I got all the audience (about 80) to write down their answers and hand them down to some of our Cardiff University postgraduates who had agreed to fill in a gdoc spreadsheet with the results so that by the end of my talk I could show the results (and announce the winner!).

The first graph (i.e. before we all discussed rational behaviour) shows the distribution of guesses:

Interestingly the lowest guess was actually 5 but also you can see that all the guesses were relatively uniform... The winning guess was 18.

The second chart shows the results after we all discussed the rational behaviour (i.e. that all strategies other then 0 are in fact dominated).

Straight away we see the overall strategies are beginning to "converge" (the maximum guess was 40 this time as opposed to 63). The winning guess was 10 (a 4 way tie).

None of this is surprising but I thought it was interesting to see that we do indeed get similar behaviour to the behaviour discuss in this previous blog post where this game was played with high school kids as opposed to PhD students.

I've been more or less (as and when time allows) taking the game theory course offered by coursera and I know that they are collecting similar data. They have obviously got a ridiculously large sample set in comparison to mine so I like forward to seeing the same graphs...

EDIT: Marc Harper on G+ pointed me to one of his papers that "somewhat captures the result of your experiment that even knowing that a guess of anything other than 0 is dominated, 0 is not the winning guess." Here's the link: http://arxiv.org/pdf/1005.1311.pdf

Csv to LaTeX

There's a great website that I've used many times to convert csv to \LaTeX available here. I decided to try and code my own such program in python. I posted about it on G+.

Here's a screen shot of a csv file (running on a Mac):

Here's my little program called "csv2latex" that outputs the LaTeX code to the terminal screen and creates a txt file with the code as well.

 With a close up of the output code and the output txt file:

                     

The python file is here if anyone would like (to improve?) it.

Playing games during an outreach event...

On the 25th of January Professor Paul Harper and I took part in the Monmouth Science Initiative by delivering an outreach event for a group of 13 16~17 year olds. Paul gave a very neat introduction to epidemiology using a role playing game (6d's included!).

I tried to introduce the kids to game theory using these slides. We only got as far as the prisoner's dilemma tournament and here's an account of the day.

First of all we started with a "Guess 2/3 of the average" game. We played twice, once with no prior reasoning (just a clear explanation of the rules). Here's a chart of the guesses:

Overall the distribution of guesses is pretty uniform (as is to be expected, right now the students are basically guessing). The average guess was 26 and 2/3rds of the average was 17. Two students happened to win this first round (the two students who actually guessed 17). 

Immediately after playing this round I gave an explanation of the fact that all strategies (guesses) other than 0 are dominated (by iteratively eliminating all guesses that are greater than 2/3 of the maximum guess): 

Once this had been explained we get the students to play again, here are the results:

We no longer have a uniform distribution of the guesses and the students are indeed getting it (mostly...). The average guess was now 4 which gives a 2/3 average of 2: so we had a single winner (the student who guessed 2). This was good fun and led to a short discussion of how people are not always rational (as shown by the guess of 14 and 25 in particular).

After this, we went on to look at some videos depicting Prisoner's Dilemmas (these videos are both on the slides link to above): 

Going on to explain the logic behind an actual prisoner's dilemma, we proceed to have an Iterated Prisoner's Dilemma tournament:

• Round robin with 4 teams
• Every "duel" was 8 rounds of the Prisoner's Dilemma
• The team with the total lowest score ("years in prison") won the tournament

The first duel (between team "C" and team "D") wasn't that great as the two teams mainly wanted to Defect:

Just at the end of this duel however there was a glimmer of hope! The teams started talking to each other (throughout we were trying to encourage them to talk) and indeed "promised" to both cooperate and of course both defected...

Here's a photo of the scores of this duel (you can see that at the 4th round team "D" tried to cooperate):

The next few duels (which included team "X" and team "Korea") got a bit more interesting and the teams starting talking to each other, here's the scores:

This next video however is great, both these teams had had a long chat before this duel. As you see team "Korea" defecting before team "D" were expecting them too (at 1:00). and putting themselves in pole position to win the tournament (they did the same trick in the next duel against team "C"):

Going in to the last duel the scores were:

•  team "Korea" had 72 points
•  team "C" had 82 points
•  team "X" had 53 points (with one more duel to play)
•  team "D" had 58 points (with one more duel to play)

BUT this is where things got interesting...

Up until here I think the ideas of dominated strategies and equilibria were fairly clear, and I think Paul and I were happy with that. The students however were not and it got slightly personal (all in good humour of course) and the guys in team "X" did not want the leader of team "Korea" to win, so they formed a coalition (a very particular and complex idea in game theory) with team "D" to ensure that team "Korea" did not win. Here's the video of this (at 0:16 the leader of team "Korea" realises what's going on and shouts "I'll buy you a kitkat if one of you starts playing 'D'"):

Here's the final 3 duels of the tournament (including the great play of team "Korea" and the coalition formed at the end between team "D" and team "X"):

The final scores where:

•  team "Korea" had 72 points
•  team "C" had 82 points
•  team "X" had 83 points
•  team "D" had 68 points

All in all Paul and I had great fun and the feedback from the kids was great. I think this is a great way of getting some fundamental ideas of game theory across. To shorten the amount of time it takes, we might end up using duels of 4 or 5 rounds instead of 8 but overall we won't change much, in particular having 4 teams works great as it allows time for the non playing teams to try and communicate.