An Ordinal Banzhaf Index for Social Ranking

1 Introduction

In decision making and social choice theory, a number of studies are devoted to ranking individuals based on the performance of the coalitions formed by them. For instance, in cooperative game theory, (marginalistic) power indices like the Banzhaf value [Banzhaf III, 1964] and the Shapley value [Shapley, 1953] are defined to measure the importance of individuals based on their marginal contributions to all possible coalitions of players. Such methods can be used in a variety of applications, such as, comparing the influence of different countries inside an international council (for instance, the European Union Council); or finding the most "valuable" items, when the preferences of a user are defined over their combinations.

However, in many real world applications, a precise evaluation on the coalitions' "power" may be hard for many reasons (e.g., uncertain data, complexity of the analysis, missing information or difficulties in the update, etc.). In this case, it may be interesting to consider only ordinal information concerning binary comparisons between coalitions.

The main objective of this paper is to study the problem of finding an ordinal ranking over the set N of individuals (called social ranking), given an ordinal ranking over its power set (called power relation).

∗This work has been supported by the project ANR-14CE240007-01 "CoCoRICo-CoDec".

Example 1. Consider the total and transitive power relation ⪰ such that:

Our aim is to answer the questions of type: does individual 1 have more influence than individual 2?

Despite the huge number of papers about cooperative games and their solutions as well as their extensions to games with imprecise valuation of coalitions (for more information see, for instance, [Suijs et al., 1999; Branzei et al., 2010; Marichal and Roubens, 1998]), a notion of ordinal power index has been introduced only recently in the literature in terms of a classical solution concept for cooperative games that is also invariant to the choice of the characteristic function representing the ranking over the coalitions [Moretti, 2015]. However, this invariant solution is properly defined for a very limited class of total preorders over the set of all coalitions.

