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