Social Ranking Problems at the Interplay between Social Choice Theory and Coalitional Games

Abstract

This paper reviews the recent literature on the “social ranking problem”, that is, the problem of converting group rankings into individual rankings. We introduce and categorize existing social ranking methods and we briefly explain their attributes. Three main categories of social ranking methods are identified: lexicographic social rankings, methods based on voting mechanisms, and those inspired by the theory of coalitional games. An open-source R package called socialranking for computing the majority of the existing social rankings is also presented and discussed.

1. Introduction

Various problems that may seem unrelated at first glance—like ranking researchers or athletes in team sports [1], understanding the importance of diseases in interconnected health graphs of co-morbidities [2,3], understanding how a formula contributes to the inconsistency in a belief base [4], measuring someone’s influence on a social network [5,6], explaining the impact of different factors in multi-criteria decision-making [7], and many more—in fact all come down to a common social ranking problem: how to turn rankings that involve sets of elements or coalitions into an informative ranking that applies to individual ones. Therefore, a social ranking solution aims to address the essential question of how to rank the elements within a set N in a way that aligns with an established ranking of its subsets. Additionally, it strives to ensure that this ranking accurately represents the ordinal influence of each individual element on the ranking positions of the subsets.

Inspired by the framework of three-valued simple games [8], a ranking over coalitions of political parties may represent, for instance, a bicameral legislature wherein the two houses are formed by $n^1$ and $n^2$ members, respectively. Each political party i of a set N is represented by precisely $w_i^1$ and $w_i^2$ in house 1 and 2, respectively. As it is the case for the States General of the Netherlands [8], assume that the first house can accept (reject) a bill if there is (is not) a majority in favor. In case of acceptance by the first house, the bill is sent to the second house that follows the same rule to give a final ruling on whether to accept or reject the bill. If the bill is accepted by the two houses, it becomes a law. However, only the first house has the right to submit a bill and start the procedure. Precisely, any coalition of S of the set N of political parties can reach one of the following three outcomes denoted as $f\left(S\right)$:

• $f\left(S\right)=2$ if the parties in coalition S form a majority in both houses (i.e., ${\sum }_{i\in S}{w}_i^1\ge \lfloor \frac{n^1}{2}\rfloor +1$ and ${\sum }_{i\in S}{w}_i^2\ge \lfloor \frac{n^2}{2}\rfloor +1$);
• $f\left(S\right)=1$ if the parties in coalition S form a majority in the first house but not in the second one (i.e., ${\sum }_{i\in S}{w}_i^1\ge \lfloor \frac{n^1}{2}\rfloor +1$ and ${\sum }_{i\in S}{w}_i^2<\lfloor \frac{n^2}{2}\rfloor +1$);
• $f\left(S\right)=0$ in all the remaining cases.

Such a situation can be represented as a ranking of the subsets of N such that, for any pair of coalitions S and T, we have that S “is at least as powerful as T” whenever $f\left(S\right)$ is at least as large as $f\left(T\right)$. Notice that, in this situation, the outcomes associated to coalitions are purely ordinal, as the ordering $0,1,2$ only encodes an increasing preference of political parties over the possible outcomes, and not a specific amount of utility. Nevertheless, it seems rather appealing to try to estimate the relative importance of the different political parties, taking into account their role in determining the most preferred levels of acceptance of a bill through the formation of alternative coalitions. The theory of social rankings is aimed at addressing this kind of problems by proposing a portfolio of alternative solutions. This paper aims to systematically categorize those solutions, clearly outlining their key features and demonstrating how they are computed using numerical examples. Furthermore, we will provide a concise overview of the socialranking R package [9], which facilitates the computation of social rankings for more intricate cases.

Our analysis has delineated three distinct categories of social ranking solutions within the existing literature:

• Lexicographic social rankings. These rankings prioritize elements based on a predetermined hierarchy of importance related to the roles played within coalitions. Additionally, they may factor in the size of the coalitions, offering a nuanced approach to ranking [10,11,12].
• Social rankings based on voting rules: This category assesses the impact of individual elements by examining their unique contributions to various coalitions. These rankings maintain consistency (ceteris paribus) by altering only one element at a time while keeping all other factors constant. The aggregation of individual contributions in this approach is guided by principles akin to classical voting systems [13,14,15].
• Game theory-inspired social rankings: These rankings are grounded in the principles of cooperative game theory. They leverage established solution concepts from this field to formulate rankings, providing a theoretical and strategic framework for understanding social rankings [15,16,17,18].

We start in the next section with some preliminary definitions. The three aforementioned families of social rankings are presented in Section 3, Section 4 and Section 5, respectively. Section 6 is devoted to a short introduction of the socialranking package. We conclude in Section 7 with a mention to related studies and applications of social rankings from the literature.

2. Preliminaries and Notations

Consider a finite set of elements $N=\{1,\dots ,n\}$. The set of subsets of N (also called coalitions) is denoted by $\mathcal{P}\left(N\right)$ (for many social rankings, like the lexicographic ones in Section 3, the empty coalition Ø, and the coalition of all elements N, are irrelevant and can be omitted from $\mathcal{P}\left(N\right)$. For other social rankings, however (e.g., the ordinal Banzhaf index in Section 5), these two special coalitions play an important role). The set of coalitions without i is denoted by $U_i=\{S\in \mathcal{P}\left(N\right):i\notin S\}$, whereas the set of coalitions containing neither i nor j is denoted by $U_{ij}=\{S\in \mathcal{P}\left(N\right):\{i,j\}\cap S=Ø\}$, for any $i,j\in N$, $i\ne j$.

A binary relation on N is a set $R\subseteq N\times N$ and it is: reflexive, if for each $i\in N$, $iRi$; transitive, if for each $i,j,k\in N$, $iRj$ and $jRk$ ⇒ $iRk$; total, if for each $i,j\in N$, $iRj$ or $jRi$; antisymmetric, if for each $i,j\in N$, $iRj$ and $jRi$ ⇒ $i=j$. A total preorder or ranking is a reflexive, transitive, and total binary relation. A total or linear order is an antisymmetric ranking. $\mathcal{R}\left(N\right)$ and $\mathcal{L}\left(N\right)$ denote, respectively, the set of rankings and the one of linear orders on N.

The lexicographic order ${\ge }_L$ and the lexicographic* order ${\ge }_{L^{*}}$ among vectors $\mathbf{i}=(i_1,\dots ,i_u)$ and $\mathbf{j}=(j_1,\dots ,j_u)$ are defined, respectively, as follows:

• $\mathbf{i}{\ge }_L\mathbf{j}$ if either $\mathbf{i}=\mathbf{j}$ or there exists t such that $i_t>j_t$ and $i_r=j_r$ for all $r\in \{1,\cdots ,t-1\}$.
• $\mathbf{i}{\ge }_{L^{*}}\mathbf{j}$ if either $\mathbf{i}=\mathbf{j}$ or there exists t such that $i_t<j_t$ and $i_r=j_r$ for all $r\in \{t+1,\dots ,u\}$.

Hereafter, a total preorder $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ is referred to as a power relation. In the following, for all $S,T\in \mathcal{P}\left(N\right)$, $(S,T)\in \succsim$ or, equivalently, $S\succsim T$ is interpreted as “coalition S is at least as powerful as coalition T according to the power relation ≿”. We denote by ∼ the symmetric part of ≿ (i.e., for all $S,T\in \mathcal{P}\left(N\right)$, $S\sim T\iff S\succsim T$ and $T\succsim S$) and by ≻ the asymmetric part of ≿ (i.e., for all $S,T\in \mathcal{P}\left(N\right)$, $S\succ T\iff S\succsim T$ and not $T\succsim S$). Therefore, for all $S,T\in \mathcal{P}\left(N\right)$, $S\succ T$ means that “coalition S is strictly more powerful than coalition T”, whereas $S\sim T$ means that “coalitions S and T are equally powerful”.

Let $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ be a power relation of the form $S_1\succsim S_2\succsim \cdots \succsim S_{|\mathcal{P}(N)|}.$ The quotient order of ≿ is denoted as ${\Sigma }_1\succ {\Sigma }_2\succ \cdots \succ {\Sigma }_l$ in which the subsets $S_j$ are grouped in the equivalence classes ${\Sigma }_k$ generated by the symmetric part of ≿. This means that all the sets in ${\Sigma }_1$ are equally powerful to $S_1$ and are strictly better than the sets in ${\Sigma }_2$, and so on. Given a power relation ≿ and its associated quotient order ${\Sigma }_1\succ {\Sigma }_2\succ \cdots \succ {\Sigma }_l,$ we denote by $i_k=|\{S\in {\Sigma }_k:i\in S\}|$ the number of sets in ${\Sigma }_k$ containing i for $k=1,\dots ,l$ and by ${\theta }^{\succsim }\left(i\right)$ the l-dimensional vector ${\theta }^{\succsim }\left(i\right)=(i_1,\dots ,i_l)$ associated to ≿.

A social ranking (solution) on N is a function $R:\mathcal{R}\left(\mathcal{P}\right(N\left)\right)⟶\mathcal{R}\left(N\right)$ associating to each power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ a total preorder $R(\succsim )\in \mathcal{R}\left(N\right)$ (or $R^{\succsim }\in \mathcal{R}\left(N\right)$) over the elements of N. By this definition, the notion $i{R}^{\succsim }j$ means that “applying the social ranking R to the power relation ≿ gives the result that i is ranked higher than or equal to j”. We denote by $I^{\succsim }$ the symmetric part of $R^{\succsim }$, and by $P^{\succsim }$ its asymmetric part.

