On the Ordinal Invariance of Power Indices on Coalitional Games

1 Introduction

Classical power indices and, more in general, solutions or values for coalitional games [Shapley, 1953; Banzhaf III, 1964; Dubey et al., 1981] aim at converting the information about the performance of coalitions into a personal attribution of "power" representing each player's role over all possible coalitions. Game theory is arguably the field which has dealt with the notion of power index the most [Holler and Nurmi, 2013]. The notion has also been extensively applied in voting theory (for instance, in order to define the "power" of different countries in the European Council [Algaba et al., 2003]), network theory (for measuring the centrality of network elements [Michalak et al., 2013]), belief merging/revision (for the responsibility of a formula in the inconsistency of a belief base [Hunter and Konieczny, 2006]), multicriteria decision aiding (the impact and synergy of some criteria [Grabisch and Roubens, 2000], machine learning (selecting best features, for instance using SHAP [Lundberg and Lee, 2017]), argumentation theory (influence of an argument in a debate [Amgoud et al., 2017]), etc.

∗Contact Author

Due to the high number of power indices in the literature and their heterogeneous nature, some studies looked for conditions under which distinct power indices rank players in the same manner (see, for instance, [Carreras and Freixas, 2008; Lambo and Moulen, 2002]).

Unfortunately, power indices computed on the characteristic function of a game often are very sensitive to small fluctuations of coalitions' performance. Moreover, due to multiple and barely measurable attributes of performance to coalitions, it is more reasonable to expect that only a ranking over coalitions is given as input for the computation of the relative power of players [Haret et al., 2018; Bernardi et al., 2019]. There results our main question: For a given power index, characterize the coalitional games v for which the ranking over the players set remains the same when the game v is replaced with any game w such that v and w induce the same ranking over the coalitions. By definition, such a game v is stable for the given power index, and the power index is then ordinally invariant for the game. Consider for example a coalitional game with three players. If we are interested in ranking two players i and j using the Banzhaf index [Banzhaf III, 1964], it is easy to verify that a little variation in the worths of coalitions containing either i or j (but not both of them) may completely change the relative ranking of the two players (see for instance Example 2 in Section 3). To the contrary, any game on two players is always stable, not only for the Banzhaf index but also for any semivalue (in the sense of [Dubey et al., 1981; Lucchetti et al., 2015]); see Proposition 1.

As an answer to our main question, Theorem 1 offers a characterization of stable games under the mundane assumption that the power index is linear (linearity allows us to take advantage of a certain decomposition of the game function). Note that the Shapley and Banzhaf indices, as well as the more general semivalues, all are linear indices. For the Banzhaff index, Theorem 2 provides a better characterization of game stability (in that it involves a lesser number of coalitions worths). It is extended to all semivalues in Theorem 3.

Before stating the three theorems in Sections 5 and 6, we introduce in Section 2 some necessary notation and definitions, and show some results on particular cases in Sections 3 and 4. We conclude by some perspectives in Section 7.

2 Notations and Definitions

2.1 Set Functions

A set function (N, v) consists of a finite set N, of cardinality n, together with a mapping v : 2N →R; it is a (Transferable Utility or coalitional) game when v(∅) = 0. The elements of the set N are the players, the subsets of N are the coalitions, the map v is the characteristic function, and v(S) is the worth of coalition S. When N is clear from the context, we denote the set function (N, v) simply by v. The collection of all set functions on N is denoted as R2N . A set function v is bivalued when there exist two real numbers λ and µ such that v(S) = λ or v(S) = µ for all S in 2N , and binary if moreover λ = 0 and µ = 1.

2.2 Scorings

A social scoring rule or scoring π on N attributes to any set function 1 v on N a scoring vector in RN . The score of player i for the set function v under the scoring π is the component πi(v) of π(v).

The Shapley scoring of a set function v on N, with |N| = n, attributes to player i the score

The Banzhaf scoring attributes to player i the score

Here is a first family of scorings which generalizes both the Shapley and the Banzhaf scorings. Let q be a vector whose components q(k), for k = 0, 1, . . . , n - 1, are positive 2 real numbers such that ∑n-1 k=0 q(k)(n-1 k ) = 1. A (regular) semivalue π(q) with parameter vector q attributes, for any given set function v, to player i the score

