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

Installing Sage

My girlfriend and I have recently bought a new computer which has resulted in our old mac moving up to my home office.

A student of mine has supposedly had a few problems installing sage on his mac so this blog post is going to be a full and detailed description of me attempting to install it myself from scratch including all the mistakes I make along the way.

For those of you who are unfamiliar with sage it is an open source math package built on python. I've discovered it over the past 6 months or so and can't speak highly enough of it. It's a brilliant open-source alternative to Maple, Mathematica, Matlab etc...

For info I have a modest understanding of computing. I run ubuntu on my box at work (and have installed sage without a problem there) but in no way consider myself a computer expert... So hopefully this post will be an "idiot's walkthrough" of the installation process (or failure there of).

10:13 am

Here's a screen shot of my computer's system:

10:15 am

First things first I navigate to www.sagemath.org:

Then I head to the download mirror (I chose the UK server):

and choose intel (as my mac is old but not very old):

10:21 am

Now for my first choice. This is perhaps where I show my ignorance a bit. Based on my comfort with the command line I don't think I need to download the *app.dmg package but as I'm hoping to send my student towards this blog post I'll try it anyway. The problem I do have though is that I'm not sure which package to download.  I found this page to help me figure out what bit system I'm running (32 or 64):

Following the instructions gives this result:

Based on the instructions (the last part of the output reads "i386" as opposed to "x86_64") I'm running a 32 bit system (as I thought given that this is an old mac). There are still a few choices that remain however, including what version of the OS I should be pointing at:

Focusing on the 32 bit installs there's still some confusion over the 10.x. I supposedly have a 10.6.8 version of Mac OS X but the only 10.6 install is a 64 bit. I'm deciding to try the 10.5 32 bit install:

10:31 am 

Here goes the download! :)

In the mean time I'm going to run my dmg for inkscape (another great piece of open source software).

10:46 am 

