Fair Resource Distribution using Shapley Values

Hello! In our last lesson, we explored the strategic dynamics that determine which coalitions are likely to form within a vee relationship. We saw how the distribution of power and the "Strength-is-Weakness" effect can lead to the formation of dyadic sub-coalitions, even when a grand coalition of all three partners would create the most total value. This left us with a crucial unanswered question: once a coalition agrees to cooperate, how should they divide the value they create in a way that all members perceive as fair?

This lesson directly addresses that question. We will introduce one of the most celebrated concepts in cooperative game theory: the Shapley value. Your background in operations research and game theory will serve you well here, as we delve into a method that provides a unique, axiomatically-justified solution to fair division problems. Our goal is to apply the Shapley value to propose fair resource distributions in a vee and interpret the results. By the end of this lesson, you'll be able to calculate this value for a three-player game and use it to argue for a specific division of cooperative surplus.

What is a "Fair" Division?

Imagine the three members of a vee decide to pool their resources—be it time, money, or effort—to achieve a collective outcome that's better for everyone. The total benefit they create is the value of the "grand coalition," $v ({H, P_{1}, P_{2}})$ . The problem is dividing this benefit. Should it be split equally? Proportional to what each person could achieve alone? What about the synergies that only appear when specific people work together?

The Shapley value provides a compelling answer by assigning each player a payoff equal to their average marginal contribution to all the coalitions they could possibly join. Let's start with an intuitive video explanation that uses a simple, tangible problem: fairly splitting a taxi fare.

How to fairly split weird bills using GAME THEORY

This video by Dr. Trefor Bazett provides a wonderfully clear and intuitive introduction to the core concepts behind the Shapley value.

Please watch the first two sections of the video: The Problem: Watch from the beginning to understand the setup of a fair division problem. Marginal Contributions: Pay close attention to the section from 03:10 to 06:44. This introduces the two key ideas: the characteristic function, which we already know, and the crucial concept of marginal contribution—the value a player adds when they join an existing group.

As the video explains, the central idea is to consider every possible order in which the players could have come together to form the grand coalition. For each ordering, we can calculate each player's marginal contribution at the moment they join. The Shapley value is simply the average of these marginal contributions taken over all possible orderings.

Calculating the Shapley Value

The formal definition of the Shapley value, $ϕ_{i} (v)$ , for a player $i$ in a game with characteristic function $v$ is:

ϕ_{i} (v) = S \subseteq N ∖ {i} \sum \frac{∣ S ∣ ! \cdot ( ∣ N ∣ - ∣ S ∣ - 1 )!}{∣ N ∣ !} (v (S \cup {i}) - v (S))

While the formula may look complex, its interpretation is exactly what we just discussed: it's a weighted average of a player's marginal contributions $(v (S \cup {i}) - v (S))$ to every coalition $S$ they are not yet a part of.

The most straightforward way to calculate this for a three-player game is to use a table, just as demonstrated in the video. Let's apply this method to a concrete vee relationship scenario.

Example: The Profit-Sharing Vee

Consider the following scenario involving three individuals: "You" (the hinge), Emma, and Liam. Their potential for generating profit, both alone and together, is captured in the diagram below. The "Synergy Bonus" represents the extra value created when certain people cooperate.

This diagram shows the individual profits for You, Emma, and Liam, as well as the synergy bonuses generated by different coalitions. We will use these values to define our characteristic function.

From this diagram, we can construct the characteristic function $v (C)$ for every coalition $C$ :

Individuals (what they make alone):
- $v ({You}) = $30$
- $v ({Emma}) = $20$
- $v ({Liam}) = $10$
Dyads (sum of individual profits + synergy):
- $v ({You, Emma}) = 30 + 20 + 40 = $90$
- $v ({You, Liam}) = 30 + 10 + 60 = $100$
- $v ({Emma, Liam}) = 20 + 10 + 0 = $30$
Grand Coalition (sum of all parts):
- $v ({You, Emma, Liam}) = 30 + 20 + 10 + 40 + 60 + 0 + 120 = $280$

Now, let's calculate the Shapley value for each person. There are $3! = 6$ possible orderings for the players to form the grand coalition. We will calculate the marginal contribution for each player in each ordering.

Order of Joining	You (Y)	Emma (E)	Liam (L)
Y → E → L	$v ({Y}) = 30$	$v ({Y, E}) - v ({Y}) = 60$	$v ({Y, E, L}) - v ({Y, E}) = 190$
Y → L → E	$v ({Y}) = 30$	$v ({Y, L, E}) - v ({Y, L}) = 180$	$v ({Y, L}) - v ({Y}) = 70$
E → Y → L	$v ({E, Y}) - v ({E}) = 70$	$v ({E}) = 20$	$v ({E, Y, L}) - v ({E, Y}) = 190$
E → L → Y	$v ({E, L, Y}) - v ({E, L}) = 250$	$v ({E}) = 20$	$v ({E, L}) - v ({E}) = 10$
L → Y → E	$v ({L, Y}) - v ({L}) = 90$	$v ({L, Y, E}) - v ({L, Y}) = 180$	$v ({L}) = 10$
L → E → Y	$v ({L, E, Y}) - v ({L, E}) = 250$	$v ({L, E}) - v ({L}) = 20$	$v ({L}) = 10$
Total	720	480	480
Average (Shapley)	120	80	80

