# Taxi Problem

### Assigning_Fair_Individual_Marks_To_Group_Projects

Repo for the assignment of marks using Cooperative game theory.

## Cooperative Game Theory

### Introduction to the Shapley Value

#### Vincent Knight

www.vincent-knight.com

## 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.

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.

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)

## 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%.

## Contributions

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?