To build as in [Lucchetti et al., 2015] a more general family of scorings, let Λ be a family of positive real numbers pi(S), with i ∈ N and i /∈ S ⊂ N, called parameters, such that ∑S∈2N : i/∈S pi(S) = 1 for each player i. A (regular) probabilistic scoring rule with parameter family Λ attributes to player i the score

Any scoring rule π as in Equations (1), (2), (3), (4) is steady, that is, for the particular set function 1 mapping any coalition to 1, it assigns equal scores to all players. It is also linear in the sense that for all real numbers α1, α2 and set functions v1, v2 on N,

1 Authors often restrict here the set functions to games, and use terms as power indices, solutions or values instead of scorings.

2 By 'positive', we mean 'strictly positive'.

Figure 1 summarizes relations between different types of scorings.

2.3 Set Ordering and Player Ranking

Any set function v on N induces the set ordering on 2N which is the weak order ⊒v satisfying for S, T in 2N

Two set functions u and v on the same set N are ordinally equivalent if they induce the same set ordering on 2N . The equivalence class C(v) of v consists of all set functions u on N such that

There is thus a canonical bijection from equivalence classes of set functions to weak orders on 2N .

Any scoring π on N induces for any set function v a player ranking, which is the weak order ≿πv induced on N by the scores under π, that is, for i, j in N,

3 Stable Set Functions

When does the set ordering induced by a set function determine the player ranking for a given scoring? Let us first turn the question into the next formal problem, for a fixed set N of players.

Definition 1. Let π be a scoring. A set function v is π-stable when any set function ordinally equivalent to v produces under π the same player ranking as v does. We then also say that π is ordinally invariant for the set function v.

Problem 1. Given a scoring π on N, characterize the set functions on N that are π-stable.

Here is a kind of 'local' form of stability.

Definition 2. Let π be a scoring on N, and i, j two players in N. A set function v on N is two-player π-stable for i, j when for any set function u ordinally equivalent to v the comparison of the scores of i and j under π is the same for u as for v, that is

Many of our results on stability arise first for two-player stability; results on general stability follow then easily. Note also that two-player π-stability for players h, i with πh(v) ⩾ πi(v) together with two-player π-stability for players i, j with πi(v) ⩾ πj(v) implies two-player π-stability for h, j.

Remark 1. Let G (N) be the collection of all games on N. A solution on N is any mapping σ : G (N) → RN . Any solution σ on N extends to the scoring πσ : R2N → RN such that πσ (v) = σ(v - v(∅)), for all v ∈ R2N . A game w is two-player σ-solid for players i, j when for any game w′ ordinally equivalent to w there holds σi(w) ⩾ σj(w) exactly when σi(w′ ) ⩾ σj(w′ ). Note that the latter happens if and only if the set function w is two-player πσ -stable for i, j. Thus solidity reduces to stability, so we focus on the latter notion.

We start with the simple case in which there are only two players.

Proposition 1. When |N| = 2, any set function v on N is π(q) -stable for any semivalue π(q) with parameter vector q.

Proof. Let N = {i, j}. By Equation (3) we have

and thus

Now noteπ(q)

because q(0) and q(1) are positive. Thus the player ranking is determined by the coalition ordering.

The conclusion in Proposition 1 does not remain valid for all probabilistic scorings, as the next example shows.

Example 1. Let N = {a, b} and consider the probabilistic scoring πΛ with parameter family Λ given by

For real numbers α and β, the set function v specified by

leads to

The last quantity is negative for some choice of the numbers α and β, and positive form some other choice, with both choices satisfying β > α > 0. Thus v is not πΛ-stable.

Proposition 1 is no more satisfied if there are more than two players. For the Banzhaf scoring, the two set functions in Example 2 lead to opposite player rankings although the two set functions are ordinally equivalent.

Example 2. Let N = {a, b, c} and v be the set function specified by

For the Banzhaf scoring, the player rankings are a ≻Ban v b ≻Ban v c and c ≻Ban w b ≻Ban w a. Thus neither v nor w is Banzhaf-stable.

4 First Results

The next two propositions present two families of set functions which are stable for fairly general scorings.

Proposition 2. Any bivalued set function v on N is π-stable for any steady and linear scoring π (thus in particular for any probabilistic scoring, the Shapley scoring and the Banzhaf scoring).

Proof. Let v(2N ) = {α, β} with α > β. The set ordering ⊒v is a weak order with two equivalence classes (namely v-1 (α) and v-1 (β) with v-1 (α) ⊐v v-1 (β)). Thus the same must hold for any set function w ordinally equivalent to v. As a consequence, there exist some real numbers λ and µ, with λ > 0, such that w = λ v + µ 1. Linearity of π then gives

