Ceteris paribus majority for social ranking

1 Introduction

The design of procedures aimed at ranking individuals according to how they behave in various groups is of great importance in many practical situations. The problem occurs in a variety of scenarios coming from social choice theory, cooperative game theory or multiattribute decision theory, and examples include: comparing researchers in a scientific department by taking into account their impact across different teams; finding the most influential political parties in a parliament based on past alliances within alternative majority coalitions; rating attributes according to their influence in a multiattribute decision context, where independence of attributes is not verified because of mutual interactions (see [Bouyssou and Marchant, 2007] for a discussion on winning coalitions of criteria, [Boutilier et al., 2011] for CP-nets concerned by qualitative conditional dependence and independence of preference statements under a ceteris paribus interpretation).

In such situations, as in many others, the worth of each group (or coalition) is, in general, hardly quantifiable, with the only available information about the relative strength of groups being purely ordinal. Therefore, the main objective of this paper is to provide an answer to the general question of how to obtain a ranking over a finite set N (called a social ranking), given a ranking over the elements of the power set 2N (called a power relation). Following earlier work on the topic [Moretti and ¨Ozt¨urk, 2017], we will call a map from the power relation to a social ranking a social ranking solution.

Example 1. Consider a scientific department with five individuals N = {1, 2, 3, 4, 5} and the following power relation, given by the performance of different teams based on their past research activities: 2345 ≻ 245 ≻ 1234 ≻ 13 ≻ 12 ≻ 23 ≻ 145 ≻ 35 ≻ 24 ≻ 14. 1 Imagine that two candidates, say 1 and 2, are up for an award. We are interested in how to choose between 1 and 2 when the only given information is the power relation ≻.

To the best of our knowledge, the issue was first introduced in [Moretti and ¨Ozt¨urk, 2017], where social ranking solutions were studied following a property-driven approach. Within the same framework, [Bernardi et al., 2017] axiomatically characterized a social ranking solution based on the idea that the most influential individuals are those appearing more frequently in the highest positions in the ranking of coalitions.

In this paper we propose a social ranking solution based on a ceteris paribus majority principle, provide an axiomatic characterization of it, and analyze conditions under which the social ranking is transitive. The intuition behind the social ranking solution is that individuals i and j are compared using only information from the power relation that ranks them under a ceteris paribus (i.e., everything else being equal) interpretation. More precisely, if S is a coalition containing neither i nor j, we only look at the relation between S ∪ {i} and S ∪ {j} in order to infer some information about the relative strength of i and j, as it is shown in the following example.

Example 2. For the power relation ≻ in Example 1, the ceteris paribus ranking of candidates 1 and 2 implies that only three comparisons from ≻ can be used: 245 ≻ 145, 24 ≻ 14 and 13 ≻ 23. These comparisons are interpreted as saying, e.g., that keeping 45 equal, the team containing 2 (i.e., 245) performs better than the team containing 1 (i.e., 145). The (ceteris parisbus) majority principle states that 2 should be rewarded, since candidates 2 wins against 1 in two comparisons (i.e., 245 ≻ 145 and 24 ≻ 14) whereas 1 wins against 2 only in one (i.e, 13 ≻ 23).

Unfortunately, if we do not assume any restriction over the domain of power relations, it is easy to show that the ceteris paribus majority solution can lead to a Condorcetlike paradox in the social ranking. In order to mitigate this issue, we were able to identify a restriction on the power relation domain that is analogous to the classical singlepeakedness property from social choice theory [May, 1952; Merlin, 2003], and prevents the Condorcet paradox.

1 Throughout the paper, we often write teams without commas and parentheses, e.g., we write 245 instead of {2, 4, 5}.

The ceteris paribus principle also suggests an interpretation of our problem along the lines of a virtual election, with groups of individuals (coalitions) playing the role of voters: in Example 2, groups 45, 3 and 4 may be seen as voters for the comparison of candidates 1 and 2. Nevertheless, our framework differs from a classical voting scenario in that candidates can also be voters: in the comparison 12 ≻ 23, the coalition containing only 2 acts as a voter, while in the comparison 245 ≻ 345, 2 is a candidate.

