Fair Cost Allocation
Fair Cost Allocation
The Shapley Value is a concept from cooperative game theory developed by Lloyd Shapley in 1953. It provides a mathematically rigorous method for allocating costs or rewards among participants according to the value they contribute to a group.
Unlike many allocation methods that rely on arbitrary rules or negotiated agreements, the Shapley Value satisfies a set of desirable fairness properties and produces a unique allocation.
The central question it answers is:
If a group of participants creates value together, how much of that value should each participant receive?
The intuition
Imagine three friends sharing a taxi home.
Alice lives closest to the city centre.
Bob lives slightly further away.
Charlie lives furthest away.
The taxi costs £30.
A simple approach would split the fare equally:
- Alice pays £10
- Bob pays £10
- Charlie pays £10
But this clearly isn't fair.
Alice leaves the taxi early.
Charlie is responsible for most of the journey.
The value each passenger receives is different.
The challenge is determining what constitutes a fair contribution.
Characteristic Function
The Shapley Value begins by defining a characteristic function.
The characteristic function assigns a value to every possible coalition of participants.
For the taxi example,
[ v(S) ]
represents the total taxi cost incurred by coalition (S).
Suppose the costs are
| Coalition | Cost |
|---|---|
| ∅ | £0 |
| {Alice} | £8 |
| {Bob} | £15 |
| {Charlie} | £30 |
| {Alice,Bob} | £15 |
| {Alice,Charlie} | £30 |
| {Bob,Charlie} | £30 |
| {Alice,Bob,Charlie} | £30 |
Marginal Contribution
The Shapley Value asks:
How much extra value does each participant contribute when joining a coalition?
For example,
If Alice and Bob are already sharing a taxi,
adding Charlie increases the total cost from
£15
to
£30.
Charlie's marginal contribution is therefore
[ 30-15=15 ]
If Charlie is already travelling alone,
adding Alice changes nothing.
Alice's marginal contribution is zero.
Every possible ordering of passengers is considered.
Each passenger's marginal contribution is calculated.
The average of all those marginal contributions becomes that passenger's Shapley Value.
Why this is fair
The remarkable feature of the Shapley Value is that it satisfies several intuitive fairness properties.
Symmetry
Participants making identical contributions receive identical allocations.
Dummy Player
Participants contributing no additional value receive nothing.
Efficiency
The entire cost is allocated.
Nothing is lost or created.
Additivity
Independent allocation problems can be combined consistently.
Because of these properties, the Shapley Value has become one of the most widely accepted approaches for allocating shared costs and rewards.
The same mathematics can be applied far beyond taxi fares.
It can also be used to allocate the value created by electricity generators.