Characteristic Function Games

Motivating example: a taxi trip

Consider the following situation:

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

• Player 1: 6

• Player 2: 12

• Player 3: 42

As illustrated here:

How can we represent this situation mathematically?

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.

Question

For the taxi fare what is the characteristic function?

Answer

The number of players \(N=3\) and 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 \(\Omega=\{1,2,3\}\).

The characteristic function is given below:

\[\begin{split}v(C)=\begin{cases} 0,&\text{if }C=\emptyset\\ 6,&\text{if }C=\{1\}\\ 12,&\text{if }C=\{2\}\\ 42,&\text{if }C=\{3\}\\ 12,&\text{if }C=\{1,2\}\\ 42,&\text{if }C=\{1,3\}\\ 42,&\text{if }C=\{2,3\}\\ 42,&\text{if }C=\{1,2,3\}\\ \end{cases}\end{split}\]

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

Question

Which of the following characteristic function games are monotone:

1. The taxi fare.

2. \(G=(3,v_1)\) with \(v_1\) defined as:

\[\begin{split}v_1(C)=\begin{cases} 0,&\text{if }C=\emptyset\\ 6,&\text{if }C=\{1\}\\ 12,&\text{if }C=\{2\}\\ 42,&\text{if }C=\{3\}\\ 10,&\text{if }C=\{1,2\}\\ 42,&\text{if }C=\{1,3\}\\ 42,&\text{if }C=\{2,3\}\\ 42,&\text{if }C=\{1,2,3\}\\ \end{cases}\end{split}\]

Answer

1. The taxi fare characteristic function is monotone.

2. This game is not as \(\{2\}\subseteq\{1,2\}\) however \(v_1(\{2\}) > v_1(\{1, 2\})\).

Definition of a superadditive characteristic function 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).\)

Question

Which of the following characteristic function games are superadditive:

1. The taxi fare.

2. \(G=(3,v_2)\) with \(v_2\) defined as:

\[\begin{split}v_2(C)=\begin{cases} 0,&\text{if }C=\emptyset\\ 6,&\text{if }C=\{1\}\\ 12,&\text{if }C=\{2\}\\ 42,&\text{if }C=\{3\}\\ 18,&\text{if }C=\{1,2\}\\ 48,&\text{if }C=\{1,3\}\\ 55,&\text{if }C=\{2,3\}\\ 80,&\text{if }C=\{1,2,3\}\\ \end{cases}\end{split}\]

Answer

1. The taxi fare characteristic function is not superadditive as \(v(\{1\}) + v(\{2\}) = 18\) but \(v(\{1, 2\})=12\).

2. This game is superadditive.

[Maschler2013] is recommended for further reading.