📈 economics

A Tractable Class of Cooperative Games Defined by Directed Networks: Unanimity Decomposition and Shapley Value

This paper introduces a tractable class of cooperative games defined by weighted directed networks that admit a unanimity decomposition, enabling efficient closed-form computation of Shapley and Banzhaf values while guaranteeing a nonempty core and total balancedness, thereby illustrating a setting where stability-based and fairness-based allocations diverge.

Original authors: David Ryzák, Tomáš Kroupa

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Ryzák, Tomáš Kroupa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to decide how to split a pot of money they earned together. In the world of Cooperative Game Theory, this is a classic problem: How do you fairly divide the rewards based on who contributed what?

This paper introduces a new, clever way to model this situation using a directed network (a map of one-way arrows) and a specific set of rules called the "Trust Game."

Here is the breakdown of their idea, using simple analogies.

1. The Setup: The "Trust Map"

Imagine a group of people where everyone can rate everyone else on a scale from 0 to 1. These ratings are like arrows pointing from one person to another.

The Arrow: If Alice rates Bob highly, there is an arrow from Alice to Bob with a high number.
The Direction: The rating doesn't have to be mutual. Alice might love Bob, but Bob might think Alice is mediocre.

2. How the "Team Value" is Calculated

When a group of people (a "coalition") decides to work together, the paper says their total value comes from two distinct sources, like a two-part salary:

Part A: The "Internal Party" (Internal Interaction)
This is the value generated by the friends inside the group rating each other. If Alice and Bob are both in the group, and they rate each other, that adds to the pot. It's like the fun and productivity they generate just by being together.
- Mathematically: This is the sum of all the arrows pointing between members of the group.
Part B: The "Bottleneck" (External Exposure)
This is the tricky part. The group also gets value based on how the outsiders view them. However, the group doesn't get the average rating from the outside; they get the lowest rating they receive from any single outsider.
- The Analogy: Imagine a team of climbers. Their safety depends on the weakest rope holding them to the mountain. Even if 99 people think the team is great, if one person thinks they are dangerous, the team's "safety score" drops to that low level.
- Why it matters: This creates a "bottleneck." The group is only as strong as its weakest external connection.

3. The Big Breakthrough: The "Unanimity" Trick

Usually, calculating fair shares in these complex networks is a nightmare for computers (it takes too long). But the authors found a magic key: Unanimity Decomposition.

Think of the game not as a messy web of ratings, but as a stack of simple "Yes/No" games.

In a "Unanimity Game," a group only gets points if everyone in a specific small circle is present.
The authors proved that their complex "Trust Game" can be broken down into a neat, ordered stack of these simple games.
The Result: Because the game is built from these simple blocks, they can write down a closed-form formula (a direct math recipe) to calculate the fair share for anyone in the group instantly, without needing a supercomputer.

4. The Two Ways to Split the Pie

The paper calculates the "fair share" using two famous methods:

The Shapley Value (The "Fairness" Approach): This asks, "If I add this person to every possible group, how much extra value do they create on average?" It's about contribution and marginal impact.
The Banzhaf Value (The "Power" Approach): This asks, "How often is this person the 'swing vote' that turns a losing group into a winning one?"

The Surprise: The paper shows that in this specific "Trust Game," the Fairness share (Shapley) and the Stability share (Core) are different.

The Core (The "Stability" Approach): This is the only way to split the money so that no subgroup can break away and say, "We can do better on our own!"
The Finding: The paper proves there is only one stable way to split the money (a "singleton core"). Interestingly, this stable split is simply giving everyone the sum of all the ratings they received from others.
The Conflict: This stable split is usually not the same as the Shapley value. This highlights a real-world tension: What is mathematically "fair" (Shapley) is often not what is "stable" enough to keep the group from breaking apart.

5. Why This Matters

The authors created a "toy model" of a complex social network that is:

Realistic enough: It captures how external opinions (even negative ones) can limit a group's success.
Simple enough: We can actually solve the math for it quickly.
Insightful: It proves that in networks where "the weakest link" matters, the way we define "fairness" and "stability" can lead to very different results.

In a nutshell: The paper builds a mathematical model where a team's worth depends on its internal chemistry and its weakest external critic. They found a fast way to calculate who deserves what, revealing that the "fair" share often differs from the "safe" share, and that the "safe" share is simply everyone getting paid for how much the world trusts them.

Technical Summary: A Tractable Class of Cooperative Games Defined by Directed Networks

Problem Statement

The paper addresses the computational and analytical challenges inherent in cooperative game theory, specifically regarding games induced by weighted directed graphs. Cooperative games typically suffer from an exponential representation size relative to the number of players, making the computation of solution concepts (such as the Shapley and Banzhaf values) and stability properties (such as the core) intractable ( $\sharp$ P-complete in many cases).

While previous works have studied games induced by undirected graphs or specific subclasses (e.g., weighted voting games), there is a need for structured classes of games defined by directed networks that remain analytically and computationally tractable. The authors introduce a specific class of games, termed "trust games," where the coalitional value is determined by both internal interactions and external exposures. The primary challenge is to derive closed-form, polynomial-time formulas for solution concepts and to characterize the stability properties of these games, particularly given that the external component introduces non-additive, bottleneck-like behavior.

