Wednesday, 9 November 2011

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:



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