A trivial social ranking, neglecting the position of non-singletons coalitions in the power relation, is the map $R_0:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)⟶\mathcal{R}\left(N\right)$ such that $i{R}_0^{\succsim }j⟺\left\{i\right\}\succsim \left\{j\right\}$ for all $i,j\in N$ and all $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$. Another extremely simple social ranking may only look at the comparisons of coalitions containing all-but-one elements, like the map $R_{n-1}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)⟶\mathcal{R}\left(N\right)$ such that $i{R}_{n-1}^{\succsim }j⟺N\setminus \left\{j\right\}\succsim N\setminus \left\{i\right\}$ for all $i,j\in N$.

Example 1.

Let $N=\{1,2,3\}$ and consider the power relation ≿ as follows (in the remaining of this paper, we will continue to use the concise notation introduced in this example to save space in the expression of a ranking. So, for example, the notation $\{1,3\}\sim \{2,3\}\succ \{1,2\}$ indicates a power relation ≿ such that $\{1,3\}\sim \{2,3\}$, $\{2,3\}\succ \{1,2\}$ and also $\{1,3\}\succ \{1,2\}$, due to the transitivity of ≻; similarly, for a relation R on the individual elements with $1P2I3$, we have that $1P2$, $2I3$, and also $1P3$; etc.):

$$\{1,2,3\}\sim \{1,3\}\sim \{2,3\}\succ \{1,2\}\sim \left\{2\right\}\succ \left\{1\right\}\succ \left\{3\right\}\sim Ø.$$

The quotient order of ≿ is such that

$${\Sigma }_1=\{\{1,2,3\},\{1,3\},\{2,3\}\}\succ {\Sigma }_2=\{\{1,2\},\left\{2\right\}\}\succ {\Sigma }_3=\left\{\left\{1\right\}\right\}\succ {\Sigma }_4=\{\left\{3\right\},Ø\}.$$

So, ${\mathit{R}}_0^{\succsim }$ returns the ranking $2{\mathit{P}}_{0}1{\mathit{P}}_{0}3$ while ${\mathit{R}}_{n-1}^{\succsim }$ yields the ranking $1{\mathit{I}}_{n-1}2{\mathit{P}}_{n-1}3$.

The remaining of this section is devoted to the presentation of families of social ranking solutions from the literature.

3. Lexicographic Social Rankings

The lexicographic excellence (lex-cel) [12] has received increasing attention in the recent literature on social rankings. The lex-cel is based on the idea that the most influential individuals are those appearing more frequently in the highest positions in the ranking of coalitions. Precisely, to compare two elements i and j in N, lex-cel proceeds in a lexicographic way over the vectors of occurrences of the two elements in the equivalence classes of a power relation. With the objective to award the excellence of the elements in contributing to the best-ranked sets, the lex-cel first compares the occurrences of i and j in the first equivalence class of a power relation (i.e., the equivalence class with the lowest index in the quotient order, on the left side), placing the element occurring the most above the other. In case of a tie, i.e., i and j occur the same number of times in the sets of the first equivalence class, lex-cel demands to compare the occurrences of i and j in the second equivalence class of the power relation, again placing the element occurring the most above the other or, in case of a tie, proceeding with the examination of the third equivalence class, and so on, until one finds a difference between the number of occurrences in a certain equivalence class (declaring a strict preference for the element occurring the most) or the last equivalence class is reached with all ties and, in this case, i and j are declared indifferent by the lex-cel. More formally,

Definition 1

(Lexicographic-excellence (lex-cel) [12]). The lexicographic excellence (lex-cel) is the map ${\mathit{R}}_{le}^{\succsim }$ such that for all $i,j\in N$:

$$i{\mathit{R}}_{le}^{\succsim }j⟺{\theta }^{\succsim }\left(i\right){\ge }_L{\theta }^{\succsim }\left(j\right).$$

for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ (following the same convention as before, ${\mathit{I}}_{le}(\succsim )$ and ${\mathit{P}}_{le}(\succcurlyeq )$ stand for the symmetric part and the asymmetric part of ${\mathit{R}}_{le}(\succsim )$, respectively).

Example 2.

Let $N=\{1,2,3\}$ and let us consider the power relation ≿ of Example 1. We have ${\theta }^{\succsim }\left(1\right)=(2,1,1,0)$, ${\theta }^{\succsim }\left(2\right)=(2,2,0,0)$ and ${\theta }^{\succsim }\left(3\right)=(3,0,0,1)$. Notice that ${\theta }^{\succsim }\left(3\right){>}_L{\theta }^{\succsim }\left(2\right){>}_L{\theta }^{\succsim }\left(1\right)$. So, the lex-cel returns the following ranking: $3{\mathit{P}}_{le}^{\succsim }2{\mathit{P}}_{le}^{\succsim }1$.

While the lex-cel solution rewards excellence, its dual definition may be used to punish mediocrity. Therefore, to compare two elements i and j in N, the dual lexicographic-excellence (dual-lex) [12] first compares the occurrences of i and j in the last equivalence class of a power relation (i.e., the sets in the equivalence class with the highest index in the quotient order, on the right side), placing the element occurring the least above the other one, for appearing more frequently in the worst equivalent class denotes weakness. In case of a tie, i.e., i and j occur equally in the sets of the last equivalence class, the dual-lex focuses on the occurrences of i and j in the penultimate equivalence class, always punishing the less frequent element and proceeding to the next equivalence class in case of a tie, and so on, from the right to the left side. Once again, if the number of occurrences remains the same over all equivalence classes, the dual-lex declares i and j indifferent.

Definition 2

(Dual lexicographic-excellence (dual-lex) [12]). The dual-lexicographic (dual-lex) solution is the map ${\mathit{R}}_d:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(N\right)$ such that, for all $i,j\in N$,

$$i{\mathit{R}}_d^{\succsim }j⟺{\theta }^{\succsim }\left(i\right){\ge }_{L^{*}}{\theta }^{\succsim }\left(j\right).$$

for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ (${\mathit{I}}_d(\succsim )$ and ${\mathit{P}}_d(\succsim )$ stand for the symmetric part and the asymmetric part of ${\mathit{R}}_d(\succsim )$, respectively).

Example 3.

Let $N=\{1,2,3\}$ be the set of agents and let us consider the power relation ≿ of Example 1. Notice that ${\theta }^{\succsim }\left(2\right){>}_{L^{*}}{\theta }^{\succsim }\left(1\right){>}_{L^{*}}{\theta }^{\succsim }\left(3\right)$. So, the dual-lex returns the following ranking: $2{\mathit{P}}_d^{\succsim }1{\mathit{P}}_d^{\succsim }3$.

Other lexicographic social rankings have been introduced in [10]. Like lex-cel, the two social rankings $L^1$ and $L^2$ proposed in [10] are aimed at rewarding the excellence of elements in contributing to the best coalitions in a power relation, but the excellence is mediated by the size of the coalitions, promoting the importance of smaller ones. More precisely, as lex-cel, $L^1$ starts the comparison of two elements i and j looking at the first equivalence class of a power relation (from the left). Different from lex-cel, $L^1$ distinguishes the number of occurrences in coalitions of different sizes giving, as a secondary principle (after the principle of excellence), priority to smaller coalitions. The main argument supporting such a principle is that, in an ordinal framework, where it is not possible to quantify the performance of coalitions, individual contributions to smaller coalitions are likely more relevant and should count more. So, in the first equivalence classes, $L^1$ first focuses on the occurrences of i and j as singletons; then, in case of a tie (i.e., both singletons do or do not belong to the first equivalence class), it considers coalitions of size 2, and so on, until all possible coalition sizes are considered. Possibly, the smallest coalition size such that i and j occur differently determines a strict relation in favor of the most frequent one; otherwise, in case i and j occur equally over coalitions of the same sizes throughout the first equivalence class, $L^1$ looks at the second equivalence class and it compares again elements’ occurrences based on the size of coalitions, like for the first equivalence class, and so on proceeding from left to right over all possible equivalence classes. An indifference may arise according to $L^1$ only in case all the per-size occurrences are equal in all equivalence classes. To formally introduce $L^1$, we need some further notations.

Given a power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$, with quotient order ${\Sigma }_1\succ {\Sigma }_2\succ \cdots \succ {\Sigma }_l$, we define the matrix $M^{\succsim ,i}\in {\mathbb{N}}^{n\times l}$ for any element $i\in N$ such that $M_{sk}^{\succsim ,i}$ denotes the number of coalitions of size $s\in \{1,\dots ,n\}$ containing i in the equivalence class ${\Sigma }_k$, $k\in \{1,\dots ,l\}$. Notice that ${\sum }_{k=1}^l{M}_{sk}^{\succsim ,i}={\displaystyle \left(\begin{array}{c}n-1\\ s-1\end{array}\right)}$, so ${\sum }_{s=1}^n{\sum }_{k=1}^l{M}_{sk}^{\succsim ,i}=2^{n-1}$.

Definition 3

