On the Ordinal Invariance of Power Indices on Coalitional Games
On the Ordinal Invariance of Power Indices on Coalitional Games
Jean-Paul Doignon, Stefano Moretti, Meltem Ozturk
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 258-264.
https://doi.org/10.24963/ijcai.2022/37
In a coalitional game, the coalitions are weakly ordered according to their worths in the game. When moreover a power index is given, the players are ranked according to the real numbers they are assigned by the power index. If any game inducing the same ordering of the coalitions generates the same ranking of the players then, by definition, the game is (ordinally) stable for the power index, which in turn is ordinally invariant for the game. If one is interested in ranking players of a game which is stable, re-computing the power indices when the coalitional worths slightly fluctuate or are uncertain becomes useless. Bivalued games are easy examples of games stable for any power index which is linear. Among general games, we characterize those that are stable for a given linear index. Note that the Shapley and Banzhaf scores, frequently used in AI, are particular semivalues, and all semivalues are linear indices. To check whether a game is stable for a specific semivalue, it suffices to inspect the ordering of the coalitions and to perform some direct computation based on the semivalue parameters.
Keywords:
Agent-based and Multi-agent Systems: Cooperative Games
Agent-based and Multi-agent Systems: Computational Social Choice