Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

Technical Summary: Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

Problem Statement
In cooperative game theory and related fields such as network centrality and machine learning data valuation, a fundamental challenge is extending individual player assessments to groups. Existing methods typically rely on two straightforward approaches:

1. Summation: Aggregating individual values (e.g., the sum of Shapley values). This ignores the underlying structure of cooperation and dependencies between players.
2. Merging: Treating the group as a single merged element and assessing it (e.g., the Merge Shapley value). This alters the game structure and fails to distinguish between independent and highly dependent players.

Both approaches often fail to accurately capture dependencies within groups. For instance, in a game where two disjoint pairs of players generate value independently, summing individual values or merging groups may incorrectly assign equal importance to a pair of cooperating players and a pair of independent players, failing to reflect the asymmetry in their systemic impact.

Methodology
The authors propose and analyze a third approach based on sequential elimination. In this framework, elements of a group are removed one by one, and their assessments in the resulting reduced games are aggregated. The core hypothesis is that this method naturally measures the net contribution of a group by discounting overlapping effects and focusing on the damage caused by the group's absence.

The study is grounded in a comprehensive axiomatic analysis of group values in coalitional games. The methodology involves:

• Defining Axiomatic Classes: The authors introduce a class of group (weak consistent) semivalues. These are group values satisfying Linearity, Symmetry, Weak Monotonicity, Null Player Out, and the Dummy Player axiom. They also define a corresponding class of synergy semivalues, which replace the Dummy Player axiom with the Dummifying Player axiom (introduced by Grabisch and Roubens).
• Sequential Extension: The paper establishes that a player value admits a sequential extension if and only if it satisfies the Balanced Contributions property. It is proven that every consistent semivalue (satisfying Null Player Out) admits a unique sequential extension.
• Potential Function: The authors utilize the potential function introduced by Hart and Mas-Colell to characterize the sequential extension of the Shapley value.

Key Contributions and Results

1. The Union Shapley Value:
   The authors introduce the Union Shapley Value as the unique sequential extension of the Shapley value. It is defined as the difference between the potential of the original game and the potential of the game after the group is removed:
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   where $\Delta v(T)$ are the Harsanyi dividends.

   • Interpretation: This value measures the "damage" inflicted on the game when a group leaves. It aggregates contributions such that each coalition's dividend is counted at most once, even if the group contains multiple members of that coalition.
   • Axiomatization: The Union Shapley value is uniquely characterized by the axioms of Potential (or Balanced Contributions) combined with Efficiency. It is also uniquely characterized among group semivalues by Group Equality (all groups in a unanimity game are equally important).

2. Axiomatic Classification of Group Values:
   The paper distinguishes between two variants of group assessment:

   • Total Worth: Values that assess the total worth of a group (e.g., Sum extension, Merge Shapley, Union Shapley). These are captured by group semivalues.
   • Synergy: Values that measure the synergy of a group (e.g., Interaction Index). These are captured by synergy semivalues.
     The authors provide a functional correspondence between these two classes. Specifically, they show that the Merge Shapley value corresponds to the Interaction Index (a synergistic counterpart), and the Union Shapley value corresponds to a new synergistic value called the Intersection Shapley Value.

3. The Intersection Shapley Value:
   Defined as the sum of dividends of coalitions that contain the entire group:
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   This value measures the intersection of contributions. For a group of size two, the sum of the Union Shapley value and the Intersection Shapley value equals the sum of the individual Shapley values:
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   This decomposition allows for the separation of a group's joint value into a "union" part (counting contributions once) and an "intersection" part (synergy).

4. Comparison with Existing Work:
   The analysis clarifies the relationship between the proposed values and existing literature:

   • The Merge Shapley value (Marichal et al.) is shown to be the unique group semivalue satisfying the Dummy Coalition axiom.
   • The Interaction Index (Grabisch and Roubens) is identified as a synergy semivalue, distinct from group semivalues because it violates the standard Dummy Player axiom in favor of the Dummifying Player axiom.
   • The paper demonstrates that the sequential extension approach is theoretically robust, as it applies to all consistent semivalues and yields values with strong axiomatic properties.

Significance
The paper claims that the sequential extension approach, and specifically the Union Shapley value, constitutes one of the most natural and theoretically grounded extensions of player values to groups in coalitional games. By distinguishing between assessing total worth and measuring synergy, the authors provide a unified framework that clarifies the differences between existing notions in the literature. The introduction of the Union and Intersection Shapley values offers new tools for analyzing interactions, particularly in scenarios where the overlap of contributions must be discounted (Union) or where pure synergy must be isolated (Intersection). The work establishes that these values are not arbitrary heuristics but are uniquely determined by fundamental axioms such as Balanced Contributions, Potential, and Group Equality.