The Shapley value suggests a "fair" distribution of the $280 total profit is:

You (Hinge): $120
Emma (Partner 1): $80
Liam (Partner 2): $80

The following part of the video walks through a complete calculation using this table method.

How to fairly split weird bills using GAME THEORY

This segment demonstrates the step-by-step calculation for a three-player game.

Watch the section from 08:03 to 10:17, which shows how to fill out the permutation table and compute the final average for each player. The process is identical to what we just did.

Interpreting the Results: The Axioms of Fairness

What makes this specific distribution "fair"? The power of the Shapley value is that it's the only distribution method that satisfies four intuitive properties, or axioms, of fairness.

14.126(S16) Cooperative Games Lecture Slides - MIT OpenCourseWare

These lecture notes from MIT OpenCourseWare provide a formal definition of the Shapley value and its axioms.

In Section 8, "The Shapley Value," please read from the beginning of the section up to the start of Theorem 6. This covers the formal definition and the four axioms: Symmetry, Dummy Player, and Additivity, along with Efficiency (which is implicitly assumed in the setup).

Let's review these four axioms and see how they apply to our example:

Efficiency: The sum of the payoffs equals the total value of the grand coalition. In our case, $120 + 80 + 80 = 280$ , which is exactly $v ({You, Emma, Liam})$ . No value is wasted or created out of thin air.
Symmetry: If two players are interchangeable (i.e., they contribute the exact same amount to every coalition they could join), they must receive the same payoff. In our example, Emma and Liam received the same payoff ($80), but they are not symmetric players. For instance, $v ({Emma}) = 20$ while $v ({Liam}) = 10$ . Their equal Shapley values are a result of the specific numbers in this game—Liam's higher synergy with the Hinge ($60) perfectly balanced out Emma's higher standalone profit ($20) and dyadic synergy with the Hinge ($40) when averaged over all contexts.
Null Player: A player who adds no value to any coalition receives a payoff of zero. This is an obvious fairness condition that is met by the Shapley value.
Additivity (or Linearity): If a game can be thought of as the sum of two separate games (e.g., one financial, one temporal), the Shapley value of the combined game is the sum of the Shapley values of the individual games. This allows for complex situations to be broken down and analyzed consistently.

The remarkable theorem by Lloyd Shapley states that his value is the unique payoff scheme that satisfies these four properties. If you want a division to be efficient, symmetric, treat null players appropriately, and be consistent across combined games, then you must use the Shapley value.

What the Shapley Value Tells Us About the Vee

The calculation gives us a principled proposal for distributing the surplus generated by the vee relationship.

The Hinge's Value: "You" receive the largest share ($120). This reflects your high marginal contributions across the board. You are crucial for enabling the high-synergy dyads and are essential for unlocking the massive $120 bonus in the grand coalition. The Shapley value quantitatively acknowledges your central role.
The Partners' Value: Emma and Liam receiving equal shares ($80) is a fascinating outcome. It demonstrates that the Shapley value doesn't just reward what you can do on your own, but your total contribution in all contexts. Liam's low individual profit is offset by his high synergistic potential with You. This result could be used to argue that despite different "baseline" contributions, their overall importance to the cooperative success of the triad is equal.

This method provides a powerful tool for negotiation. Instead of relying purely on intuition, partners can model their situation and use the Shapley value as a neutral, mathematically-grounded starting point for discussions about how to share time, finances, or other resources. Since you are already familiar with the Nash bargaining solution, it's interesting to note that for a two-player game, the Shapley value is identical to it. The Shapley value essentially extends that same logic of fair division to games with more than two players.

Conclusion

In this lesson, we have tackled the second fundamental question of cooperative games: how to divide the spoils. We have seen that the Shapley value provides a powerful and axiomatically unique solution.

Key Takeaways:
- The Shapley value calculates a fair payoff for each player by averaging their marginal contributions across all possible sequences of coalition formation.
- It is the only allocation method that satisfies the four fairness axioms: Efficiency, Symmetry, Null Player, and Additivity.
- Calculating the value for a three-player vee provides a quantitative basis for negotiating the division of resources, reflecting each person's total contribution to the group's success, not just their individual worth.
- The results can reveal non-obvious equalities in players' importance, balancing individual strengths against synergistic potential.

So far, we have analyzed how to divide the payoff. But this is different from analyzing a player's power or influence within the game structure. In our next lesson, we will explore a different concept, the Banzhaf power index, which also quantifies a player's importance but from a different perspective. We will then contrast it with the Shapley value to gain a richer understanding of player roles in a cooperative game.

Recommended resources