TL;DR
This paper introduces the concept of "ordinal stability" for coalitional games, addressing how robust player rankings are to small changes in coalition worths. They provide a theoretical framework and characterizations for when these rankings remain consistent, particularly for linear and semivalue-based power indices. This work is crucial for understanding the reliability of power index computations in real-world scenarios where exact coalition values are often unknown.
What Problem Does This Paper Address?
In cooperative game theory, "power indices" are used to quantify a player's influence within a coalition. These indices typically take the exact worth of every possible coalition as input and output a numerical score for each player, which then implies a ranking of players. However, in many practical applications (like voting systems, network analysis, or AI feature selection), the precise worth of coalitions is often uncertain or only a relative ordering of coalitions is known. This paper tackles the problem of ordinal stability: when does the ranking of players derived from a power index remain the same even if the exact coalition worths change, as long as the relative ordering of coalitions is preserved? This is critical because if a power index is ordinally stable for a given game, we don't need precise coalition values; only their relative order matters for determining player influence.
Methods
The authors develop a formal framework for analyzing ordinal stability. They define a set function as "π-stable" if any other set function that induces the same ordering of coalitions also produces the same player ranking under a given scoring rule π. They then focus on linear scoring rules, which include many common power indices like Shapley and Banzhaf values (as they are all semivalues).
Key methodological contributions include:
- Characterization of Stable Set Functions: They provide necessary and sufficient conditions for a set function to be stable with respect to a linear scoring rule. This involves decomposing any set function into a sum of "binary set functions" and analyzing the scoring rule's behavior on these components.
- Two-Player Stability Analysis: They delve into the simpler case of two players, deriving conditions for stability that depend on the relative ordering of coalition worths involving those two players.
- Generalization to Semivalues: The analysis is extended to semivalues, a broad class of linear scoring rules that includes Shapley and Banzhaf indices. Theorem 3, in particular, offers a more computationally tractable condition for two-player stability for semivalues.
Datasets
Not discussed in the paper. The paper is theoretical and focuses on the properties of set functions and scoring rules rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Ordinal Stability is Key for Robustness: The core idea is that in many real-world scenarios, we only have ordinal information about coalition worths. Ordinal stability ensures that our conclusions about player power are robust to this inherent uncertainty.
- Linearity is Crucial: The paper heavily relies on the linearity of scoring rules. This property allows for the decomposition of complex set functions into simpler binary components, making the analysis tractable.
- Bivalued Games are Always Stable: A surprising and useful result is that any "bivalued" game (where coalition worths can only take two distinct values) is ordinally stable for any linear scoring rule. This means for such games, only the partition of coalitions into two groups matters for player ranking.
- Two-Player Stability as a Building Block: The paper shows that understanding stability for two players is a fundamental step towards understanding stability for larger groups.
- The Power of Decomposition: The technique of decomposing any set function into binary set functions is a powerful tool for analyzing linear scoring rules.
Key Results
- Theorem 1: Provides a necessary and sufficient condition for a set function to be stable for any steady and linear scoring rule, based on the comparison of binary set functions derived from the set function's ordering.
- Proposition 1: Demonstrates that for any semivalue, any two-player game is ordinally stable.
- Proposition 2: Shows that all bivalued set functions are ordinally stable for any steady and linear scoring rule.
- Theorem 2: Offers a characterization of two-player stability for the Banzhaf scoring rule, relating it to the sorted order of coalition worths involving the two players.
- Theorem 3: Extends the characterization of two-player stability to general semivalues, providing a condition based on specific coalition comparisons.
Limitations and Future Work
- Focus on Linear Scoring Rules: While linearity is a powerful assumption, many interesting power indices might not be linear. The paper acknowledges this by stating that future work could explore ordinal stability for non-linear solutions.
- Computational Complexity: While theorems provide characterizations, the practical computation of these conditions for very large numbers of players or coalitions might still be challenging.
- Future Research Directions: The authors suggest exploring ordinal stability for solutions that are not semivalue-like (e.g., the nucleolus) and integrating restricted possibilities of cooperation into the ordinal framework. They also propose investigating the impact of these restrictions on player ranking stability.
Summary updated