($L^1$ ranking [10]). The $L^1$-solution is the map ${\mathit{R}}_{L^1}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(N\right)$ such that, for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and $i,j\in N$,

$$i{\mathit{I}}_{L^1}(\succsim )j⟺M^{\succsim ,i}=M^{\succsim ,j}$$

and

$$i{\mathit{P}}_{L^1}(\succsim )j⟺\left\{\begin{array}{c}\mathit{there}\mathit{exist}\widehat{s}\in \{1,\dots ,n\}\mathit{and}\widehat{k}\in \{1,\dots ,l-1\}\mathit{such}\mathit{that}\hfill \\ \begin{array}{cc}\hfill \left(i\right)& M_{sk}^{\succsim ,i}=M_{sk}^{\succsim ,j}foralls\in \{1,\dots ,n\}andallk\in \{1,\dots ,\widehat{k}-1\},\hfill \\ \hfill \left(ii\right)& M_{s\widehat{k}}^{\succsim ,i}=M_{s\widehat{k}}^{\succsim ,j}foralls\in \{1,\dots ,\widehat{s}-1\},\mathit{and}\hfill \\ \hfill \left(iii\right)& M_{\widehat{s}\widehat{k}}^{\succsim ,i}>M_{\widehat{s}\widehat{k}}^{\succsim ,j}\hfill \end{array}\hfill \end{array}\right.$$

(${\mathit{I}}_{L^1}(\succsim )$ and ${\mathit{P}}_{L^1}(\succsim )$ stand for the symmetric part and the asymmetric part of ${\mathit{R}}_{L^1}(\succsim )$, respectively).

Example 4.

Let $N=\{1,2,3,4\}$ be the set of agents. Consider the power relation ≿ defined as

$$\{1,3\}\sim \{2,4\}\succ \{2,3\}\sim \{1,2\}\sim \left\{4\right\}\succ S,$$

where all coalitions $S\in \mathcal{P}\left(N\right)$ not explicitly listed belong to the last equivalent class. The quotient order of ≿ can be expressed as

$${\Sigma }_1=\{\{1,3\},\{2,4\}\}\succ {\Sigma }_2=\{\{1,2\},\{2,3\},\left\{4\right\}\}\succ {\Sigma }_3=\{S\in \mathcal{P}\left(N\right):S\notin {\Sigma }_1\cup {\Sigma }_2\}.$$

Focusing on elements 2 and 4, their respective vectors are ${\theta }^{\succsim }\left(2\right)=(1,2,5)$ and ${\theta }^{\succsim }\left(4\right)=(1,1,6)$. Consequently, lex-cel yields $2P_{le}^{\succsim }4$.

On the other hand, we have that

$$M^{\succsim ,2}=\left(\begin{array}{ccc}0& 0& 1\\ 1& 2& 0\\ 0& 0& 3\\ 0& 0& 1\end{array}\right)and{M}^{\succsim ,4}=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 2\\ 0& 0& 3\\ 0& 0& 1\end{array}\right).$$

It is easy to verify that, according to Definition 3, with $\widehat{s}=1$ and $\widehat{k}=2$, the $L^1$ solution produces $4P_{L^1}^{\succsim }2$.

Based on a per-size comparison within each equivalence class, $L^1$ may completely reverse a strict relation between two elements yielded by lex-cel (see, for instance, the relation between elements 2 and 4 in Example 4). One can argue that, if the overall excellence is the main criterion to rank elements, then reversing the indication of the total amount of occurrences within a discriminating equivalence class is too extreme.

To rectify this, the authors in [10] introduce another social ranking solution, namely $L^2$. Like $L^1$, $L^2$ also begins by examining the equivalence classes from left to right and counts occurrences on a per-size basis. However, the per-size comparison is only allowed to determine a strict relation between two elements when there is an inequality in the total number of occurrences within an equivalence class.

To formalize the $L^2$ social ranking solution as introduced in [10], we extend our notation for the matrix $M^{\succsim ,i}$. Let $M_k^{\succsim ,i}$ denote the sum of the values of column $k\in \{1,\dots ,l\}$, calculated as $M_k^{\succsim ,i}={\sum }_{s=1}^n{M}_{sk}^{\succsim ,i}$. Then, $L^2$ is defined as follows:

Definition 4

($L^2$ ranking [10]). The $L^2$-solution is the map ${\mathit{R}}_{L^2}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(N\right)$ such that, for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and $i,j\in N$,

$$i{\mathit{I}}_{L^2}(\succsim )j⟺M^{\succsim ,i}=M^{\succsim ,j}$$

and

$$i{\mathit{P}}_{L^2}(\succsim )j\iff \left\{\begin{array}{c}\mathit{there}\mathit{exist}\widehat{s}\in \{1,\dots ,n\}\mathit{and}\widehat{k}\in \{1,\cdots ,l-1\}\mathit{such}\mathit{that}\hfill \\ \begin{array}{cc}\hfill \left(i\right)& M_{sk}^{\succsim ,i}=M_{sk}^{\succsim ,j}\mathit{for}\mathit{any}s\in \{1,\dots ,n\}\mathit{and}k\in \{1,\dots ,\widehat{k}-1\}, and\hfill \\ \hfill \left(ii\right)& \mathit{either}{M}_{\widehat{k}}^{\succsim ,i}>M_{\widehat{k}}^{\succsim ,j}\hfill \\ & \mathit{or}{M}_{\widehat{k}}^{\succsim ,i}=M_{\widehat{k}}^{\succsim ,j},M_{s\widehat{k}}^{\succsim ,i}=M_{s\widehat{k}}^{\succsim ,j}\mathit{for}\mathit{alls}\in \{1,\dots ,\widehat{s}-1\}\mathit{and}{M}_{\widehat{s}\widehat{k}}^{\succsim ,i}>M_{\widehat{s}\widehat{k}}^{\succsim ,j}.\hfill \end{array}\hfill \end{array}\right.$$

(${\mathit{I}}_{L^2}(\succsim )$ and ${\mathit{P}}_{L^2}(\succsim )$ stand for the symmetric part and the asymmetric part of ${\mathit{R}}_{L^2}(\succcurlyeq )$, respectively).

Example 5.

Let $N=\{1,2,3\}$ be the set of agents and let us consider again the power relation ≿ of Example 1. We have that

$$M^{\succsim ,1}=\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 1& 0& 0\\ 1& 0& 0& 0\end{array}\right),M^{\succsim ,2}=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 1& 0& 0\\ 1& 0& 0& 0\end{array}\right),M^{\succsim ,3}=\left(\begin{array}{cccc}0& 0& 0& 1\\ 2& 0& 0& 0\\ 1& 0& 0& 0\end{array}\right).$$

To compute the $L^1$ social ranking between 1 and 2, notice that $M_{sk}^{\succsim ,1}=M_{sk}^{\succsim ,2}$ for all $s\in \{1,2,3\}$ and $k=1$, but $M_{12}^{\succsim ,1}=0<1=M_{12}^{\succsim ,2}$. As such, according to Definition 3, $2{\mathit{P}}_{L^1}^{\succsim }1$. In a similar way, $M_{11}^{\succsim ,2}=M_{11}^{\succsim ,3}$ but $M_{21}^{\succsim ,2}=1<2=M_{21}^{\succsim ,3}$. So, $L^1$ returns the ranking $3{\mathit{P}}_{L^1}^{\succsim }2{\mathit{P}}_{L^1}^{\succsim }1$.

The social ranking $L^2$ yields the same ranking on N, but for different reasons. In fact, $M_1^{\succsim ,1}=M_1^{\succsim ,2}=2$ while $M_1^{\succsim ,3}=3$ and $M_1^{\succsim ,1}=M_1^{\succsim ,2}=2$, which implies that 3 is ranked higher than both 1 and 2 according to Definition 4. One can verify that $L^2$ returns the ranking $3{\mathit{P}}_{L^2}^{\succsim }2{\mathit{P}}_{L^2}^{\succsim }1$.

Example 6.

Let $N=\{1,2,3,4\}$ be the set of agents and consider the power relation ≿ from Example 4.

According to Definition 4, with parameters $\widehat{s}=1$ and $\widehat{k}=2$, one obtains $M_{\widehat{k}}^{\succsim ,2}=2>1=M_{\widehat{k}}^{\succsim ,4}$. Therefore, $L^2$ yields the relation $2{\mathit{P}}_{L^2}^{\succsim }4$, which aligns with the outcome from the lex-cel solution.

However, it is easy to find an example wherein the $L^2$ and lex-cel solutions diverge in their rankings. Consider the slightly different power relation ${\succsim }^{\prime }$ such that

$$\{1,3\}{\sim }^{\prime }\{2,4\}{\succ }^{\prime }\{2,3\}{\sim }^{\prime }\left\{4\right\}{\succ }^{\prime }\{1,2\}{\succ }^{\prime }S$$

where all $S\in \mathcal{P}\left(N\right)$ not explicitly listed belong to the same last equivalence class. The quotient order of ${\succsim }^{\prime }$ can be represented as

$${\Sigma }_1=\{\{1,3\},\{2,4\}\}{\succ }^{\prime }{\Sigma }_2=\{\{2,3\},\left\{4\right\}\}{\succ }^{\prime }{\Sigma }_3=\left\{\{1,2\}\right\}{\succ }^{\prime }{\Sigma }_4=\{S\in \mathcal{P}\left(N\right)\setminus \bigcup _{t=1}^3{\Sigma }_t\}.$$