Another distinguishing feature of our paper relates to the incompleteness of the power relation. In both papers [Bernardi et al., 2017; Moretti and ¨Ozt¨urk, 2017] it is assumed that one has access to a ranking over all possible coalitions, i.e., that the power relation is a total or complete preorder over the elements of 2N . However, in many situations this assumption might not be satisfied, e.g., due to missing data, incomparability of certain coalitions or their impossibility to be formed, etc. Therefore, we also consider power relations that are not necessarily total. In Section 3 incompleteness does not provide any complementary information for the social ranking rule, though in other cases the lack of comparisons may be a source of information and can be exploited in the definition of a social ranking. In this light, in Section 5 we briefly discuss different interpretations of incompleteness and conclude with an example of a social ranking rule based on the idea of information level for coalitions.

It is also worth mentioning that a social ranking solution can be seen as an ordinal power index, hence related works on simple games ([Banzhaf, 1965; Dubey et al., 1981]) are relevant here (see, e.g., [Freixas, 2010; Laruelle and Merlin, 2002; Saari and Sieberg, 2001; Taylor and Zwicker, 1999]). Finally, the literature contains a large number of results on the inverse problem, i.e., how to rank sets of objects given a ranking over the individual objects (for an overview, see [Barber`a et al., 2004]).

The paper is organized as follows: Section 2 introduces basic notions and notations; Section 3 presents the characterization of a social ranking solution based on the ceteris paribus majority principle; Section 4 deals with the analysis of single-peakedness in our framework; Section 5 discusses incompleteness of the power relation, and Section 6 concludes with some open questions for future work.

2 Preliminaries

Let N = {1, . . . , n} be a finite set of individuals. A binary relation R on N (xRy meaning that x is in relation R with y, for x, y ∈ N) is a preorder iff it is reflexive and transitive. A preorder that is also total (or complete) is called a total preorder. A total preorder that also satisfies antisymmetry is called linear order (each equivalence class is a singleton). We denote by T (N) the set of all total preorders on N.

A power relation is a binary relation on the power set 2N , and we denote it by ⪰∈ B(2N ), where B(2N ) is the family of all subsets of 2N × 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 : B(2N ) -→ T (A) associating to each power relation ⪰∈ B(2N ) a total preorder RA(⪰) (or R⪰ A ) over the elements of A. By this definition, the notion xR⪰ A y means that applying the social ranking solution to the power relation ⪰ gives the result that x is ranked higher than or equal to y. When R⪰ A is a total preorder, we denote by I ⪰ A its symmetric part, and by P ⪰ A its asymmetric part. Notice that, in general, we do not impose any property over the binary relations in the domain of a solution (the set of power relations).

3 Social Ranking Solutions

Starting from the classical approaches to the voting procedure, in this section we expand the simple majority rule to the domain of coalitional voting systems and reformulate the properties introduced by May [1952] in our coalitional setting. The first property discussed in this section says that each coalition should influence the social ranking of two alternatives x and y equally, so we can interchange the relation involving coalitions S∪{x} and S∪{y} with the one T ∪{x} and T ∪ {y} involving another coalition T different from S but having the same kind of relation, and without changing the final social ranking over x and y. In the following, recall that, given two power relations ⪰ and ⊒, the notations ∼ and ≃ denote indifference in ⪰ and in ⊒, respectively.

Definition 1 (Equality of Coalitions). Let A ⊆ N. A solution RA : B(2N ) -→ T (A) satisfies the property of Equality of Coalitions (EC) if and only if for all power relations ⪰,⊒∈ B(2N ), x, y ∈ A and bijection π : 2N\{x,y} → 2N\{x,y} such that S ∪ {x} ⪰ S ∪ {y} ⇔ π(S) ∪ {x} ⊒ π(S) ∪ {y} for all S ∈ 2N\{x,y} , it holds that xR⪰ A y ⇔ xR⊒ A y.

Differently stated, the social ranking of two alternatives x and y should only depend on the ranking expressed by coalitions over x and y, regardless of the number and the identity of coalitions' members. In particular, a coalition of one member has the same influence as a coalition with many members.

The next condition states that a solution should not favor any candidate in A ⊆ N: if the name of two elements in A is reversed, the social ranking remains the same.

Definition 2 (Neutrality). Let A ⊆ N. A solution RA : B(2N ) -→ T (A) satisfies the property of Neutrality (N) if and only if for all power relations ⪰,⊒∈ B(2N ) and x, y ∈ A such that S ∪{x} ⪰ S ∪{y} ⇔ S ∪{y} ⊒ S ∪{x} for all S ∈ 2N\{x,y} , it holds that xR⪰ A y ⇔ yR⊒ A x.

The next property states that a solution should be coherent with changes of the power relation of coalitions. More precisely: if, on a power relation, a social ranking solution is indifferent or in favor of x with respect to y, and if the power relation of all coalitions remains the same except that a single coalition becomes favorable to x, then the social ranking becomes strictly favorable to x.

Definition 3 (Positive Responsiveness). Let A ⊆ N. A solution RA : B(2N ) -→ T (A) satisfies the property of Positive Responsiveness (PR) if and only if for all power relations ⪰, ⊒∈ B(2N ), x, y ∈ A with xR⪰ A y and such that for some T ∈ 2N\{x,y} , [T ∪{x} ∼ T ∪{y} and T ∪{x} ⊐ T ∪{y}], or, [T ∪ {y} ≻ T ∪ {x} and T ∪ {x} ≃ T ∪ {y}] and S∪{x} ⪰ S∪{y} ⇔ S∪{x} ⊒ S∪{y} for all S ∈ 2N\{x,y} with S ̸= T , it holds that xP ⊒ A y, but not yP ⊒ A x.

We now define our social ranking rule based on the notion of ceteris paribus majority. We first need to introduce some further notations. Given a power relation ⪰∈ B(2N ) and two elements x, y ∈ N we define two sets: Dxy(⪰) = {S ∈ 2N\{x,y} : S ∪ {x} ≻ S ∪ {y}} and Exy(⪰) = {S ∈ 2N\{x,y} : S ∪ {x} ∼ S ∪ {y}}. We denote the cardinalities of Dxy(⪰) and Exy(⪰) as d⪰xy and e⪰xy , respectively.

Definition 4 (Ceteris Paribus Majority). Let ⪰∈ B(2N ). The ceteris paribus majority relation (CP-majority) is the binary relation R⪰ ⊆ N × N such that for all x, y ∈ N:

The following result characterizes CP-majority rule using the properties introduced above.

Theorem 1. Let A = {x, y} ⊆ N be a set with only two alternatives. 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.

Proof. (⇒) Amap assigning to each ⪰∈ 2N ×2N the corresponding CP-majority relation R⪰ ∩A×A is a solution since the two alternatives in A can always be compared (it also is obviously transitive and reflexive). Hereby, we denote such a map the CP-majority solution (on only two alternatives). EC is satisfied since the CP-majority relation only depends on the numbers dxy(⪰) and dyx(⪰), and not on which coalitions are in favor of one or the other alternative. The Neutrality property is clearly also satisfied, since the interchange of the alternatives does not affect the definition of the CP-majority relation. Also notice that the CP-majority satisfies the PR property: if dxy(⪰) = dyx(⪰), the change of one single indifference S ∪ {x} ∼ S ∪ {y} with S ∈ Exy(⪰) in favor of x or y breaks the tie.

(⇐) Suppose RA satisfies EC, N and PR. Let ⪰, ⊒∈ B(2N ) be such that dxy(⪰) = dxy(⊒) and dyx(⪰) = dyx(⊒). Define a permutation π of the elements in 2N\{x,y} such that the elements of Dxy(⪰) are in a one-to-one correspondence with the elements in Dxy(⊒), the elements of Dyx(⪰) are in a oneto-one correspondence with the elements in Dyx(⊒) and the elements of Exy(⪰) are in a one-to-one correspondence with the elements in Exy(⊒). Then, property EC implies that:

Now, suppose now that dxy(⪰) = dyx(⪰), and dxy(⊒) = dyx(⊒). Define another coalitional relation ≽∈ B such that Dxy(≽) = Dyx(⪰), Dyx(≽) = Dxy(⪰) and Exy(≽) = Eyx(⪰). By the property N, we have that xR≽ A y ⇔ yR⪰ A x Moreover, since dxy(⊒) = dxy(≽) and dyx(⊒) = dyx(≽), for the previous arguments, by EC we have that xR≽ A y ⇔ xR⊒ A y. So, yR⪰ A x ⇔ xR⊒ A y, and together with relation (1), we have that xR⪰ A y ⇔ yR⪰ A x. Since R⪰ A must be total, we have then proved that:

Now, take a power relation ⪰∈ B(2N ) such that dxy(⪰) > dyx(⪰). Take X ⊆ Dxy(⪰) with |X| = dxy(⪰) - dyx(⪰). Define another power relation ⊒∈ B(2N ) such that S∪{x} ⊐ S ∪ {y} for all S ∈ Dxy(⪰) \ X, S ∪ {x} ≃ S ∪ {y} for all S ∈ Exy(⪰) ∪ X and S ∪ {y} ⊐ S ∪ {x} for all S ∈ Dyx(⪰). Clearly, dxy(⊒) = dyx(⊒) and therefore, by relation (2), xI ⊒ A y. Break a tie for precisely one element S ∈ X such that now S ∪ {x} ⊐ S ∪ {y}: by property PR, we have that now xP ⊒ A y. By induction, using this result and the PR property, we have that breaking 0 < m ≤ |X| ties in favour of x for m elements of E, always gives xP ⊒ A y. So, if now S ∪ {x} ⊐ S ∪ {y} for all S ∈ X, we have that dxy(⪰) = dxy(⊒) and dyx(⪰) = dyx(⊒), and by EC we obtain that xP ⪰ A y. More precisely, we have proved that:

and by the N property it immediately follows that:

Relations (2), (3) and (4) are the definition of the CP-majority relation, which concludes the proof.

Proposition 1. Axioms EC, N and PR are independent.

Proof. In order to establish the independence of the three axioms, we show that for each pair of axioms there exists a social ranking solution that satisfies them but not the remaining one (available on request).

The ceteris paribus simple majority solution is grounded in intuitive and appealing principles. However, it turns out that strict Condorcet-like cycles are possible for more than two candidates, similarly to classical voting theory.

Example 3. For the power relation in Example 1 (candidates 1, 2 and 3), ceteris paribus majority implies that 3R⪰2 (since 13 ≻ 12), 2R⪰1 (since 245 ≻ 145, 24 ≻ 14 and 13 ≻ 23), but 1R⪰3 (since 12 ≻ 23).

The question raised by Example 3 is whether there are reasonable assumptions about the power relation under which strict Condorcet-like majority cycles can be avoided. Section 4 introduces a domain restriction which acts as a sufficient condition for avoiding cycles in the majority solution. Notice that monotonic power relations (each individual has a positive effect when joining a coalition) belong to another type of domain restriction. Even if such an assumption seems natural in some contexts (for instance, in multi-attribute decision making), it might be violated in others (for instance, in the context of our Example 1, the performance of a researcher may decrease joining a larger team). Moreover, the ranking generated by the CP-majority is only affected by comparisons between coalitions of the type S ∪{i} and S ∪{j}, where the monotonicity condition does not apply.

4 Single-peakedness of the Power Relation

It is an important insight from the classical voting literature that certain restrictions on the preferences of the voters are sufficient to guarantee a feasible majority solution. From this perspective, an interesting restriction is what we will call here individual single-peakedness [Black, 1948]. In a classical voting scenario, a basic assumption is that there exists a linear order ◁ on candidates; then, supposing voters rank candidates linearly (i.e., no ties), it goes on to say that a voter V 's preference ≻V over candidates is individually single-peaked if, for any candidates i, j and k such that i ◁ j ◁ k, it is not the case that both i ≻V j and k ≻V j. We will formalize a similar property for the power relation ≻, which we will, for simplicity, assume to be a linear order.

Definition 5 (Social single peakedness). The (linear) power relation ≻ is socially single-peaked if there exists a linear order ◁ on the set of items N such that for any i, j, k ∈ N for which i ◁ j ◁ k and any S ∈ 2N\{i,j,k} , none of the following conditions holds:

Intuitively, the linear order ◁ stands for a dimension along which items in N can be ranked. We then assume that the power relation ≻ orders coalitions in a manner consistent with ◁, as follows: a coalition S containing neither i, j nor k is interpreted as a voter with the power to rank i, j and k. Then, according to sp1, S does not rank the median candidate j as the least preferred of the lot; according to sp2, the extreme candidates i and k are not the most preferred among the combinations {i, j}, {i, k} and {j, k}. Thus, though clearly not identical with it, single-peakedness evokes the similarly named condition from voting theory.

We further exploit this (by now familiar) tactic of interpreting coalitions as voters in order to generate an individually single-peaked voting profile out of a socially single-peaked power relation ≻.

Definition 6 (Revealed preferences). Given a power relation ≻ on N, a linear order ◁ on N, items i, j, k ∈ N such that i ◁ j ◁ k, and a coalition S ∈ 2N\{i,j,k} , the S-revealed (respectively, ijkS-revealed) preference relations >S (respectively, >ijkS) based on ≻, are defined as follows:

• i >S j iff S ∪ {i} ≻ S ∪ {j},
• i >ijkS j iff (S∪{i, j, k}) \{j} ≻ (S∪{i, j, k}) \{i}.

Intuitively, >s and >ijkS stand in for the preferences of S and S ∪ {i, j, k} over candidates i and j. Relation >S encodes the fact that coalition S prefers i to j, since adding i to S leads to better performance than adding j; >ijkS encodes the fact that coalition S ∪ {i, j, k} prefers i to j, since losing i from S ∪ {i, j, k} leaves the coalition in a worse position than losing j. Stated differently, >ijkS expresses the fact that i is more valuable to S ∪ {i, j, k} than j.

We can show now that social single-peakedness of ≻ (as introduced in Definition 5) implies individual singlepeakedness of the revealed preference relations.

Lemma 1. If ≻ is a power relation on N, i, j, k ∈ N and S ∈ 2N\{i,j,k} , then ≻ is socially single-peaked iff >S and ijk are individually single-peaked.

Proof. Assume, first, that the power relation ≻ is socially single-peaked but that >S is not individually single-peaked, for some coalition S. Then there are i, j, k /∈ S such that i ◁ j ◁ k and i >S j, k >S j, which implies that S ∪ {i} ≻ S ∪ {j} and S ∪ {k} ≻ S ∪ {j}. But this contradicts condition sp1, and hence the social single-peakedness of ≻. Similarly, if >ijkS is not individually single-peaked, it follows that S ∪ {i, k} ≻ S ∪ {i, j} and S ∪ {i, k} ≻ S ∪ {j, k}, contradicting condition sp2. The proof that individual single-peakedness of >S and >ijkS implies social single-peakedness of ≻ is analogous.

The revealed preference relations allow us to interpret the ceteris paribus majority solution over items i, j, k as the result of an election over i, j, k where the voters are coalitions S and S ∪ {i, j, k}, for S ∈ 2N\{i,j,k} . The following example illustrates this.

Example 4. Suppose we want to rank items 1, 2 and 4 from a set N = {1, 2, 3, 4} of items and we are given a power relation ≻ which generates the revealed relations depicted in Table 1. We have orders >∅ and >3, corresponding to the revealed preferences of coalitions S ∈ 2N\{1,2,4} , as well as >124 and >1234, corresponding to revealed preferences of coalitions S ∪ {1, 2, 4}. The majority relation in the election over the revealed preferences is 2 > 1 > 4, which corresponds to the ceteris paribus majority solution over ≻. Notice that the revealed preference orders are individually singlepeaked (with linear order 1 ◁ 2 ◁ 3 ◁ 4 over items), and that the social ranking ≻ is socially single peaked (with the same linear order over items).

Now we can state our main result of this section.

Theorem 2. If the power relation ⪰ is socially singlepeaked, then for any items i, j, k ∈ N, it does not hold that iR≻jR≻kR≻i (i.e., the ceteris paribus majority solution does produce any non-transitive cycles).

Proof. For every coalition S ∈ 2N\{i,j,k} , construct a profile of votes over i, j and k from the revealed preference relations >S and >ijkS. We have that iR≻j iff i is a majority winner over j in this profile. Since, by Lemma 1, the relations >S and >ijkS are individually single-peaked, we get that there is no majority cycle between i, j and k in the final result, which implies that there is no cycle between i, j and k in the ceteris paribus majority solution.

As an illustration of how a socially single-peaked power relation can be obtained, consider the fact that a linear order ≻ over the elements of 2N can be numerically represented by a characteristic function v : 2N → R such that S ≻ T iff v(S) > v(T) for all S, T ∈ 2N . Suppose now that the marginal contribution v(S ∪ {i}) - v(S) of player i ∈ N \ S is somehow (inversely) related to the distance, on a policy scale, of the ideal position of player i from the jointly preferred position of coalition S ∈ 2N (the lower the distance from the joint position, the higher the marginal contribution). More precisely, suppose that:

• agents in N have a preferred ideal position xi ∈ [0,+∞), where the line [0,+∞) represents the policy scale, and
• each coalition S ∈ 2N is also characterized by a jointly preferred position pS ∈ [0,+∞) on the same policy scale, e.g., resulting from an aggregation process over the individual positions of players in S, or provided by an external actor (see, e.g., the model of coalition formation in [Bilal et al., 2001]).

For every S ∈ 2N and i, j ∈ N \ S, we assume that the following monotonicity relation exists between the distance diS = |pS - xi| and the marginal contribution of i:

In addition, we assume that the jointly preferred position of a coalition monotonically increases over the policy scale with the positions of its members, that is:

for every S ∈ 2N and i, j ∈ N \ S. This is the case, for instance, when the jointly preferred position xS is computed as the median of the individual positions xi in S. The following proposition shows that the power relation ≻ is single-peaked according to Definition 5.

Proposition 2. Let ≻ be a linear order on 2N and let v : 2N → R be such that S ≻ T iff v(S) > v(T) for all S, T ∈ 2N . Consider the vectors x ∈ RN+ and p ∈ R2N + satisfying conditions (5) and (6) for all S ∈ 2N and i, j ∈ N \ S. Then, ≻ is socially single peaked.

Proof. Take i, j, k ∈ N with xi < xj < xk. Notice that since ≻ is a linear order over 2N , then by Definition 6, relations ≻S and ≻ijkS, for each S ∈ 2N\{i,j,k} , are linear orders over N. To prove that ≻S and ≻ijkS are single-peaked (with respect the ordering (i, j, k)), it remains to show that if i ≻S j and i ≻ijkS j, then j ≻S k and j ≻ijkS k.

Let S ∈ 2N\{i,j,k} . First, suppose that i ≻S j or, equivalently, S ∪ {i} ≻ S ∪ {j}. Then, v(S ∪ {i}) - v(S) > v(S ∪ {j}) - v(S) and by relation (5) diS < djS. Consequently, pS < xi+xj 2 , and since xj < xk we have that djS < dkS. Then, by relation (5), we have v(S ∪ {j}) - v(S) > v(S ∪ {k}) - v(S) and, by the definition of v as a numerical representation of ≻, it follows that S ∪ {j} ≻ S ∪ {k}, implying that j ≻S k.

Now, suppose that i ≻ijkS j or, equivalently, S ∪ {i, k} ≻ S∪{j, k}. Then, v(S∪{i, k})-v(S∪{k}) > v(S∪{j, k})- v(S ∪ {k}) and by relation (5), we have diS∪{k} < djS∪{k}. Consequently, pS∪{k} < xi+xj 2 . Moreover, by relation (6), since xi < xk we have that pS∪{i} ≤ pS∪{k}. So, pS∪{i} < xi+xj 2 , then djS∪{i} < dkS∪{i}, and again by relation (5), v(S ∪ {i, j}) - v(S ∪ {i}) > v(S ∪ {i, k}) - v(S ∪ {i}). By the definition of v as numerical representation of ≻, we obtain S ∪ {i, j} ≻ S ∪ {i, k}, implying that j ≻ijkS k.

Example 5. Consider a set N = {1, 2, 3, 4} of four agents, with individual preferred position xi = i for each i ∈ N, the linear power relation ≻ in Table 1 that can be numerically represented by a characteristic function v satisfying condition (5), and jointly preferred positions pS = median([xi]i∈S)-ϵ for each S ∈ 2N . 2 To be more specific, we have that the jointly preferred positions are p∅ = 0 (by convention), p{i} = xi, p{i,j} = xi+xj 2 - ϵ, p{i,j,k} = xj if xi < xj < xk. The single-peaked linear orders ≻S and ≻124S on 1, 2, 4, with S ∈ {∅, {3}}, correspond to the revealed orders in Table 1.

A different, though related way to obtain socially singlepeaked power relations starts off assuming that there is a valuation v : N → R on the items themselves such that i < j iff v(i) < v(j), and that v(S) = ∑i∈S v(i). In other words, coalitions are ranked according to the sum of the values of their members. This also leads to a socially single-peaked power relation ≻, which we will be denoted as ≻Σ.

Proposition 3. Power relation ≻Σ is socially single-peaked.

Proof. Take the linear order ◁ on items of N to be given by the valuation v, i.e., i◁j iff v(i) < v(j). We obtain that v(S∪ {i}) = v(S) + v(i) and v(S ∪ {i, j}) = v(S) + v(i) + v(j) and it is straightforward to check that conditions sp1 and sp2 are satisfied.

Finally, note that (as per Theorem 2) social single-peakedness provides only a sufficient condition under which ⪰ supports application of the ceteris paribus majority rule. As we have shown in this section, some natural interpretations of the power relation turn out to satisfy it, but nonetheless social single-peakedness should not be thought of as exhaustive of the cases favorable to the ceteris paribus majority rule. Consider, for instance, a (total and transitive) power relation ⪰M such that for all non-empty coalitions S, T ∈ 2N

where, for each S ∈ 2N , S ̸= ∅, b(S) is a best element of S, i.e., such that {b(S)} ⪰M {i} for each i ∈ S. Even if ⪰M is not socially single peaked (some ties may occur in ⪰M), we show now that the CP-majority relation R⪰M is transitive.

Proposition 4. The CP-majority relation R⪰M is transitive.

Proof. First, note that for each x, y ∈ N, if {x} ⪰M {y}, then there is no S ∈ 2N\{x,y} such that S∪{y} ≻M S∪{x}. So, d⪰M yx = 0. Now, assume that {x} ≻M {y}. Then, d⪰M xy ≥ 1 > 0 = d⪰M yx . On the other hand, if {x} ∼M {y}, we have that S ∪ {y} ∼M S ∪ {x} for each S ∈ 2N\{x,y} , implying d⪰M xy = d⪰M yx = 0. We have then shown that xR⪰M y if and only if {x} ⪰M {y}, and the transitivity of R⪰M follows from the definition of ⪰M.

2 Since ≻ is a linear order, the factor ϵ ∈ (0, 12 ) is used to break ties diS = djS in favor of the element with the lowest individual position min{i, j}.

5 Discussion on the Use of Incompleteness

As mentioned in the introduction, it is likely that in certain contexts the power relation will, for various reasons, not be complete. One may, for instance, distinguish between incompleteness reflecting the absence of coalitions (case 1) and incompleteness due to difficulty in comparing existing coalitions (case 2). Moreover, various configurations may appear in each case. For instance, in case 1, the absence of coalitions may be caused by the structure of the problem (in a company, teams are defined by the manager and some of them are not feasible, case 1a) or may reflect the fact that some people do not want to work together, hence they do not form coalitions (case 1b). In case 2, incompleteness may be related to the heterogeneity of teams and reflects an incomparability (in Example 1, we can imagine one team being very strong in terms of research achievements, but not in terms of teaching quality, with the situation reversed for a different team), or just the absence of information. In such cases, additional information can be obtained using missing comparisons. Obviously, the interpretation of such information depends on the context. For instance, in case 1b, the absence of a coalition is a negative factor for the individuals forming it, while this is not the case in case 1a. Hence, taking incompleteness into account when defining a social ranking rule must depend on the reasons for incompleteness, and different solutions must be considered for alternative contexts.

In the following, we present a new social ranking solution as an example of rules that can be defined if we find ourselves in case 1a. The general idea is to classify coalitions in terms of their information level and compare two candidates using the information inferred from the most informed coalitions.

Let S ∈ 2N and S = N \ S be its complement. We define the set of comparisons in which S is involved in the power relation ⪰ as the set S⪰ = {x ∈ S : ∃y ∈ S\{x} s.t. S∪{x} ⪰ S ∪ {y} or S ∪ {y} ⪰ S ∪ {x}}. Consequently, the set of elements that cannot be compared by means of a coalition S is given by S \ S⪰, and we call its cardinality |S \ S⪰| the ignorance of S. We denote by ci, i ∈ {0, . . . , n}, the set of all coalitions S such that | ¯ S \ S⪰| = i. So, the class c0 (i.e., the class of most aware coalitions having the lowest ignorance), contains all coalitions that are involved in the comparison among all the elements in their complement set (e.g., c0 coincides with the powerset 2N if ⪰ is total); the class c1 (i.e., the class with the second lowest ignorance) contains all coalitions involved in the comparison of all elements, except one, in their complement set, etc. Obviously, some classes ci may be empty, and each coalition S may belong to at most one class ci. The family of all n + 1 classes defined over a power relation ⪰ is denoted by C⪰ = {c0, . . . , cn}. Given two elements x, y ∈ N and slightly abusing notation, we denote by:

the restriction of Dxy(⪰) on C⪰, where Dxy(ci, ⪰), for each i ∈ {0, . . . , n}, is the (possibly empty) set of coalitions S ∈ ci such that S ∪ {x} is strictly stronger than S ∪ {y}, and by:

the vector of cardinalities dxy(ci, ⪰) = |dxy(ci, ⪰)|.

We now introduce a generalized version of the CP-majority relation, aimed at giving more weight to coalitions with lower ignorance. First, consider the lexicographic order among vectors v = (v0, . . . , vn) and w = (w0, . . . ,wn): v ≥L w if either v = w or ∃j : vi = wi, i = 1, . . . , j - 1 ∧ vj > wj .

Definition 7 (Informative CP-Majority). Let ⪰⊆ B(2N ). The Informative CP-majority relation (ICP-majority) is the binary relation RC⪰ ⊆ N × N such that for all x, y ∈ N:

Example 6. Consider again the power relation of Example 1. The CP-majority concludes that 1 and 5 are indifferent since 13 ≻ 35 and 2345 ≻ 1234. Using information level, D15(c0,⪰) = ∅, D51(c0,⪰) = {234} (i.e., 234 = 15, 234≻ = 15 and 2345 ≻ 1234). Moreover, we have that D15(c1, ⪰) = {3} (i.e., 3 = 1245, 3≻ = 125 and 13 ≻ 35), whereas all the other sets D15(ci,⪰) and D51(ci,⪰) are empty. So, d51(C⪰) = (1, 0, 0, 0, 0, 0) ≥L d15(C⪰) = (0, 1, 0, 0, 0, 0), implying that, according to the ICP-majority, 5 is ranked better than 1.

A deeper discussion of the meaning of incompleteness in our context and the information that can be derived from an incomplete power relation leads to alternative definitions of social ranking solutions. Such an analysis also concerns the axiomatic characterization of solutions, as well as their computational aspects. Unfortunately, due to the space limit, we are forced to omit the axiomatic analysis of the ICP-majority relation (available upon request).

6 Conclusion and FutureWork

In this paper, we have put forward a social ranking solution based on a ceteris paribus majority principle, provided an axiomatic characterization (on only two alternatives), and studied a domain restriction which guarantees the transitivity of the generated rankings for an arbitrary number of alternatives. A discussion on how to exploit incompleteness in the power relation is also provided.

One direction for future research is to further investigate necessary and sufficient conditions over the domain of power relations which guarantee the transitivity of the ranking induced by the CP-majority. Another open issue is the definition of social ranking solutions that benefit from a larger amount of information in the power relation (and not only focusing on the information coming from the comparison of ceteris paribus coalitions). Moreover, alternative criteria could be used to generate the classes of coalitions used for the ICPmajority rule. For instance, it could be argued that the weight of a class is related to the overall probability that the coalition in that class forms. Another interesting problem is the analysis of the robustness of our social ranking solutions to "small" changes in the power relation. From this perspective, a related issue deals with an application to multi-criteria decision making (MCDM) where, given the relative strength of coalitions of criteria (represented by a power relation), a social ranking solution can be used as an alternative method for comparing the importance of criteria, independently from the (arbitrary to some extent) weight assigned to coalitions by a capacity [Grabisch and Labreuche, 2010].

Acknowledgments

This work has been supported by the projects, ANR-14CE24-0007-01 "CoCoRICo-CoDec", AMANDE ANR-13BS02-0004, FWF P30168-N31, W1255-N23 and a Marietta Blau grant (OeAD-GmbH).