Methodology

The authors define the Trust Game $(N, v)$ induced by a weighted directed graph $G = (N, E)$ with edge weights $a_{ij} \in [0, 1]$ . The value of a coalition $S \subseteq N$ is defined as the sum of two components:

Internal Term: The sum of weights of all edges $(i, j)$ where both $i, j \in S$ . This corresponds to an induced subgraph game.
External Term: For each player $i \in S$ who has incoming edges from outside $S$ , the value includes the minimum weight among those incoming edges. If a player in $S$ has no incoming edges from outside, this term contributes 0.

Mathematically:
$v(S) = \sum_{i \in S, j \in S, (i,j) \in E} a_{ij} + \sum_{i \in S^*} \min_{j \notin S: (j,i) \in E} a_{ji}$
where $S^*$ is the set of players in $S$ with at least one incoming edge from $N \setminus S$ .

To analyze this game, the authors employ the Möbius transform to decompose the game into a linear combination of unanimity games ( $u_T$ ).

The internal component is straightforward, involving pairwise unanimity games.
The external component is more complex due to the $\min$ operator. The authors order the in-neighbors of each player $i$ by non-decreasing edge weights. They demonstrate that the external game for player $i$ can be expressed as a telescopic sum of unanimity games, where the supports form an inclusion chain determined by the ranking of incoming neighbors.

This decomposition allows the authors to leverage the linearity of the Shapley and Banzhaf operators to derive explicit formulas.

Key Contributions and Results

1. Unanimity Decomposition

The paper establishes a closed-form unanimity decomposition for the trust game.

Lemma 2.3: The external game $w_i(S)$ for a player $i$ is decomposed into a sum of unanimity games $u_{T_i(t)}$ , where $T_i(t)$ consists of player $i$ and their first $t-1$ in-neighbors (ordered by weight). The coefficients are differences in the sorted edge weights.
Lemma 3.2: The total game $v(S)$ is the sum of the internal pairwise unanimity games and the decomposed external unanimity games.

2. Polynomial-Time Solution Concepts

Using the unanimity decomposition, the authors derive explicit, polynomial-time formulas for:

Shapley Value ( $\phi_i$ ): The value is expressed as a sum of three parts:
1. The average of internal edge weights (symmetric weighted degree centrality).
2. A term derived from player $i$ 's own incoming edges (external exposure).
3. A term derived from edges incoming to $i$ 's out-neighbors (shared-neighbor effects).
  The formula (Theorem 3.1) explicitly accounts for the rank of each player among the in-neighbors of others.
Banzhaf Value ( $\beta_i$ ): Similarly, a closed-form formula is derived (Theorem 4.2), utilizing the specific Banzhaf value of unanimity games ( $2^{1-|T|}$ ).

3. Marginal Effects Analysis

The paper analyzes how local changes in edge weights affect the solution values.

Lemma 3.5 & 4.3: The marginal effect of an edge weight $a_{kj}$ $a_{k j}$ on a player's value depends on the player's position relative to the edge:
- Internal edges: Contribute linearly to both Shapley and Banzhaf values.
- External edges: The effect is non-linear and depends on the rank of the player among the in-neighbors of the target node. For the Shapley value, the effect involves terms like $\frac{1}{r(r+1)}$ , while the Banzhaf value involves $\frac{1}{2^r}$ .
Null Player Characterization: Lemma 3.6 provides necessary and sufficient conditions for a player to be a null player (value 0), which occurs if they have no incoming edges or if their incoming edges are from players who are themselves null in a specific structural sense.

4. Stability and Core Properties

The authors investigate the stability of the trust game:

Core Characterization (Lemma 5.1): The core of the trust game is a singleton. It consists of a unique allocation where each player $i$ receives the sum of all incoming edge weights from the entire graph ( $\sum_{j} a_{ji}$ ).
Total Balancedness (Lemma 5.2): The game is totally balanced, meaning every subgame (restricted to any coalition $S$ ) has a non-empty core. This is proven by constructing an explicit core allocation for any subgame.
Divergence of Concepts: The paper highlights that the unique core allocation (based on total incoming weights) generally does not coincide with the Shapley or Banzhaf values. This demonstrates a setting where stability-based allocations and fairness-based solution concepts diverge.

Significance and Claims

The paper claims to provide a tractable example of structured network-induced cooperative games. Its significance lies in:

Computational Tractability: It offers a class of games where solution concepts (Shapley, Banzhaf) and stability properties (Core) can be computed in polynomial time, avoiding the exponential complexity typical of general cooperative games.
Structural Insight: The unanimity decomposition reveals that the complex "minimum" operator in the external component creates a nested chain of unanimity games, making the game analytically manageable.
Theoretical Distinction: It explicitly illustrates a scenario where the core (stability) and the Shapley value (fairness/marginal contribution) yield different allocations, despite the game being totally balanced.
Foundation for Future Work: The authors suggest this class serves as a baseline for exploring parametric generalizations, alternative aggregation rules for the external component, and mechanism design problems regarding incentive compatibility.

The work does not propose new experimental applications but rather establishes a theoretical framework for analyzing cooperative interactions in directed networks with asymmetric, local evaluations.