Taxi Problem
Taxi Problem
5 4
Assigning_Fair_Individual_Marks_To_Group_Projects
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.
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
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%.