Because π is steady, πi(1) is independent of i. Thus v and w induce the same player ranking under π.

The following example (with only three distinct coalition worths) shows that when there are more than two worths assigned by a set function we can no longer guarantee the stability.

Example 3. Let N = {a, b, c}. Take any set function v on N with set ordering ⊒ satisfying {a, b, c} ≃ {a, b} ≃ {a, c} ⊐ {b, c} ≃ {c} ≃ {b} ⊐ {a} ≃ ∅. Letting α, β, γ respectively be the numbers assigned by v to the coalitions in the three equivalence classes, there must only hold α > β > γ. For any semivalue π(q) with parameter q, we then have

By setting β = 1 and γ = 0, and taking α > 1, with either α sufficiently close to 1 or sufficiently high, we obtain set functions ordinally equivalent to v, whose player rankings have either b or a before the other (details are left to the reader). Thus the monotone set function v is unstable for any semivalue.

The next Lemma and Proposition assume properties of set functions close to responsiveness 3 .

3 According to [Roth, 1985], a set function v satisfies responsiveness if and only if v({j}) ⩾ v({i}) ⇐⇒ v(S∪{j} ⩾ v(S∪{i}) for all i, j ∈ N and S ⊆ N \ {i, j}.

Lemma 1. Let i, j be players in N, let v be a set function on N and let π(q) be any semivalue. If for all S in 2S\{i,j} there holds v(S ∪ {j}) ⩾ v(S ∪ {i}), then π(q) j (v) ⩾ π(q) i (v). Moreover, if for at least one S the inequality is strict, then π(q) j (v) > π(q) i (v).

Proof. For any semivalue π(q) with parameter vector q we have

Both assertions immediately follow, because all numbers q(|S|) + q(|S| + 1) are positive.

Proposition 3. Let v be any set function satisfying the following double condition: for all i, j in N and S ∈ 2N\{i,j} ,

Then the set function v is π(q) -stable for any semivalue π(q) (thus in particular for the Shapley scoring and the Banzhaf scoring). Moreover the player ranking ≿π(q) v satisfies

However there are Banzhaf-stable games satisfying (9) which do not meet the double condition.

Proof. Assume that the set function v satisfies the double condition. Then for all i, j in N, by Lemma 1, v({i}) > v({j}) implies π(q) i (v) > π(q) j (v). Similarly, v({i}) = v({j}) implies π(q) i (v) = π(q) j (v) and v({i}) < v({j}) implies π(q) i (v) < π(q) j (v). Thus the player ranking ≿π(q) v satisfies Equation (9).

All set functions w ordinally equivalent to v also satisfy the double condition (where we substitute w for v). Therefore w satisfies Equation (9) when v is replaced with w. The first two assertions follow, because v and w induces the same ordering of one-element sets.

The game v in the following example is Banzhaf-stable and satisfies (9) for i = a and j = b, but not the double condition (indeed, v({a}) > v({b}) and v({a, c}) < v({b, c})).

5 Necessary and Sufficient Conditions for Two-player Stability

Until now we met some special cases guarantying stability of a set function for a linear scoring. Theorem 1 in this section delivers a necessary and sufficient condition for stability (again for a fixed set N of players).

Given any set function v on N and any coalition A, we define a binary set function vA by letting for S ∈ 2N

Fix a nondecreasing labelling of all coalitions

in the sense that

For 1 ⩽ k ⩽ 2n , we then write vk for the binary set function vSk . Thus vk(Sj) = 1 for all j ∈ {k, k + 1, . . . , 2n }, and vk(Sj) = 0 if and only if Sj ⊏v Sk.

Proposition 4. With the above notations, there holds the equality of set functions

Definition 3. We say that v1, v2, . . . , v2n are the binary set functions attached to the given set function v for the chosen, nondecreasing labelling of coalitions, and call the right-hand side of Equation (13) the corresponding binary set function decomposition of v or in short the binary decomposition of v.

Proposition 5. Given a set function v, select a nondecreasing labelling of all coalitions and form the corresponding decomposition of v in binary set functions v1, v2, . . . , v2n as in Equation (13). For any scoring π which is linear (in particular for all probabilistic scorings πΛ), there holds the equality of vectors in RN

Proof. Equation (14) follows from applying the linear mapping π to both sides of Equation (13).

Here is a necessary and sufficient condition for two-player stability, which ultimately relies only on the set ordering induced by v.

Theorem 1. Let v be a set function on N, π be a scoring on N which is steady and linear, and i, j be players in N. Then the two following conditions are equivalent, where vA is as in Equation (10):

(i) for all set functions u on N ordinally equivalent to v:

Proof. Let S1, S2, . . . , S2n be the sequence of coalitions labeled in such a way that v(S1) ⩽ v(S2) ⩽ . . . ⩽ v(S2n). For any set function u ordinally equivalent to v, notice u(S1) ⩽ u(S2) ⩽ . . . ⩽ u(S2n). So for k = 1, 2, . . . , 2n we can make vk = uk, where vk and uk are the binary set functions attached to v and u, respectively. Hence by Equation (14) together with πi(v1) = πj(v1) (because v1 is the constant mapping 1 and the scoring π is steady), we have

(16)

(⇐) Condition (ii) implies Condition (i) in view of Equation (17), because for k = 2, 3, . . . , 2n , both u(Sk) - u(Sk-1) ⩾ 0 and vk = vA for Sk = A.

(⇒) Proceeding by contradiction, assume Condition (i) and also πi(vA) < πj(vA) for some A ∈ 2N . Select the smallest k such that v(A) = v(Sk), then k > 1 and v(Sk-1) < v(Sk). Moreover, it is not restrictive to assume A = Sk (indeed, if v(Sk) = v(Sℓ), then vk = vℓ). So πi(vk) < πj(vk).

Let

then α ⩾ 0 (by the assumed Condition (i)) and β > 0. Define a new set function u by letting for S ∈ 2N

Then u is ordinally equivalent to v, and moreover for ℓ ̸= k

Then by Equations (17), (18), (19) and (16) successively

in contradiction with Condition (i).

Remark 2. Here is a straightforward variant of Theorem 1 for games (using terms and notations introduced in Remark 1). For a solution σ on N, the game w in G (N) is twoplayer σ-solid for players i, j if and only for all coalitions A in 2N :

(the wA's are the binary set functions attached to the set function w; note that the steadyness assumption is not needed anymore because πσ (1) = σ(0) = 0 by linearity of σ-here the first 0 is the null game, the second 0 is the origin in RN ).

We can easily turn Theorem 1 into a characterization of π-stability; in doing this, we do not need to require Condition (ii) for all players i and j (see after Definition 2).

It seems difficult to reformulate Condition (ii) in terms of v alone. To give more weight to the assertion, notice that any collection of distinct set functions vA is linearly independent in the real vector space R2N , therefore we can let the linear mapping π assign any score vectors to distinct vA's.

For any players i and j, Theorem 1 particularized to any semivalue π delivers technically simpler conditions equivalent to two-player π-stability for i and j. However, the resulting conditions involve all images of v. To the contrary, Equation (8) shows that only the images by v of sets containing exactly one of i and j suffice to test two-player π-stability for i and j. It is exploided in the next section to provide better conditions for two-player stability.

6 Two-player Stability for a Semivalue

For two given players i and j, the next theorem characterizes the two-player stability for i and j for the Banzhaf scoring: after the numbers v(S ∪ {i}), for S ∈ 2N\{i,j} , are sorted in nondecreasing order, and similarly the numbers v(S ∪ {j}) are sorted in nondecreasing order, we have that the k-th v(S ∪ {i}) is not larger than the k-th v(S ∪ {j}). Theorem 3 provides the extension of the result to semivalues, with a more technical condition involving the parameters of the semivalue.

Theorem 2. Let v : 2N → R be a set function, and i, j be players in N. Then the three following conditions are equivalent for the Banzhaf scoring πBan :

• (i) πBan i (u) ⩽ πBan j (u), for all set functions u ordinally equivalent to v;
• (ii) let x1 ⩽ x2 ⩽ . . . ⩽ x2n-2 be the sequence of 2n-2 numbers v(S ∪ {i}) written in nondecreasing order, where S ∈ 2N\{i,j} , and similarly let y1 ⩽ y2 ⩽ . . . ⩽ y2n-2 be the sequence of 2n-2 numbers v(S ∪ {j}) written in nondecreasing order; then

(iii) for each S in 2N\{i,j} there holds

Proof. By Equation (8), πBan j (v) -πBan i (v) is equal to

the last equality holds because its sides are each a rewriting of 1 2n-2 (∑2n-2 ℓ=1 yℓ - ∑2n-2 ℓ=1 xℓ).

(ii) ⇒ (i) Let f : R → R be a strictly increasing function such that u(S) = f (v(S)) for all S in 2N . The (nondecreasingly) sorted sequence of numbers u(S ∪ {i}), for S ∈ 2N\{i,j} , coincides with the nondecreasing sequence of the f(xℓ)'s. Similarly the sorted sequence of numbers u(S ∪{j}), for S ∈ 2N\{i,j} , coincides with the nondecreasing sequence of the f(yℓ)'s. Then by replacing v with u in (21) we obtain

From (ii) and the nondecreasingness of f there follows f(yℓ) - f(xℓ) ⩾ 0, and thus (i).

(i) ⇒ (ii). Proceeding by contraposition, assume (ii) does not hold. Take the smallest k such that yk < xk. Then

Now for any positive real number M define the strictly increasing function f : R→R by letting

Then

In view of (22), the number of (index values) ℓ's such that xℓ ⩽ yk equals k - 1. Let m be the number of ℓ's such that yℓ ⩽ yk; then by (23) we have m ⩾ k (note that yk = yk+1 could happen). By subtracting from each of k - 1 and m the number of ℓ's such that both xℓ ⩽ yk and yℓ ⩽ yk, we derive that the number of ℓ's such that xℓ ⩽ yk < yℓ minus the number of ℓ's such that yℓ ⩽ yk < xℓ equals (k - 1) -m. Hence

where (k - 1) - m < 0. With M large enough, both sides become strictly negative. This establishes the negation of (i), because for the set function u = f ◦ v we now derive πBan j (u) -πBan i (u) < 0 from Equation (21) rewritten for u in place of v.

(ii) ⇐⇒ (iii) Because the xℓ's are the sorted v(S ∪{i})'s, and the yℓ's are the sorted v(S ∪ {j})'s, the equivalence of (ii) and (iii) is easily established.

We now aim at generalizing Theorem 2 to semivalues. Let π(q) be a semivalue with parameter vector q, and set q′ (s) = q(s) + q(s + 1). For any S0 in 2N\{i,j} , define successively (with ⊑v denoting as before the set ordering induced by v)

Note that the quantity Dπ(q) i,j (⊑u, S0) takes the same value for all set functions u ordinally equivalent to v.

Theorem 3. Let π(q) be a semivalue with parameter vector q, let i, j be two players, and let v be a set function for which

Then the two following conditions are equivalent:

(i) for all u ∈ R2N ordinally equivalent to v:

Proof. The proof relies on two lemmas (requiring one and half more page) which we present in a supplementary document for sake of clarity.

7 Conclusion

We define ordinal stability of a set function with respect to any given scoring rule (thus covering also games and socalled power index, solution or value). Stability captures coalitional situations that are more robust to possible fluctuations in the data, and for which the accuracy in determining the precise worths of coalitions is less crucial for the correct computation of the players' ranking. For any semivalue, we show that (i) a set function on a two-player set is stable (Proposition 1), and (ii) all bivalued set functions are stable (Proposition 2). Our main contributions are twofold. First we characterize stability for any given steady and linear scoring, by relying on a special decomposition of any set function. Theorem 1 covers in particular semivalues, with the Banzhaf and Shapley scorings as particular cases. Second, for semivalues, Theorem 3 provides an improved characterization of stability. It shows the operational advantage to build, for any two players i and j, a fixed set of coalitions from ordinal comparisons of coalitions (namely, T + i,j and T - i,j in Section 6). Then, to verify the stability of the relative rankings of the players i and j for any proposed semivalue π, it suffices to check nonnegativity of algebraic sums of semivalue parameters (Condition (ii) in Theorem 3).

In future research, it would be interesting to explore the ordinal stability of coalitional games for solutions which are not semivalue-like, for instance, the nucleolus [Schmeidler, 1969] or other power indices for simple games which are based on minimal winning coalitions [Deegan and Packel, 1978; Holler, 1982]. Another potential generalization of our ordinal framework integrates restricted possibilities of cooperation [Myerson, 1977] and calls for an investigation of their impact on the stability of the player ranking with respect to a power index.

Acknowledgements

We acknowledge a financial support from the project THEMIS ANR-20-CE23-0018 of the French National Research Agency (ANR).