Focusing on elements 2 and 4, their respective vectors under lex-cel are ${\theta }^{{\succsim }^{\prime }}\left(2\right)=(1,1,1,5)$ and ${\theta }^{{\succsim }^{\prime }}\left(4\right)=(1,1,0,6)$. Consequently, lex-cel produces $2{\mathit{P}}_{le}^{{\succsim }^{\prime }}4$.

On the other hand, the matrices for $L^2$ are as follows:

$$M^{{\succsim }^{\prime },2}=\left(\begin{array}{cccc}0& 0& 0& 1\\ 1& 1& 1& 0\\ 0& 0& 0& 3\\ 0& 0& 0& 1\end{array}\right),M^{{\succsim }^{\prime },4}=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 2\\ 0& 0& 0& 3\\ 0& 0& 0& 1\end{array}\right).$$

For column $\widehat{k}=2$, both $M_{\widehat{k}}^{{\succsim }^{\prime },2}$ and $M_{\widehat{k}}^{{\succsim }^{\prime },4}$ add up to 1. However, with $\widehat{s}=1$, $M_{\widehat{s}\widehat{k}}^{{\succsim }^{\prime },4}=1>0=M_{\widehat{s}\widehat{k}}^{{\succsim }^{\prime },2}$. As such, $L^2$ yields $4{\mathit{P}}_{L^2}^{{\succsim }^{\prime }}2$.

Two other lexicographic social ranking solutions have been introduced more recently in the paper [11] with the name of $L^p$ and $L^{p^{*}}$. These solutions aim to use the information about the performance of coalitions only in the case of a tie between two elements whose singleton coalitions belong to the same equivalence class in the power relation. The procedure to compute the $L^p$ social ranking is as follows (if $\left\{i\right\}\sim \left\{j\right\}$, we denote by $k^{ij}$ the index of the equivalence class to which $\left\{i\right\}$ and $\left\{j\right\}$ belong, and we have $M_{1k^{ij}}^{\succsim ,i}=M_{1k^{ij}}^{\succsim ,j}$):

Definition 5

($L^p$ ranking [11]). The $L^p$-solution is the map ${\mathit{R}}_{L^p}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(N\right)$ such that, for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and $i,j\in N$,

$$i{\mathit{P}}_{L^p}(\succsim )j$$

if one of the following conditions hold:

(1) 

$\left\{i\right\}\succ \left\{j\right\}$;

(2) 

$\left\{i\right\}\sim \left\{j\right\}$ and there exists $\widehat{s}\in \{2,\dots ,n\}$ such that

(i) 

if $\widehat{s}>2$, then ${\sum }_{k=1}^{k^{ij}-1}{M}_{sk}^{\succsim ,i}={\sum }_{k=1}^{k^{ij}-1}{M}_{sk}^{\succsim ,j}$ for all $s\in \{2,\dots ,\widehat{s}-1\}$,

(ii) 

${\sum }_{k=1}^{k^{ij}-1}{M}_{\widehat{s}k}^{\succsim ,i}>{\sum }_{k=1}^{k^{ij}-1}{M}_{\widehat{s}k}^{\succsim ,j}$

Otherwise, if $\left\{i\right\}\sim \left\{j\right\}$ and ${\sum }_{k=1}^{k^{ij}-1}{M}_{sk}^{\succsim ,i}={\sum }_{k=1}^{k^{ij}-1}{M}_{sk}^{\succsim ,j}$ for all $s\in \{2,\dots ,n\}$, we have that $i{\mathit{I}}_{L^p}(\succsim )j$.

Example 7.

In the power relation ≿ of Example 2, by condition $1)$, we immediately have the ranking $2{\mathit{P}}_{L^p}(\succsim )1{\mathit{P}}_{L^p}(\succsim )3$.

Now, consider a slightly different power relation ${\succsim }^{\prime }$ such that

$$\{1,2,3\}{\sim }^{\prime }\{1,3\}{\succ }^{\prime }\{2,3\}{\sim }^{\prime }\{1,2\}{\succ }^{\prime }\left\{2\right\}{\sim }^{\prime }\left\{1\right\}{\succ }^{\prime }\left\{3\right\}{\sim }^{\prime }Ø.$$

The quotient order of ≿ is such that

$${\Sigma }_1=\{\{1,2,3\},\{1,3\}\}\succ {\Sigma }_2=\{\{1,2\},\{2,3\}\}\succ {\Sigma }_3=\{\left\{1\right\},\left\{2\right\}\}\succ {\Sigma }_4=\{\left\{3\right\},Ø\}.$$

As before, $1{\mathit{P}}_{L^p}\left({\succsim }^{\prime }\right)3$ and $2{\mathit{P}}_{L^p}\left({\succsim }^{\prime }\right)3$. But now, $\left\{1\right\}{\sim }^{\prime }\left\{2\right\}$ and we have that $k^{12}=3$.

$$M^{\succsim ,1}=\left(\begin{array}{cccc}0& 0& 1& 0\\ 1& 1& 0& 0\\ 1& 0& 0& 0\end{array}\right),M^{\succsim ,2}=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 2& 0& 0\\ 1& 0& 0& 0\end{array}\right),M^{\succsim ,3}=\left(\begin{array}{cccc}0& 0& 0& 1\\ 2& 0& 0& 0\\ 1& 0& 0& 0\end{array}\right).$$

Notice that ${\sum }_{k=1}^2{M}_{2k}^{\succsim ,1}={\sum }_{k=1}^2{M}_{2k}^{\succsim ,2}=2$ and ${\sum }_{k=1}^2{M}_{3k}^{\succsim ,1}={\sum }_{k=1}^2{M}_{3k}^{\succsim ,2}=1$. So, there is no $\widehat{s}$ such that condition $2.ii)$ in Definition 5 is satisfied, subsequently yielding $1{\mathit{I}}_{L^p}\left({\succsim }^{\prime }\right)2$ (also notice that both $L^1$ and $L^2$ in this example place 1 above 2, as in, $1{\mathit{P}}_{L^1}^{\succsim }2$ and $1{\mathit{P}}_{L^2}^{\succsim }2$).

The social ranking solution $L^p$ resolves ties between two elements who exhibit identical individual performances counting the coalitions with a size of two, followed by those of size three, and so forth, that belong to equivalence classes above the one of the two singletons. Consequently, the $L^p$ ranking is not concerned by the actual performance levels exhibited by the considered coalitions, as long as they outperform the singletons’ performance. An alternative social ranking solution, referred to as $L^{p^{*}}$, is designed to rectify this particular effect.

Definition 6

($L^{p^{*}}$ ranking [11]). The $L^{p^{*}}$-solution is the map ${\mathit{R}}_{L^{p^{*}}}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(X\right)$ such that, for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and $i,j\in N$,

$$i{\mathit{P}}_{L^{p^{*}}}(\succsim )j$$

if one of the following conditions holds:

(1) 

$\left\{i\right\}\succ \left\{j\right\}$;

(2) 

$\left\{i\right\}\sim \left\{j\right\}$ and there exists $\widehat{s}\in \{2,\dots ,n\}$ and $\widehat{k}\in \{1,\dots ,k^{ij}-1\}$ such that

(i) 

if $\widehat{s}>2$, then $M_{sk}^{\succsim ,i}=M_{sk}^{\succsim ,j}$ for all $s\in \{2,\dots ,\widehat{s}-1\}$ and $k\in \{1,\dots ,k^{ij}-1\}$;

(ii) 

if $\widehat{k}>1$, then $M_{\widehat{s}k}^{\succsim ,i}=M_{\widehat{s}k}^{\succsim ,j}$ for all $k\in \{1,\dots ,\widehat{k}-1\}$;

(iii) 

$M_{\widehat{s}\widehat{k}}^{\succsim ,i}>M_{\widehat{s}\widehat{k}}^{\succsim ,j}$.

Otherwise, if $\left\{i\right\}\sim \left\{j\right\}$ and $M_{sk}^{\succsim ,i}=M_{sk}^{\succsim ,j}$ for all $s\in \{2,\dots ,n\}$ and $k\in \{1,\dots ,k^{ij}-1\}$, we have that $i{\mathit{I}}_{L^{p^{*}}}(\succsim )j$.

Example 8.

Consider the power relation ${\succsim }^{\prime }$ of Example 7. According to Definition 6, the $L^p$ ranking gives us immediately $1{\mathit{P}}_{L^{p^{*}}}\left({\succsim }^{\prime }\right)3$ and $2{\mathit{P}}_{L^{p^{*}}}\left({\succsim }^{\prime }\right)3$ by condition 6.1. On the other hand, for $\widehat{s}=2$ and $\widehat{k}=2$, conditions $6.2.\left(i\right)$ and $6.2.\left(ii\right)$ are automatically satisfied, as well as condition $6.2.\left(iii\right)$, for $M_{21}^{\succsim ,1}=1>0=M_{21}^{\succsim ,2}$. So, we have $1{\mathit{P}}_{L^{p^{*}}}\left({\succsim }^{\prime }\right)2$.

For alternative axiomatic characterizations of lex-cel, dual-lex, $L^1$, $L^2$, $L^p$, and $L^{p^{*}}$, we refer to the original papers wherein these solutions have been introduced [10,11,12].

