Taxi Problem

Taxi Problem

5 4


Repo for the assignment of marks using Cooperative game theory.

On Github drvinceknight / Assigning_Fair_Individual_Marks_To_Group_Projects

Cooperative Game Theory

Introduction to the Shapley Value

Vincent Knight

Alice and Bob share a taxi:

  • It costs Alice £5 to get home.
  • It costs Bob £12 to get home (this will be the total fare).
  • Alice lives on Bob's way home.

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

Cooperative Games

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


  • 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

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

Taxi Problem

\pi Alice Bob (A,B) 5 7 (B,A) 0 12 \phi 2.5 9.5

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)

Why am I telling you this?

Applying this to group work

  • Assume Amy, Bernard and Caroline work on a group project.
  • Assume the marking criteria states: 70% output and 30% group work.
  • Assume the total mark given to the project is 85%.


S v(S) A 40 B 40 C 20 \{A,B\} 70 \{A,C\} 60 \{B,C\} 40

Shapley Value Calculation

\pi Amy Bernard Caroline (A,B,C) 40 30 30 (A,C,B) 40 40 20 (B,A,C) 30 40 30 (B,C,A) 60 40 0 (C,A,B) 40 40 20 (C,B,A) 60 20 20 \phi 45 35 20

Mark Calculation

\text{m}(i)=\text{M}\times\left(\text{OP}+\text{CW}\times{\phi(i)\over \max_j{\phi(j)}}\right)

Fair Marks

Efficiency: only way to maximise group mark is equal contribution; Null player: if i does not contribute, then m(i)=0; Symmetry: if i and j contribute equally, they get the same mark.
\text{m}(A)=85\times(.7+.3)=85\text{m}(B)=85\times\left(.7+.3\times {35\over 45}\right)={238\over 3}\approx 79.33\text{m}(C)=85\times\left(.7+.3\times{20\over45}\right)={425\over 6}\approx 70.83


The real problem...

How do we get \phi?