# 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?
{"ft_lang_label":"__label__en","ft_lang_prob":0.58237416,"math_prob":0.9901876,"size":2540,"snap":"2022-40-2023-06","text_gpt3_token_len":921,"char_repetition_ratio":0.089511044,"word_repetition_ratio":0.057894737,"special_character_ratio":0.36102363,"punctuation_ratio":0.14003295,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9995135,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-24T20:36:36Z\",\"WARC-Record-ID\":\"<urn:uuid:5577f9f6-fa62-4d12-a5e3-38e94f8d8e87>\",\"Content-Length\":\"23720\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a9e8ece1-cdf2-429f-81a8-5f0ae535e024>\",\"WARC-Concurrent-To\":\"<urn:uuid:9eb6a32f-7574-48c3-a8f6-6ead42f868b4>\",\"WARC-IP-Address\":\"185.31.40.158\",\"WARC-Target-URI\":\"https://slidedeck.io/drvinceknight/Assigning_Fair_Individual_Marks_To_Group_Projects\",\"WARC-Payload-Digest\":\"sha1:SFTDWXCNZG7VTGO5RLJ4KGR3N7BRR4PI\",\"WARC-Block-Digest\":\"sha1:AXYYI6BF3DUOC73O7WEHZBPQ64MRLUDV\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030333455.97_warc_CC-MAIN-20220924182740-20220924212740-00022.warc.gz\"}"}