Sunday, 23 March 2014

Basketball and cooperative games in class

Here is the state of my class after my students learnt about cooperative game theory (Chapter 16 of my course):


Cooperative game theory is concerned with situations where coalitions are allowed to form in game theoretic situations. In my class the particular aspect we consider is the Shapley value which is of interest when sharing a particular commodity amongst a group of player who each contribute to the commodity differently.

I use this in practice when dealing with attributing individual marks to a group project: you can read about that here.

To introduce this I asked 3 students to come down and play a game: $S$, $L$ and $C$ volunteered (or at least gave a lazy nod when I asked if anyone had played basketball before) to come down.

They had 20 seconds to get as many crumpled up pieces of paper as possible in the bin above (it was on the table). The paper was stapled and it needed to be separated and crumpled so I suggested that perhaps 1 or 2 of them could spend some of the 20 seconds separating and crumpling.

We played this 3 times and it was all good fun. After $S$, $L$ and $C$ had their go 3 other students thought they could do better (no comment).

After that I asked the class how we could share out the 10 chocolates between $S$, $L$ and $C$: what would be the fair way? After some discussion it was clear that L had made the biggest contribution to the group for example and so this was not a trivial question.

After a little while I started to ask 'how many do you think $L$ and $C$ would have had together? etc... We wrote down the characteristic function for our game:


$$v(C)=\begin{cases}4, & C=\{S\}\\2, & C=\{C\}\\6, & C=\{L\}\\4, & C=\{S,C\}\\8, & C=\{S,L\}\\10, & C=\{C,L\}\\10, & C=\Omega\end{cases}$$


where $\Omega$ denotes the grand coalition.

At this point one student suggested that we somehow needed to take all this information in to account. He couldn't quite articulate how to do that but he's completely correct.

The way to share the chocolates 'fairly' is to consider all permutations of the players and consider marginal contributions for each permutation (take a look at my notes to read about that some more).

Let me try and explain with an example:

For the first permutation $\pi=(S,C,L)$ we calculate the contribution of $S$ first: $4$. We then calculate the marginal contribution of $C$ to the coalition $\{S,C\}$, which from above has value $4$ so $C$ needs to contribute 0. Finally $L$ needs to contribute $6$.

For the second permutation $\pi=(S,L,C)$ we calculate the contribution of $S$ first: $4$ (again). We then calculate the marginal contribution of $L$ to the coalition $\{S,L\}$, which from above has value $8$ so $L$ needs to contribute 4. Finally $C$ needs to contribute $2$.

Here's all the marginal contributions for each permutation:

  • $(S,C,L)$ gives: $(4,0,6)$
  • $(S,L,C)$ gives: $(4,2,4)$
  • $(C,S,L)$ gives: $(2,2,6)$
  • $(C,L,S)$ gives: $(0,2,8)$
  • $(L,S,C)$ gives: $(2,2,6)$
  • $(L,C,S)$ gives: $(0,4,6)$
We calculate the average values of the contribution vector (indexed by the players) to give the Shapley value:

$$\phi=(2,2,6)$$

This was good fun and I'm really happy with the discussion that lead us to the calculations and it was also fun to get students to mess around in class.

Here's one (of my most viewed!) +YouTube videos that I put together on it: