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.

To box kick or not to box kick

On 3/11/2011 Wales played Australia in a rugby test at the Millennium Stadium in Cardiff. I watched the game at home on TV and it was thoroughly enjoyable. My only problem was with one member of the commentary team who to put it diplomatically 'isn't the most knowledgeable'.

At one point he exclaimed: 'teams should always box kick to clear their lines'. Before I use game theory to show that the commentator is here completely wrong let me give some background to rugby. Rugby is a 15 player game where each position on the field has a specific role to play. Whilst the skill sets of each player is in no way as specific as American football (and this is where my comparison of rugby to football starts and ends) it's generally accepted that there are two players on the team who do the kicking: the scrum half and the outside half.

There are various reasons for a team to need to kick the ball, one of the main ones and the one alluded to by the commentator is to relieve pressure when close to your own score line. In this case one of the two mentioned players will (usually) kick whilst some defenders try to block the kick.

Here's a video just on the subject of kicks in rugby :)

Let us simplify the above situation by assuming that a team close to their own score line with the ball (which we'll refer to from now on as the "kicking team") has two strategies available to it: "Box kick" (where the scrum half kicks the ball):

or "Clearance Kick" (where the scrum half passes to the outside half who kicks the ball):

As soon as the scrum half touches the ball the defenders can rush past the offside line to try and block the kick. We assume that the defenders will either anticipate a box kick (rushing the scrum half) or anticipate a clearance kick (rushing the fly half)

I haven't really been able to find any data as to the success of these things so I'll go with my own experience (I'm a scrum half but have played a bit of outside half as well). My success rate at box kicks when they're not anticipated is probably 80% however when teams anticipate a box kick I reckon my success rate probably drops to 20%. To clarify by success rate, I simply mean rate at which the kick successfully relieves pressure.

When an outside half does the kicking I reckon the success rate is probably about 95% when not anticipated and perhaps 70% when it is anticipated.

Assuming this is all a zero sum game this gives the following bi-matrix:

$$\begin{pmatrix}(20,-20)&(80,-80)\\(95,-95)&(70,-70)\end{pmatrix}$$

If the kicking team indeed follows that commentator's advice and always box kicks then the expected utility to the other team as a function of $0\leq q\leq1$ (the frequency with which they anticipate a box kick) is given by:

$$-20q-80(1-q)=60q-80$$

the plot of which is given below:

It's immediate to see that the best response is to choose $q=1$, i.e. to always anticipate a box kick. This gives the kicking team a success rate of clearing their lines of 20%. Can this be improved? 

Well here's a plot of the utility to the kicking team as a function of $p$ and $q$: 

$$u_1(p,q)=-85  p q + 10 p + 25 q + 70$$

So a success rate of 20% is in fact the worst possible utility for the kicking team. As soon as the kicking team deviates from a strategy of always box kicking then their utility will increase (assuming a best response by the defensive team or not).

Using some simple sage code (available here) to compute the Nash equilibria we can equate the equilibrium strategies to be:

$p={5\over17}$ and $q={2\over17}$

At this strategy pairing (where we only box kick 29% of the time) we see that the utility to the kicking team is: 73%. These numbers are to be taken with an obvious amount of caution (remember my original assumptions where based on my personal success rates) but the main message still holds: you should mix your strategies.

If we modify the game slightly taking $r\in[0,100]$ to be the utility gained for an anticipated box kick:

$$\begin{pmatrix}(r,-r)&(80,-80)\\(95,-95)&(70,-70)\end{pmatrix}$$

The following graph plots the equilibrium values for $p$ and $q$ for varying values of $r$:

We see straight away (remember that 80% is the success rate of a box kick against a defense that anticipates a clearance kick) that as long as box-kicking is sometimes the worse option then both teams should mix up their strategies.

These ideas apply to more or less all sports, in American Football you should have a healthy mix of running and passing plays (even if you're a better running team), in tennis you should serve both wide and narrow (even if your wide serve is your stronger serve), in soccer you should take penalty kicks left and right etc...