4. Social Rankings Inspired by Voting Rules

The family of weighted majority relations was introduced in [15] to rank individuals based on the comparisons of coalitions that are identical except for one element (also called CP-comparisons in [14]). More precisely, for any pair of individuals i and j in N, we consider the set of coalitions $U_{ij}$ and we refer to the CP-comparisons for i and j as the set of comparisons between $S\cup \left\{i\right\}$ and $S\cup \left\{j\right\}$, for any $S\in U_{ij}$. Roughly speaking, a CP-comparison $S\cup \left\{i\right\}$ vs. $S\cup \left\{j\right\}$ can be interpreted as the expression of a “voter” casting a preference relation over i and j.

To introduce the family of weighted majority relations, we first define the notion of ordinal difference between individuals i and j within a coalition S. For any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$, $i,j\in N$ and $S\in U_{ij}$, define the ordinal difference $d_{ij}^S$ such that

$$d_{ij}^S(\succsim )=\left\{\begin{array}{cc}\hfill 1& \mathrm{if}S\cup \left\{i\right\}\succ S\cup \left\{j\right\},\hfill \\ \hfill -1& \mathrm{if}S\cup \left\{j\right\}\succ S\cup \left\{i\right\},\hfill \\ \hfill 0& \mathrm{otherwise}.\hfill \end{array}\right.$$

(1)

Definition 7 (Weighted majority relation).

Let $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and let $\mathbf{w}={\left[w_{ij}^S\right]}_{i,j\in N,S\in U_{ij}}$ be a weight scheme such that $w_{ij}^S\ge 0$ for all $i,j\in N$ and $S\in U_{ij}$. The weighted majority relation associated to $\mathbf{w}$ is the binary relation (notice that $R_{\mathbf{w}}^{\succsim }$ is not necessarily transitive; therefore, it cannot be denoted using the notation ${\mathcal{R}}_{\mathbf{w}}^{\succsim }$, which is reserved to well-defined social rankings). $R_{\mathbf{w}}^{\succsim }\subseteq A\times A$ such that for all $i,j\in A\subseteq N$,

$$i{R}_{\mathbf{w}}^{\succsim }j\iff \sum _{S\in U_{ij}}{w}_{ij}^S{d}_{ij}^S(\succsim )\ge 0.$$

Example 9.

Consider the power relation ≿ of Example 1 and a weight system $\overline{\mathbf{w}}$ such that ${\overline{w}}_{ij}^S=|S|+1$. As indicated in

Table 1. The weight scheme of Example 9 on the power relation of Example 1 concerning the CP-comparisons for individuals 1 and 2.

$\mathit{S}\in {\mathit{U}}_{12}$	$\mathit{S}\cup \left\{1\right\}$ vs. $\mathit{S}\cup \left\{2\right\}$	${\mathit{d}}_{12}^{\mathit{S}}(\succsim )$	${\overline{\mathit{w}}}_{12}^{\mathit{S}}$
Ø	$\left\{1\right\}\prec \left\{2\right\}$	$-1$	1
3	$\{1,3\}\sim \{2,3\}$	0	2

, to compare elements 1 and 2, we compute

$${\overline{w}}_{12}^{Ø}{d}_{12}^{Ø}(\succsim )+{\overline{w}}_{12}^{\left\{3\right\}}{d}_{12}^{\left\{3\right\}}(\succsim )=-1+0<0$$

and so $2P_{\overline{\mathbf{w}}}^{\succsim }1$. In a similar way, we have that

$${\overline{w}}_{13}^{Ø}{d}_{13}^{Ø}(\succsim )+{\overline{w}}_{13}^{\left\{2\right\}}{d}_{13}^{\left\{2\right\}}(\succsim )=1-2<0$$

implying that $3P_{\overline{\mathbf{w}}}^{\succsim }1$ and

$${\overline{w}}_{23}^{Ø}{d}_{23}^{Ø}(\succsim )+{\overline{w}}_{23}^{\left\{1\right\}}{d}_{23}^{\left\{1\right\}}(\succsim )=1-2<0$$

which implies $3P_{\overline{\mathbf{w}}}^{\succsim }2$, too.

In a special case, all CP-comparisons are assigned an equal weight of 1. With such a weight system, the corresponding weighted majority ranking is also known as the Ceteris Paribus (CP-)majority relation that has been introduced and axiomatically studied in [14].

Definition 8

(CP-majority [14]). The CP-majority relation is the binary relation $R_{CP}^{\succsim }\in \mathcal{R}\left(N\right)$ such that, for all $i,j\in N$,

$$i{R}_{CP}^{\succsim }j\iff \sum _{S\in U_{ij}}{d}_{ij}^S(\succsim )\ge 0.$$

for any power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$.

In voting theory, the majority rule is not necessarily a ranking when there are more than two individuals, as illustrated by May’s work [19]. This is also true for weighted majority relations. The following example demonstrates an instance of a CP-majority relation that fails to satisfy transitivity.

Example 10.

Consider the power relation ≿ of Example 1. We have that ${\sum }_{S\in U_{12}}{d}_{12}^S(\succsim )=-1$, and both ${\sum }_{S\in U_{13}}{d}_{13}^S(\succsim )$ and ${\sum }_{S\in U_{23}}{d}_{23}^S(\succsim )$ equal 0. Consequently, the CP-majority relation gives us $1I_{CP}^{\succsim }3$ and $2I_{CP}^{\succsim }3$, yet also $2P_{CP}^{\succsim }1$.

Special weight systems can be generated to guarantee that the corresponding weighted majority relation is transitive. For instance, in [15] a special weight system $\widehat{w}$ was considered wherein ${\widehat{w}}_{ij}^S(\succsim )$ is exactly the number of coalitions S and $S\cup \{i,j\}$ that are comprised between $S\cup \left\{i\right\}$ and $S\cup \left\{j\right\}$ in the power relation ≿. Precisely, let $\mathcal{T}=\{T\in \mathcal{P}(N):S\cup \{i\}\succ T\succ S\cup \{j\}\mathrm{or}S\cup \{j\}\succ T\succ S\cup \{i\left\}\right\}$ be the set of coalitions that are strictly between $S\cup \left\{i\right\}$ and $S\cup \left\{j\right\}$ in the power relation ≿. The weight for the CP-comparison then corresponds to the number of coalitions in $\{S,S\cup \{i,j\left\}\right\}$ that are also in $\mathcal{T}$. More formally,

$${\widehat{w}}_{ij}^S(\succsim )=|\{S,S\cup \{i,j\}\}\cap \mathcal{T}|.$$

(2)

Clearly, ${\widehat{w}}_{ij}^S(\succsim )\in \{0,1,2\}$ (i.e., if $S\cup \left\{i\right\}\succ S\cup \{i,j\}\succ S\succ S\cup \left\{j\right\}$, we obtain ${\widehat{w}}_{ij}^S(\succsim )=2$).

Example 11.

Consider the linear power relation $\succsim \in \mathcal{L}\left(\mathcal{P}\right(N\left)\right)$ such that

$$\{1,3\}\succ \{1,2,3\}\succ \left\{3\right\}\succ \left\{2\right\}\succ \{1,2\}\succ \{2,3\}\succ \left\{1\right\}\succ Ø$$

The CP-comparisons and the corresponding weights are shown in

Table 2. CP-comparisons and the weight scheme $\widehat{\mathbf{w}}$ on the power relation of Example 11.

1 vs. 2	${\widehat{\mathit{w}}}_{12}^{\mathit{S}}$	2 vs. 3	${\widehat{\mathit{w}}}_{23}^{\mathit{S}}$	1 vs. 3	${\widehat{\mathit{w}}}_{13}^{\mathit{S}}$
$\left\{1\right\}\prec \left\{2\right\}$	1	$\left\{2\right\}\prec \left\{3\right\}$	0	$\left\{1\right\}\prec \left\{3\right\}$	0
$\{1,3\}\succ \{2,3\}$	2	$\{1,2\}\prec \{1,3\}$	1	$\{1,2\}\succ \{2,3\}$	0
${\sum }_{S\in U_{12}}{\widehat{w}}_{12}^S{d}_{12}^S(\succsim )=$	1	${\sum }_{S\in U_{23}}{\widehat{w}}_{23}^S{d}_{23}^S(\succsim )=$	$-1$	${\sum }_{S\in U_{13}}{\widehat{w}}_{13}^S{d}_{13}^S(\succsim )=$	0

.

Notice that the CP-majority yields $1I_{CP}^{\succsim }2$ and $1I_{CP}^{\succsim }3$, but also $3P_{CP}^{\succsim }2$, breaking transitivity again. In contrast, using the weighted majority relation with weights $\widehat{\mathbf{w}}$, we obtain the ranking $1I_{\widehat{\mathbf{w}}}^{\succsim }3P_{\widehat{\mathbf{w}}}^{\succsim }2$.

For any linear power relation, the weighted majority relation with weights $\widehat{\mathbf{w}}$ yields a ranking which holds for any linear power ranking. This is proven in [15] by showing that $R_{\widehat{\mathbf{w}}}^{\succsim }$ coincides with the ordinal Banzhaf ranking, a social ranking solution introduced in [15] that is inspired by the celebrated Banzhaf index [20] for coalitional games (see also Theorem 2 in Section 5).

Alternative methods to eliminate cycles in the CP-majority solution have been studied in [13], which proposes social ranking solutions inspired by established voting rules. For instance, a solution akin to the Copeland’s rule [21] has been introduced. This approach ranks individuals by balancing the number of favorable pairwise comparisons against defeats, taking into account the full range of CP-comparisons.

Definition 9

(Copeland-like social ranking [13]). The Copeland-like solution is the map ${\mathit{R}}_{Cop}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(N\right)$ such that for each $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and $i,j\in N$

$$i{\mathit{R}}_{Cop}^{\succsim }j\iff Scor{e}_{Cop}^{\succsim }\left(i\right)\ge Scor{e}_{Cop}^{\succsim }\left(j\right).$$

where $Scor{e}_{Cop}^{\succsim }\left(i\right)=|\{j\in N\setminus \left\{i\right\}:i{P}_{CP}^{\succsim }j\}|-|\{j\in N\setminus \left\{i\right\}:j{P}_{CP}^{\succsim }i\}|.$

Example 12.

Consider the power relation ≿ of Example 1 and the CP-majority relation of Example 10. The corresponding scores are $Scor{e}_{Cop}^{\succsim }\left(1\right)=|Ø|-|\left\{2\right\}|=-1$, $Scor{e}_{Cop}^{\succsim }\left(2\right)=|\left\{1\right\}|-|Ø|=1$, and $Scor{e}_{Cop}^{\succsim }\left(3\right)=|Ø|-|Ø|=0$. The Copeland-like solution therefore yields the ranking $2{\mathit{P}}_{Cop}^{\succsim }3{\mathit{P}}_{Cop}^{\succsim }1$.

Another approach studied in [13] draws inspiration from the Kramer–Simpson methodology in social choice theory, commonly referred to as Minmax REF. In this approach, individuals are ranked in reverse order according to their worst pairwise defeat, taking into account all possible CP-comparisons.

Definition 10

(Kramer–Simpson (KS)-like social ranking [13]). The KS-like social ranking is the map ${\mathit{R}}_{KS}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\to \mathcal{R}\left(N\right)$ such that for each $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ and $i,j\in N$

$$i{\mathit{R}}_{KS}^{\succsim }j\iff Scor{e}_{KS}^{\succsim }\left(i\right)\le Scor{e}_{KS}^{\succsim }\left(j\right),$$

where (we point out a difference in Definition 4 in [13] concerning the notion of $Scor{e}_{KS}^{\succsim }\left(i\right)$, which seems to count ties as defeats).

$$Scor{e}_{KS}^{\succsim }\left(i\right)=\underset{j\in N}{\max }(|\{S\in U_{ij}:S\cup \left\{j\right\}\succ S\cup \left\{i\right\}\}|).$$

Example 13.

Consider the power relation ≿ of Example 1. Individual 1 is defeated once by 2 ($\left\{2\right\}\succ \left\{1\right\}$) and once by 3 ($\{2,3\}\succ \{1,2\}$); thus, $Scor{e}_{KS}^{\succsim }\left(1\right)=1$; individual 2 is also defeated only once by 3 ($\{1,3\}\succ \{1,2\}$), so $Scor{e}_{KS}^{\succsim }\left(2\right)=1$; finally, individual 3 is defeated as well once by 1 ($\left\{1\right\}\succ \left\{3\right\}$) and once by 2 ($\left\{2\right\}\succ \left\{3\right\}$); hence, $Scor{e}_{KS}^{\succsim }\left(3\right)=1$. It follows that, according to the KS-like social ranking, $1I_{KS}^{\succsim }2I_{KS}^{\succsim }3$.

5. Social Ranking Based on Solution Concepts for Coalitional Games

We start this section by introducing some basic definitions from coalitional game theory. A coalitional game on a set N is a map $v:\mathcal{P}\left(N\right)\to \mathbb{R}$ that satisfies $v(Ø)=0$. Let $\mathbf{p}=(p_0,\dots ,p_{n-1})$ be a vector of n non-negative weights such that ${\sum }_{k=0}^{n-1}{p}_k{\displaystyle \left(\begin{array}{c}n-1\\ k\end{array}\right)}=1$. A semivalue ${\pi }_i^{\mathbf{p}}\left(v\right)$ is defined as the sum

$${\pi }_i^{\mathbf{p}}\left(v\right)=\sum _{S\in U_i}{p}_s{m}_i^S\left(v\right).$$

(3)

where $m_i^S\left(v\right)=v(S\cup \left\{i\right\})-v\left(S\right)$ is the marginal contribution of i to $S\cup \left\{i\right\}$, for each $i\in N$ and $S\in \mathcal{P}\left(N\right)$. Since $p_s$ can be seen as the probability that a coalition of size s forms, for each $s\in \{0,\dots ,n-1\}$, ${\pi }_i^{\mathbf{p}}\left(v\right)$ represents an expected marginal contribution of player i to all possible subsets of N containing i. Semivalues have been used in the literature to convert the information of a game v into an overall personal attribution of element i (see, for instance, [22,23,24]). Well-studied semivalues in the literature (also interpreted as power indices) are the Shapley value [25], with $p_s=\frac{1}{n{\displaystyle \left(\begin{array}{c}n-1\\ s\end{array}\right)}}$, and the Banzhaf value [20], with $p_s=\frac{1}{2^{n-1}}$, for each $s\in \{0,\dots ,n-1\}$.

The use of semivalues is rather limited in the ordinal framework, for two distinct coalitional games that are “consistent” with the same power relation may lead to contradictory orderings over the elements. Consider for instance a power relation ≿ on $\mathcal{P}\left(N\right)$ with $N=\{1,2,3\}$ and two elements i and j in N. Take a coalitional game v consistent with ≿, such that

$$v\left(S\right)\ge v\left(T\right)\iff S\succsim T$$

(4)

for all $S,T\in \mathcal{P}\left(N\right)$. One can verify that a semivalue ${\pi }^{\mathbf{p}}$ computed on v yields a relation between i and j corresponding to the sign of the difference

$${\pi }_i^{\mathbf{p}}\left(v\right)-{\pi }_j^{\mathbf{p}}\left(v\right)=(p_0+p_1)(v\left(\left\{i\right\}\right)-v\left(\left\{j\right\}\right))+(p_1+p_2)(v\left(\{i,k\}\right)-v\left(\{j,k\}\right)),$$

(5)

where $k\in N\setminus \{i,j\}$. It is obvious that, except for some particular situations, the difference in relation (5) can be made negative or positive, with a suitable choice of game v (for instance, if $\{j,k\}\succ \left\{i\right\}\succ \{i,k\}\succ \left\{j\right\}$, we necessarily have that $v\left(\right\{i\left\}\right)-v\left(\right\{j\left\}\right)>0$ and $v\left(\right\{i,k\left\}\right)-v\left(\right\{j,k\left\}\right)<0$). So, in general, any attempt to use semivalues to rank individuals seems strongly affected by an arbitrary choice of the game v (among those which are consistent with a given power relation).

The restricted domain of power relations where the ranking provided by a semivalue is invariant to the choice of compatible coalitional games has been studied in the papers [17,26]. For instance, a necessary and sufficient condition for a power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ such that the Banzhaf value of i is larger than the Banzhaf value of element j for all games satisfying condition (4) is given in Definition 11.

Definition 11

([17,26]). Let $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ be a power relation and $i,j\in N$. Consider the sequence of sets $S_1\cup \left\{i\right\},\dots ,S_{n-2}\cup \left\{i\right\}$ with $S_k\in \mathcal{P}\left(N\right)$ and $\{i,j\}\cap S_k=Ø$ and the sequence $T_1\cup \left\{j\right\},\dots ,T_{n-2}\cup \left\{j\right\}$ with $S_k\in \mathcal{P}\left(N\right)$ and $\{i,j\}\cap S_k=Ø$, for all $k=1,\dots ,2^{n-2}$ and such that

$$S_1\cup \left\{i\right\}\succsim \dots \succsim S_{n-2}\cup \left\{i\right\}$$

and

$$T_1\cup \left\{j\right\}\succsim \dots \succsim T_{n-2}\cup \left\{j\right\}.$$

We say that i orderly responds to j if

$$S_k\cup \left\{i\right\}\succsim T_k\cup \left\{j\right\}$$

for all $k=1,\dots ,2^{n-2}$.

Theorem 1

([17,26]). Let $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ be a power relation and $i,j\in N$. Consider the semivalue ${\pi }^{\mathbf{p}}\left(v\right)$ with $p_s=\frac{1}{2^{n-1}}$, for each $s\in \{0,\cdots ,n-1\}$.

Then, ${\pi }_i^{\mathbf{p}}\left(v\right)\ge {\pi }_j^{\mathbf{p}}\left(v\right)$ for all coalitional games v such that $v\left(S\right)\ge v\left(T\right)\iff S\succsim T$ if and only if i orderly responds to j.

Example 14.

Consider the power relation of Example 4. For element 1, we have

$$\{1,3\}\succ \{1,2\}\succ \left\{1\right\}\sim \{1,2,3\}$$

and for element 4,

$$\{2,4\}\succ \left\{4\right\}\succ \{1,4\}\sim \{2,3,4\}.$$

Notice that $\{1,3\}\sim \{2,4\}$, $\{1,2\}\sim \left\{4\right\}$, $\left\{1\right\}\sim \{1,4\}$ and $\{1,2,3\}\sim \{2,3,4\}$. Consequently, 1 orderly responds to 4 as well as 4 to 1. By Theorem 14, for any coalitional game that satisfies relation (4) with respect to ≿ of Example 4, we have that the Banzhaf value of element 1 is identical to the Banzhaf value of element 4 (a similar consideration can be made between 1 and 3 and between 3 and 4). One can also verify that 2 orderly responds to 1, but it is not true that 1 orderly responds to 2. So, again by Theorem 14, for any coalitional game that satisfies relation (4) with respect to ≿ of Example 4 we have that the Banzhaf value of 2 is strictly larger than the Banzhaf value of 1 (and the one of 3 and of 4).

Another approach inspired by semivalues and applying to a larger family of power relation has been introduced in [15], starting with the counterpart of the notion of marginal contribution in an ordinal framework.

Definition 12

(Ordinal marginal contribution [15]). Let $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$. For each element $i\in N$ and all $S\in U_i$, we define the ordinal marginal contribution $M_i^S(\succsim )$ of i to coalition $S\cup \left\{i\right\}$ in ≿ as follows:

$$M_i^S(\succsim )=\left\{\begin{array}{cc}\hfill 1& ifS\cup \left\{i\right\}\succ S,\hfill \\ \hfill -1& ifS\succ S\cup \left\{i\right\},\hfill \\ \hfill 0& otherwise.\hfill \end{array}\right.$$

(6)

Clearly, the ordinal marginal contribution of an element i to a coalition $S\cup \left\{i\right\}$ only depends on the power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$, and not on the choice of a coalitional game consistent with ≿ according to relation (4). Then, the ordinal Banzhaf relation is simply defined as a map that associates to each power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ a ranking over N induced by the average ordinal marginal contribution of each element of N to all possible coalitions containing it. Precisely,

Definition 13

(Ordinal Banzhaf relation [15]). Let $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$. The ordinal Banzhaf ranking${\mathit{R}}_{Bh}^{\succsim }\in \mathcal{R}\left(N\right)$ is such that

$$i{\mathit{R}}_{Bh}j\iff \sum _{S\in U_i}{M}_i^S(\succsim )\ge \sum _{S\in U_j}{M}_j^S(\succsim )$$

(7)

for all elements $i,j\in N$.

Example 15.

Consider the power relation from Example 11.

As shown by the sum of ordinal marginal contributions in

Table 3. Ordinal marginal contributions derived from the power relation in Example 11.

$\mathit{S}\in {\mathit{U}}_1$	${\mathit{M}}_1^{\mathit{S}}(\succcurlyeq )$	$\mathit{S}\in {\mathit{U}}_2$	${\mathit{M}}_2^{\mathit{S}}(\succcurlyeq )$	$\mathit{S}\in {\mathit{U}}_3$	${\mathit{M}}_3^{\mathit{S}}(\succcurlyeq )$
Ø	1	Ø	1	Ø	1
$\left\{2\right\}$	$-1$	$\left\{1\right\}$	1	$\left\{1\right\}$	1
$\left\{3\right\}$	1	$\left\{3\right\}$	$-1$	$\left\{2\right\}$	$-1$
$\{2,3\}$	1	$\{1,3\}$	$-1$	$\{1,2\}$	1
${\sum }_{S\in U_i}{m}_i^S(\succsim )$	2		0		2

, the ordinal Banzhaf ranking on ≿ is such that $1{\mathit{I}}_{Bh}^{\succsim }3{\mathit{P}}_{Bh}^{\succsim }2$.

Since the ordinal Banzhaf relation is represented by a numerical score, it is obvious that it always provides a ranking over the elements of N. It is less obvious that the weighted majority relation with weights $\widehat{\mathbf{w}}$ yields a ranking in general. Nevertheless, in [15] the authors proved that the weighted majority relation with weights $\widehat{\mathbf{w}}$ and the ordinal Banzhaf relation coincide on linear power relations.

Theorem 2

([15]). Let $\succsim \in \mathcal{L}\left(\mathcal{P}\right(N\left)\right)$. Then, ${\mathit{R}}_{Bh}^{\succsim }(\succsim )={\mathit{P}}_{\widehat{\mathbf{w}}}^{\succsim }$.

As a consequence of Theorem 2, and as already stated in the previous section, the weighted majority relation with weights $\widehat{\mathbf{w}}$ is a well-defined ranking solution when it is applied to the domain of linear power relations.

A social ranking that is strongly based on models of coalition formation has been introduced in [16]. More precisely, in [16] the authors study a notion of set-valued social ranking that is defined as a set-valued function $\overline{\mathit{R}}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\rightrightarrows \mathcal{R}\left(N\right)$ associating to each power relation a subset of rankings over the individuals ${\overline{\mathit{R}}}^{\succsim }\subseteq \mathcal{R}\left(N\right)$. In particular, core stability, a widely studied notion in the field of coalition formation games [27,28], is a central notion for the set-valued social ranking studied in [16]. To introduce this notion, we need some further notations. A partition $\Pi =\{{\Pi }_1,\dots ,{\Pi }_m\}$, for some integer $m\le N$, where N is a collection of m non-empty subsets of N that are disjoint (i.e., ${\Pi }_h\cap {\Pi }_l=Ø$ for all $h,l\in \{1,\cdots ,m\}$) and cover N (i.e., ${\bigcup }_{h=1}^m{\Pi }_h=N$). Given a partition $\Pi$ of N and an individual $i\in N$, we denote as $\Pi \left(i\right)$ the (unique) coalition in $\Pi$ containing i.

Now, given a partition $\Pi$ of N and a power relation $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$, we say that $\Pi$ is blocked by a non-empty coalition $S\in A$ if $S\succ \Pi \left(i\right)$ for all $i\in S$. So, a partition $\Pi$ is considered blocked by a coalition S when, for every individual i within S, coalition S attains a higher rank in the power relation, compared to the rank of the coalition within $\Pi$ that contains i. The intuition here is that, if individuals prefer to stay in top-ranked coalitions, each individual’s inclination leans toward S over the coalition assigned to them by partition $\Pi$ (in other words, $\Pi$ is not “stable”). A partition $\Pi$ is referred to as a core-partition if it achieves stability, meaning it is not blocked by any coalition S. Formally, a partition $\Pi$ of N is core-stable in $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ if for each $S\in \mathcal{P}\left(N\right)$, $S\ne Ø$, there exists $i\in S$ such that ${\Pi }_i\succsim S$. The set of core-stable partitions in ≿ is denoted by $\mathcal{C}(\succsim )$.

Example 16.

Consider again the power relation ≿ of Example 1. The set of core-stable partitions in ≿ is as follows:

$$\mathcal{C}(\succsim )=\left\{\Pi =\left\{\{1,2,3\}\right\},{\Pi }^{\prime }=\{\{1,3\},\left\{2\right\}\},{\Pi }^{″}=\{\left\{1\right\},\{2,3\}\}\right\}.$$

As remarked in [16], the non-emptiness of the core-partition social ranking can be directly proved as a consequence of some results shown in [29]. A simple procedure has been proposed in [16] to compute an element of a core-partition social rankings. We introduce the procedure as the following pseudo-code (Algorithm 1).

Algorithm 1: Finding core-partitions on power relations

Based on the fact that the set of core-stable partitions is always non-empty, in [16] the authors introduce the notion of core-partition social ranking as the set-valued social ranking associating to each power ranking $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ the set of rankings “induced” by partitions $\Pi$, as follows:

Definition 14

(Core-partition social ranking [16]). The core-partition social ranking is the map set-valued social ranking ${\overline{\mathit{R}}}_{\mathcal{C}}:\mathcal{R}\left(\mathcal{P}\left(N\right)\right)\rightrightarrows \mathcal{R}\left(N\right)$ associating to each power ranking $\succsim \in \mathcal{R}\left(\mathcal{P}\right(N\left)\right)$ the set of rankings

$${\overline{\mathit{R}}}_{\mathcal{C}}^{\succsim }=\{R\in \mathcal{R}\left(N\right):\exists \Pi \in \mathcal{C}(\succsim )s.t.Risinducedby\Pi \},$$

where a ranking R induced by a partitions Π is such that

$$iRj\iff \Pi \left(i\right)\succsim \Pi \left(j\right).$$

Example 17.

Continue to consider Example 16. The core-partitions on ≿ is

$${\overline{\mathit{R}}}_{\mathcal{C}}^{\succsim }=\left\{\left\{1I2I3\right\},\left\{1I3P2\right\},\left\{2I3P1\right\}\right\}$$

6. An R Package for Social Ranking Computation

The socialranking package in R, available on CRAN, serves as a practical tool for researchers interested in experimenting with these social ranking methodologies. It encompasses many of the aforementioned solution concepts and offers the ability to introduce new ones. This section serves to highlight the fundamental structure and usage of the package. A more complete guide is available as a vignette on the CRAN page [9].

Vectors of unit types (such as number or character) represent coalitions. For example, c(1,2,3) is the coalition $\{1,2,3\}$, c(1) (or just 1) a singleton, and c() the empty set.

Orders between coalitions are represented by a list of lists, wherein each nested list can be thought of as an equivalence class containing one or more vectors of coalitions.

Trying to construct the power relation ≿ from Example 1, Listing 1 shows how it can be achieved by passing a list of equivalence classes to PowerRelation(). This function returns a PowerRelation object. As a more convenient alternative, as.PowerRelation() can be passed a character string. Here, every alphanumerical character represents an individual element. Coalitions are ranked intuitively with the ˜ and > symbols.

Listing 1. Creating power relations.

Once the PowerRelation object is constructed, it can be passed to a social ranking function to construct a SocialRanking object, which is an ordinal relation between the elements. Additionally, ranking solutions make use of some numerical comparisons to rank its elements, such as the lex-cel comparing vectors ${\theta }_i$ of the number of occurrences in each equivalence class, or the ordinal Banzhaf method comparing the number $M_i^S$ of positive versus negative ordinal marginal contributions an element makes by joining a coalition. These values can also be requested by passing the PowerRelation object to a scores function, as shown in Listing 2.

Listing 2. Applying social ranking functions.

For introducing one’s own ranking function, Listing 3 demonstrates the simple ${\mathit{R}}_0$ solution from the introduction, as well as the much more sophisticated $L^p$-solution from Definition 5, both of which are not currently present in the package. The function doRanking() aids us in creating a SocialRanking object.

In the case of ${\mathit{R}}_0$, it is easy for each element i to determine k such that $\left\{i\right\}\in {\Sigma }_k$. We construct a vector of numbers wherein each index represents the index k for each element in pr$elements by calling pr$coalitionLookup(el). Then, elements with a lower number, implying that its singleton belongs to a higher-ranking equivalence class, will be strictly preferred over elements with a higher number.

As for $L^p$, L1Scores() already produces the correct matrix $M^{\succsim ,i}$ for each element $i\in N$. However, the way the matrices are compared and sorted is fairly different, which requires either the introduction of new R classes or a custom comparison function which is passed as a parameter to doRanking(). This comparison function takes two parameters, say a and b, and returns a positive number if a > b, a negative number if a < b, or 0.

To enhance user experience and encourage further exploration, the package includes a set of helper functions. These functions streamline common tasks such as generating power sets with createPowerSet(), augmenting existing PowerRelation objects with appendMissingCoalitions(), modifying it such that it becomes monotonic ($T\supseteq S\Rightarrow T\succsim S$), and dynamically generating permutations of power relations via powerRelationGenerator(). Listing 4 briefly demonstrates these functionalities.

Listing 3. An implementation of the ${\mathit{R}}_0$ and $L^p$-solution.

The socialranking package is designed to be a versatile tool for researchers and practitioners in computational social choice. Its architecture is modular, facilitating the addition of new social ranking algorithms and methodologies, as illustrated in Listing 3. As also explained in the vignette [9], contributions from the academic and broader communities are highly encouraged to enhance the package’s capabilities, improve its reliability, and broaden its applicability. Such contributions can substantially enrich this open-source initiative, further establishing it as an additional resource for research in the framework of social rankings.

Listing 4. Helper functions in the socialranking package.

We conclude this section with a numerical example representing an (invented) bicameral legislature on the same lines of the one presented in Section 1 with the objective to show that the use of our package may offer a concrete opportunity to facilitate the social ranking computation in practical problems.

Example 18.

To illustrate a potential application of the socialranking package in practice, following the example of a bicameral legislature introduced in Section 1, we consider a situation with a set $N=\{1,2,3,4\}$ of four political parties and where the first house is composed by $n^1=9$ members while the second house is composed by $n^2=6$ members. Following the example in Section 1, we imagine a country with a bicameral legislature comprising two houses. The $n^1=9$ seats in House 1 and $n^2=6$ seats in House 2 are distributed between the four major ruling parties, the Progressive Party (1), the Conservative Party (2), the Green Party (3), and the Libertarian Party (4), $N=\{1,2,3,4\}$. Suppose that each political party in N is represented in the two respective houses, as shown in

Table 4. Distributions of seats in a bicameral legislature.

Party	1	2	3	4	Total
House 1	$w_1^1=4$	$w_2^1=2$	$w_3^1=2$	$w_4^1=1$	9
House 2	$w_1^2=3$	$w_2^2=2$	$w_3^2=0$	$w_4^2=1$	6

.

So, the three-valued function representing the outcomes of the coalitions is

$$f\left(S\right)=\left\{\begin{array}{cc}\hfill 2,& if\sum _{i\in S}{w}_i^1\ge 5and\sum _{i\in S}{w}_i^2\ge 4;\hfill \\ \hfill 1,& if\sum _{i\in S}{w}_i^1\ge 5and\sum _{i\in S}{w}_i^2<4;\hfill \\ \hfill 0,& otherwise.\hfill \end{array}\right.$$

One can easily verify that $f\left(S\right)=2$ for all $S\in A=\left\{\right\{1,2\},\{1,4\},\{1,2,3\},\{1,2,4\}$, $\{1,3,4\},N\}$, $f\left(S\right)=1$ for all $S\in B=\left\{\right\{1,3\},\{2,3,4\left\}\right\}$, and $f\left(S\right)=0$ for all the remaining coalitions $S\in \mathcal{P}\left(N\right)\setminus (A\cup B)$. Such a function yields the power relation ≿ such that

$$\{1,2\}\sim \{1,4\}\sim \{1,2,3\}\sim \{1,2,4\}\sim \{1,3,4\}\sim N\succ \{1,3\}\sim \{2,3,4\}\succ S,$$

where all coalitions $S\in \mathcal{P}\left(N\right)$ not explicitly listed belong to the last equivalent class.

By means of the instructions introduced in this section, we can use our socialranking package to compute the social rankings presented in this paper. As simple games are monotonic, inputting the information in R can be greatly simplified by, one, only specifying the minimal winning coalitions for the first two equivalence classes, and two, utilizing the combination of appendMissingCoalitions and makePowerRelationMonotonic to make the power relation object total and monotonic. Alternatively, if one were to experiment more with three-valued simple games with associated weight vectors, Listing 5 also demonstrates how this could be achieved.

Running the data through all the solutions, it is found that a large majority of social rankings, precisely lex-cel, dual-lex, $L^1$, $L^2$, $L^{p^{*}}$, Copeland-like, and ordinal Banzhaf, all yield the same output, that is, the ranking $1{\mathit{P}}^{\succsim }2{\mathit{I}}^{\succsim }4{\mathit{P}}^{\succsim }3$ (note that parties 2 and 4 are equally ranked, despite the fact that the weight of 2 in each house is strictly larger than the one of 4). Only the $L^p$ and $KS$-like solutions give the slightly different ranking $1{\mathit{P}}^{\succsim }2{\mathit{I}}^{\succsim }3{\mathit{I}}^{\succsim }4$, where parties 2, 3, and 4 are equally ranked.

Listing 5. Applying the socialranking package.

7. Conclusions

In this paper, we have undertaken a comprehensive examination of various social rankings presented in the recent literature. To better understand which social ranking solution is most suitable for a given application context, we suggest that the interested readers look at the original papers wherein such solutions were introduced. In fact, almost all social rankings considered in this paper were originally proposed trough an axiomatic approach, grounded in properties motivated by specific application contexts. Although interesting, a comprehensive analysis of those properties from the literature is beyond the scope of this paper. On the other hand, to guide the interested reader toward the appropriate choice of a social ranking, we recommend to adopt the following general strategy. If the application context requires a prioritization in the evaluation of some particular criteria of performance, such as the positions in a power relation, or other criteria, like the size of coalitions, we suggest to look at solutions in the family of lexicographic social rankings (Section 3). Differently, if the objective is to highlight the differences between individuals in terms of their ability to collaborate with predefined groups, the family of solutions to be considered should be the one of social rankings based on voting rules (Section 4). Finally, if the main objective is to rank individuals considering a fairness principle, or even a notion of stability within coalitions, the family of social rankings inspired by solutions for coalitional games (Section 5) could be the most suitable one.

Our primary aim has been to provide a self-contained and readily applicable reference to existing methodologies aimed at ranking elements within a set based on a ranking over their subsets. It is noteworthy that certain social rankings discussed in this paper have also been employed in diverse contexts in the related literature, and we herein cite a selection of illustrative instances.

Algorithm 1 has also been studied in [18], where it served as a preliminary framework for the integration of coalition formation models with the domain of social rankings. Within the context of [18], the authors explore alternate models of coalition formation, wherein rational agents possess preferences over partitions of the agent set. In this framework, agents take into consideration both the relative ranking of the coalitions they are part of, as determined by a power relation, and their position in the social ranking computed within each element of a partition. More sophisticated algorithms presented in [18] take in as input, in addition to a power relation, the lex-cel to evaluate the position of agents within coalitions.

Other promising directions for the application of social rankings are in the field of the value alignment problem [30] where, given a collection of candidate norms, a decision-maker wants to select the set of norms (called a norm system) that is best “aligned” with some predefined moral values. Given the preferences of the decision-maker, over moral values in a value system, and the relations of promotion and demotion between norms and moral values (also interpreted as norm features) some adaptations of the lex-cel are used in this framework to generate a ranking over single norms from preferences over sets of norm features.

The social ranking problem has also been studied under slightly different perspectives. An axiomatic study on a restricted domain of coalitions has been presented in [31]. Computational aspects via numerical simulations of the CP-majority have been analyzed in [32].