The download is complete (I expect it took longer than usual as we're running a huge back up of our new computer so that's taking up a bit of the router's effort...).

I'm now double clicking on the dmg file:

(I'm realising that I've perhaps chosen the wrong install package as this is sage 4.7 and not the newer release 4.7.2 but let's see what happens)

10:53 am 

This just popped up:

I'm clicking on the README file to see what's next. It seams pretty straightforward:

[Update: my first mistake this is actually the readme file for the .dmg install if you're using the *.app.dmg install then you should scroll down the readme file where there are instructions for that. This is all clear in the readme, I just didn't read the whole thing. Note that the install still works if you follow what I did as the instructions from the readme are basically the same.]

10:55 am 

I'm dragging the sage icon in to the applications folder now:

11:00 am

(sorry for the irrelevant picture but I'm bored)

11:01 am

The copy is done and so now according to the above instructions I'm double clicking on the sage icon. This (which is standard) pops up:

I click on "Open".

11:05 am:

After a bit of a wait (this is an old box), all sorts of things happen:

• Firstly a neat little sage icon popped up:

• Then the sage icon turned up in my dock:

•  Finally a browser window appeared: 

The above is basically telling me to wait, which I do and then a terminal window opens with the first run of sage:

This is now pretty familiar as it's exactly what happens everytime I've installed sage on a linux box. I type in a password and press enter (this password setup only happens the first time):

After retyping my password I press enter and then the next bit of code is basically sage starting a GUI ("notebook") session which looks like this:

It's all working :) :

Bizarrely it seems that I have to launch a notebook GUI no matter what I do and then open up a terminal session but perhaps this is due to me picking the *app.dmg package (I seem to have missed step 3 of the readme file). Note that this comment is irrelevant if all you're interested in is using the GUI. I'm now going to uninstall this and see what installing one of the *.dmg packages does (I won't document that process...).

This all seemed very straightforward to me so I'm not too sure what my student's problem was but hopefully this little write up will help him (and perhaps others). 

The cooperation game underlying social networks

I have recently been a lot more active on social networks. First I joined twitter (@drvinceknight), then I got a G+ invite and subsequently closed my Facebook account down and now I'm writing my first blog post!

The actual point of this post is to discuss the game that we're all playing with these social networks. Namely we're all playing a coordination game.

The most commonly taught coordination game is the battle of the sexes. Consider the following scenario: a couple are going on a date. They have to decide where to go:

- Alice would rather go to the movies.
- Bob would rather go to see a rugby match.

It is assumed that both Alice and Bob would rather attend the same event. This game can be represented with the following bi-matrix:

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

We see that if they both choose to go to the rugby match then Alice receives a utility of 1 and bob a utility of 2 etc... It can be shown that there are 3 equilibria to this game:

- Alice and Bob go to the rugby
- Alice and Bob go to a movie
- Alive goes to the rugby with probability $1/3$ and a movie with probability $2/3$, while Bob goes to the rugby with probability $2/3$ and a movie with probability $1/3$.

How does this relate to social networks? Well let's say that Alice and Bob where no longer choosing what to do on their date but where in fact choosing social networks. Bob prefers G+ whilst Alice prefers Facebook. Obviously they both want to be on the same network as there's no point in being on a social network alone (this assume that the only people in our little world are Alice and Bob). Under these assumptions the same previous equilibria apply.

This game can be extended/modified to $n$ players and let us assume that the utility to any player is give by the following function:

$$u_i(s_i)={\sqrt{|\{1\leq j\leq n\;|s_i=s_j\}|}\over n}$$

I.e. the utility to players choosing G+ is the (somewhat) normalised square root of the number of people choosing G+ (and similarly for Facebook). Why choose a concave function? This simply allows us to say that the difference between having 2 and 3 people on the network is a lot bigger (in terms of utility) than the difference between having 2000 and 2001. If we assume that prior to G+ everyone was on Facebook then when G+ appeared the game was already at an equilibria. This implies that our utility function is somewhat lacking (since some people did indeed move over to G+). Thus we modify it to include a term $\beta_i(s)$ meant to represent a personal preference.

$$u_i(s_i)={\sqrt{|\{1\leq j\leq n\;|s_i=s_j\}|} + \beta_i(s_i)\over n}$$

This utility function justifies that some people (like myself) were happy enough to move from the one equilibria (everyone on Facebook) to a potential unstable strategy (G+). Indeed for me the privacy settings (which I am to understand are now available on Facebook), hangout facilities and overall clean user interface was enough to lure me away from Facebook even though there was not a large amount of people on G+ to start. The assumed utility function looks somewhat like this:

Let us consider an example with 5 people. Each with the following preferences:

• Alice - $\beta_A(G+)=2$ and $\beta_A(FB)=4$
• Bob - $\beta_B(G+)=2$ and $\beta_B(FB)=4$
• Charles - $\beta_B(G+)=2$ and $\beta_B(FB)=4$
• Danielle - $\beta_D(G+)=6$ and $\beta_D(FB)=1$
• Erin - $\beta_E(G+)=6$ and $\beta_E(FB)=1$

If everyone choose $FB$ then the utility gained by Alice, Bob and Charles is ${\sqrt{5}+4\over 5}\approx 1.25$ whereas the utility to Danielle and Erin is ${\sqrt{5}+1\over 5}\approx .65$. It's pretty easy to see that Danielle and Erin can both improve their utility by deviating from $FB$. Indeed if first Danielle chooses the strategy $G+$ then Alice, Bob and Charles gain a utility of ${\sqrt{4}+4\over 5}=1.2$, Danielle gains a utility of ${\sqrt{1}+6\over 5}=1.4$ and Erin gains a utility of ${\sqrt{4}+1\over 5}=.6$.

If Erin then deviates as well we see that we arrive at a new equilibrium:

• Alice, Bob, Charles choose $FB$ each gaining a utility of  ${\sqrt{3}+5\over 5}\approx 1.35$
• Danielle, Erin choose $G+$ each gaining a utility of ${\sqrt{2}+6\over5}\approx 1.48$

This is an equilibrium as it is in no player's interest to deviate from their strategy.

A very important assumption that I've made so far is that every individual can only choose to use a particular network. In fact I know that a lot of people have ended up using both. For example I know that my girlfriend uses G+ to blog about her research and uses Facebook to keep in touch with friends and family. A game theoretical interpretation of this is simply that they're playing mixed strategies.

This game and concept is very similar to most of my research but it is in fact fundamentally different. In the games I model, players don't like congestion...

If I had the time I would perhaps actually do some work on this, developing a more realistic game and various algorithms to solve it as well as using evolutionary game theory. I am currently reading and really think every researcher should read:

Reinventing Discovery by Michael Nielson

The book (and above talk) is all about open research and encourages researchers to invite other researchers to start open research projects. On that note and given the subject of this post (social networking) I am very humbly suggesting that if there are any Game Theorists, Applied Graph Theorists etc... who might be interested in working on an open research project on the above subject (collaboration games applied to online social networks) then please leave a comment on this currently empty googledoc.

For now I'm giving commenting rights to the world but if anyone would like to contribute then please let me know and I'll give you editing rights. I don't expect to be able to give too much time to this project as it is currently just a small idea (pretty much summed up in this blog post) and I have various other research projects that I'm not really brave enough just yet to make open research projects but who knows what will happen if there is indeed a little bit of interest...