Following a property-driven approach, in [Moretti and ¨Ozt¨urk, 2017] the authors provide some impossibility theorems showing that no ordinal power index, also called social ranking solution, satisfies a given set of attractive properties. Also in [Bernardi et al., 2017], the authors axiomatically characterize a social ranking solution based on the idea that the most influential individuals are those which belong to coalitions ranked in the highest positions. Another social ranking solution has been proposed and studied in [Haret et al., 2018], where two individuals are ranked using information from ceteris paribus (i.e., everything else being equal) comparisons over all possible coalitions. The resulting ranking, called CP-majority, is not necessarily transitive. So, a domain restriction over the family of ranking of coalitions is proposed in [Haret et al., 2018] to guarantee the transitivity of the ranking over the individuals. We also notice that the social ranking problem can be seen as the inverse formulation of the well-known problem from the literature of deriving a ranking over the set of all subsets of N, in a compatible way with a primitive ranking over the single elements of N. This problem is generally called ranking sets of objects (see [Barber`a et al., 2004] for a survey).

In this article, we propose a new social ranking solution based on an ordinal version of the notions of marginal contribution and of Banzhaf value [Banzhaf III, 1964]. For this solution, we provide an axiomatic characterization that is mostly inspired from the axioms used in [Haret et al., 2018] to characterize the CP-majority solution on a set of only two individuals. Both the CP-majority and the ordinal Banzhaf solution suggest an interpretation of our social ranking problem along the lines of a virtual election, with groups of individuals (coalitions) playing the role of voters: according to the CP-majority solution, a coalition S prefers individual i to individual j if S ∪ {i} ⪰ S ∪ {j}, i.e. coalition S ∪ {i} is "stronger" than coalition S ∪ {j}; according to the ordinal Banzhaf solution, coalition S approves an individual i if S ∪ {i} ⪰ S, i.e. the marginal contribution of i to S ∪ {i} is positive. Under this interpretation, we propose a new family of relations on the elements of N that we call weighted majority relations, and we show that the CP-majority and the ordinal Banzhaf solution are special cases of this family.

The remaining of the paper is organized as follows. Section 2 introduces basic notions and notations. Section 3 is devoted to the definition of the ordinal Banzhaf relation and its main features as a social ranking solution. Section 4 is devoted to the discussion of an axiomatic characterization of the ordinal Banzhaf solution and to its comparison with the CP-majority. Section 5 introduces weighted majority rules. Section 6 concludes the paper.

2 Preliminaries

Let N = {1, . . . , n} be a finite set of elements or individuals and let R ⊆ N × N be a binary relation on N (xRy meaning that x is in relation R with y, for x, y ∈ N). A binary relation R on N is said to be: reflexive, if for each i ∈ N, iRi; transitive, if for each i, j, z ∈ N, (iRj and jRk) ⇒ iRk; total, if for each i, j ∈ N, i ̸= j ⇒ iRj or jRi; antisymmetric, if for each i, j ∈ N, iRj and jRi ⇒ i = j. A preorder is a reflexive and transitive binary relation. A preorder that is total is called total preorder. An antysimmetric total preorder is called linear order (each equivalence class is a singleton). We denote by T (N) the set of all total preorders on N, and by L(2N ) the set of all linear orders on 2N . Following the notations in [Haret et al., 2018], a power relation is a binary relation ⪰∈ B(2N ) where B(2N ) is the family of all subsets of 2N ×2N . For all S, T ∈ 2N , S ≻ T means that (S, T) ∈⪰ and (T, S) /∈⪰ and S ∼ T means that (S, T) ∈⪰ and (T, S) ∈⪰. A social ranking solution or solution on A ⊆ N, is a function RA : C ⊆ B(2N ) -→ T (A) associating to each power relation ⪰∈ C a total preorder RA(⪰) (or R⪰ A ) over the elements of A. By this definition, the notion iR⪰ A j means that applying the social ranking solution to the power relation ⪰ gives the result that i is ranked higher than or equal to j. Since R⪰ A is a total preorder, we denote by I ⪰ A its symmetric part, and by P ⪰ A its asymmetric part. We denote by Ui = {S ∈ 2N : i /∈ S} the set of coalitions without i and by Uij = {S ∈ 2N : i, j /∈ S} the set of coalitions not containing neither i nor j.

Finally, we provide few well-known definitions from game theory. A Transferable Utility (TU)-game is a pair (N, v) where v is a function v : 2N → R such that v(∅) = 0. The Banzhaf value β(v) of v is the n-vector β(v) =

(β1(v), β2(v), . . . , βn(v)), such that for each i ∈ N:

3 Ordinal Banzhaf Index

We start by showing that the Banzhaf value defined in equation 2 is very sensible to small changes on the values of v.

Consider a situation where a complete ranking over the subsets of N is given. For instance, take the power relation on 2{1,2,3} such that 123 ≻ 12 ≻ 1 ≻ 23 ≻ 2 ≻ 13 ≻ 3 ≻ ∅. If a real-valued function is available representing the "strength" of each coalition on a numerical scale such that S ⪰ T ⇔ v(S) ≥ v(T), it would be possible to compare the social ranking (power) of individuals 1 and 2 using the Banzhaf value of v. It is easy to check that the difference of Banzhaf values βi(v) - βj(v) for each i, j, k ∈ {1, 2, 3} can be written as follows:

One can verify that the difference β1(v)-β2(v) can be made positive or negative with a suitable choice of v compatible with the constraint v(1) > v(23) > v(2) > v(13). For instance, consider the functions v′ and v′′ such that v′ (1) = 4, v′ (23) = 3, v′ (2) = 2, v′ (13) = 1 + ϵ and v′′ (1) = 4, v′′ (23) = 3, v′′ (2) = 2, v′′ (13) = 1 - ϵ, with 1 > ϵ > 0. Both v′ and v′′ satisfy the aforementioned constraints, but according to relation (3), β1(v′ ) > β2(v′ ) and β2(v′′ ) > β1(v′′ ), even for very small ϵ. In order to get more robust results to evaluate individuals, our goal is to introduce a social ranking solution inspired from the classical notion of Banzhaf value.

We begin with the notion of ordinal marginal contribution.

Definition 1 (Ordinal marginal contribution). Let ⪰∈ B(2N ). The ordinal marginal contribution mSi (⪰) of player i w.r.t. coalition S, i /∈ S, in power relation ⪰ is defined as:

Example 2. Consider the power relation ⪰ of Example 1. In ⪰, the ordinal marginal contribution of individual 2 w.r.t. coalition 134, m134 2 (⪰), is equal to 1 since 1234 ≻ 134 holds. However the ordinal marginal contribution of individual 2 w.r.t. coalition 4, m42 (⪰) , is -1 due to 4 ≻ 24.

We denote by u+,⪰ i (u-,⪰ i ) the number of coalitions S ∈ Ui such that mSi (⪰) = 1 (mSi (⪰) = -1). We also refer to the difference s⪰i = u+,⪰ i - u-,⪰ i as the ordinal Banzhaf score of i in ⪰.

Definition 2 (Ordinal Banzhaf relation). Let ⪰∈ B(2N ) and A ⊆ N. The ordinal Banzhaf relation is the binary relation ˆR⪰ A ⊆ A×A such that for all i, j ∈ A:

Remark 1. From the definition of ordinal Banzhaf score, it immediately follows that the relation ˆR⪰ A on A ⊆ N is transitive and total. So, ˆR⪰ A is a social ranking solution.

Example 3. Consider the power relation of Example 1 and let A = {1, 2}. We have

and

Ordinal marginal contributions and ordinal Banzhaf scores of individuals 1 and 2 are reported in Table 1. Since s⪰2 = -2 > -4 = s⪰1 , it follows 2 ˆ P ⪰ A 1.

Example 4. Consider 123 ≻ 12 ≻ 1 ≻ 23 ≻ 2 ≻ 13 ≻ 3 ≻ ∅ given at the beginning of this section. Let A = {1, 2} be the set of elements to be ranked. We have that m∅1 = m21 = m31 = m23 1 = 1 and m∅2 = m12 = m32 = m13 2 = 1. So, s⪰1 = s⪰2 = 4 and, according to the ordinal Banzhaf relation, 1 and 2 are indifferent, i.e. 1ˆ I ⪰ A 2.

As shown in the previous example, given a linear order relation ⪰ on 2N , the social ranking provided by the ordinal Banzhaf relation does not depend on the choice of a compatible cardinal function v, and therefore it answers to the initial question of this section concerning robustness. Another natural question is whether it always exists a cardinal evaluation v compatible with ⪰, such that the ranking provided by the classical Banzhaf value on v coincides with the ranking provided by the ordinal Banzhaf relation on ⪰. A negative answer to this question follows from Example 5.

Example 5. Consider the power relation ⪰ such that 123 ≻ 12 ≻ 1 ≻ 23 ≻ 3 ≻ 13 ≻ 2 ≻ ∅. Let A = {1, 2} be the set of elements to be ranked. Consider every compatible cardinal function v such that v(S) ≥ v(T) ⇔ S ⪰ T for each S, T ∈ 2N . By relation (3) we have that

Since v(1) - v(2) > v(23) - v(13), we have that β1(v) > β2(v) (independently from the choice of v). On the other hand m∅1 = m21 = m23 1 = 1 and m31 = -1, whereas m∅2 = m12 = m32 = m13 2 = 1. So, s⪰1 = 2 and s⪰2 = 4. Then, according to the ordinal Banzhaf relation, 2 is strictly better than 1, i.e. 2 ˆ P ⪰ A 1, yielding an opposite conclusion with respect to the classical Banzhaf value for every compatible function v.

4 Axiomatic Analysis

In this section, we introduce a set of axioms which are inspired from those in classical social choice theory [May, 1952] and in the axiomatic approach presented in [Haret et al., 2018].

The first property requires that any permutation of coalitions that preserves the sign of the ordinal marginal contributions of individuals should not affect the social ranking. So, a positive (negative) ordinal marginal contribution to distinct coalitions S and T should carry the same weight.

Definition 3. (Coalitional Anonymity, CA) Let A ⊆ N. A solution RA : C ⊆ B(2N ) → T (A) satisfies the coalitional anonymity axiom on C if and only if for all power relations ⪰ ,⊒∈ C, for all players i, j ∈ A and bijections πi : Ui → Ui and πj : Uj → Uj such that S ∪ {i} ⪰ S ⇔ πi (S) ∪ {i} ⊒ πi (S) for all S ∈ Ui and S ∪ {j} ⪰ S ⇔ πj (S) ∪ {j} ⊒ πj (S) for all S ∈ Uj, then it holds that iR⪰ A j ⇔ iR⊒ A j.

The second axiom is a classical neutrality axiom, and it states that a social ranking solution should not be biased in favor of one alternative. So, if the names of players i and j are reversed, the ranking of players i and j must also be reversed. Before introducing its definition, we need some further notation. Let σ : N → N be a bijection. For a set S = {i, j, k, ..., t} ⊆ N, we denote the image of S through σ σ(S) = {σ(i), σ(j), σ(k), ..., σ(t)}.

Definition 4. (Neutrality, N) Let A ⊆ N. A solution RA : C ⊆ B(2N ) → T (A) satisfies the neutrality axiom on C if and only if for all power relations ⪰,⊒∈ C and each bijection σ : N → N such that σ(A) = A and S ⪰ T ⇔ σ(S) ⊒ σ(T) for all S, T ∈ 2N , then it holds that iR⪰ A j ⇔ σ(i)R⊒ A σ(j) for every i, j ∈ A.

Next axiom says that a social ranking solution needs to be coherent with the modifications on the performance of different coalitions. Therefore, suppose that in a given power relation, the solution ranks player i higher or indifferent to j. If the power relation remains the same for all coalitions except one that becomes in favor of i, then the solution must rank player i strictly better than j.

Definition 5. (Monotonicity, M) Let A ⊆ N. A solutionRA : C ⊆ B(2N ) → T (A) satisfies the monotonicity axiom on C if and only if for all power relations ⪰,⊒∈ C and i, j ∈ A such that:

• there exists a coalition S ∈ Ui such that S ≻ S ∪ i and S ∪ i ⊐ S, and
• T ∪ i ≻ T ⇔ T ∪ i ⊐ T and T ∪ j ≻ T ⇔ T ∪ j ⊐ T for all the other coalitions T ∈ 2N , T ̸= S,

The following theorem shows that the ordinal Banzhaf solution is the unique solution that satisfies the previous three axioms on the family of linear orders L(2N ).

Theorem 1. Let A ⊆ N. A solution RA : L(2N ) → T (A) is the ordinal Banzhaf solution if and only if it satisfies the three axioms CA, N and M on L(2N ).

Proof. (⇒) First, we prove that the ordinal Banzhaf solution ˆRA, satisfies the three axioms N, CA and M on L(2N ). It is straightforward to see that ˆRA satisfies the N axiom (just notice that the value s⪰i is independent of the individuals' labels, for all i ∈ A and ⪰∈ L(2N ))).

Consider two power relations ⪰,⊒∈ L(2N ) such that for all individuals i, j ∈ A the following conditions hold:

1. There exists a bijection πi : Ui →Ui with S ∪i ≻ S ⇔ πi (S) ∪ i ⊐ πi (S) for all S ∈ Ui;
2. ii) there exists a bijection πj : Uj →Uj with S∪j ≻ S ⇔ πj (S) ∪ j ⊐ πj (S) for all S ∈ Uj .

We first show that it holds i ˆR⪰ A j ⇔ i ˆR⊒ A j. Since condition (i) holds it means that there is a bijection from the set of coalitions S ∈ Ui with mSi (⪰) = 1 (mSi (⪰) = -1) to the set of all S ∈ Ui with mSi (⊒) = 1 (mSi (⊒) = -1). Moreover, from condition (ii) it also follows that there exists a bijection from the set of S ∈ Uj with mSj (⪰) = 1 (mSj (⪰) = -1) to the set of all S ∈ Uj with mSj (⊒) = 1 (mSj (⊒) = -1). Then we have that

and

that directly imply

By conditions (i) and (ii) and relation (5) it follows that ˆRA

satisfies the property of coalitional anonymity (CA). Finally, consider two power relations ⪰, ⊒∈ L(2N ) and suppose that for any two individuals i, j ∈ A the following conditions hold:

• iii) there exists a coalition S ∈ Ui such that S ≻ S ∪ i and S ∪ i ⊐ S
• iv) T ∪ i ≻ T ⇔ T ∪ i ⊐ T and V ∪ j ≻ V ⇔ V ∪ j ⊐ V for all the other coalitions T ∈ Ui, T ̸= S, and V ∈ Uj .

We want to prove that i ˆR⪰ A j ⇒ i ˆ P ⊒ A j. According to condition (iii) and (iv), we have that

and

Moreover, if i ˆR⪰ A j, by definition of ordinal Banzhaf score, we have that

Then, by relations (6), (7) and (8) it immediately follows that

which means that i ˆ P ⊒ A j.

(⇐) We have to prove that if a solution RA satisfies axioms CA, N and M on L(2N ) then it is the ordinal Banzhaf solution ˆRA, i.e. iR⪰ A j ⇔ s⪰i ≥ s⪰j for all ⪰∈ L(2N ) and i, j ∈ A.

We start showing that if RA satisfies axioms CA and N on L(2N ), then for all ⪰∈ L(2N ) and i, j ∈ A such that s⪰i = s⪰j , we have that iI ⪰ A j.

Consider a power relation ⪰∈ L(2N ) with s⪰i = s⪰j , for some i, j ∈ A. By Remark 1 and by the fact that there are no indifferences in the power relation, we also have that

Now, consider another power relation ⊒ such that for all S, T ∈ 2N ,

where σ : N → N is a bijection with σ(i) = j, σ(j) = i and σ(k) = k for all k ∈ A, k ̸= i and k ̸= j. By axiom N it holds that

Moreover, by construction of ⊒, it holds that

Then it is easy to define a bijection πi : Ui → Ui such that S ∪ i ≻ S ⇔ πi (S) ∪ i ⊐ πi (S) for all S ∈ Ui (defining a one-to-one correspondence between elements S ∈ Ui with mSi (⊒) = 1 and those with mSi (⪰) = 1, and a one-toone correspondence between S ∈ Ui with mSi (⊒) = -1, and those with mSi (⪰) = -1) and, in a similar way, another bijection πj : Uj →Uj such that S∪j ≻ S ⇔ πj (S)∪j ⊐ πj (S) for all S ∈ Uj . Therefore, from the CA axiom, we have that

From relation (11) and (13), and since RA is total, it immediately follows that

Now, consider a power relation ⪰∈ L(2N ) such that q = u+,⪰ i > u+,⪰ j = p for some integer numbers p and q ∈ {0, 1, . . . , 2n-1 }. One can opportunely rearrange the relation ⪰ within each set {S ∪ ij, S ∪ i, S ∪ j, S} for all S ∈ Uij to obtain a new power relation ⪰′∈ L(2N ) such that u+,⪰′ i = u+,⪰′ j = p (for instance, just taking q -p coalitions S ∈ Uij, with S ∪ ij ≻ S ∪ i or S ∪ j ≻ S and inverting the relation). Then, since RA satisfies both N and CA, we have that iI ⪰′ A j. Using a similar argument, and restoring precisely one of the previously changed comparison to move from ⪰ to ⪰′ , we can now form another power relation ⪰′′ with u+,⪰′′ i = p+1 and u+,⪰′ j = p. By the M axiom of RA we have now that iP ⪰′′ A j. By applying this procedure a sufficient number of times, it is then possible to reconstruct the power relation ⪰ from ⪰′ in q -p steps, and by the application of the M axiom of RA at each step, we can conclude that iP ⪰ A j.

Remark 2. In the claim of Theorem 1, it is possible to substitute the domain of linear orders L(2N ) with the larger domain of power relations C ⊆ B(2N ) such that for each ⪰∈ C, i, j ∈ A and all S ∈ Uij the following two conditions hold: c.1) ⪰ is transitive and total on {S∪ij, S∪i, S∪j, S}; c.2) only strict comparisons hold, i.e. for all A,B ∈ {S ∪ ij, S ∪ i, S ∪ j, S}, A ̸= B, we never have A ∼ B.

We devote the remaining of this section to the comparison of some fundamental features of the CP-majority relation introduced in [Haret et al., 2018] and the ordinal Banzhaf solution. We first need to define some further notations. The set of all coalitions S ∈ Uij for which S ∪ i ≻ S ∪ j (CPcomparison) is denoted by Dij(⪰). In addition, the cardinality of the set Dij(⪰) is denoted by dij(⪰).

Definition 6 (CP-Majority [Haret et al., 2018]). Let ⪰∈ B(2N ) and A ⊆ N. The Ceteris Paribus (CP-) majority relation is the binary relation ¯R⪰ A ⊆ N ×N such that for all i, j ∈ N:

Example 6. Consider the power relation defined in Example 1. Table 2 shows the CP-comparisons between 1 and 2. It holds that 1 ¯ P ⪰ A 2 (d12(⪰) = 3 and d21(⪰) = 1) according to the CP-majority relation, whereas 2 ˆ P ⪰ A 1 according to the ordinal Banzhaf one (see Table 1).

We recall two axioms introduced in [Haret et al., 2018]. The first one states that the social ranking of i and j should only depend on their relative positions in the power relation across all coalitions, regardless of the number and the identity of coalitions' members.

Definition 7 (Equality of Coalitions, EC). Let A ⊆ N. A solution RA : C ⊆ B(2N ) -→ T (A) satisfies the Equality of Coalitions (EC) axiom on C if and only if for all power relations ⪰,⊒∈ C, i, j ∈ A and bijection π: 2N\{i,j} → 2N\{i,j} such that S ∪ {i} ⪰ S ∪ {j} ⇔ π(S) ∪ {i} ⊒ π(S) ∪ {j} for all S ∈ Uij, it holds that iR⪰ A j ⇔ iR⊒ A j.

The second axiom from [Haret et al., 2018], states that if two elements i and j are indifferent in the social ranking over a power relation, a single change in the power relation in favor of i determines a new social ranking also favorable to i.

Definition 8 (Positive Responsiveness, PR). Let A ⊆ N. A solution RA : C ⊆ B(2N ) -→ T (A) satisfies the Positive Responsiveness (PR) axiom on C if and only if for all power relations ⪰,⊒∈ C, i, j ∈ A with iR⪰ A j and such that for some T ∈ Uij , [T ∪ {i} ∼ T ∪ {j} and T ∪ {i} ⊐ T ∪ {j}], or, [T ∪ {j} ≻ T ∪ {i} and T ∪ {i} ≃ T ∪ {j}] and for all S ∈ Uij with S ̸= T , S∪{i} ⪰ S∪{j} ⇔ S∪{i} ⊒ S∪{j}, it holds that iP ⊒ A j.

As shown in [Haret et al., 2018], if |A| = 2, the following axiomatic characterization of the CP-majority holds true.

Theorem 2 ([Haret et al., 2018]). Let A = {i, j} ⊆ N be a set with only two elements. A solution RA : B(2N ) -→ T (A) associates to each ⪰∈ B(2N ) the corresponding CP-majority relation ¯R⪰ ∩A×A if and only if it satisfies axioms EC, N and PR on B(2N ).

Remark 3. Note that the two axiomatic characterizations in Theorem 1 and 2 show two important differences:

1. As extensively discussed in [Haret et al., 2018], the CPmajority relation, is not necessarily transitive, if |A| > 2, whereas the ordinal Banzhaf solution yields a transitive relation over the elements of A, for any A ⊆ N.
2. ii) The axiomatic characterization for the CP-majority solution holds true over the domain of all binary relations B(2N ), while the one for the ordinal Banzhaf solution applies to the restricted domain of linear orders L(2N ) (or the larger one defined in Remark 2).

Even if the CP-majority solution and the ordinal Banzhaf one may rank individuals in a very different manner (see, for instance, Example 6), they share some fundamental similarities, at least over sets with only two elements.

First, for both Theorem 1 and 2, the same neutrality axiom is used. Actually, the axiom of neutrality as introduced in this paper implies, on the same domain C ⊆ B(2N ), the axiom of neutrality used in [Haret et al., 2018], that only considers the particular bijection σ : N → N such that for i, j ∈ N, σ(i) = j and σ(j) = i, and σ(k) = k for all k ∈ N \ {i, j}.

In addition, for the ordinal Banzhaf solution, the CA axiom plays a role similar to the one played by the EC axiom for the CP-majority: the social ranking must be invariant with respect to particular permutations of coalitions. However, how coalitions are permuted is different in the two axioms, focusing on permutations preserving the number of CPcomparisons in the EC axiom, and on permutations preserving the number of positive and negative ordinal marginal contributions in the CA one.

Finally, the PR axiom for the CP-majority solution and the M axiom for the ordinal Banzhaf solution follow a similar principle for breaking ties in favour of individuals that improve their position. However, there are two main differences here: first, in the CP-majority, we consider improvements on CP-comparisons, while for the ordinal Banzhaf solution we consider improvements on ordinal marginal contributions; second, due to the domain restriction on L(2N ), the possibility to have indifference is not considered for the characterization of the ordinal Banzhaf solution.

A further similarity between the two solutions is discussed in the next section, where the ordinal Banzhaf solution and the CP-majority are presented as two special cases of a new family of weighted majority relations.

5 WeightedMajority Relations

We start by rewriting the definition of CP-majority as follows. Let A ⊆ N and i, j ∈ A. Then,

where

for all S ∈ Uij . We can generalize this definition, to any nonnegative linear combination of the terms ¯ dSij , for all S ∈ Uij.

Definition 9 (Weighted majority relation). Let ⪰∈ B(2N ), A ⊆ N and let w = [wS ij ]i,j∈A,S∈2N :i,j/∈S be a weight scheme such that wS ij ≥ 0 for all i, j ∈ A and S ∈ Uij. The weighted majority relation associated to w is the binary relation R⪰,w A ⊆ A×A such that for all i, j ∈ A ⊆ N:

Obviously, if wS ij = 1 for all i, j ∈ A and S ∈ Uij, then we get the CP-majority, i.e. R⪰,w A = ¯R⪰ A .

Example 7. Consider the power relation (1). Let A = {1, 2} and consider a weight scheme ¯w where ¯wS 12 = |S| + 1 for each S ∈ U12, as shown in Table 3. We have that 1P ⪰, ¯w A 2, since ∑S∈U12 ¯wS 12 ¯ dS12 (⪰) = 1 + 2 + 2 - 3 = 2 > 0.

Definition 10 (Bz-distance). Let ⪰∈ L(2N ), i, j ∈ N and let S ∈ Uij . The Banzhaf (Bz-) distance between i and j with respect to S is denoted by ˆw = [ ˆwS ij (⪰)]i,j∈A,S∈Uij and is defined as the cardinality of an intersection as follows:

Note that ˆwS ij (⪰) is just the number of S and S∪ij between S ∪ i and S ∪ j in the power relation ⪰. For instance, if we have S ∪ 1 ≻ S ∪ 12 ≻ S ∪ 2 ≻ S, then ˆwS 12 (⪰) =1 and if we have S ∪ 3 ≻ S ≻ S ∪ 34 ≻ S ∪ 4, then ˆwS 34 (⪰) =2.

Remark 4. Notice that the Bz-distance ˆwS ij (⪰) is a welldefined metric: it can only take values 0,1, or 2 (nonnegativity); ˆwS ii (⪰) = 0 (identity); ˆwS ij (⪰) = ˆwS ji (⪰) (symmetry); ˆwS ik (⪰) ≤ ˆwS ij (⪰)+ ˆwS jk (⪰) for all S ∈ 2N with i, j, k ∈ S (triangle inequality).

We are now ready to prove that the weighted majority relation based on the Bz-distance is equivalent to the ordinal Banzhaf solution.

Theorem 3. Let ⪰∈ L(2N ) and A ⊆ N. We have that

Proof. We have to prove that for all i, j ∈ A

First note that we can rewrite the difference of ordinal Banzhaf scores s⪰i - s⪰j as follows

Consider all coalitions S ∈ Uij such that ¯ dSij (⪰) = 1 as reported in Table 4 (the case ¯ dSij (⪰) = -1 is very similar). It follows that

Therefore, we have that ∑S∈Uij ˆwS ij ¯ dSij (⪰) ≥ 0 iff s⪰i ≥ s⪰j , which concludes the proof.

We showed that the CP-majority and the ordinal Banzhaf solution belong to the family of weigthed majority relations. Note that one can obtain other members of this family by assigning other non-negative real values to a weight scheme such (for instance, the size of coalitions, etc.).

6 Conclusion

In this paper we have studied the problem of ranking individuals given an ordinal ranking over the set of coalitions formed by them. Following the analogy with cooperative games, we have extended the classical notion of Banzhaf value to our ordinal framework. We have analyzed the ordinal Banzhaf solution using a property-driven approach and we have compared its fundamental features with the ones of another solution from the literature, the CP-majority relation. Finally, we have introduced a new family of relations over the set of individuals that includes the ordinal Banzhaf solution and the CP-majority one, and many others.

Since we have characterized the ordinal Banzhaf solution over the domain of all linear orders, as a direction for future work it would be interesting to investigate how the ordinal Banzhaf solution can be extended to other families of power relations, and to see which axioms characterize this solution on a those classes. Another open problem is to study and axiomatically characterize ordinal versions of other semivalues [Carreras et al., 2003] like, for instance, the Shapley value [Shapley, 1953].