When Alice gets out of the cab, how much should she pay?

Cooperative Games

• $N=\{1,\dots,n\}$ players.
• Coalitions $S\subseteq N$.

Examples:

• $S_1=\{2,5\}$
• $S_2=\{1\}$
• $S_2=N$
• $S_2=\emptyset$

Characteristic Function Games

A characteristic game $G$ is given by a pair: $(N,v)$. Where: $$v:2^{N}\to\mathbb{R}$$ is a characteristic function which maps each coalition $S\subseteq N$ to a real number $v(S)$.

Taxi Problem

$N=\{A,B\}$ and we have:

• $v(\emptyset)=0$
• $v(A)=5$
• $v(B)=12$
• $v(A,B)=12$

Monotone Games

A characteristic function game $G=(N,v)$ is said to be monotone if it satisfies $v(S_2)\geq v(S_1)$ for all pairs $S_1\subseteq S_2$.

Superadditive Games

A characteristic function game $G=(N,v)$ is said to be superadditive if it satisfies $v(S_1\cup S_2)\geq v(S_1)+v(S_2)$ for all pairs $S_1,S_2\subseteq N$.

Solution Concepts

The 'solution' of a superadditive game corresponds to a vector: $x\in\mathbb{R}^{|N|}_{\geq0}$ that satisfies: $$\sum_{i\in N}x_i=v(N)$$

Fair Distribution

1. Efficiency: $\sum_{i\in N}x_i=v(N)$;
2. Null player: if $i$ does not contribute, then $x_i=0$;
3. Symmetry: if $i$ and $j$ are symmetric in then $x_i=x_j$;
4. Additivity: (look it up if you're interested).

Shapley Value

Given a characteristic function game $G=(N,v)$ the Shapley value of a player $i\in N$ is given by: $$\phi_{i}(G)={1\over |N|!}\sum_{\pi\in\Pi_N}\Delta_{\pi}^{G}(i)$$

Contributions

Shapley Value Calculation

Mark Calculation

Fair Marks

1. Efficiency: only way to maximise group mark is equal contribution;
2. Null player: if $i$ does not contribute, then $m(i)=0$;
3. Symmetry: if $i$ and $j$ contribute equally, they get the same mark.

The real problem...