Recap

In the previous chapter:

  • We defined matching games;
  • We described the Gale-Shapley algorithm;
  • We proved certain results regarding the Gale-Shapley algorithm.

In this Chapter we’ll take a look at another type of game.

Cooperative Games

In cooperative game theory the interest lies with understanding how coalitions form in competitive situations.

Definition of a characteristic function game


A characteristic function game G is given by a pair \((N,v)\) where \(N\) is the number of players and \(v:2^{[N]}\to\mathbb{R}\) is a characteristic function which maps every coalition of players to a payoff.


Let us consider the following game:

“3 players share a taxi. Here are the costs for each individual journey:

  • Player 1: 6
  • Player 2: 12
  • Player 3: 42 How much should each individual contribute?”

This is illustrated.

A taxi journey. \label{L16-img01}

To construct the characteristic function we first obtain the power set (ie all possible coalitions) \(2^{{1,2,3}}=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\Omega\}\) where \(\Omega\) denotes the set of all players (\(\{1,2,3\}\)).

The characteristic function is given below:

Definition of a monotone characteristic function game


A characteristic function game \(G=(N,v)\) is called monotone if it satisfies \(v(C_2)\geq v(C_1)\) for all \(C_1\subseteq C_2\).


A diagrammatic representation of monotonicity.\label{L16-img02}

Our taxi example is monotone, however the \(G=(3,v_1)\) with \(v_1\) defined as:

is not.

Definition of a superadditive game


A characteristic function game \(G=(N,v)\) is called superadditive if it satisfies \(v(C_1\cup C_2)\geq v(C_1)+v(C_2).\) for all \(C_1\cap C_2=\emptyset\).


A diagrammatic representation of superadditivity.\label{L16-img03}

Our taxi example is not superadditive, however the \(G=(3,v_2)\) with \(v_2\) defined as:

is.

Shapley Value

When talking about a solution to a characteristic function game we imply a payoff vector \(\lambda\in\mathbb{R}_{\geq 0}^{N}\) that divides the value of the grand coalition between the various players. Thus \(\lambda\) must satisfy:

Thus one potential solution to our taxi example would be \(\lambda=(14,14,14)\). Obviously this is not ideal for player 1 and/or 2: they actually pay more than they would have paid without sharing the taxi!

Another potential solution would be \(\lambda=(6,6,30)\), however at this point sharing the taxi is of no benefit to player 1. Similarly \((0,12,30)\) would have no incentive for player 2.

To find a “fair” distribution of the grand coalition we must define what is meant by “fair”. We require four desirable properties:

  • Efficiency;
  • Null player;
  • Symmetry;
  • Additivity.

Definition of efficiency


For \(G=(N,v)\) a payoff vector \(\lambda\) is efficient if:


Definition of null players


For \(G(N,v)\) a payoff vector possesses the null player property if \(v(C\cup i)=v(C)\) for all \(C\in 2^{\Omega}\) then:


Definition of symmetry


For \(G(N,v)\) a payoff vector possesses the symmetry property if \(v(C\cup i)=v(C\cup j)\) for all \(C\in 2^{\Omega}\setminus\{i,j\}\) then:


Definition of additivity


For \(G_1=(N,v_1)\) and \(G_2=(N,v_2)\) and \(G^+=(N,v^+)\) where \(v^+(C)=v_1(C)+v_2(C)\) for any \(C\in 2^{\Omega}\). A payoff vector possesses the additivity property if:


We will not prove in this course but in fact there is a single payoff vector that satisfies these four properties. To define it we need two last definitions.

Definition of predecessors


If we consider any permutation \(\pi\) of \([N]\) then we denote by \(S_\pi(i)\) the set of predecessors of \(i\) in \(\pi\):


For example for \(\pi=(1,3,4,2)\) we have \(S_\pi(4)=\{1,3\}\).

Definition of marginal contribution


If we consider any permutation \(\pi\) of \([N]\) then the marginal contribution of player \(i\) with respect to \(\pi\) is given by:


We can now define the Shapley value of any game \(G=(N,v)\).

Definition of the Shapley value


Given \(G=(N,v)\) the Shapley value of player \(i\) is denoted by \(\phi_i(G)\) and given by:


As an example here is the Shapley value calculation for our taxi sharing game:

For \(\pi=(1,2,3)\):

For \(\pi=(1,3,2)\):

For \(\pi=(2,1,3)\):

For \(\pi=(2,3,1)\):

For \(\pi=(3,1,2)\):

For \(\pi=(3,2,1)\):

Using this we obtain:

Thus the fair way of sharing the taxi fare is for player 1 to pay 2, player 2 to pay 5 and player 3 to pay 35.