# Desirability and social ranking

Michele Aleandri, Felix Fritz, Stefano Moretti

► To cite this version:

Michele Aleandri, Felix Fritz, Stefano Moretti. Desirability and social ranking. Social Choice and Welfare, 2025, 65 (3), pp.721-763. 10.1007/s00355-025-01590-1 . hal-05365555

HAL Id: hal-05365555

https://hal.science/hal-0536555v1

Submitted on 14 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
Desirability and social ranking

Michele Aleandri¹*, Felix Fritz² and Stefano Moretti²

¹*Department Economics and Finance, LUISS University, viale Romania 32, Roma, 00198, Italy.

²LAMSADE, CNRS, Université Paris-Dauphine, Université PSL, Paris, 75016, France.

*Corresponding author(s). E-mail(s): maleandri@luiss.it;

Contributing authors: felix.fritz@dauphine.psl.eu;

stefano.moretti@dauphine.fr;

**Abstract**

We present an axiomatic study of various solutions to the social ranking problem, where a solution links any ranking of coalitions of players to a binary relation between individual players. We focus on solutions that align with the desirability relation, asserting that player *i* is more desirable than player *j* if any coalition including *i* but not *j* ranks higher than the corresponding coalition formed by replacing *i* with *j*. Unlike previous characterizations, our study highlights the central role of the desirability property as a foundational axiom in the characterization of five solutions from the related literature: *Ceteris Paribus* majority, lexicographic excellence and its dual, $L^{(1)}$ solution and its dual. Our main results reveal additional similarities among these five solutions and emphasize the essential features that should be considered when selecting the most appropriate solution for a given scenario. A practical application involving a bicameral legislature is also presented.*

**Keywords:** social ranking problem, axiomatic approach, desirability, coalitional ranking, coalitional games, power index

<footnote>*Conflicts of interests: All authors have no conflicts of interest. Funding: A support of the ANR project THEMIS (ANR-20-CE23-0018) is gratefully acknowledged. Michele Aleandri is member of the Gruppo Nazionale per l'Analisi Matematica, la Probabilità e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM).</footnote>
# 1 Introduction

The design of indices to assess the power of players in a legislature or in other voting situations is a long-standing area of study in the field of simple games. In this paper, we focus on methods for comparing players’ power in an ordinal manner, extending the notion of simple games (where coalitions may be winning or losing) to games where coalitions are partitioned into more than two classes (like, for instance, in three-valued simple games [1] and in (2, k) simple voting games [2, 3]). As further discussed in Section 2, in this setting, coalitional values are a mere numerical representation of ordinal preferences over coalitional outcomes; so, our problem boils down to the problem of ranking players based on a ranking of their coalitions. This problem is also known in literature as the social ranking problem, and a solution is defined as a map that associates to any coalitional ranking (i.e., a ranking over the subsets of a finite set N of players) a total binary relation over the elements of N [4, 5]. A very intuitive concept that, partially, addresses the social ranking problem, is the notion of desirability, which has been widely studied in the field of coalitional games to compare two players based on their respective contributions to any coalition [6–9]. Precisely, a player i is said to be more desirable than a player j if player i always contributes at least as much as player j when joining coalitions containing neither i nor j. Unfortunately, the desirability relation is not necessarily complete in a game. So, although many authors have studied particular classes of coalitional games where the desirability relation is complete [8, 10–14], it does not match the definition of a solution for the social ranking problem in general.

In this study, we focus on solutions that align with the desirability relation for any pair of players such that a desirability relation holds, while they complete the relation between the other pairs of players in a compatible way with additional basic properties aimed at comparing the relative relevance of players. In fact, the solutions studied in this paper have been axiomatically characterized in previous articles using alternative sets of properties [4, 5, 15], including different notions of monotonicity. The key differences among these monotonicity properties (as illustrated in Section 1.1) make it difficult to perform a clear axiomatic comparison of the considered solutions, as a clearly identified set of core properties common to all axiomatic systems is missed. In contrast, our main results focus on axiomatic characterizations that emphasize a well-defined central property: desirability. Any solution that satisfies the aforementioned monotonicity properties, along with other axioms, also satisfies the desirability property. In this respect, the axiomatic characterizations of solutions discussed in this article are stronger than those presented in the related literature.

Specifically, we analyze the following solutions: 1) the *Ceteris Paribus (CP)-majority* [5], which ranks two players *i* and *j* according to a majority rule. The “voters” are all coalitions *S* that contain neither *i* nor *j*, and each voter-coalition *S* casts its vote for the player who contributes more to its total value when added, i.e., between *S* ∪ {*i*} and *S* ∪ {*j*}. It is worth noting that, unlike the other solutions considered in this paper, CP-majority does not necessarily return a transitive binary relation over players; 2) the *lexicographic excellence* solution (*lex-cel*) [4], which compares players lexicographically based on their occurrences in the equivalence classes of a coalitional ranking. The comparison starts in the first equivalence class, prioritizing players with
a higher number of occurrences. In case of a tie, this process moves to the next class, continuing until a difference is found or until all equivalence classes have been considered without breaking the tie; 3) the *L*⁽¹⁾ solution [15], similar to lex-cel, ranks players based on their occurrences within the equivalence classes, using a lexicographic comparison from the first to the last class. Additionally, it incorporates a secondary principle that favors smaller coalitions within the same equivalence class, assuming that they are more likely to form and should therefore carry more weight.

Moreover, by making a simple adjustment to just one axiom, we achieve two other sets of independent axioms that provide new characterizations of a dual version of lex-cel and *L*⁽¹⁾ named in the literature as *dual-lex* [4, 16] and *L*⁽¹⁾ [15], respectively.

In our analysis, we deal with ten different axioms in total, desirability being central to every axiomatic system considered. Another axiom, inspired by desirability, applies to coalitions with equal size, and is necessary to complete the characterization of the *L*⁽¹⁾ solution and its dual *L*⁽¹⁾. We classify the remaining axioms studied in this paper into two main families. In the first family, we group the axioms dealing with alternative notions of invariance of solutions to permutations of players, or of coalitions. Those axioms are named *neutrality*, which states that the identity of the players should not affect their ranking; *equality of coalitions*, *coalitional anonymity* and *per-size coalitional anonymity*, all dealing with alternative notions of independence of the identity of coalitions, with the latter also accounting for their cardinality. Notice that these axioms do not identify a specific relevance relation *a priori*, and they are often used in combination to characterize coalitional rankings where a solution should declare players equally relevant (indeed, these axioms are satisfied by solutions that regard all players as equally relevant).

The second family of axioms aims at keeping relevance relations consistent across coalitional rankings subject to slight modifications in coalitions' positions. They encapsulate some distinctive features of the solutions under study and can be used to guide the selection of the most suitable ranking according to some specific criteria. CP-majority needs the *consistency after tiebreaks*, specifying that a solution should behave consistently across two coalitional rankings when the same set of ties are broken. Lex-cel requires the *independence from the worst set*, interpreted as a principle aimed to reward the excellence of coalitions. Similarly, its dual version requires the *independence from the best set* to punish mediocrity. *L*⁽¹⁾, in addition to the independence from the worst set, also demands the *consistency after indifference*, saying that a solution should behave coherently across two coalitional rankings obtained by improving some coalitions from the worst class, and where players were originally ranked indifferent.

The road-map of the article is as follows. After discussing the main contributions of our work to the related literature in Section 1.1, we continue in Section 2 with some preliminaries and the definitions of the main notions, and in Section 3 with the presentations of the solutions studied in this paper. In Section 4, we proceed by introducing the axioms employed in this paper, accompanied by a comprehensive discussion and interpretation of each. Section 5 is aimed at presenting the main results of this study, that is, the axiomatic characterization of the CP-majority (Section 5.1), the lex-cel and its dual (Section 5.2) and the *L*⁽¹⁾ solution and its dual (Section 5.3).
The logical dependencies among the axioms considered in this paper are presented and analyzed in Section 6. Section 7 concludes with the discussion on potential implications of the key findings for future research directions. A practical scenario involving a bicameral legislature in the Netherlands and where the solutions considered in this article are used to rank political parties is also presented in the Appendix A.1.

## 1.1 On the role of monotonicity in the related literature

A Monotonicity axiom has been used in [4] as part of the axiomatic characterization of the lex-cel solution (along with Neutrality, Coalitional Anonymity, and Independence of the Worst Set). The axiom states that if a solution ranks two players i and j equally, breaking some ties between coalitions of type $S \cup \{i\}$ and $S \cup \{j\}$, with S containing neither i nor j, results in i being ranked strictly above j. Path Monotonicity with Priority to the Smallest Coalition is an axiom used in [15] to axiomatically characterize the $L^{(1)}$ solution (along with Neutrality, Super Weak Coalitional Anonymity, and Independence from the Worst Class). It implies the Monotonicity axiom used in [4] and applies the notion of a path between two players (i.e., a sequence of improving and deteriorating changes) to keep into account the size of the smallest coalitions involved in a path. Finally, [5] provides an axiomatic characterization of the CP-majority solution using Positive Responsiveness (along with Neutrality and Equality of Coalitions). Positive Responsiveness specifies a monotonic change of the relation between two players in response to a set of improvements of coalitions containing a (non-dominated) player but not the other (reversing a strict relation is not allowed). None of the monotonicity properties mentioned earlier are used in this paper to characterize the five studied solutions.

The only exception in the literature concerning an axiomatic characterization of the lex-cel solution and its dual without making use of a monotonicity property is the one presented in [16], where it has been proved that lex-cel and its dual are the only pair of solutions satisfying four properties: Consistency, Complete Dominance, Neutrality, and Weak Coalitional Anonymity. The setting studied in [16] is more general than ours due to the fact that a solution is defined on rankings whose domain of coalitions is assumed to be variable, and the property of Consistency governs the way to build the relation between two players when combining coalitional rankings over two distinct sets of coalitions. Moreover, the Complete Dominance property specifies that a player i should be strictly more relevant than a player j in a partial coalitional ranking if any feasible coalition S containing i but not j is strictly stronger than any coalition T containing j but not i (with $S \setminus \{i\}$ not necessarily equal to $T \setminus \{j\}$, as it is instead required by the notion of desirability). As observed in [16], it is easy to find a situation where the desirability axiom (also called Weak Dominance according to [16] and [17]) specifies a strict relation between two players, while the Complete Dominance property does not specify any relation (see [16] page 561, first paragraph). However, it is still an open question how to combine the Consistency property and desirability property, together with other axioms, to characterize each solution considered in this article.
## 2 Preliminary notions and notations on coalitional rankings

In the following, $N$ is a finite set whose elements are called players and $2^N$ is the set of subsets of $N$, also called coalitions, while $\mathcal{F}(N) = 2^N \setminus \{\emptyset\}$ denotes the set of non-empty subsets of $N$. Given a set $S \in 2^N$, its cardinality is indicated by $|S|$ ($|\emptyset| = 0$). In the following, $n = |N|$. A binary relation on $N$ is a set $R \subseteq N \times N$ and the fact that $(i, j) \in R$, for some $i, j \in N$, is also denoted as $iRj$. A binary relation $R$ is said transitive if $iRj$ and $jRk$ imply $iRk$, for each $i, j, k \in N$; $R$ is said total or complete if $iRj$ or $jRi$, for each $i, j \in N$; $R$ is said antisymmetric, if $iRj$ and $jRi$ imply $i = j$, for each $i, j \in N$. A transitive and total binary relation on a finite set $N$ is called a total preorder or a ranking on $N$. A ranking on the set of non-empty subsets of $N$ is called a coalitional ranking. A transitive, total and antisymmetric binary relation on $N$ is called a total order. $\mathcal{B}(N)$ and $\mathcal{R}(N)$ denote, respectively, the sets of total binary relations and the sets of rankings (or total preorders) on a finite set $N$.

To represent a coalitional ranking, in general we use the notation $\gtrsim$, with $\gtrsim \in \mathcal{R}(\mathcal{F}(N))$. In the related literature, a coalitional ranking $\gtrsim$ is also called power relation [5, 18]. The symmetric part of $\gtrsim$ is denoted by $\sim$ ($S \sim T$ if both $S \gtrsim T$ and $T \gtrsim S$). Conversely, $\succ$ denotes the asymmetric part ($S \succ T$ if $S \gtrsim T$ but not $T \gtrsim S$). Thus, for any pair of subsets $S, T \in \mathcal{F}(N)$, $S \succ T$ conveys that $S$ is strictly stronger (or preferred) than $T$, while $S \sim T$ indicates equivalence in strength (or indifference) between $S$ and $T$.

Suppose a coalitional ranking $\gtrsim \in \mathcal{R}(\mathcal{F}(N))$ is of the form<fnref n="1" />

$$S_1 \gtrsim S_2 \gtrsim S_3 \gtrsim \dots \gtrsim S_{2^n-1}.$$

Given this ranking $\gtrsim$, consider its quotient order, denoted as follows

$$\Sigma_1 \succ \Sigma_2 \succ \Sigma_3 \succ \dots \succ \Sigma_l$$

in which the subsets $S_j$ are grouped in the equivalence classes $\Sigma_k$ generated by the symmetric part of $\gtrsim$. This means that all the sets in $\Sigma_1$ are indifferent to $S_1$ and are strictly better than the sets in $\Sigma_2$ and so on. Observe that $\Sigma_i = \{S_i\}$ for any $i = 1, \dots, 2^n - 1$ if and only if $\gtrsim$ is a total order.

**Example 1.** As an example of a coalitional ranking in a practical situation, consider a bicameral legislature where some political parties of a set $N$ are represented in two distinct houses, namely, the Lower House and the Upper House, by $n_l$ and $n_u$ members, respectively. Precisely, suppose that each political party $i$ in $N$ is represented by $w_i^l$ members in the Lower House and $w_i^u$ in the Upper House, and that the Lower House has the authority to either accept or reject a bill based on whether there is or is not a majority of at least $q^l$ of its members in favor. If the Lower House approves the bill, it is then transmitted to the Upper House, where a similar process occurs, requiring a majority of at least $q^u$ members for acceptance. The bill becomes law only if it gains approval from both houses. Notably, only the Lower House holds the prerogative to

<footnote n="1">¹In the rest of the paper, when a ranking is presented in the form of a chain like $i R \dots R j R \dots R k$, it is understood that any element in the chain is in relation $R$ with each element in the chain on its right.</footnote>
initiate the submission of a bill and commence the entire procedure. As it was initially suggested and discussed in [1], such a situation can be represented as a three-valued simple game (N, v) where the function v: 2N → {0, 1, 2} is such that

$$v(S) = \begin{cases} 2, & \text{if } \sum_{i \in S} w_i^\ell \ge q^\ell \text{ and } \sum_{i \in S} w_i^u \ge q^u; \\ 1, & \text{if } \sum_{i \in S} w_i^\ell \ge q^\ell \text{ and } \sum_{i \in S} w_i^u < q^u; \\ 0, & \text{otherwise.} \end{cases} \quad (1)$$

As for simple games, where classical 0 and 1 values are used to represent losing and winning coalitions, respectively, the values associated with coalitions in game v of Example 1 do not immediately convey a connotation in terms of transferable utility. Nevertheless, their higher magnitudes allow for representing most preferred coalitional outcomes. The ordering of 2 > 1 > 0 merely signifies a rising preference of political parties regarding outcomes that coalitions may guarantee, without quantifying a specific level of utility.

In general, in the context of a multi-cameral electoral system [10], where the approval of an alternative such as a bill or an amendment supported by a coalition needs a sequential approval in a series of elections within distinct chambers, a coalition prevailing in a greater number of chambers might be preferred to one prevailing in a lower one, and so the respective coalitional values should be ranked according to such preferences. Due to its ordinal nature, such a situation can be described as a coalitional ranking $\succeq \in \mathcal{R}(\mathcal{F}(N))$ such that for all coalitions $S, T \in \mathcal{F}(N)$:

$$S \succeq T \Leftrightarrow v(S) \ge v(T). \quad (2)$$

**Example 2.** A bicameral legislature with two houses is composed of members of three political parties, $N = \{1, 2, 3\}$. Seats are shared equally in the lower house, $(w_1^\ell, w_2^\ell, w_3^\ell) = (2, 2, 2)$, while 2 has one seat less in the upper house, $(w_1^u, w_2^u, w_3^u) = (2, 1, 2)$. The quota to reach in both houses is $q^\ell = q^u = 4$. The corresponding three-valued simple game according to relation (1) gives value 2 to coalitions $\{1, 2, 3\}$ and $\{1, 3\}$, value 1 to coalitions $\{1, 2\}$ and $\{2, 3\}$, and value 0 to all singleton coalitions. According to (2), this scenario can be represented as a coalitional ranking $\succeq \in \mathcal{R}(\mathcal{F}(N))$ such that$^2$

$$123 \sim 13 \succ 12 \sim 23 \succ 1 \sim 2 \sim 3.$$

### 3 Solutions for the social ranking problem

Given a coalitional ranking over the subsets of $N$, there is a compelling interest in attempting to compare the relative importance of the single elements within $N$ taking into account the position of coalitions they may form. For instance, comparing the “relevance” of political parties in a bicameral legislature, as outlined in Example 1, can be done by examining their potential to form coalitions with high v values or,

<footnote>$^2$For notational convenience, we sometimes omit braces or commas to write a subset of $N$. For instance, instead of $\{1, 2\}$ we write 12.</footnote>
equivalently, high positions in $\tilde{\sim}$. A solution<fnref n="3" /> seeks to address this problem by linking to every coalitional ranking a total binary relation on the set $N$ aimed at comparing the ordinal relevance of each pair of elements in $N$.

**Definition 1.** A solution is a function<fnref n="4" /> $R: \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$.

The image of a coalitional ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ under a solution $R$ is a total binary relation on $N$, notated as $R^{\tilde{\sim}}$. The semantics of a relation between two elements $i$ and $j$ expressed as $iR^{\tilde{\sim}}j$ is described as follows: “$i$ is at least as relevant as $j$, when the solution $R$ is applied to the coalitional ranking $\tilde{\sim}$”. We also denote by $I^{\tilde{\sim}}$ its symmetric part ($iI^{\tilde{\sim}}j$ if $(i,j) \in R^{\tilde{\sim}}$ and $(j,i) \in R^{\tilde{\sim}}$) and, conversely, by $P^{\tilde{\sim}}$ its asymmetric part ($iP^{\tilde{\sim}}j$ if $(i,j) \in R^{\tilde{\sim}}$ but $(j,i) \notin R^{\tilde{\sim}}$).

As discussed in the introduction, several solutions have been introduced in the literature. In this paper, we will focus on three particular ones: the CP-majority [5], the lex-cel [4], and the $L^{(1)}$ solution [15]. In the remainder of this section, we recall the formal definition of each of those solutions, and we illustrate their computation on short numerical examples. The dual versions of the lex-cel and the $L^{(1)}$ solution will also be introduced and studied in Sections 5.2 and 5.3, respectively.

CP-majority compares two elements $i$ and $j$ in $N$ by uniquely considering the ranking of pairs of subsets $S \cup \{i\}$ and $S \cup \{j\}$, where $S$ is a coalition excluding both $i$ and $j$. This kind of comparisons, also named *CP-comparisons* [5], involve coalitions that only differ in the exclusion of either $i$ or $j$, while everything else remains the same. Before recalling the formal definition of the *Ceteris Paribus* relation (*CP-majority*) [5], we introduce some further notations. Given a coalitional ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ and two elements $i, j \in N$, we define two sets: the set $D_{ij}(\tilde{\sim}) = \{S \in 2^{N \setminus \{i,j\}} : S \cup \{i\} \succ S \cup \{j\}\}$ of coalitions $S$ (containing neither $i$ nor $j$) such that $S \cup \{i\}$ is strictly stronger than $S \cup \{j\}$, and the set $E_{ij}(\tilde{\sim}) = \{S \in 2^{N \setminus \{i,j\}} : S \cup \{i\} \sim S \cup \{j\}\}$ of coalitions $S$ (containing neither $i$ nor $j$) such that $S \cup \{i\}$ and $S \cup \{j\}$ are equally strong. So, the cardinality of set $D_{ij}(\tilde{\sim})$ represents the number of times $i$ defeats $j$, and the definition of the CP-majority relation between $i$ and $j$ in $\tilde{\sim}$ follows according to the comparison between $|D_{ij}(\tilde{\sim})|$ and $|D_{ji}(\tilde{\sim})|$.

**Definition 2.** (*CP-majority* [5].) The CP-majority is the solution $R_{CP}: \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ such that for all $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ and $i, j \in N$:

$$iR_{CP}^{\tilde{\sim}}j \quad \text{if} \quad |D_{ij}(\tilde{\sim})| \geq |D_{ji}(\tilde{\sim})|.$$

(Following the same convention as before, $I_{CP}^{\tilde{\sim}}$ and $P_{CP}^{\tilde{\sim}}$ stand for the symmetric part and the asymmetric part of $R_{CP}^{\tilde{\sim}}$, respectively.)

<footnote n="3">³Notice that in the literature, the co-domain of a solution has been often defined as the set of total preorders on $N$ (see, for instance, the seminal papers [4, 15]). In this paper, we consider a larger co-domain in order to make a consistent analysis of the lex-cel and the $L^{(1)}$ solution (and their dual versions) with the CP-majority, that in general does not yield a transitive relation for $|N| > 2$.</footnote>

<footnote n="4">⁴Here we use a slight abuse of notation $R$ to recall an image under a solution $R$ is a total binary relation.</footnote>
**Example 3.** Consider the coalitional ranking ≽ of Example 2. For instance, we have that $D_{12}(？」) = \{3\}$ (for $13 \succ 23$), whereas $D_{21}(？」) = \emptyset$ (there are no coalitions $S \in \{\emptyset, \{3\}\}$ such that $S \cup \{2\} \succ S \cup \{1\}$). Since $|D_{12}(？」)| > |D_{21}(？」)|$, it follows that the CP-majority ranks party 1 strictly more relevant than 2, which is notated as $1P_{CP}？」^2$. We have the following matrix

$$ (|D_{ij}(？」)|)_{i,j \in N} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} $$

which yields the ranking $1I_{CP}？」^33P_{CP}？」^2$, i.e., parties 1 and 3 are equally relevant and each of them is strictly more relevant than party 2 according to the CP-majority on the coalitional ranking？」.

The lex-cel solution [4] is based on the idea that individuals who consistently appear at the top of a coalitional ranking should be ranked as the most relevant. It compares any pair of elements by examining their occurrences in equivalence classes of a coalitional ranking, starting with the lowest indexed equivalence class (as in, the class of top coalitions). If there is a tie, it proceeds to compare occurrences in subsequent classes until a difference is found or all classes show ties, in which case the elements are declared indifferent in terms of their relevance.

We first need some more notations. Given a coalitional ranking ≽ ∈ $\mathcal{R}(\mathcal{F}(N))$ with quotient order $\Sigma_1 \succ \Sigma_2 \succ \cdots \succ \Sigma_l$, denote by $i_k$ the number of sets in $\Sigma_k$ containing $i$:

$$ i_k = |\{S \in \Sigma_k : i \in S\}|, $$

for $k = 1, \dots, l$. Now, let $\theta？」^k(i)$ be the $l$-dimensional vector $\theta？」^k(i) = (i_1, \dots, i_l)$ associated to？」. Consider the lexicographic order among vectors:

$$ \mathbf{i} \geq_{L} \mathbf{j} \quad \text{if either } \mathbf{i}=\mathbf{j} \quad \text{or} \quad \exists s: i_k = j_k, k = 1, \dots, s-1 \text{ and } i_s > j_s. $$

The lex-cel is defined as follows.

**Definition 3 (lex-cel [4]).** The lexicographic excellence (lex-cel) solution is the function $R_{le} : \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ defined for any coalitional ranking ≽ ∈ $\mathcal{R}(\mathcal{F}(N))$ as

$$ iR_{le}？」^j \quad \text{if} \quad \theta？」^k(i) \geq_L \theta？」^k(j). $$

(Following the same convention as before, $I_{le}$ and $P_{le}$ stand for the symmetric part and the asymmetric part of $R_{le}$, respectively.)

We illustrate its computation in the following example.

**Example 4.** Consider again the coalitional ranking ≽ of Example 2. Its quotient order is

$$ \Sigma_1 \succ \Sigma_2 \succ \Sigma_3, $$
with $\Sigma_1 = \{123, 13\}$, $\Sigma_2 = \{12, 23\}$ and $\Sigma_3 = \{1, 2, 3\}$. Then we have that

$$ \theta^{\tilde{\sim}}(1) = (2, 1, 1), $$

$$ \theta^{\tilde{\sim}}(2) = (1, 2, 1), $$

$$ \theta^{\tilde{\sim}}(3) = (2, 1, 1). $$

It follows that the lex-cel yields the ranking $1I_{\tilde{le}}^33P_{\tilde{le}}^2$, i.e., element 1 and 3 are equally relevant, each of whom is strictly more relevant than element 2 according to the lex-cel on the coalitional ranking $\tilde{\sim}$.

The third main solution considered in this article is the $L^{(1)}$ solution introduced in [15]. Similar to lex-cel, the $L^{(1)}$ solution also seeks to recognize the contributions of elements to top coalitions within a coalitional ranking. However, in the lexicographic comparisons of their occurrences in the equivalence classes of a coalitional ranking, from the top one to the worst one, it accounts for the size of coalitions, thus emphasizing the importance of smaller ones.

Given a coalitional ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with quotient order $\Sigma_1 \succ \Sigma_2 \succ \cdots \succ \Sigma_l$, and an agent $i \in N$, define the matrix $M^{\tilde{\sim},i}$ of size $(n, l)$ where each entry

$$ M_{sk}^{\tilde{\sim},i} = |\{S \in \Sigma_k : i \in S \text{ and } |S| = s\}| $$

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\}$. Consider the column-wise lexicographic order among matrices such that $M^{\tilde{\sim},i} \ge_{L^c} M^{\tilde{\sim},j}$ if

* either $M^{\tilde{\sim},i} = M^{\tilde{\sim},j}$

* or $\exists \hat{s} \in \{1, \dots, n\}$ and $\hat{k} \in \{1, \dots, l-1\}$ such that<fnref n="5" />

$$ \left\{ \begin{array}{l} M_{sk}^{\tilde{\sim},i} = M_{sk}^{\tilde{\sim},j}, \forall s \in \{1, \dots, n\}, \forall k \in \{1, \dots, \hat{k}-1\}; \\ M_{\hat{k}}^{\tilde{\sim},i} = M_{\hat{k}}^{\tilde{\sim},j}, \forall s \in \{1, \dots, \hat{s}-1\}; \\ M_{\hat{s}\hat{k}}^{\tilde{\sim},i} > M_{\hat{s}\hat{k}}^{\tilde{\sim},j}. \end{array} \right. $$

The $L^{(1)}$ solution is defined as follows.

**Definition 4** ($L^{(1)}$ [15]). The $L^{(1)}$ solution is the map $R_{L^{(1)}}: \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ such that for any coalitional ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ and $i, j \in N$:

$$ i R_{L^{(1)}}^{\tilde{\sim}} j \quad \text{if} \quad M^{\tilde{\sim},i} \ge_{L^c} M^{\tilde{\sim},j}. $$

(Following the same convention as before, $I_{L^{(1)}}^{\tilde{\sim}}$ and $P_{L^{(1)}}^{\tilde{\sim}}$ stand for the symmetric part and the asymmetric part of $R_{L^{(1)}}^{\tilde{\sim}}$, respectively.)

<footnote n="5">⁵If either $\hat{k} = 1$ or $\hat{s} = 1$, the set $\{1, \dots, -1\} = \emptyset$.</footnote>
**Example 5.** Consider again the coalitional ranking ≽ of Example 2. We have that

$$M^{\tilde{\sim},1} = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}, \quad M^{\tilde{\sim},2} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 0 \end{pmatrix}, \quad M^{\tilde{\sim},3} = \begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}.$$

It follows that the $L^{(1)}$ solution yields the ranking $1I_{L^{(1)}}3P_{L^{(1)}}2$, i.e., parties 1 and 3 are ranked with equal relevance (for $M^{\tilde{\sim},1}$ and $M^{\tilde{\sim},3}$ are identical), and each of them is strictly more relevant than party 2, according to Definition 4 with $\hat{s} = 2$ and $\hat{k} = 1$.

In section 5 we provide a concise analysis of dual versions of both lex-cel and $L^{(1)}$.

# 4 Properties for solutions

In this section, we introduce and discuss various properties for solutions, and we explore their implications within specific contexts. We start with the central property studied in this work, which is based on the notion of desirability relation [6–9]. For any coalitional ranking ≽ ∈ $R(F(N))$ and players $i, j \in N$, we say that $i$ is more desirable than $j$ in ≽ if $S \cup \{i\} \preceq S \cup \{j\}$ for all $S \in 2^{N\setminus\{i,j\}}$.

**Axiom 1 (Desirability (Des)).** A solution $R : R(F(N)) \to B(N)$ satisfies the Desirability property if

$$i \text{ is more desirable than } j \text{ in } \preceq \implies i R^{\tilde{\sim}} j$$

for any $\tilde{\sim} \in R(F(N))$ and $i, j \in N$.

The concept of desirability plays an important role for various solution concepts in cooperative game theory [13, 19]. In our framework, the Desirability axiom mirrors the responsiveness of a solution in assessing the relative contributions of players across the entire spectrum of coalitions: a player $i$ that consistently beats $j$ in contributing to any coalition $S$ containing neither $i$ nor $j$ cannot be declared strictly less relevant than $j$. Clearly, Axiom 1 also states that if $i$ is more desirable than $j$ in a coalitional ranking ≽ and there exists some coalition $T$ such that $T \cup \{i\}$ is strictly stronger than $T \cup \{j\}$ (i.e., $T \cup \{i\} \succ T \cup \{j\}$), then $i$ should be declared strictly more relevant than $j$ according to $R^{\tilde{\sim}}$ (i.e., $iP^{\tilde{\sim}}j$). Moreover, if $i$ and $j$ are equally desirable in a coalitional ranking ≽, namely $S \cup \{i\} \sim S \cup \{j\}$ for every $S \in 2^{N\setminus\{i,j\}}$, then $i$ and $j$ are equally relevant according to $R^{\tilde{\sim}}$ (i.e., $iI^{\tilde{\sim}}j$).

**Example 6.** Consider the coalitional ranking ≽ of Example 2. A solution $R$ satisfying Desirability states that party 1 and 3 are in strict relation with 2, $1P^{\tilde{\sim}}2$ and $3P^{\tilde{\sim}}2$, thanks to the fact that parties 1 and 3 together form the only coalition having a majority in both houses (so, $13 \succ 12$ and $13 \succ 23$), while singleton coalitions are all indifferent, making both 1 and 3 strictly more relevant than 2. Instead, due to the fact that $1 \sim 3$ and $12 \sim 23$, the property of Desirability states that parties 1 and 3 must be equally relevant.
As already observed, according to the Desirability axiom, a strict relation between an individual i over another individual j can be dictated by even a single coalition $S \cup \{i\}$ that is strictly stronger than $S \cup \{j\}$ if all the other CP-comparisons $S \cup \{i\}$ versus $S \cup \{j\}$ state indifference. One could argue that the reliability of some CP-comparisons may be questioned under certain circumstances; for instance, the involved coalitions may be deemed implausible or their probability to form might be considered not sufficiently high, due to a political contrast between some of their members. Nevertheless, throughout this article, we shall operate under the assumption that all coalitions are feasible, thereby adopting the Desirability property as a pivotal axiom for all solutions aiming to capture any evidence of coalitional dominance.

The next property of Neutrality for solutions has been introduced in [5] to ensure that a solution treats two elements identically, independent of their individual identities.

**Axiom 2 (Neutrality (Neu)).** A solution $R: \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ satisfies the property of Neutrality if, for all coalitional rankings $\succcurlyeq, \succcurlyeq' \in \mathcal{R}(\mathcal{F}(N))$ and $i, j \in N$ such that

$$S \cup \{i\} \succcurlyeq S \cup \{j\} \Leftrightarrow S \cup \{j\} \succcurlyeq' S \cup \{i\} \\ \text{for all } S \in 2^{N\{i,j\}}, \text{ it holds that}$$

$$iR\succcurlyeq j \Leftrightarrow jR\succcurlyeq' i.$$

In an adjusted scenario from Example 2, imagine transferring one unit of weight from party 3 to party 2 in the Upper House, altering the weights to (2, 2, 1). This shift grants the coalition 12 a majority in both Houses, unlike the coalition 13, which can only secure a majority in the Lower House. Consequently, party 2 essentially swaps its position with party 3 in the coalitional ranking. Given that only the legislative weight of parties should influence their relevance, but not, i.e., their names or other irrelevant attributes, a solution satisfying neutrality ensures that party 3 is at least as relevant as party 2 before the transfer if and only if party 2 is at least as relevant as party 3 after the transfer. Notice that a solution satisfying neutrality also states that parties 1 and 3 are equally relevant in Example 2.

A further property introduced in [5] with the name of Equality of Coalitions requires that for any pair of individuals $i$ and $j$, all CP-comparisons $S \cup \{i\}$ vs. $S \cup \{j\}$ have an equal impact in establishing the relevance relation between individuals $i$ and $j$, regardless of the size or structure of each coalition $S$ involved in the CP-comparison.

**Axiom 3 (Equality of Coalitions (EC)).** A solution $R: \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ satisfies the property of Equality of Coalitions if, for all coalitional rankings $\succcurlyeq, \succcurlyeq' \in \mathcal{R}(\mathcal{F}(N))$, $i, j \in N$, and a bijection $\pi$ on $2^{N\{i,j\}}$ such that

$$S \cup \{i\} \succcurlyeq S \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \succcurlyeq' \pi(S) \cup \{j\} \\ \text{for all } S \in 2^{N\{i,j\}}, \text{ it holds that}$$

$$iR\succcurlyeq j \Leftrightarrow iR\succcurlyeq' j.$$

Notice that taking a bijection $\pi$ such that $\pi(S) = S$ for all $S \in 2^{N\{i,j\}}$, Axiom 3 states that a solution should remain unaffected by coalitional comparisons other
than the CP-comparisons, i.e., those involving sets of the form $S \cup \{i\}$ and $S \cup \{j\}$. Differently stated, Equality of Coalitions requires that the relation specified by a solution between elements $i$ and $j$ should be independent of all comparisons that are not CP for $i$ and $j$, as will be illustrated in the following example.

**Example 7.** Consider the coalitional ranking $\gtrsim$ from Example 2 and a new coalitional ranking $\gtrsim'$ that may emerge as a result of alterations in the weights of the parties in the two houses (the specific weight details are omitted for brevity) such that

$$123 \sim' 12 \succ' 13 \sim' 23 \sim' 1 \succ' 2 \sim' 3.$$

Notice that in $\gtrsim$ we have $13 \succ 23$ and $1 \sim 2$, while in $\gtrsim'$ we have that $13 \sim' 23$ and $1 \succ' 2$. So, defining a bijection $\pi$ on $\{\emptyset, 3\}$ such that $\pi(\emptyset) = 3$, we obtain $S \cup \{1\} \gtrsim S \cup \{2\} \Leftrightarrow \pi(S) \cup \{1\} \gtrsim' \pi(S) \cup \{2\}$ for all $S \in \{\emptyset, 3\}$. Then, a solution satisfying EC should rank parties 1 and 2 in $\gtrsim$ precisely as in $\gtrsim'$.

Moreover, the fact that coalition 1 is in the intermediate equivalence class in the quotient order of $\gtrsim'$ together with some coalitions of size two, or that 12 is in the first equivalence, has no effect on the final relation between 1 and 2. A solution satisfying EC must rank 1 and 2 independently of the relative position of coalitions that are not involved in CP-comparisons for 1 and 2.

In a political context, the EC property can be useful to compare the relevance of political parties with respect to their ability to withstand potential shifts in alliances of the other parties in a coalition, irrespective of their size or their political identities. However, one could argue that forging alliances in smaller coalitions is more likely in a practical political landscape, or that other types of comparisons other than the CP-ones play a role. In this scenario, using EC might not be suitable, and employing alternative versions that rely on other kinds of comparisons could prove more effective.

Another property that is based on the use of a bijection that transforms each coalition (not containing the two individuals $i$ and $j$) into another is the coalitional anonymity property introduced in [4].

**Axiom 4 (Coalitional Anonymity (CA))**. A solution $R$ satisfies Coalitional Anonymity if it holds that

$$iR\gtrsim j \Leftrightarrow iR\gtrsim' j$$

for all coalitional rankings $\gtrsim, \gtrsim' \in \mathcal{R}(\mathcal{F}(N))$, $i, j \in N$ and a bijection $\pi$ on $2^{N\{i,j\}}$ such that:

$$S \cup \{i\} \gtrsim T \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \gtrsim' T \cup \{j\}. \qquad (3)$$

for all $S, T \in 2^{N\{i,j\}}$.

Unlike the EC property, the CA property does not require that the ranking between $i$ and $j$ is based exclusively on CP-comparisons $S \cup \{i\}$ vs. $S \cup \{j\}$. The notion of relevance considered by a solution satisfying the CA axiom refers to the position of coalitions containing either $i$ or $j$ in the coalitional ranking, regardless of the size and structure of the coalition to which they belong. Consequently, the impact of a relation $S \cup \{i\} \succ S \cup \{j\}$ to a solution may also differ according to the position of $S \cup \{i\}$ and
$S \cup \{j\}$ in the coalitional ranking. Furthermore, CA embodies a principle of positional independence of coalitions containing either both $i$ and $j$ or neither.

**Example 8.** Consider the coalitional ranking $\succeq$ from Example 2 and a new coalitional ranking $\succeq'$ reflecting a shift in power balance from 3 to 1 that, for some political reason or consensus drift, has reversed the relative position of coalitions 1 with coalition 13 as follows

$$123 \sim' 1 \sim' 12 \succ' 23 \succ' 13 \sim' 2 \sim' 3.$$

If we define a bijection $\pi$ on $\{\emptyset, 3\}$ with $\pi(\emptyset) = 3$, then $S \cup \{1\} \succeq T \cup \{2\} \Leftrightarrow \pi(S) \cup \{1\} \succeq' T \cup \{2\}$ holds for all $S \in \{\emptyset, 3\}$. Therefore, a solution satisfying CA ranks parties 1 and 2 identically in $\succeq$ and $\succeq'$. Moreover, repositioning coalition 12 in $\succeq'$ (placing it in the first equivalence class) does not affect the ranking of 1 and 2, just as repositioning coalition 3 or 123 would not.

In $\succeq'$, we have $1 \succ' 2$ and $23 \succ' 13$, whereas in $\succeq$ (as noted in Example 7), $13 \sim' 23$ and $1 \succ' 2$. Consequently, no bijection can establish a one-to-one correspondence between the CP-comparisons $S \cup \{1\}$ vs. $S \cup \{2\}$ while preserving coalitional rankings, as required by Axiom 3 (EC). Thus, Axiom 3 does not constrain the relationship between the solutions for 1 and 2 in $\succeq$ and $\succeq'$.

Similarly, condition (3), imposed by the CA property, does not hold when comparing $\succeq$ and $\succeq'$ from Example 7. In other words, EC and CA may apply to distinct pairs of coalitional rankings. As a result, solutions can satisfy Axiom 3 without satisfying Axiom 4, and vice versa. A formal proof of the logical independence of Axioms 3 and 4 is provided in Proposition 6.

In a political framework, Axiom 4 suggests ranking parties based solely on the position of the coalitions they join, independently of the coalitions' identities or their number of members. Alternatively, one could argue that coalition size should play a role. This perspective leads to a slightly modified definition: per-size coalitional anonymity, where each coalition is mapped to another of the same cardinality, as recalled from [15].

**Axiom 5 (Per-size Coalitional Anonymity (PCA))**. A solution $R$ satisfies Per-size Coalitional Anonymity if it holds that

$$iR\succeq j \Leftrightarrow iR\succeq' j$$

for all coalitional rankings $\succeq, \succeq' \in \mathcal{R}(\mathcal{F}(N))$, $i, j \in N$, and a bijection $\pi$ on $2^{N\{i,j\}}$ such that $|\pi(S)| = |S|$

$$S \cup \{i\} \succeq T \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \succeq' T \cup \{j\} \quad (4)$$

for all $S, T \in 2^{N\{i,j\}}$ with $|S| = |T|$.

The interpretation of the PCA property is obvious and follows the same lines of CA, except that it applies to a restricted set of pairs of coalitional rankings. For instance, the PCA property does not say anything about the relation between the coalitional ranking $\succeq$ of Example 2 and $\succeq'$ of Example 8, as the unique bijection $\pi$
on $2^N \setminus \{1,2\} = \{\emptyset, \{3\}\}$ satisfying the condition $|\pi(S)| = |S|$ is the identity $\pi(S) = S$. It is also clear that a solution satisfying Axiom 4 (CA) also satisfies Axiom 5 (PCA) (see Proposition 6 and [15] for more details).

The following property addresses scenarios in which two individuals $i$ and $j$ initially hold equal relevance in two distinct coalitional rankings according to a certain solution. Subsequently, ties among coalitions are broken, resulting in new coalitional rankings. The Consistency After Tiebreaks property states that the relevance relation between $i$ and $j$ should remain unchanged according to the same solution applied on the revised coalitional ranking.

In the following, the notation $\gtrsim \setminus B$ stands for the classical set difference between $\gtrsim$ and $B$ (two sets of coalitions pairs).

**Axiom 6 (Consistency After Tiebreaks (CAT)).** A solution $R : \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ satisfies the property of Consistency After Tiebreaks if, for all coalitional rankings $\gtrsim, \gtrsim' \in \mathcal{R}(\mathcal{F}(N))$ such that $iI\gtrsim\gtrsim'j$ and $iI\gtrsim'\gtrsim'j$, we have that

$$iR\gtrsim\setminus B j \Leftrightarrow iR\gtrsim'\setminus B j$$

for any set of equally strong pairs of coalitions $B \subset \{(S,T) : S \sim T \text{ and } S \sim' T\}$ such that $\gtrsim \setminus B$ and $\gtrsim' \setminus B$ are still coalitional rankings in $\mathcal{R}(\mathcal{F}(N))$.

**Remark 1.** Notice that removing the same set $B$ of equally strong coalition pairs in $B$ from coalitional rankings $\gtrsim$ and $\gtrsim'$ in such a way that the new relations obtained as set difference $\gtrsim \setminus B$ and $\gtrsim' \setminus B$ are still (transitive and complete) coalitional rankings in $\mathcal{R}(\mathcal{F}(N))$, corresponds to breaking exactly the same set of ties in $\gtrsim$ and $\gtrsim'$ between coalition pairs in $B$ for equal equivalence classes.

The CAT property can be interpreted as a measure of fairness aimed to treat individuals equally in response to identical changes in the position of coalitions in two distinct coalitional rankings: the solution between two individuals should not depend on the initial coalitional ranking if they start from a social position of indifference and precisely the same tie-breaks are operated between certain coalitions.

**Example 9.** Consider the coalitional ranking $\gtrsim$ from Example 2 and a new coalitional ranking $\gtrsim' \in \mathcal{R}(\mathcal{F}(N))$ such that

$$123 \sim' 13 \sim' 12 \sim' 23 \sim' 1 \sim' 2 \sim' 3.$$

Suppose that a solution $R$ determines 1 and 3 to be equally relevant in both coalitional rankings, $1I\gtrsim 3$ and $1I\gtrsim' 3$ (for instance, because 1 and 3 are symmetric).

Now, let $B = \{(3,1), (2,1), (3,2)\}$ and suppose that in both rankings $\gtrsim$ and $\gtrsim'$ the elements of $B$ are removed, resulting in two new coalitional rankings $\gtrsim = (\gtrsim \setminus B)$ and $\gtrsim' = (\gtrsim' \setminus B)$, both in $\mathcal{R}(\mathcal{F}(N))$, such that

$$123 \sim 13 \sim 12 \sim 23 \sim 1 \sim 2 \sim 3,$$

and

$$123 \sim' 13 \sim' 12 \sim' 23 \sim' 1 \sim' 2 \sim' 3.$$
Here, all ties among singleton coalitions from $\tilde{\sim}$ and $\tilde{\sim}'$ are broken. The CAT property does not dictate how the solution should adjust the ranking of 1 and 3 (i.e., favoring 1, favoring 3, or keeping them equally ranked). It only ensures that their relative ranking stays the same in both $\tilde{\sim}$ and $\tilde{\sim}'$.

The next property, introduced in [4], requires giving greater relevance to players within excellent coalitions compared to positions in less favorable coalitions when determining a solution. In this direction, if a decision was made that an element must be considered socially strictly more relevant than another, the property of independence from the worst set states that breaking ties between coalitions in the last equivalence class should not affect such a decision.

**Axiom 7 (Independence from the Worst Set (IWS)).** A solution R satisfies Independence from the Worst Set if, for any ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $\succ$ such that

$$ \Sigma_1 \succ \Sigma_2 \succ \Sigma_3 \succ \dots \succ \Sigma_l $$

with $l \ge 2$, and $i, j \in N$ such that

$$ iP^{\tilde{\sim}j}, $$

then it holds:

$$ iP^{\tilde{\sim}'j} $$

for any partition $T_1, \dots, T_m$ of $\Sigma_l$ and for any ranking $\tilde{\sim}' \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $\succ'$ such that

$$ \Sigma_1 \succ' \Sigma_2 \succ' \dots \succ' \Sigma_{l-1} \succ' T_1 \succ' \dots \succ' T_m. $$

**Example 10.** Consider again the coalitional ranking $\tilde{\sim}$ from Example 2 and the coalitional ranking $\hat{\sim}$ from Example 9. Notice that $\tilde{\sim}$ is obtained from $\tilde{\sim}$ by breaking ties in the worst equivalence class of $\tilde{\sim}$, while the relations involving coalitions not in the worst position in $\tilde{\sim}$ remain unchanged. So, if for some reason a solution satisfying the IWS property states that in the coalitional ranking $\tilde{\sim}$ a party $i \in \{1, 2, 3\}$ is strictly more relevant than $j \in \{1, 2, 3\} \setminus \{i\}$, then it must continue to declare $i$ strictly more relevant than $j$ also in the coalitional ranking $\hat{\sim}$.

**Axiom 7 (IWS)** can be interpreted as a principle aimed at rewarding the excellence of coalitions. It posits that if one believes that alterations in the positions of coalitions within the worst equivalence class of a coalitional ranking play a secondary role (provided that the worst coalitions continue to be dominated), then the decision about a strict ranking between elements should remain unaltered.

By contrast, if, instead of rewarding a coalition's excellence, a decision is guided by the punishment of mediocrity, a dual principle introduced in [4] can be utilized: once a strict relation is established for a pair of players, it remains unchanged even if we refine the best-preferred equivalence class.

**Axiom 8 (Independence from the Best Set (IBS)).** A solution R satisfies Independence from the Best Set if, for any ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient
order ⋇ such that

$$ \Sigma_1 \succ \Sigma_2 \succ \Sigma_3 \succ \dots \succ \Sigma_l $$

with $l \ge 2$, and $i, j \in N$ such that

$$ iP\tilde{j}, $$

then it holds:

$$ iP\tilde{j}' $$

for any partition $T_1, \dots, T_m$ of $\Sigma_1$ and for any ranking $\succ' \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order ⋇' such that

$$ T_1 \succ' \dots \succ' T_m \succ' \Sigma_2 \succ' \dots \succ' \Sigma_l. $$

**Example 11.** Consider the coalitional ranking $\succ' \in \mathcal{R}(\mathcal{F}(N))$ that emerges as a result of a slight alteration in the weights of parties only affecting coalitions in the first equivalence class such that

$$ 123 \succ'' 13 \succ'' 12 \sim'' 23 \succ'' 1 \sim'' 2 \sim'' 3. $$

Notice that $\succ''$ is obtained by breaking ties in the first equivalence class of $\succ'$, while the relations involving coalitions not in the first position in $\succ'$ remain unchanged. So, if for some reason a solution satisfying the IBS property declares a party $i \in \{1, 2, 3\}$ strictly more relevant than $j \in \{1, 2, 3\} \setminus \{i\}$ in the coalitional ranking $\succ'$, then it must assert that $i$ is strictly more relevant than $j$ also in the coalitional ranking $\succ''$.

To introduce the next axiom, we first need to define the notion of $k$-dominance relation aimed at describing those coalitional rankings where, for any coalition $S$ of a fixed cardinality $k \in \{0, \dots, n-2\}$ containing neither $i$ nor $j$, we have that $S \cup \{i\}$ is at least as strong as $S \cup \{j\}$.

**Definition 5 (k-dominance relation).** Consider a coalitional ranking $\succ' \in \mathcal{R}(\mathcal{F}(N))$. For any pair of players $i, j \in N$ and any $k \in \{0, \dots, n-2\}$, the $k$-dominance relation $R_k^{\succ'} \subseteq N \times N$ is defined as follows:

$$ iR_k^{\succ'}j \Leftrightarrow S \cup \{i\} \succ R_k^{\succ'}j \text{ for all } S \in 2^{N\setminus\{i,j\}} \text{ with } |S| = k. $$

Moreover, we say that $i$ $k$-dominates $j$ strictly (denoted as $iP_k^{\succ'}j$) if $iR_k^{\succ'}j$ and there exists $S \in 2^{N\setminus\{i,j\}}$ with $|S| = k$ such that $S \cup \{i\} \succ S \cup \{j\}$, while $i$ and $j$ are said to be indifferent in a $k$-dominance relation (denoted as $iI_k^{\succ'}j$) if $S \cup \{i\} \sim S \cup \{j\}$ for all $S \in 2^{N\setminus\{i,j\}}$ with $|S| = k$.

Notice that if a coalitional ranking is such that an element $i$ $k$-dominates an element $j$ for any $k \in \{0, \dots, n-2\}$, then it holds that $i$ is more desirable than $j$, and a solution satisfying Axiom 1 (Des) must declare $i$ more relevant than $j$.

Denote by $KP_{ij}^{\succ'} = \{k \in \{0, \dots, n-2\} : iP_k^{\succ'}j\}$ the set of indices $k$ such that $i$ $k$-dominates $j$ strictly, and by $KI_{ij}^{\succ'} = \{k \in \{0, \dots, n-2\} : iI_k^{\succ'}j\}$ the set of indices $k$ such that $i$ and $j$ are indifferent in an $k$-dominance relation. The following axiom addresses dichotomous coalitional rankings where $KP_{ij}^{\succ'} \neq \emptyset$ and $KP_{ji}^{\succ'} \neq \emptyset$ and therefore Axiom 1 (Des) does not apply.
**Axiom 9** (k-Desirability on a Dichotomous ranking (k-DD)). A solution R satisfies the property of k-Desirability on a Dichotomous ranking if, for any dichotomous coalitional ranking $\succcurlyeq \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $\Sigma_1 \succ \Sigma_2$, and for any $i, j \in N$ such that

$$KP_{ij}^{\succcurlyeq} \cup KP_{ji}^{\succcurlyeq} \cup KI_{ij}^{\succcurlyeq} = \{0, \dots, n-2\}, \quad KP_{ij}^{\succcurlyeq} \neq \emptyset \text{ and } KP_{ji}^{\succcurlyeq} \neq \emptyset,$$

it holds that

$$\min\{k \in KP_{ij}^{\succcurlyeq}\} < \min\{k \in KP_{ji}^{\succcurlyeq}\} \implies iP^{\succcurlyeq}j.$$

In dichotomous coalitional rankings where the information conveyed by the k-dominance relation between two elements i and j is conflicting (i.e., $KP_{ij}^{\succcurlyeq} \neq \emptyset$ and $KP_{ji}^{\succcurlyeq} \neq \emptyset$), the k-DD property advocates in favor of the strict k-dominance relation with the smallest value of k. Axiom 9 is applied exclusively to dichotomous coalitional rankings (commonly also known as simple games), where only two equivalence classes $\Sigma_1 \succ \Sigma_2$ exist (in the framework of simple games, elements of $\Sigma_1$ are also called winning coalitions and those in $\Sigma_2$, losing coalitions). In these situations, the k-DD property, akin to other power indices for simple games [19–22], demands that the comparison between two elements i and j focuses on the analysis of coalitions within the class of winning coalitions. Moreover, an element showing a relation of k-dominance over winning coalitions with small cardinality should be declared more relevant than another showing k-dominance on larger coalitions.

**Example 12.** Consider the dichotomous coalitional ranking $\succcurlyeq \mathcal{R}(\mathcal{F}(N))$ with $N = \{1, 2, 3\}$ such that

$$123 \sim 12 \sim 23 \sim 1 \succ 13 \sim 2 \sim 3.$$

Notice that element 1 (strictly) 0-dominates element 2, while 2 (strictly) 1-dominates element 1. So, $KP_{12} = \{0\}$, $KP_{21} = \{1\}$ and $KI_{12} = \emptyset$. For $0 = \min\{k \in KP_{12}^{\succcurlyeq}\} < \min\{k \in KP_{21}^{\succcurlyeq}\} = 1$, a solution satisfying the Axiom 9 (k-DD) must rank party 1 strictly better than party 2. Differently stated, in this example the k-DD property states that singleton coalitions count more than coalitions of two elements.

Axiom 9 (k-DD) is well adapted to compare the relevance in a political framework, where the formation of large coalitions may prove more challenging than creating smaller ones due to many factors, including the existence of intricate institutional rules, the necessity for mediators in decision-making processes, increased negotiation costs, and various “psychological” aspects related to divergent political positions among coalition members.

The next axiom focuses on the comparison of two coalitional rankings obtained from one where two elements i and j initially share the same social position. The first coalitional ranking is obtained by improving some coalitions from the last equivalence class to the penultimate one. The second coalitional ranking undergoes the same kind of improvements of coalitions but also merges all coalitions from the first to the penultimate equivalence class into a single equivalence class, resulting in a dichotomous coalitional ranking. The property of consistency after indifference then specifies
that the ranking between i and j should be coherently maintained across the two new coalitional rankings.

**Axiom 10** (Consistency after Indifference (CI)). A solution R satisfies Consistency after Indifference if, for any coalitional ranking $\succeq \in \mathbf{R}(\mathcal{F}(N))$ with the associated quotient order $\succ$ such that

$$ \Sigma_1 \succ \Sigma_2 \succ \Sigma_3 \succ \cdots \succ \Sigma_l $$

with $l \ge 2$, and with $iI\tilde{j}, i, j \in N$, it holds that:

$$ iR\tilde{j}' \Leftrightarrow iR\tilde{j}'' $$

for any $\Sigma \subset \Sigma_l$ and for all coalitional rankings $\succeq', \succeq'' \in \mathbf{R}(\mathcal{F}(N))$ with the associated quotient order $\succ'$ and $\succ''$ such that

$$ \Sigma_1 \succ' \Sigma_2 \succ' \cdots \succ' \Sigma_{l-1} \cup \Sigma \succ' \Sigma_l \setminus \Sigma $$

and

$$ \Sigma_1 \cup \Sigma_2 \cup \cdots \cup \Sigma_{l-1} \cup \Sigma \succ'' \Sigma_l \setminus \Sigma. $$

Notice that as a particular case where $\succeq''$ in Axiom 10 is obtained with $\Sigma = \emptyset$ (and so, $\succeq' = \succeq$) the CI property asserts that a relation of equal relevance between i and j must persist on a dichotomous ranking $\succeq''$ derived by making the union of the first $l-1$ equivalence classes of a coalitional ranking $\succeq$ where elements i and j are equally relevant.

The CI axiom proves useful for guiding the behavior of a social ranking under moderate changes in coalition strength within the worst equivalence class, and where a dichotomous coalitional ranking serves as a reference point for a simplified analysis of such changes, as illustrated by the following example.

**Example 13.** Consider the coalitional ranking $\succeq'$ from Example 8, and suppose that a solution R ranks 1 and 2 socially indifferent in $\succeq'$, so $1I\tilde{\succeq}'2$. Consider the coalitional rankings $\succeq''$ and $\succeq'''$ such that

$$ 123 \sim'' 1 \sim'' 12 \succ'' 23 \sim'' 13 \succ'' 2 \sim'' 3, $$

and

$$ 123 \sim''' 12 \sim''' 23 \sim''' 1 \sim''' 13 \succ''' 2 \sim''' 3. $$

The ranking $\succeq''$ is obtained from $\succeq'$ improving the position of coalition 13 from the last equivalence class to the penultimate one, and $\succeq'''$ is a dichotomous coalitional ranking obtained from $\succeq''$ by taking the union of the first two equivalence classes. The CI property does not dictate the exact relation between 1 and 2 in $\succeq''$ and $\succeq'''$, but it requires a solution's relation between 1 and 2 to be consistent in both of these coalitional rankings, i.e., $1R\tilde{\succeq}''2 \Leftrightarrow 1R\tilde{\succeq}'''2$.
# 5 Main results

## 5.1 An axiomatic characterization of the CP-majority

In this section, we explore the implications of adopting a solution that satisfies Axioms 1 (Des), 2 (Neu), 3 (EC) and 6 (CAT).

We start our axiomatic analysis with the following lemma showing that solutions satisfying Axioms 2 (Neu) and 3 (EC) should declare equally relevant two players that show the same number of favorable CP-comparisons$^6$.

**Lemma 5.1.** Let $R$ be a solution satisfying Axioms 2 (Neu) and 3 (EC). Then for any $i, j \in N$ and $\succeq \in \mathcal{R}(\mathcal{F}(N))$ such that $|D_{ij}(\succeq)| = |D_{ji}(\succeq)|$ it holds that $iI\succeq j$.

*Proof* Let $i, j \in N$ and $\succeq \in \mathcal{R}(\mathcal{F}(N))$ be such that $|D_{ij}(\succeq)| = |D_{ji}(\succeq)|$.

Consider a bijection $\pi$ on $2^{N\{i,j\}}$ such that $\pi(S) \in D_{ji}(\succeq)$ for each $S \in D_{ij}(\succeq)$ and $\pi(S) = S$ for all the remaining coalitions $S \in 2^{N\{i,j\}} \setminus (D_{ij}(\succeq) \cup D_{ji}(\succeq))$.

Define another ranking $\succeq' \in \mathcal{R}(\mathcal{F}(N))$

$$S \cup \{i\} \succeq S \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \succeq' \pi(S) \cup \{j\},$$

for all $S \in 2^{N\{i,j\}}$. By Axiom 3 (EC)

$$iR\succeq j \Leftrightarrow iR\succeq' j. \qquad (5)$$

Notice that by construction of $\pi$, it holds that for all $S \in 2^{N\{i,j\}}$

$$S \cup \{i\} \succeq' S \cup \{j\} \Leftrightarrow S \cup \{j\} \succeq S \cup \{i\}.$$

Then, by Neu,

$$iR\succeq' j \Leftrightarrow jR\succeq i. \qquad (6)$$

By relations (5) and (6), it follows that

$$iR\succeq j \Leftrightarrow jR\succeq i,$$

and by the fact that $R\succeq$ is a total relation, it holds that $iI\succeq j$. $\square$

We now present an axiomatic characterization of CP-majority using the Desirability property.

**Theorem 1.** CP-majority is the only solution that satisfies Axioms 1 (Des), 2 (Neu), 3 (EC) and 6 (CAT).

*Proof* It is easy to check that $R_{CP}$ satisfies Axiom 1 (Des). It also satisfies Axioms 2 (Neu) and 3 (EC) as already shown in the literature [5].

To see that $R_{CP}$ satisfies also Axiom 6 (CAT), recall that $\succeq$ and $\succeq'$ are subsets of the cartesian product $\mathcal{F}(N) \times \mathcal{F}(N)$ from which $\succeq \setminus B$ is obtained by removing the elements of $B$ from $\succeq$. Notice that, given two rankings $\succeq, \succeq'$, removing a set $B \subset \{(S, T) : S \sim T \text{ and } S \sim' T\}$ (such that if $(S, T) \in B$ then $(T, S) \notin B$) impacts the cardinalities of $D_{ij}(\cdot)$ and $D_{ji}(\cdot)$ to the same extent. More precisely, let $W_{ij} = \{S \in 2^{N\{i,j\}} : (S \cup \{j\}, S \cup \{i\}) \in B\}$ be the set of

<footnote>$^6$A similar result is also used in the proof of Theorem 1 in the paper [5].</footnote>
coalitions such that the corresponding CP-comparisons in B are in favor of j. Removing pairs in $W_{ij}$ from a coalitional ranking $\tilde{\sim}$ or $\tilde{\sim}'$ plays in favor of i without affecting j. Analogously, removing pairs in $W_{ji}$ from a coalitional ranking $\tilde{\sim}$ or $\tilde{\sim}'$ plays in favor of j without affecting i (recall that $\tilde{\sim} \setminus B$ and $\tilde{\sim}' \setminus B$ are total preorders). Therefore, we have that $|D_{ij}(\tilde{\sim} \setminus B)| = |D_{ij}(\tilde{\sim})| + |W_{ij}|$, $|D_{ji}(\tilde{\sim} \setminus B)| = |D_{ji}(\tilde{\sim})| + |W_{ji}|$, $|D_{ij}(\tilde{\sim}' \setminus B)| = |D_{ij}(\tilde{\sim}')| + |W_{ij}|$, and $|D_{ji}(\tilde{\sim}' \setminus B)| = |D_{ji}(\tilde{\sim}')| + |W_{ji}|$. Now suppose that $iI_{CP}^{\tilde{\sim}}j$ and $iI_{CP}^{\tilde{\sim}'}j$ as demanded by Axiom 7 (CAT). Then, $|D_{ij}(\tilde{\sim})| = |D_{ji}(\tilde{\sim})|$ and $|D_{ij}(\tilde{\sim}')| = |D_{ji}(\tilde{\sim}')|$. Consequently,

$$iR_{CP}^{(\tilde{\sim} \setminus B)}j \Leftrightarrow |D_{ij}(\tilde{\sim})| + |W_{ij}| \geq |D_{ji}(\tilde{\sim})| + |W_{ji}| \Leftrightarrow |W_{ij}| \geq |W_{ji}|,$$

and

$$iR_{CP}^{(\tilde{\sim}' \setminus B)}j \Leftrightarrow |D_{ij}(\tilde{\sim}')| + |W_{ij}| \geq |D_{ji}(\tilde{\sim}')| + |W_{ji}| \Leftrightarrow |W_{ij}| \geq |W_{ji}|;$$

so, it follows that $iR_{CP}^{(\tilde{\sim} \setminus B)}j \Leftrightarrow iR_{CP}^{(\tilde{\sim}' \setminus B)}j$.

To show that $R_{CP}$ is the unique solution fulfilling Axioms 1 (Des), 2 (Neu), 3 (EC) and 6 (CAT) it must be proved that, if a solution $R$ satisfies these axioms, then $iR^{\tilde{\sim}}j \Leftrightarrow iR_{CP}^{\tilde{\sim}}j$ for all $i, j \in N$ and $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$.

Let $R$ be a solution fulfilling Axioms 1 (Des), 2 (Neu), 3 (EC) and 6 (CAT) and $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $\succ$ such that $\Sigma_1 \succ \dots \succ \Sigma_l$.

At first, prove that for any $i, j \in N$, $iP_{CP}^{\tilde{\sim}}j \Leftrightarrow iP^{\tilde{\sim}}j$.

(⇒) Let $iP_{CP}^{\tilde{\sim}}j$. So, $|D_{ij}(\tilde{\sim})| > |D_{ji}(\tilde{\sim})|$. Define a set of coalitions $E \subseteq D_{ij}(\tilde{\sim})$ such that $|E| = |D_{ij}(\tilde{\sim})| - |D_{ji}(\tilde{\sim})|$. Consider a new ranking $\tilde{\sim}' \in \mathcal{R}(\mathcal{F}(N))$ such that $D_{ij}(\tilde{\sim}') = D_{ij}(\tilde{\sim}) \setminus E$ and $D_{ji}(\tilde{\sim}') = D_{ji}(\tilde{\sim})$, and there exists an equivalence class $\Sigma$ of $\tilde{\sim}'$ such that $\Sigma = \{S \cup \{i\} : S \in E\} \cup \{S \cup \{j\} : S \in E\}$. By Lemma 5.1, it follows that $iP^{\tilde{\sim}}j$.

Now consider another ranking $\tilde{\sim}'' \in \mathcal{R}(\mathcal{F}(N))$ where $|D_{ji}(\tilde{\sim}'')| = |D_{ji}(\tilde{\sim}'')| = 0$ and there exists an equivalence class $\Sigma$ of $\tilde{\sim}''$ such that $\Sigma = \{S \cup \{i\} : S \in E\} \cup \{S \cup \{j\} : S \in E\}$. By Axiom 2 (Neu), it holds that $iP^{\tilde{\sim}''}j$. Let

$$B = \{(S \cup \{j\}, S \cup \{i\}) : S \in E\}.$$

Clearly, $B \subset \{(S, T) : S \sim' T \text{ and } S \sim'' T\}$. Moreover, if $(S \cup \{j\}, S \cup \{i\}) \in B$, then $(S \cup \{i\}, S \cup \{j\}) \notin B$, and by removing these pairs from $\tilde{\sim}'$ and $\tilde{\sim}''$ two new relations are created: $\tilde{\sim}' = \tilde{\sim}' \setminus B$ and $\tilde{\sim}'' = \tilde{\sim}'' \setminus B$. They are still rankings in $\mathcal{R}(\mathcal{F}(N))$. In fact, only the ties between coalitions in the equivalence class $\Sigma$ of both rankings are broken in favor of i, and so $\Sigma$ is split in two equivalence classes $\Sigma_i = \{S \cup \{i\} : S \in E\}$ and $\Sigma_j = \{S \cup \{j\} : S \in E\}$ such that $\Sigma = \Sigma_i \cup \Sigma_j$ and in the respective quotient orders $\Sigma_i \succ' \Sigma_j$ and $\Sigma_i \succ'' \Sigma_j$.

So, $(S \cup \{i\}, S \cup \{j\}) \in \tilde{\sim}'$ but $(S \cup \{j\}, S \cup \{i\}) \notin \tilde{\sim}''$ for all $S \in E$ (i.e., any $S \cup \{i\}$ with $S \in E$ is strictly stronger than $S \cup \{j\}$ in the ranking $\tilde{\sim}'' \setminus B$) while all the other coalitions $T \in 2^{N \setminus \{i,j\}} \setminus E$ are such that $T \cup \{i\} \sim T \cup \{j\}$. Therefore, by Axiom 1 (Des), $iP^{(\tilde{\sim}'' \setminus B)}j$ ($i$ is ranked strictly better than $j$ by the CP-majority in $\tilde{\sim}'' \setminus B$). So, by Axiom 6 (CAT) on $\tilde{\sim}'$ and $\tilde{\sim}''$, it follows that

$$iP^{(\tilde{\sim}' \setminus B)}j. \qquad (7)$$

Finally, notice that

$$S \cup \{i\} \tilde{\sim} S \cup \{j\} \Leftrightarrow S \cup \{i\} \tilde{\sim}' \setminus B S \cup \{j\},$$

for all $S \in 2^{N \setminus \{i,j\}}$ and, by Axiom 3 (EC) on $\tilde{\sim}$ and $\tilde{\sim}' \setminus B$ (using the identity bijection on $2^{N \setminus \{i,j\}}$),

$$iR^{\tilde{\sim}}j \Leftrightarrow iR^{\tilde{\sim}' \setminus B}j,$$
which finally yields $iP^{\tilde{\sim}}j$ in view of relation (7).

(=$\Leftarrow$) Let $iP^{\tilde{\sim}}j$. Suppose that $iI_{CP}^{\tilde{\sim}}j$. By definition of CP-majority, $|D_{ji}(\tilde{\sim}’)| = |D_{ji}(\tilde{\sim}’)|$. So, by Lemma 5.1, since $R$ satisfies both Axioms 3 (EC) and 2 (Neu), it holds $iI^{\tilde{\sim}}j$, which yields a contradiction with $iP^{\tilde{\sim}}j$. Since it can't even be $jP^{\tilde{\sim}}_{CP}i$ (by the implication previously proved), it must be $iP^{\tilde{\sim}}_{CP}j$.

Now prove that $iI_{CP}^{\tilde{\sim}}j \Leftrightarrow iI^{\tilde{\sim}}j$.

(=$\Rightarrow$) Let $iI_{CP}^{\tilde{\sim}}j$. Then, again by the definition of CP-majority, $|D_{ji}(\tilde{\sim}’)| = |D_{ji}(\tilde{\sim}’)|$ and so, by Lemma 5.1, $iI^{\tilde{\sim}}j$.

(=$\Leftarrow$) Let $iI^{\tilde{\sim}}j$. As previously shown, $iP_{CP}^{\tilde{\sim}}j \Leftrightarrow iP^{\tilde{\sim}}j$. So, it is not possible that $iP_{CP}^{\tilde{\sim}}j$ or $jP_{CP}^{\tilde{\sim}}i$ and by the fact that $R_{CP}^{\tilde{\sim}}$ is total, it follows that $iI_{CP}^{\tilde{\sim}}j$. $\square$

## 5.2 An axiomatic characterization of the lex-cel

In this section, we explore the implications of adopting a solution that satisfies Axioms 1 (Des), 4 (CA) and 7 (IWS).

First, we show that any solution satisfying Axioms 1 (Des) and 4 (CA) treats elements occurring with the same frequency in each equivalence class of a coalitional ranking as equally relevant.

**Lemma 5.2.** Let $R$ be a solution satisfying Axioms 1 (Des) and 4 (CA). Then for any $i, j \in N$ and $\succeq \in \mathcal{R}(\mathcal{F}(N))$ such that $\theta\tilde{\sim}(i) = \theta\tilde{\sim}(j)$ it holds that $iI^{\tilde{\sim}}j$.

*Proof* Since $\theta\tilde{\sim}(i) = \theta\tilde{\sim}(j)$, then $i_k = j_k$ for all $k \in \{1, \dots, n\}$. Define a bijection $\pi$ on $2^{N\setminus\{i,j\}}$ such that $\pi(S) \cup \{j\} \in \Sigma_k$ for each $k \in \{1, \dots, n\}$ and for each coalition $S \in 2^{N\setminus\{i,j\}}$ with $S \cup \{i\} \in \Sigma_k$. Consider a power relation $\preceq$ $\in \mathcal{R}(\mathcal{F}(N))$ such that $S \cup \{i\} \succeq T \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \preceq' T \cup \{j\}$. Notice that $T \cup \{i\} \sim' T \cup \{j\}$ for all $T \in 2^{N\setminus\{i,j\}}$. So, by Axiom 1 (Des), $iI^{\tilde{\sim}}j$ and, by Axiom 4 (CA) on $\succeq$ and $\preceq'$, it holds that $iI^{\tilde{\sim}}j$. $\square$

We now present an axiomatic characterization of the lex-cel.

**Theorem 2.** *The lex-cel solution $R_{le}$ is the unique solution fulfilling Axioms 1 (Des), 4 (CA) and 7 (IWS).*

*Proof* We start proving that $R_{le}$ satisfies Axioms 1 (Des). Take $i, j \in N$, $\succeq \in \mathcal{R}(\mathcal{F}(N))$ and suppose that $S \cup \{i\} \sim S \cup \{j\}$ for all $S \subseteq N \setminus \{i, j\}$. So, $\theta\tilde{\sim}(i) = \theta\tilde{\sim}(j)$ and $iI_{le}^{\tilde{\sim}}j$.

Now, suppose that $S \cup \{i\} \sim S \cup \{j\}$ for all $S \subseteq N \setminus \{i, j\}$ and $T \cup \{i\} \succ T \cup \{j\}$ for some $T \in 2^{N\setminus\{i,j\}}$. Consider the associated quotient order $\succ$ such that $\Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_l$ and let $s \in \{1, \dots, l\}$ be the smallest index such that there exists some $T \cup \{i\} \in \Sigma_s$ with $T \cup \{i\} \succ T \cup \{j\}$. Then $i_k = j_k$ for $k \in \{1, \dots, s-1\}$ and $i_s > j_s$ which implies $iP_{le}^{\tilde{\sim}}j$.

As already proved in Theorem 1 in [4], $R_{le}$ also satisfies Axioms 4 (CA) and 7 (IWS).

Take a solution $R$ satisfying Axioms 1 (Des), 4 (CA) and 7 (IWS).
It remains to show that $iR^{\sim}j \Leftrightarrow iR^{\tilde{\sim}}_{\tilde{l}e}j$ for all $i,j \in N$ and $\sim \in \mathcal{R}(\mathcal{F}(N))$. Fix $\sim \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $>_{\sim}$ such that $\Sigma_1 >_{\sim} \Sigma_2 >_{\sim} \dots >_{\sim} \Sigma_l$ and $i,j \in N$. The first step of the proof consists in showing that $iP^{\tilde{\sim}}_{\tilde{l}e}j \Leftrightarrow iP^{\sim}j$.

(⇒) Suppose $iP^{\tilde{\sim}}_{\tilde{l}e}j$. Let $s$ be the smallest integer in $\{1, \dots, l\}$ with $i_s > j_s$. Define a set of coalitions $B = \{S \in 2^{N\setminus\{i,j\}} : S \cup \{i\} \in \Sigma_s\}$ with $|B| = i_s - j_s > 0$.

Define a new coalitional ranking $\sim'$ with the associated quotient order $>_{\sim'}$ such that $\Sigma_1 >_{\sim'} \dots >_{\sim'} \Sigma_s >_{\sim'} T_{s+1}$ such that $T_{s+1} = \Sigma_{s+1} \cup \dots \cup \Sigma_l$. By Axiom 7 (IWS),

$$ iP^{\tilde{\sim}'}j \Rightarrow iP^{\tilde{\sim}}j. \qquad (8) $$

Define a bijection $\pi$ on $2^{N\setminus\{i,j\}}$ such that $\pi(S) \cup \{j\} \in \Sigma_k$ for each $k \in \{1, \dots, s\}$ and each coalition $S \in 2^{N\setminus\{i,j\}} \setminus B$ with $S \cup \{i\} \in \Sigma_k$, and such that $\pi(S) \cup \{j\} \in T_{s+1}$, for each $S \in B$. Let $\sim''$ be a coalitional ranking such that $S \cup \{i\} \sim' T \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \sim'' T \cup \{j\}$. Notice that $iP^{\tilde{\sim}''}_{\tilde{l}e}j$. So, by the fact that $R$ fulfils Axiom 1 (Des), it holds that $iP^{\tilde{\sim}''}j$. Moreover, by Axiom 4 (CA), $iR^{\tilde{\sim}'}j \Leftrightarrow iR^{\tilde{\sim}''}j$ and by relation (8) it follows that $iP^{\tilde{\sim}}j$.

( ⇐ ) Now, suppose $iP^{\tilde{\sim}}j$. If $iI^{\tilde{\sim}}_{\tilde{l}e}j$, by definition of lex-cel, $\theta^{\tilde{\sim}}(i) = \theta^{\tilde{\sim}}(j)$. So, by Lemma 5.2, $iI^{\tilde{\sim}}j$, which yields a contradiction with $iP^{\tilde{\sim}}j$. Since it can't even be $jP^{\tilde{\sim}}_{\tilde{l}e}i$ (by the implication previously proved), it must be $iP^{\tilde{\sim}}_{\tilde{l}e}j$.

The second step of the proof consists in showing that $iI^{\tilde{\sim}}_{\tilde{l}e}j \Leftrightarrow iI^{\tilde{\sim}}j$.

(⇒) Suppose $iI^{\tilde{\sim}}_{\tilde{l}e}j$. Then, again by the definition of the lex-cel, $\theta^{\tilde{\sim}}(i) = \theta^{\tilde{\sim}}(j)$ and so, by Lemma 5.2, $iI^{\tilde{\sim}}j$.

( ⇐ ) Now, suppose $iI^{\tilde{\sim}}j$. As previously shown, $iP^{\tilde{\sim}}_{\tilde{l}e}j \Leftrightarrow iP^{\tilde{\sim}}j$. So, it is not possible that $iP^{\tilde{\sim}}_{\tilde{l}e}j$ or $jP^{\tilde{\sim}}_{\tilde{l}e}i$ and by the fact that $R^{\tilde{\sim}}_{\tilde{l}e}$ is total, it follows that $iI^{\tilde{\sim}}_{\tilde{l}e}j$. $\square$

In [4] the dual-lex solution has been introduced as the dual solution of the lex-cel solution. Given two $l$-dimensional vectors $i, j$ we define the lexicographic* order $\geq_{L^*}$ as

$$ i \geq_{L^*} j \quad \text{if either } i = j \quad \text{or} \quad \exists s : i_k = j_k, k = s+1, \dots, l \quad \text{and } i_s < j_s. $$

**Definition 6 (dual-lex [4]).** The dual-lexicographic (dual-lex) solution is the function $R_d : \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ defined for any ranking $\sim \in \mathcal{R}(\mathcal{F}(N))$ as
$$ iR_d(\sim)j \quad \text{if} \quad \theta_{\sim}(i) \geq_{L^*} \theta_{\sim}(j). $$

We now introduce an axiomatic characterization for the dual-lex.

**Theorem 3.** The dual-lex solution $R_d$ is the unique solution fulfilling Axioms 1 (Des), 4 (CA) and 8 (IBS).

*Proof* First observe that the dual-lex solution $R_d$ satisfies Axiom 1 (Des). Fix $\sim \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $>_{\sim}$ such that $\Sigma_1 >_{\sim} \dots >_{\sim} \Sigma_l$ and $i, j \in N$ such that $S \cup \{i\} \sim S \cup \{j\}$ for all $S \in 2^{N\setminus\{i,j\}}$. Clearly, if $S \cup \{i\} \sim S \cup \{j\}$ for all $S \in 2^{N\setminus\{i,j\}}$, then it immediately follows that $\theta_{\sim}(i) = \theta_{\sim}(j)$. Suppose now that there exists a coalition
$T \in 2^{N \setminus \{i,j\}}$ such that $T \cup \{i\} \succ T \cup \{j\}$. Let $s \in \{1, \dots, l\}$ be the highest index such that there exists a coalition $\tilde{T} \in 2^{N \setminus \{i,j\}}$ such that $\tilde{T} \cup \{i\} \succ \tilde{T} \cup \{j\}$ and $\tilde{T} \cup \{j\} \in \Sigma_s$. Then $i_s < j_s$ and $i_k = j_k$, $\forall k > s$. It follows that $\theta_{\tilde{\sim}}(i) \geq_{L^*} \theta_{\tilde{\sim}}(j)$, and so $i R_d j$. The rest of the proof of the theorem follows the same arguments of the proof of Theorem 2 and they are omitted. □

## 5.3 An axiomatic characterization of the $L^{(1)}$ solution

In this section, we explore the implications of adopting a solution that satisfies Axioms 1 (Des), 7 (IWS), 9 (k-DD), 5 (PCA) and 10 (CI).

We start our axiomatic analysis with the following lemma showing that solutions satisfying Axioms 1 (Des) and 5 (PCA) state that two elements that occur with the same frequency and within coalitions of the same size in each equivalence class of a coalitional ranking should be considered as equally relevant (this result was also shown in paper [15]).

**Lemma 5.3.** Let $R$ be a solution satisfying Axioms 1 (Des) and 5 (PCA). Then for any $i, j \in N$ and $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ such that $M_{sk}^{\tilde{\sim},i} = M_{sk}^{\tilde{\sim},j}$ for all $s \in \{1, \dots, n\}$ and $k \in \{1, \dots, l\}$ it holds that $i I^{\tilde{\sim}} j$.

*Proof* Define a bijection $\pi$ on $2^{N \setminus \{i,j\}}$ such that $\pi(S) \cup \{j\} \in \Sigma_k$ if $S \cup \{i\} \in \Sigma_k$, for each $k \in \{1, \dots, l\}$, for each coalition $S \in 2^{N \setminus \{i,j\}}$ with $|\pi(S)| = |S|$. Consider a coalitional ranking $\tilde{\sim}' \in \mathcal{R}(\mathcal{F}(N))$ such that

$$S \cup \{i\} \succ T \cup \{j\} \Leftrightarrow \pi(S) \cup \{i\} \succ' T \cup \{j\}.$$

Notice that $T \cup \{i\} \sim' T \cup \{j\}$ for all $T \in 2^{N \setminus \{i,j\}}$. So, by Axiom 1 (Des), it holds that $i I^{\tilde{\sim}',j}$ and, by Axiom 5 (PCA) on $\tilde{\sim}$ and $\tilde{\sim}'$, it follows that $i I^{\tilde{\sim},j}$. □

We now introduce an axiomatic characterization of the $L^{(1)}$ solution.

**Theorem 4.** The solution $R_{L^{(1)}}$ is the unique solution fulfilling Axioms 1 (Des), 5 (PCA), 7 (IWS), 9 (k-DD), and 10 (CI).

*Proof L*(1) solution satisfies Axiom 5 (PCA) and 7 (IWS) as showed in [15].

Let start proving that $L^{(1)}$ satisfies Axiom 1 (Des). Consider a coalitional ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with quotient order $\Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_l$ such that $S \cup \{i\} \succ S \cup \{j\}$, for all $S \in 2^{N \setminus \{i,j\}}$. First, consider the case $S \cup \{i\} \sim S \cup \{j\}$, for all $S \in 2^{N \setminus \{i,j\}}$. This means that coalitions $S \cup \{i\}$ and $S \cup \{j\}$ belong to the same equivalence class and then $M_{sk}^{\tilde{\sim},i} = M_{sk}^{\tilde{\sim},j}$ for all $s \in \{1, \dots, n\}$, and all $k \in \{1, \dots, l\}$. So, we have $i I_{L^{(1)}} j$. Now, suppose that $S \cup \{i\} \succ S \cup \{j\}$, for all $S \in 2^{N \setminus \{i,j\}}$ and there exist some $T \in 2^{N \setminus \{i,j\}}$ with $T \cup \{i\} \succ T \cup \{j\}$. Let $\bar{k}$ be the smallest index in $\{1, \dots, l\}$ such that there exist some coalitions $\bar{T} \cup \{i\} \in \Sigma_{\bar{k}}$ with $\bar{T} \in 2^{N \setminus \{i,j\}}$ and $\bar{T} \cup \{i\} \succ \bar{T} \cup \{j\}$. Moreover, let $\bar{s}$ be the smallest index in $\{1, \dots, n\}$ such that there exist some coalitions $\bar{S} \cup \{i\} \in \Sigma_{\bar{k}}$ with $\bar{S} \in 2^{N \setminus \{i,j\}}$, $|\bar{S} \cup \{i\}| = \bar{s}$ and $\bar{S} \cup \{i\} \succ \bar{S} \cup \{j\}$. Then we have that $M_{sk}^{\tilde{\sim},i} = M_{sk}^{\tilde{\sim},j}$ for all $s \in \{1, \dots, n\}$ and
$k \in \{1, \dots, \bar{k} - 1\}; M_{\bar{s}\bar{k}}^{\sim, i} = M_{\bar{s}\bar{k}}^{\sim, j}$ for all $s \in \{1, \dots, \bar{s} - 1\}; M_{\bar{s}\bar{k}}^{\sim, i} < M_{\bar{s}\bar{k}}^{\sim, j}$. So, by Definition 4, $iP_{\tilde{L}(1)}^{\sim, j}$ and we can conclude that $R_{\tilde{L}(1)}$ satisfies Axiom 1 (Des).

To prove that $L^{(1)}$ satisfies Axiom 9 (k-DD) let $s_i^* = \min\{s \in \mathcal{K}P_{ij}^{\sim}\}, \text{ where } \sim \in \mathcal{R}(\mathcal{F}(N))$ is a dichotomous coalitional ranking with quotient order $\Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_l$ such that $i I_{\tilde{L}(1)}^{\sim, j}$. By Definition 4, it holds $M_{\tilde{s}, i}^{\sim, j} = M_{\tilde{s}, j}^{\sim, i}$. Consider two coalitional ranking $\sim^j, \sim^{j''} \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $\succ^j$ and $\succ^{j''}$ with

$$M_{\bar{s}1}^{\sim, i} = M_{\bar{s}1}^{\sim, j}, \forall s < s_i^* \text{ and } M_{\bar{s}_1^1}^{\sim, i} > M_{\bar{s}_1^1}^{\sim, j},$$

then $R_{\tilde{L}(1)}^{\sim}$ satisfies Axiom 9 (k-DD).

It remains to prove that $L^{(1)}$ also satisfies Axiom 10. Let $\sim \in \mathcal{R}(\mathcal{F}(N))$ and $i, j \in N$ with quotient order $\Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_l$ such that $i I_{\tilde{L}(1)}^{\sim, j}$. By Definition 4, it holds $M_{\tilde{s}, i}^{\sim, j} = M_{\tilde{s}, j}^{\sim, i}$. Consider two coalitional ranking $\sim^j, \sim^{j''} \in \mathcal{R}(\mathcal{F}(N))$ with the associated quotient order $\succ^j$ and $\succ^{j''}$ with

$$\Sigma_1 \succ^j \Sigma_2 \succ^j \dots \succ^j \Sigma_{l-1} \cup \Sigma \succ^j \Sigma_l \setminus \Sigma$$

and

$$\Sigma_1 \cup \Sigma_2 \cup \dots \cup \Sigma_{l-1} \cup \Sigma \succ^{j''} \Sigma_l \setminus \Sigma,$$

for $\Sigma \subset \Sigma_l$. It holds that $i P_{\tilde{L}(1)}^{\sim, j} \Leftrightarrow j P_{\tilde{L}(1)}^{\sim, j''}$. i. Indeed, by Definition 4, it is obvious that $i I_{\tilde{L}(1)}^{\sim, j} \Leftrightarrow j I_{\tilde{L}(1)}^{\sim, j''}$. i. Moreover, suppose that $i P_{\tilde{L}(1)}^{\sim, j}$ and $j P_{\tilde{L}(1)}^{\sim, j''}$. i. By $i P_{\tilde{L}(1)}^{\sim, j}$, there is an index $\bar{s}$ such that $M_{\bar{s}\bar{l}-1}^{\sim, i} > M_{\bar{s}\bar{l}-1}^{\sim, j}$ and such that $M_{\bar{s}\bar{l}-1}^{\sim, i} = M_{\bar{s}\bar{l}-1}^{\sim, j}$, if $\bar{s} > 1, \forall s < \bar{s}$. This implies that the number of coalitions containing either $i$ or $j$ of size less than $\bar{s}$ in $\Sigma_1 \cup \Sigma_2 \cup \dots \cup \Sigma_{l-1} \cup \Sigma$ is the same. This observation contradicts the assumption $j P_{\tilde{L}(1)}^{\sim, j''}$. i and then $L^{(1)}$ satisfies Axiom 10 (CI).

Let $R$ be a solution satisfying Axioms 1 (Des), 7 (IWS), 9 (k-DD), 5 (PCA), and 10 (CI). Last part of the proof is devoted to show that $iR^{\sim, j} \Leftrightarrow iR_{\tilde{L}(1)}^{\sim, j}, \forall i, j \in N$ and $\forall \sim \in \mathcal{R}(\mathcal{F}(N))$. Take $\sim \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\succ$,

$$\Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_l.$$

The first step consists in proving that $iP_{\tilde{L}(1)}^{\sim, j} \Leftrightarrow iP^{\sim, j}$

(⇒) Suppose $iP_{\tilde{L}(1)}^{\sim, j}$, then there are $\hat{k} \in \{1, \dots, l\}$ and $\hat{s} \in \{1, \dots, n\}$ such that

$$M_{\hat{s}\hat{k}}^{\sim, i} > M_{\hat{s}\hat{k}}^{\sim, j}, \text{ and}$$

$$M_{\hat{s}\hat{k}}^{\sim, i} = M_{\hat{s}\hat{k}}^{\sim, j} \text{ for all } s \in \{1, \dots, n\} \text{ and all } k \in \{1, \dots, \hat{k} - 1\},$$

$$M_{\hat{s}\hat{k}}^{\sim, i} = M_{\hat{s}\hat{k}}^{\sim, j} \text{ for all } s \in \{1, \dots, \hat{s} - 1\}.$$

Consider the ranking $\sim^j$ with associated quotient order

$$\Sigma_1 \succ^j \dots \succ^j \Sigma_{\hat{k}} \succ^j \underbrace{\Sigma_{\hat{k}+1} \cup \dots \cup \Sigma_l}_{T_{\hat{k}+1}}.$$

By Axiom 7 (IWS)

$$iP^{\sim, j} \Rightarrow iP^{\sim, j}. \qquad (9)$$

Define $B_{\hat{s}}^{ij} = \{S : S \cup \{i\} \in \Sigma_{\hat{k}}, |S \cup \{i\}| = \hat{s}\}$ such that $|B_{\hat{s}}^{ij}| = M_{\hat{s}\hat{k}}^{\sim, i} - M_{\hat{s}\hat{k}}^{\sim, j}$. Take a bijection $\pi$ on $2^N \setminus \{i, j\}$ such that $|\pi(S)| = |S|, \forall S \in 2^N \setminus \{i, j\}$, and

$$\pi(S) \cup \{j\} \in \Sigma_k, \text{ if } S \cup \{i\} \in \Sigma_k, \forall k < \hat{k};$$
$\pi(S) \cup \{j\} \in \Sigma_{\hat{k}}$, if $S \cup \{i\} \in \Sigma_{\hat{k}} \setminus B_s^{ij}$, with $|S \cup \{i\}| \le \hat{s}$;

$\pi(S) \cup \{j\} \in T_{k+1}$, if $S \in B_s^{ij}$.

It is necessary to distinguish two cases:

Case a) $M_{\hat{s}\hat{k}}^{\sim,i} \ge M_{\hat{s}\hat{k}}^{\sim,j}$ for all $s \in \{\hat{s}+1, \dots, n\}$.

Define the set $B_s^{ij} = \{S : S \cup \{i\} \in \Sigma_{\hat{k}}, |S \cup \{i\}| = s\}$ such that $|B_s^{ij}| = M_{\hat{s}\hat{k}}^{\sim,i} - M_{\hat{s}\hat{k}}^{\sim,j}$. Then:

$\pi(S) \cup \{j\} \in \Sigma_{\hat{k}}$, if $S \cup \{i\} \in \Sigma_{\hat{k}} \setminus B_s^{ij}$, $|S| = s$

$\pi(S) \cup \{j\} \in T_{\hat{k}+1}$, if $S \in B_s^{ij}$;

Case b) for all $s \in \{\hat{s}+1, \dots, n\}$ either $M_{\hat{s}\hat{k}}^{\sim,i} \ge M_{\hat{s}\hat{k}}^{\sim,j}$ or $M_{\hat{s}\hat{k}}^{\sim,i} \le M_{\hat{s}\hat{k}}^{\sim,j}$. The second case must be split in two sub-cases:

Case b.1) Suppose $M_{\hat{s}\hat{k}}^{\sim,i} - M_{\hat{s}\hat{k}}^{\sim,j} = b \ge 0$, define $B_s^{ij} = \{S : S \cup \{i\} \in \Sigma_{\hat{k}}, |S \cup \{i\}| = s\}$ such that $|B_s^{ij}| = b$. Then

$\pi(S) \cup \{j\} \in \Sigma_{\hat{k}}$, if $S \cup \{i\} \in \Sigma_{\hat{k}} \setminus B_s^{ij}$, $|S| = s$

$\pi(S) \cup \{j\} \in T_{\hat{k}+1}$, if $S \in B_s^{ij}$;

Case b.2) Suppose $M_{\hat{s}\hat{k}}^{\sim,j} - M_{\hat{s}\hat{k}}^{\sim,i} = b \ge 0$, define $B_s^{ji} = \{S : S \cup \{j\} \in \Sigma_{\hat{k}}, |S \cup \{j\}| = s\}$ such that $|B_s^{ji}| = b$. Then

$\pi(S) \cup \{j\} \in \Sigma_{\hat{k}}$, if $S \cup \{i\} \in \Sigma_{\hat{k}} \setminus B_s^{ji}$, $|S| = s$

$\pi(S) \cup \{i\} \in T_{\hat{k}+1}$, if $S \in B_s^{ji}$.

Consider the ranking $\sim''$ such that

Case a) $S \cup \{i\} \succ' T \cup \{j\} \iff \pi(S) \cup \{i\} \succ'' T \cup \{j\}$,

Case b.1) $S \cup \{i\} \succ' T \cup \{j\} \iff \pi(S) \cup \{i\} \succ'' T \cup \{j\}$,

Case b.2) $S \cup \{i\} \prec' T \cup \{j\} \iff \pi(S) \cup \{i\} \prec'' T \cup \{j\}$.

with the associated quotient order

$$ \tilde{\Sigma}_1 \succ'' \dots \succ'' \tilde{\Sigma}_{\hat{k}} \succ'' \tilde{T}_{\hat{k}+1}. $$

Then by Axiom 5 (PCA)

$$ iR^{\sim'} j \iff iR^{\sim''} j. \qquad (10) $$

Take $\Sigma = \{\pi(S) \cup \{i\}, S \in \cup_s B_s^{ij}\} \cup \{S \cup \{j\}, S \in \cup_s B_s^{ji}\}$ and define the ranking $\sim'''$ as follows

$$ \tilde{\Sigma}_1 \succ'''' \dots \succ'''' \tilde{\Sigma}_{\hat{k}} \setminus \Sigma \succ'''' \tilde{T}_{\hat{k}+1} \cup \Sigma. $$

Notice that in $\sim'''$, for all $S \in 2^{N\setminus\{i,j\}}$, it holds $S \cup \{i\} \sim S \cup \{j\}$ then Axiom 1 (Des) implies $iR^{\sim'''}$.

Now consider the ranking $\sim''''$ with the associated quotient order

$$ \tilde{\Sigma}_1 \cup \dots \cup \tilde{\Sigma}_{\hat{k}} \succ'''' \tilde{T}_{\hat{k}+1}. $$

Then by Axiom 10 (CI)

$$ iR^{\sim''} j \iff iR^{\sim''''} j. \qquad (11) $$

Using the construction of $\pi$ notice that in $\sim''''$

Case a) Axiom 1 (Des) implies $iP^{\sim''''} j$,
Case b) Axiom 9 (k-DD) implies $iP^{\tilde{\sim}'''}j$. In fact the following facts hold true:

* $KI_{ij}^{\tilde{\sim}'''} = \{0, \dots, \hat{s}-1\}$ and for any $s \in \{\hat{s}, \dots, n\}$ then either $S \cup \{i\} \tilde{\sim}'''' S \cup \{j\}$, $\forall S \in 2^{N \setminus \{i,j\}}$ and $|S| = s$, or $S \cup \{j\} \tilde{\sim}'''' S \cup \{i\}$, $\forall S \in 2^{N \setminus \{i,j\}}$ and $|S| = s$;

* $\hat{s} \in KP_{ij}^{\tilde{\sim}'''}$ and $KP_{ji}^{\tilde{\sim}'''} \cap \{\hat{s}+1, \dots, n\} \neq \emptyset$, otherwise $i$ would be strictly more desirable than $j$;

* $\hat{s} = \min\{k \in KP_{ij}^{\tilde{\sim}'''}\} < \min\{k \in KP_{ji}^{\tilde{\sim}'''}\}$.

Then

$$iP^{\tilde{\sim}'''}j \overset{(11)}{\implies} iP^{\tilde{\sim}''}j \overset{(10)}{\implies} iP^{\tilde{\sim}'}j \overset{(9)}{\implies} iP^{\tilde{\sim}}j. \quad (12)$$

(=$\Leftarrow$) Suppose $iP^{\tilde{\sim}}j$. If $iI_{L(1)}^{\tilde{\sim}}j$, by definition of $L^{(1)}$ solution, $M^{\tilde{\sim},i} = M^{\tilde{\sim},j}$. So, by Lemma 5.3, $iI^{\tilde{\sim}}j$, which yields a contradiction with $iP^{\tilde{\sim}}j$. Since it can't even be $jP_{L(1)}^{\tilde{\sim}}i$ (by the implication previously proved), it must be $iP_{L(1)}^{\tilde{\sim}}j$.

In the last step it is proved that $iI_{L(1)}^{\tilde{\sim}}j \Leftrightarrow iI^{\tilde{\sim}}j$.

(=$\Rightarrow$) Suppose $iI_{L(1)}^{\tilde{\sim}}j$. Then, again by the definition of the $L^{(1)}$ solution, $M^{\tilde{\sim},i} = M^{\tilde{\sim},j}$ and so, by Lemma 5.3, $iI^{\tilde{\sim}}j$.

(=$\Leftarrow$) Suppose $iI^{\tilde{\sim}}j$. As previously shown, $iP_{L(1)}^{\tilde{\sim}}j \Leftrightarrow iP^{\tilde{\sim}}j$. So, it is not possible that $iP_{L(1)}^{\tilde{\sim}}j$ or $jP_{L(1)}^{\tilde{\sim}}i$ and by the fact that $R_{L(1)}^{\tilde{\sim}}$ is total, it follows that $iI_{L(1)}^{\tilde{\sim}}j$. $\square$

In [15] the authors mention the possibility to define a dual solution of the $L^{(1)}$ solution using the Independence of the Best Set axiom in place of the Independence of the Worst Set axiom. However, at the time, no formal axiomatic characterization of $L^{(1)}$ was provided. Using Axiom 1 (Des), an axiomatic characterization also follows.

**Definition 7** ($L_*^{(1)}$ solution [15]). The $L_*^{(1)}$ solution is the map $R_{L_*^{(1)}}^{\tilde{\sim}}: \mathcal{R}(\mathcal{F}(N)) \to \mathcal{B}(N)$ such that for any power relation $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ and $i, j \in N$:
$$i I_{L_*^{(1)}}^{\tilde{\sim}} j \iff M^{\tilde{\sim},i} = M^{\tilde{\sim},j}$$

and

$$\exists \hat{s} \in \{1, \dots, n\} \text{ and } \hat{k} \in \{2, \dots, l\} \text{ such that } \\ i P_{L_*^{(1)}}^{\tilde{\sim}} j \iff \left\{ \begin{array}{l} M_{\hat{s}\hat{k}}^{\tilde{\sim},i} = M_{\hat{s}\hat{k}}^{\tilde{\sim},j}, \forall s \in \{1, \dots, n\}, \forall k \in \{\hat{k}+1, \dots, l\}; \\ M_{\hat{s}\hat{k}}^{\tilde{\sim},i} = M_{\hat{s}\hat{k}}^{\tilde{\sim},j}, \forall s \in \{1, \dots, \hat{s}-1\}; \\ M_{\hat{s}\hat{k}}^{\tilde{\sim},i} < M_{\hat{s}\hat{k}}^{\tilde{\sim},j}. \end{array} \right.$$

The next theorem gives a characterization of the $L_*^{(1)}$, the dual solution of $L^{(1)}$.

**Theorem 5.** The solution $R_{L_*^{(1)}}^{\tilde{\sim}}$ is the unique solution fulfilling Axioms 1 (Des), 8 (IBS), 9 (k-DD), 5 (PCA), and 10 (CI).
*Proof* We start by showing that the $L_*^{(1)}$ solution satisfies Axiom 1 (Des). Consider a coalitional ranking $\succcurlyeq \mathcal{R}(\mathcal{F}(N))$ with quotient order $\Sigma_1 \succ \Sigma_2 \succ \dots \succ \Sigma_l$ such that $S \cup \{i\} \succcurlyeq S \cup \{j\}$, for all $S \in 2^{N\setminus\{i,j\}}$. First, consider the case $S \cup \{i\} \sim S \cup \{j\}$, for all $S \in 2^{N\setminus\{i,j\}}$. This means that the coalitions $S \cup \{i\}$ and $S \cup \{j\}$ belong to the same equivalence class and then $M_{\hat{s}_k}^{\succcurlyeq,i} = M_{\hat{s}_k}^{\succcurlyeq,j}$ for all $s \in \{1, \dots, n\}$, and all $k \in \{1, \dots, l\}$. So, $i \in I_{L_*^{(1)}}$ $j$. Now, suppose that $S \cup \{i\} \succcurlyeq S \cup \{j\}$, for all $S \subseteq N \setminus \{i,j\}$ and there exist some $T \in 2^{N\setminus\{i,j\}}$ with $T \cup \{i\} \succ T \cup \{j\}$. Let $\hat{k}$ be the largest index in $\{1, \dots, l\}$ such that there exist some coalitions $\hat{T} \cup \{j\} \in \Sigma_{\hat{k}}$ with $\hat{T} \in 2^{N\setminus\{i,j\}}$ and $\hat{T} \cup \{i\} \succ \hat{T} \cup \{j\}$. Moreover, let $\hat{s}$ be the smallest index in $\{1, \dots, n\}$ such that there exist some coalitions $\hat{S} \cup \{j\} \in \Sigma_{\hat{k}}$ with $\hat{S} \in 2^{N\setminus\{i,j\}}$, $|\hat{S} \cup \{j\}| = \hat{s}$ and $\hat{S} \cup \{i\} \succ \hat{S} \cup \{j\}$. Then $M_{\hat{s}_k}^{\succcurlyeq,i} = M_{\hat{s}_k}^{\succcurlyeq,j}$ for all $s \in \{1, \dots, n\}$ and $k \in \{\hat{k} + 1, \dots, l\}$, $M_{\hat{s}_k}^{\succcurlyeq,i} = M_{\hat{s}_k}^{\succcurlyeq,j}$ for all $s \in \{1, \dots, \hat{s} - 1\}$, and $M_{\hat{s}_k}^{\succcurlyeq,i} < M_{\hat{s}_k}^{\succcurlyeq,j}$. So, by Definition 7, $iP_{L_*^{(1)}}^{\succcurlyeq,j}$ and this implies that $R_{L_*^{(1)}}$ satisfies Axiom 1 (Des).

The proof of the theorem proceeds in a manner analogous to that of Theorem 4 and is therefore omitted. □

# 6 Comparison between the axioms

In this section, we investigate the relationship among axioms introduced in Section 4 and their logical independence with respect to the axiomatic characterizations introduced in Section 5.

**Proposition 6.** The following statements hold true:

i) There is no logical dependence between the axioms Equality of Coalitions 3 (EC) and Coalitional Anonymity 4 (CA).

ii) There is no logical dependence between the axioms Equality of Coalitions 3 (EC) and Per-size Coalitional Anonymity 5 (PCA).

Before proving the above proposition it is useful to recall that in [15] it is shown that Coalition Anonymity implies Per-size Coalition Anonymity.

*Proof Statement (i)*

Consider the CP-majority relation $R_{CP}$. It satisfies EC, but not CA. In fact, consider a coalitional ranking $\succcurlyeq \mathcal{R}(\mathcal{F}(N))$ with $N = \{i,j,k\}$ and such that $j \succ ik \succ jk \sim i$. By definition, $iI_{CP}^{\succcurlyeq,j}$. Now, consider a bijection on $\{\emptyset, k\}$ such that $\pi(\emptyset) = k$ and a ranking $\sqsupseteq \mathcal{R}(\mathcal{F}(N))$ such that $j \sqsupseteq i \sqsupseteq jk \sim ik$. A solution that satisfies CA on $\succcurlyeq$ and $\sqsupseteq$ would give the same ranking between $i$ and $j$ over the two coalitional rankings. But $jP_{CP}^{\sqsupseteq,i}$, so $R_{CP}$ does not satisfy CA.

Now, consider the lex-cel solution $R_{le}$. The lex-cel satisfies CA, but not EC. In fact, consider, for instance, the coalitional ranking $\succcurlyeq \mathcal{R}(\mathcal{F}(N))$ with $N = \{i,j,k\}$ and such that $ik \succ jk \succ j \succ i$, and another ranking $\sqsupseteq$ such that $j \sqsupseteq i \sqsupseteq ik \sqsupseteq jk$. A solution that satisfies EC in $\succcurlyeq$ and $\sqsupseteq$ (with the identity bijection in Axiom 3) should rank $i$ and $j$ in the same way in both coalitional rankings $\succcurlyeq$ and $\sqsupseteq$. Indeed, the coalition $ik$ is better than the coalition $jk$ in both $\succcurlyeq$ and $\sqsupseteq$, and coalition $j$ is better than coalition $i$ in both $\succcurlyeq$ and $\sqsupseteq$. On the other hand the lex-cel yields $iP_{le}^{\succcurlyeq,j}$ and $jP_{le}^{\sqsupseteq,i}$. So, lex-cel does not satisfy EC.
Statement (ii)

Consider the CP-majority relation $R_{CP}$. It satisfies EC, but not PCA. In fact, consider a coalitional ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$ with $N = \{i, j, k, l\}$ and such that $jl \succ ik \succ jk \sim il \succ C$, where $C$ is an equivalence class containing all the other coalitions not already displayed. By definition, $iI_{CP}^{\succsim}j$. Now, consider a size-invariant bijection on $\{\emptyset, k, l, kl\}$ such that $\pi(k) = l$ and $\pi(l) = k$ and a ranking $\sqsupseteq \in \mathcal{R}(\mathcal{F}(N))$ such that $jl \sqsupseteq il \sqsupseteq jk \sim ik$. A solution that satisfies PCA in $\succsim$ and $\sqsupseteq$ would give the same ranking between $i$ and $j$ over the two coalitional rankings. But $jP_{CP}^{\sqsupseteq}i$, so $R_{CP}$ does not satisfy PCA.

Now, considering the $L^{(1)}$ solution, $R_{L^{(1)}}$, it satisfies PCA, but not EC. In fact, taking the same example used in Statement (i), it holds $iP_{L^{(1)}}^{\succsim}j$ and $jP_{L^{(1)}}^{\sqsupseteq}i$, but, as already observed, a solution that satisfies EC in $\succsim$ and $\sqsupseteq$ should rank $i$ and $j$ in the same way in both coalitional rankings $\succsim$ and $\sqsupseteq$. So, the $L^{(1)}$ solution does not satisfy EC.

□

## 6.1 Independence of the axioms for CP-majority

We prove that Axioms 1 (Des), 2 (Neu), 3 (EC) and 6 (CAT) are independent.

**Desirability is not satisfied:** Consider the solution $R_{Id}$ that ranks all players equally, that is, $\forall i, j \in N$, $iI_{Id}^{\succsim}j$ for all $\succsim \in \mathcal{R}(\mathcal{F}(N))$. It is easy to observe that this solution satisfies Axioms 2 (Neu), 3 (EC) and 6 (CAT), but not Axiom 1 (Des).

**Equality of coalitions is not satisfied:** Consider the solution $R_{EC}$ that coincides with the CP-majority solution if

* for a ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$, the CP-majority produces a total order,

* for a ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$ and two players $i, j \in N$ such that $\emptyset$ belongs neither to $D_{ij}(\succsim)$ nor to $D_{ji}(\succsim)$ and $|D_{ij}(\succsim)| = |D_{ji}(\succsim)|$.

In the other cases, if $\emptyset \in D_{ij}(\succsim)$, then $iP_{EC}^{\succsim}j$. By definition, this solution satisfies Axiom 1 (Des) and 2 (Neu). Moreover, given $\succsim, \succsim' \in \mathcal{R}(\mathcal{F}(N))$ such that $iI_{EC}^{\succsim}j$ and $iI_{EC}^{\succsim'}j$ then $i \sim j$ and $i \sim' j$ then removing a subset of $\succsim \cap \succsim'$ does not affect the ranking between the players, because either CP-majority can be applied or the empty set can be added in both $D_{ij}(\succsim)$ and $D_{ij}(\succsim')$ (or $D_{ji}(\succsim)$ and $D_{ji}(\succsim')$). Then this solution satisfies Axiom 6 (CAT). Consider the rankings $\succsim, \succsim' \in \mathcal{R}(\mathcal{F}(N))$ such that $|D_{ij}(\succsim)| = |D_{ji}(\succsim)|$ and $|D_{ij}(\succsim')| = |D_{ji}(\succsim')|$, $\emptyset \in D_{ij}(\succsim)$, $T \notin D_{ji}(\succsim)$ and $\emptyset \notin D_{ij}(\succsim')$, $T \in D_{ji}(\succsim')$ then $iP_{EC}^{\succsim}j$ and $jP_{EC}^{\succsim'}i$. Considering a bijection $\pi$ such that $\pi(\emptyset) = T$, a solution $R$ satisfying Axiom 3 (EC) in $\succsim$ and $\succsim'$ should be such that $iR^{\succsim}j \Leftrightarrow iR^{\succsim'}j$. It follows that $R_{EC}$ does not satisfy Axiom 3 (EC).

**Neutrality is not satisfied:** Consider a solution $R_N$ that coincides with $R_{CP}^{\succsim}$ when for a ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$ the CP-majority produces a total order. In the other cases, given $\succsim, iP_N^{\succsim}j$ holds if and only if $i < j$. This solution satisfies 1 (Des), 3 (EC) and 6 (CAT), but not Axiom 2 (Neu).
**Consistency after tiebreaks is not satisfied:** Given a power relation $\succsim \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 \succ \dots \succ \Sigma_l$ and two elements $i, j \in N$, define the sets: $D_{ij}^k(\succsim) = \{S \in 2^{N\setminus\{i,j\}} : S \cup \{i\} \in \Sigma_k, S \cup \{j\} \in \Sigma_{k'}, k < k'\}$, for $k \in \{1, \dots, l-1\}$. Consider the solution $R_{CAT}$ such that

* $iP_{CAT}^{\succsim}j$ if there exist $\hat{k} \in \{1, \dots, l-1\}$ such that $|D_{ij}^{\hat{k}}(\succsim)| > |D_{ji}^{\hat{k}}(\succsim)|$ and, if $\hat{k} > 1$, $|D_{ij}^{\hat{k}}(\succsim)| = |D_{ji}^{\hat{k}}(\succsim)|$, for all $k \in \{1, \dots, \hat{k}-1\}$,

* $iI_{CAT}^{\succsim}j$ if $|D_{ij}^{\hat{k}}(\succsim)| = |D_{ji}^{\hat{k}}(\succsim)|$, for all $k \in \{1, \dots, l-1\}$.

This solution satisfies 1 (Des) because, for all $k \in \{1, \dots, l-1\}$, either $|D_{ij}^k(\succsim)| = |D_{ji}^k(\succsim)| = 0$ or $|D_{ij}^k(\succsim)| > |D_{ji}^k(\succsim)|$. Axiom 3 (EC) is satisfied because the permutation $\pi$ does not change the cardinality of the sets $|D_{ij}^k(\succsim)|$ and $|D_{ji}^k(\succsim)|$. In order to show that this solution satisfies Axiom 2 (Neu), it is enough to observe that permuting player $i$ with player $j$ reverses all relations. Lastly, consider the rankings $\succsim, \succsim'$ with associated quotient orders

$$ \Sigma_1 \succ \Sigma_2 \succ \Sigma_3 \quad \text{and} \quad \Sigma'_1 \succ' \Sigma'_2 \succ' \Sigma'_3 $$

such that $iI_{CAT}^{\succsim}j$ and $iI_{CAT}^{\succsim'}j$. Suppose that there are coalitions $S, T \in 2^{N\setminus\{i,j\}}$ such that

$$ \Sigma_1 = \Sigma'_3 = \{S \cup \{i\}, S \cup \{j\}\}, $$

$$ \Sigma_2 = \Sigma'_2 = \{T \cup \{i\}, T \cup \{j\}\}. $$

Define a set $B = \{(S \cup \{i\}, S \cup \{j\}), (T \cup \{j\}, T \cup \{i\})\} \subset \succsim \cap \succsim'$ in accordance with Axiom 6 (recall from Remark 1 that this requires $\Sigma_1 = \Sigma'_3$ and $\Sigma_2 = \Sigma'_2$). Then,

$$ S \in D_{ji}^1(\succsim), \quad T \in D_{ij}^2(\succsim) \Rightarrow jP_{CAT}^{\succsim \setminus B}i; $$

$$ S \in D_{ji}^3(\succsim'), \quad T \in D_{ij}^2(\succsim') \Rightarrow iP_{CAT}^{\succsim' \setminus B}j. $$

The previous example shows that $R_{CAT}$ does not satisfy Axiom 6 (CAT).

## 6.2 Independence of the axioms for lex-cel

We prove that Axioms 1 (Des), 4 (CA) and 7 (IWS) are independent.

**Desirability is not satisfied:** Take an arbitrary ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 \succ \dots \succ \Sigma_l$. For every player $i \in N$, take the $l$-dimensional vector $\theta^{\succsim}(i)$ defined for the lex-cel solution. Define the ranking $R_{SD}^{\succsim}$ such that $iI_{SD}^{\succsim}j$ if $\theta^{\succsim}(i) = \theta^{\succsim}(j)$ and $iP_{SD}^{\succsim}j$ if $\exists s : i_k = j_k, k = 1, \dots, s-1$ and $i_s < j_s$. By definition $R_{SD}$ does not satisfy Axiom 1 (Des), but, as the lex-cel ranking, this solution satisfies Axiom 7 (IWS). Moreover, the permutation $\pi$ in the definition of Axiom 4 (CA) does not change the entries of the vector $\theta^{\succsim}$, implying that $R_{SD}$ satisfies Axiom 4 (CA).

**Coalition anonymity is not satisfied:** Consider a solution $R_{CA}$ that coincides with $R_{le}^{\succsim}$ when, for a ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$, the lex-cel produces a total order. If there are $i, j$ with $\theta^{\succsim}(i) = \theta^{\succsim}(j) = (a_1, \dots, a_l)$, define $\hat{k}$ the first integer such
that $a_{\hat{k}} > 0$. Then $iP_{\tilde{C}A}^j$ if the largest subset $L_i$ containing $i$ in $\Sigma_{\hat{k}}$ contains more elements than the largest subset $L_j$ containing $j$ in $\Sigma_{\hat{k}}$ and $iI_{\tilde{C}A}^j$ if $|L_i| = |L_j|$. So, if $S \cup \{i\} \sim S \cup \{j\}$, $\forall S \in 2^{N\setminus\{i,j\}}$, then $|L_i| = |L_j|$, and $iI_{\tilde{C}A}^j$. Thus, $R_{CA}$ satisfies Axioms 1 (Des) and 7 (IWS). Axiom 4 (CA) is not satisfied because defining a permutation $\pi$ such that $|\pi(L_i)| < |L_j|$ the ranking between $i$ and $j$ is exchanged.

**Independence from the worst set is not satisfied:** Take an arbitrary ranking $\succeq \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 \succ \dots \succ \Sigma_{l+1}$ and, for every player $i \in N$, define the $l$-dimensional vector $\theta^{\succeq,+(i)} = (i_1^+, \dots, i_{l+1}^+)$ where $i_k^+ = i_k + i_{k+1}$ for all $k \in \{1, \dots, l\}$, and the vector $(i_1, \dots, i_k)$ coincides with the vector $\theta^{\succeq}(i)$ defined for the lex-cel solution. Define the ranking $R_{IW}^{\succeq}$ such that $iI_{IW}^{\succeq}j$ if $\theta^{\succeq,+(i)} = \theta^{\succeq,+(j)}$ and $iP_{IW}^{\succeq}j$ if $\exists s : i_k^+ = j_k^+, k = 1, \dots, s-1$ and $i_s^+ > j_s^+$.

Observe that if $\theta^{\succeq}(i) = \theta^{\succeq}(j)$ then $\theta^{\succeq,+(i)} = \theta^{\succeq,+(j)}$, whereas if $\theta^{\succeq}(i) \ge_L \theta^{\succeq}(j)$ then $\theta^{\succeq,+(i)} \ge_L \theta^{\succeq,+(j)}$ and Axiom 1 (Des) is satisfied. Finally, given a permutation $\pi$ and the associated coalitional ranking $\succeq^{\pi}$ as in the definition of Axiom 4 (CA), it holds that, as $\theta^{\succeq}(i) = \theta^{\succeq^{\pi}(i)}$, $\theta^{\succeq,+(i)} = \theta^{\succeq^{\pi,+(i)}}$ and Axiom 4 (CA) is satisfied. The solution $R_{IW}$ does not satisfy Axiom 7 (IWS) because in the definition of $i_l^+$ last equivalence class plays a role and taking two different partitions of $\Sigma_{l+1}$ the values of $i_l^+$ and $j_l^+$ can be increased or decreased.

## 6.3 Independence of the axioms for $L^{(1)}$

We prove that Axioms 1 (Des), 5 (PCA), 7 (IWS), 9 (k-DD) and 10 (CI) are independent.

**Desirability is not satisfied:** Take an arbitrary ranking $\succeq \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 \succ \dots \succ \Sigma_l$. Consider a solution $R_{SD}$ that coincides with $R_{L^{(1)}}$ when, for a coalitional ranking $\succeq$ and players $i, j \in N$, it does not hold that $M_{\tilde{s}k}^{\succeq,i} \ge M_{\tilde{s}k}^{\succeq,j}$, for all $s \in \{1, \dots, n\}$ and $k \in \{1, \dots, l\}$. If $M_{\tilde{s}k}^{\succeq,i} = M_{\tilde{s}k}^{\succeq,j}$, for all $s, k$, then $iI_{SD}^{\succeq}j$. Otherwise, let $\hat{s}$ and $\hat{k}$ be the minimum indices such that $M_{\tilde{s}\hat{k}}^{\succeq,i} > M_{\tilde{s}\hat{k}}^{\succeq,j}$ then $j P_{SD}^{\succeq}i$. By definition, $R_{SD}$ does not satisfy Axiom 1 (Des), but, as the $L^{(1)}$ solution, it satisfies Axioms 7 (IWS), 5 (PCA) and 9 (k-DD). Axiom 10 (CI) is satisfied by $R_{SD}$ because by adding a subset of coalitions from the last equivalence class to the second-last equivalence class or to the union of the first $l-1$ equivalence classes the relative ranking between $i$ and $j$ does not change.

**Independence from the worst set is not satisfied:** Take an arbitrary ranking $\succeq \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 \succ \dots \succ \Sigma_{l+1}$. For each $i \in N$, define a new matrix $M^{\succeq,+,i}$ such that

$$M_{s,k}^{\succeq,+,i} = M_{s,k}^{\succeq,i} + M_{s,k+1}^{\succeq,i}, \text{ if } s \in \{1, \dots, n\}, k \in \{1, \dots, l\},$$
where $M^{\tilde{\sim},i}$ is the matrix defined for the $L^{(1)}$ solution. Consider a solution $R_{L^{(1)},+}^{\tilde{\sim}}$, defined as $R_{L^{(1)}}^{\tilde{\sim}}$, but taking $M^{\tilde{\sim},+i}$ instead of $M^{\tilde{\sim},i}$. Observe that, if $M_{s,k}^{\tilde{\sim},i} = M_{s,k}^{\tilde{\sim},j}$, then $M_{s,k}^{\tilde{\sim},+i} = M_{s,k}^{\tilde{\sim},+j}$; otherwise, if $M_{s,k}^{\tilde{\sim},i} \ge M_{s,k}^{\tilde{\sim},j}$ then $M_{s,k}^{\tilde{\sim},+i} \ge M_{s,k}^{\tilde{\sim},+j}$ and Axioms 1 (Des) and 9 (k-DD) are satisfied. Given a permutation $\pi$ and the associated coalitional ranking $\tilde{\sim}^{\pi}$ as in the definition of Axiom 5 (PCA), it holds that if $M^{\tilde{\sim},i} = M^{\tilde{\sim},i}$, then $M^{\tilde{\sim},+i} = M^{\tilde{\sim},+i}$, and Axiom 5 (PCA) is satisfied. Given two rankings $\tilde{\sim}, \tilde{\sim}' \in \mathcal{R}(\mathcal{F}(N))$ such that $iI_{L^{(1)},+}^{\tilde{\sim},j}$ and $iI_{L^{(1)},+}^{\tilde{\sim}'},j$, then $M^{\tilde{\sim},+i} = M^{\tilde{\sim},+j}$ and $M^{\tilde{\sim}',+i} = M^{\tilde{\sim}',+j}$. Axiom 10 (CI) is satisfied because the values of $M^{\tilde{\sim},+i}$ and $M^{\tilde{\sim}',+j}$ are not modified by a change, consistent with the definition of the axiom, in the last equivalence class. The solution $R_{IW}$ does not satisfy Axiom 7 (IWS) because in the definition of $M_{s,l}^{\tilde{\sim},+i}$, the last equivalence class plays a role and taking two different partitions of $\Sigma_{l+1}$ the values of $M_{s,l}^{\tilde{\sim},+i}$ and $M_{s,l}^{\tilde{\sim}',+j}$ can be increased or decreased.

**k-desirability on a dichotomous ranking is not satisfied:** Take an arbitrary ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 > \dots > \Sigma_l$. For every player $i \in N$, take the matrix $M^{\tilde{\sim},i}$ defined for the $L^{(1)}$ solution. Define the ranking $R_{kD}^{\tilde{\sim}}$ such that

$$M^{\tilde{\sim},i} = M^{\tilde{\sim},j} \Rightarrow iI_{kD}^{\tilde{\sim},j}$$

and

$$\exists \hat{s} \in \{1, \dots, n\} \text{ and } \hat{k} \in \{1, \dots, l-1\} \text{ such that}$$

$$i P_{kD}^{\tilde{\sim}} j \iff \left\{ \begin{array}{l} M_{\hat{s}k}^{\tilde{\sim},i} = M_{\hat{s}k}^{\tilde{\sim},j}, \forall s \in \{1, \dots, n\}, \forall k \in \{1, \dots, \hat{k}-1\}; \\ M_{\hat{s}\hat{k}}^{\tilde{\sim},i} = M_{\hat{s}\hat{k}}^{\tilde{\sim},j}, \forall s \in \{\hat{s}+1, \dots, n\}; \\ M_{\hat{s}\hat{k}}^{\tilde{\sim},i} > M_{\hat{s}\hat{k}}^{\tilde{\sim},j}. \end{array} \right.$$

This solution satisfies, by definition, Axiom 1 (Des) because if $S \cup \{i\} \supseteq S \cup \{j\}$, $\forall S \in 2^{N\setminus\{i,j\}}$, then $M_{\hat{s}k}^{\tilde{\sim},i} \ge M_{\hat{s}k}^{\tilde{\sim},j}$ for all indices $s$ and $k$. Axioms 7 (IWS) and 5 (PCA) are satisfied because the ranking does not depend on the equivalence classes $\Sigma_k$, with $k > \hat{k}$, and because the values of the matrices $M^{\tilde{\sim},i}$ and $M^{\tilde{\sim},j}$ do not change with a size invariant permutation $\pi$. The solution $R_{kD}$ satisfies Axiom 10 (CI) because in new rankings $\tilde{\sim}', \tilde{\sim}''$, the values of the matrices $M^{\tilde{\sim},i}$, $M^{\tilde{\sim},j}$ and $M^{\tilde{\sim}',i}$, $M^{\tilde{\sim}',j}$ are modified by the same quantity. However, if $M_{\hat{s}k}^{\tilde{\sim},i} < M_{\hat{s}k}^{\tilde{\sim},j}$ for some $s < \hat{s}$, $iP_{kD}^{\tilde{\sim}}j$ stays the same, contradicting what is required by Axiom 9 (k-DD).

**Per-size Coalitional Anonymity is not satisfied:** Take an arbitrary ranking $\tilde{\sim} \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 > \dots > \Sigma_l$. For each player $i \in N$, define the set $E_i^k = \{j \in N \setminus \{i\} : \{i, j\} \in \Sigma_k\}$. Take a solution $R_{PCA}$ that coincides with $R_{L^{(1)}}^{\tilde{\sim}}$ when the $L^{(1)}$ solution produces a total order. Given two players $i, j \in N$ such that $iI_{L^{(1)}}^{\tilde{\sim},j}$, let $\hat{k}$ be the first index such that, if $\min\{E_i^k\} \ne \min\{E_j^k\}$, then $iP_{PCA}^{\tilde{\sim}}j$ if and only if $\min\{E_i^k\} < \min\{E_j^k\}$ and $iI_{PCA}^{\tilde{\sim}}j$, otherwise. By definition,
<table><caption>**Table 1** Properties (on the rows) satisfied (✓) or not (✗) by each solution (on the columns). Notation + highlights sets of properties used in this work to axiomatically characterize the corresponding solutions on each column.</caption><thead><tr><th></th><th>CP-majority</th><th>lex-cel</th><th>dual-lex</th><th>L<sup>(1)</sup></th><th>L<sub>*</sub><sup>(1)</sup></th></tr></thead><tbody><tr><td>Des</td><td>✓+</td><td>✓+</td><td>✓+</td><td>✓+</td><td>✓+</td></tr><tr><td>Neu</td><td>✓+</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>CAT</td><td>✓+</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>EC</td><td>✓+</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>CA</td><td>✗</td><td>✓+</td><td>✓+</td><td>✗</td><td>✗</td></tr><tr><td>IWS</td><td>✗</td><td>✓+</td><td>✗</td><td>✓+</td><td>✗</td></tr><tr><td>IBS</td><td>✗</td><td>✗</td><td>✓+</td><td>✗</td><td>✓+</td></tr><tr><td>k-DD</td><td>✗</td><td>✗</td><td>✗</td><td>✓+</td><td>✓+</td></tr><tr><td>PCA</td><td>✗</td><td>✓</td><td>✓</td><td>✓+</td><td>✓+</td></tr><tr><td>CI</td><td>✗</td><td>✓</td><td>✓</td><td>✓+</td><td>✓+</td></tr></tbody></table>

this solution satisfies Axioms 1 (Des) and 9 (k-DD), but not 5 (PCA). Observe that, when $L^{(1)}$ does not apply, only the equivalence class $\Sigma_k$ is involved to determine the ranking of players, then Axiom 7 (IWS) is satisfied. The solution $R_{PCA}$ satisfies Axiom 10 (CI) because if $iI_{PCA}^\sim j$ then $\min\{E_i^k\} = \min\{E_j^k\}$, for every $k$, then adding a subset of coalitions from the last equivalence class to the second-last equivalence class or to the union of the first $l-1$ equivalence classes the relative ranking between $i$ and $j$ does not change.

**Consistency after indifference is not satisfied:** Take an arbitrary ranking $\sim \in \mathcal{R}(\mathcal{F}(N))$ with associated quotient order $\Sigma_1 \succ \dots \succ \Sigma_l$. Consider a solution $R_{CI}$ that coincides with $R_{L^{(1)}}^\sim$ when the $L^{(1)}$ solution produces a total order. Denote by $i_k^{\min}$ the number of sets in $\Sigma_k$ containing $i$ with minimal cardinality, that is,
$$i_k^{\min} = |\{S \in \Sigma_k : i \in S, |S| < |G|, \text{ where } i \in G \in \Sigma_k\}|$$

for $k = 1, \dots, l$. Let $\theta_{\min}^{\sim}(i)$ be the $l$-dimensional vector $\theta^{\sim}(i) = (i_1^{\min}, \dots, i_l^{\min})$ associated with $\sim$. Take two players $i, j \in N$ such that $iI_{L^{(1)}}^\sim j$. Then
if $\theta_{\min}^{\sim}(i) \ge L \theta_{\min}^{\sim}(j)$, then $iP_{CI}^\sim j$;
otherwise $iI_{CI}^\sim j$.

This solution satisfies, by definition, Axioms 1 (Des), 7 (IWS) and 9 (k-DD). Moreover, the vector $\theta_{\min}^{\sim}$ depends only on the number of coalitions of minimal cardinality containing a player, and therefore the Axiom 5 (PCA) is satisfied. The solution $R_{CI}$ does not satisfy Axiom 10 (CI) because a minimal set in the second equivalence class of a ranking could be not minimal in the union of the last $l-1$ equivalence classes.

Table 1 summarizes which axioms are satisfied by each solution studied in this paper. Additional axiomatic analysis of social ranking solutions and their properties can be found in Section A.2 of the Appendix.
# 7 Final remarks

In this paper, we have presented an axiomatic analysis of five solutions from the literature: CP-majority [5], lex-cel (and its dual) [4], and the $L^{(1)}$ solution (and its dual) [15] with the objective to highlight the role of the property of Desirability (a key focus of this study at the crossroad between social choice and coalitional games [7–9]) as a common basis in their axiomatic foundations. By analyzing the axioms that complete each axiomatic characterization alongside Desirability, our findings provide a deeper understanding of how these solutions evaluate the relevance of players in situations where coalition outcomes are measured on an ordinal scale.

Overall, our analysis shows that the CP-majority, lex-cel, and $L^{(1)}$ solution, in this order, exhibit increasing levels of sensitivity when considering the position and structure of coalitions through the coalitional ranking. This conclusion, derived from the interpretation of the axioms, broadly aligns with the results obtained from the case study in Section A.1. In fact, the ranking provided by the CP-majority aligns identically with the one of the Shapley value, which is essentially based on an average marginal contribution to coalitions’ values and is only weakly correlated with the ordinal position of coalitions. Instead, the differences are more pronounced between lex-cel and the Shapley value, and even more so between $L^{(1)}$ and the Shapley value, particularly for players who occur in the lowest positions of a coalitional ranking. In view of these evidences, our main suggestion for guiding the selection of the most suitable solution would be the gradient of importance that the ordinal position of coalitions and their structure should hold, ranging from CP-majority (low level) to lex-cel (intermediate level) and finally the $L^{(1)}$ solution (high level), when the reward of excellence is the primary criterion for measuring the relevance of players (to punish their mediocrity, consider the dual version of lex-cel and $L^{(1)}$, in this same order).

As a future research direction, we believe it would be highly beneficial to characterize the family of solutions that satisfy Desirability. Additionally, an open question remains regarding which set of independent axioms should be imposed to ensure that each total binary relation in the image of a solution is also transitive, as it is the case for lex-cel and $L^{(1)}$, but not for CP-majority, in general.

Another promising direction is related to the models in [23] and [24], where the authors axiomatically characterize a class of power indices for effectivity functions. In this framework, it is natural to consider an extension of the property of desirability: if a player *i* forms coalitions that are effective for larger sets of alternatives with respect to coalitions formed by replacing *i* with a player *j*, it is natural to assign to *i* more power than *j*. So, it would be interesting to understand in which terms a desirability property could replace the monotonicity property used in the axiomatic analysis in [23] and [24]. Moreover, since effectivity functions can be connected to simple games, it would be valuable to explore a natural generalization of this framework aimed at connecting it to coalitional rankings using effectivity functions on families of alternatives, as to study a more general concept of solutions for the social ranking problem.

# Acknowledgements

The authors gratefully acknowledge the anonymous reviewers for their careful reading and useful comments and suggestions that allowed us to improve the paper.
# A Appendix

## A.1 Case study

The States General of the Netherlands is the supreme bicameral legislature of the Netherlands. The House of Representatives (Tweede Kamer) consists of 150 members. They have the ability to propose and to revise a bill. If a majority votes in favor of a proposed bill, it is moved to the 75 members of the Senate (Eerste Kamer), who only get to vote on the bill. If a majority of the Senate votes in favor, the bill is passed to law.

The distribution of votes between each party in each house is shown in Table 2, with $w_i^l$ and $w_i^u$ corresponding to the number of votes each party $i$ has in the House of Representatives (Lower House) and the Senate (Upper House), respectively.

To assess the power of individual parties based on their contribution to coalitions, the authors in [1] have considered the Shapley value [25] of a three-valued simple game, which aims to incorporate the asymmetric structure of the vote distribution. Their value function of the three-valued simple game assigns value 2 to coalitions that are able to pass a legislation in both the House of Representatives and the Senate, 1 to coalitions that only pass the House of Representatives, and 0 to all remaining coalitions.

As argued in Example 1, quantifying the utility of a certain outcome could appear rather arbitrary. Since merely the relative power between parties is of interest, we may also consider only the relative power between coalitions.

Let $N$ be the set of 17 parties in the States General of the Netherlands. Consider a coalitional ranking $\succsim \in \mathcal{R}(\mathcal{F}(N))$ consisting of three equivalence classes.

$$ \Sigma_1 = \{S \in \mathcal{F}(N) : \sum_{i \in S} w_i^l \geq 76 \text{ and } \sum_{i \in S} w_i^u \geq 38\}, $$

$$ \Sigma_2 = \{S \in \mathcal{F}(N) : \sum_{i \in S} w_i^l \geq 76 \text{ and } \sum_{i \in S} w_i^u < 38\}, $$

$$ \Sigma_3 = \mathcal{F}(N) \setminus (\Sigma_1 \cup \Sigma_2). $$

Given the distribution of all coalitions between these three equivalence classes, Table 2 shows the resulting ranking of each solution introduced in previous sections, along with the ranking produced in [1]. The source code to arrive at these rankings is shown in Listing 1 below.

From the evaluation, we observe some minor but notable distinctions in how different solutions prioritize the influence of parties in the bicameral system. Specifically, both the lex-cel and $L^{(1)}$ solutions exhibit a marked preference for parties with stronger representation in the Senate. This preference is especially evident when comparing the rankings of the parties Van Vliet and OSF. Despite Van Vliet having a solitary vote in the House of Representatives and OSF having one in the Senate, both the lex-cel and $L^{(1)}$ solutions assign a higher rank to OSF, diverging from the ranking provided by the CP-majority.

Delving deeper, we find that, as expected from its definition, $L^{(1)}$ solution exhibits a more pronounced bias towards smaller coalitions in the Senate compared to lex-cel. When compared to the party GrKO, which holds twice as many votes in the House
<table><caption>**Table 2** Party votes and rankings according to the lex-cel, $L^{(1)}$, CP and the ranking $R_{Sh}$ is obtained by the Shapley value of the corresponding three-valued simple game [1].</caption><thead><tr><th></th><th>w<sub>i</sub><sup>l</sup></th><th>w<sub>i</sub><sup>u</sup></th><th>R<sub>lc</sub></th><th>R<sub>L(1)</sub></th><th>R<sub>CP</sub></th><th>R<sub>Sh</sub></th></tr></thead><tbody><tr><td>VVD</td><td>40</td><td>13</td><td>1.</td><td>1.</td><td>1.</td><td>1.</td></tr><tr><td>PvdA</td><td>36</td><td>8</td><td>2.</td><td>2.</td><td>2.</td><td>2.</td></tr><tr><td>SB</td><td>15</td><td>9</td><td>4.</td><td>4.</td><td>3.</td><td>3.</td></tr><tr><td>CDA</td><td>13</td><td>12</td><td>3.</td><td>3.</td><td>4.</td><td>4.</td></tr><tr><td>D66</td><td>12</td><td>10</td><td>5.</td><td>5.</td><td>5.</td><td>5.</td></tr><tr><td>PVV</td><td>12</td><td>9</td><td>6.</td><td>6.</td><td>6.</td><td>6.</td></tr><tr><td>CU</td><td>5</td><td>3</td><td>8.</td><td>8.</td><td>7.</td><td>7.</td></tr><tr><td>GL</td><td>4</td><td>4</td><td>7.</td><td>7.</td><td>8.</td><td>8.</td></tr><tr><td>SGP</td><td>3</td><td>2</td><td>9.</td><td>9.</td><td>9.</td><td>9.</td></tr><tr><td>PvdD</td><td>2</td><td>2</td><td>10.</td><td>10.</td><td>10.</td><td>10.</td></tr><tr><td>GrKO</td><td>2</td><td>0</td><td>12.</td><td>13.</td><td>12.</td><td>12.</td></tr><tr><td>GrBvK</td><td>2</td><td>0</td><td>12.</td><td>13.</td><td>12.</td><td>12.</td></tr><tr><td>50PLUS</td><td>1</td><td>2</td><td>11.</td><td>11.</td><td>11.</td><td>11.</td></tr><tr><td>Houwers</td><td>1</td><td>0</td><td>15.</td><td>15.</td><td>14.</td><td>14.</td></tr><tr><td>Klein</td><td>1</td><td>0</td><td>15.</td><td>15.</td><td>14.</td><td>14.</td></tr><tr><td>Van Vliet</td><td>1</td><td>0</td><td>15.</td><td>15.</td><td>14.</td><td>14.</td></tr><tr><td>OSF</td><td>0</td><td>1</td><td>14.</td><td>12.</td><td>17.</td><td>17.</td></tr></tbody></table>

of Representatives as Van Vliet, $L^{(1)}$ solution continues to favor OSF, unlike lex-cel, which prefers GrKO. The lex-cel vectors and $L^{(1)}$ matrices for these two parties in (13) and (14) show that this ranking difference stems from the small difference in how many winning coalitions of size five OSF can participate in, namely $M_{5,1}^{\tilde{\gamma}, \text{OSF}} = 13$ over the 12 by GrKO. In this context, we could argue that, since a bill is only passed if approved by both houses, and smaller coalitions are generally easier to form than bigger ones, the ranking according to $L^{(1)}$ solution is an appropriate choice to highlight the influence of parties with a higher representation in the Senate.

$$ \theta^{\tilde{\gamma}}(\text{GrKO}) = (28838, 4442, 32256) \qquad \theta^{\tilde{\gamma}}(\text{OSF}) = (28747, 3517, 33272) \qquad (13) $$

$$ M^{\tilde{\gamma}, \text{GrKO}} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 16 \\ 0 & 1 & 119 \\ 0 & 14 & 546 \\ \mathbf{12} & 86 & 1722 \\ 161 & 307 & 3900 \\ 910 & 696 & 6402 \\ \vdots & \vdots & \vdots \\ 1 & 0 & 0 \end{pmatrix} \qquad M^{\tilde{\gamma}, \text{OSF}} = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 16 \\ 0 & 1 & 119 \\ 0 & 14 & 546 \\ \mathbf{13} & 84 & 1723 \\ 159 & 284 & 3925 \\ 886 & 581 & 6541 \\ \vdots & \vdots & \vdots \\ 1 & 0 & 0 \end{pmatrix} \qquad (14) $$

Lastly, the CP-majority relation produces a transitive relation which is remarkably identical to the Shapley value ranking as computed in [1]. As demonstrated in Example 3, we can construct a matrix displaying the CP-comparisons for each party. Here,
we focus on the three parties GrKO, Van Vliet and OSF, which produce a different ranking in all three analyzed ranking methods.

<table><thead><tr><th>i \ j</th><th>GrKO</th><th>Van Vliet</th><th>OSF</th></tr></thead><tbody><tr><td>GrKO</td><td>0</td><td>512</td><td>1016</td></tr><tr><td>Van Vliet</td><td>0</td><td>0</td><td>504</td></tr><tr><td>OSF</td><td>405</td><td>437</td><td>0</td></tr></tbody></table>

For the computational tasks, the code predominantly leverages base R functionalities. However, for specialized operations, we employ the socialranking package [26], which provides essential functions like createPowerset() for generating the power set $2^N$ of all possible coalitions and doRanking() to determine the ranking in this legislative context. It should be noted that the package also incorporates the lex-cel, $L^{(1)}$, and CP-majority solution functions.

<caption>Listing 1 Applying the solutions to the States General in the Netherlands</caption>

```r
library(socialranking)

weights <- matrix(
  c(
    40, 36, 15, 13, 12, 12, 5, 4, 3, 2, 2, 2, 1, 1, 1, 1, 0,
    13, 8, 9, 12, 10, 9, 3, 4, 2, 2, 0, 0, 2, 0, 0, 0, 1
  ) |> asoadj(
    ncol = 2,
    dimnames = list(
      c('VVD', 'PvdA', 'SP', 'CDA', 'D66', 'PVV', 'CU', 'GL', 'SGP',
        'PvdD', 'GrKO', 'GrBvK', '50PLUS', 'Houwers', 'Klein', 'Van
        Vliet', 'OSF'),
      c('House 1', 'House 2')
    )
  )
)

powerset <- createPowerset(1:nrow weights)

# 2^n x 2 matrix (two columns for house 1 and house 2 weights)
coalitionWeights <- sapply(powerset,
  function(coalition) apply( weights[coalition,,drop=FALSE] , 2, sum)
)

qs <- apply( weights, 2, sum) %/% 2 + 1

determineEqCl <- function(votes) {
  if(votes['House 1'] < qs['House 1']) 3 else
  if(votes['House 2'] < qs['House 2']) 2 else 1
}

# Lexcel
lexMatrix <- matrix(0, ncol=ncol( weights )+1, nrow=nrow( weights ))
dimnames( lexMatrix ) <-
  list( rownames( weights ), paste0('E', 0:ncol( weights )+1))
for(i in 1:length( powerset )) {
```
```
eqcl <- determineEqCl(coalitionWeights[,i])
lexMatrix[powerset[[i]], eqcl] <- lexMatrix[powerset[[i]], eqcl] + 1
}
(lexRank <- lapply(1:nrow(lexMatrix), function(i) lexMatrix[i,])
  |> structure(class='LexcelScores', names=rownames(weights))
  |> doRanking()
)

# L1
l1Matrix <- array(0, c(nrow(weights), nrow(weights), ncolableres+1))
dimnames(l1Matrix) <- list(rownames(weights), 1:nrow(weights),
  paste0('E', 0:ncolableres+1))
for(i in 1:length(powerset)) {
  coal <- powerset[[i]]
  eqcl <- determineEqCl(coalitionWeights[,i])
  l1Matrix[coal, length(coal), eqcl] <-
    l1Matrix[coal, length(coal), eqcl] + 1
}
(l1Rank <- lapply(1:nrowableres), function(i) l1Matrix[i,,])
|> structure(class='L1Scores', names=rownamesableres))
|> doRanking()
)

# CP
cpMatrix <- structure(matrix(0, nrow=nrowableres),
  ncol=nrowableres), dimnames=list(rownamesableres),
  rownamesableres)))
for(i in 1:(nrowableres)-1)) {
  for(j in (i+1):nrowableres)) {
    Uij <- createPowerset(setdiff(1:nrowableres), c(i,j)))
    eq_ij <- sapply(Uij,
      function(S) c(applyableres[c(S,i),,drop=FALSE], 2, sum))
    ) |> apply(2, determineEqCl)
    eq_ji <- sapply(Uij,
      function(S) c(applyableres[c(S,j),,drop=FALSE], 2, sum))
    ) |> apply(2, determineEqCl)
    d_ij <- sum(eq_ij < eq_ji)
    d_ji <- sum(eq_ji < eq_ji)
    cpMatrix[i,j] <- d_ij
    cpMatrix[j,i] <- d_ji
  }
}
```

## A.2 Further axiomatic analysis

*Proposition 7. The following statements hold true:*
(i) lex-cel, dual-lex, $L^{(1)}$ solution and $L_*^{(1)}$ solution satisfy Axiom 2 (Neu);

(ii) dual-lex and $L_*^{(1)}$ solution do not satisfy Axiom 3 (EC);

(iii) lex-cel, dual-lex, $L^{(1)}$ solution and $L_*^{(1)}$ solution satisfy Axiom 6 (CAT);

(iv) $L^{(1)}$ solution and $L_*^{(1)}$ solution do not satisfy Axiom 4 (CA);

(v) CP-majority, dual-lex and $L_*^{(1)}$ solution do not satisfy Axiom 7 (IWS);

(vi) CP-majority, lex-cel and $L^{(1)}$ solution do not satisfy Axiom 8 (IWS);

(vii) CP-majority, lex-cel and dual-lex do not satisfy Axiom 9 (k-DD);

(viii) CP-majority, does not satisfy Axiom 10 (CI);

(ix) lex-cel and dual-lex both satisfy Axiom 10 (CI);

**Proof** Proof of statement (i)

The proof is straightforward and can also be found in [4], for lex-cel and dual-lex, and in [15], for $L^{(1)}$ solution and $L_*^{(1)}$ solution.

**Proof of statement (ii)**

Use the same example of the proof of statements (ii) and (iii) of Proposition 6 showing that neither dual-lex nor $L^{(1)}$ solution satisfies EC.

**Proof of statement (iii)**

We prove that lex-cel satisfies CAT.

First, recall that in the CAT statement, removing the same set $B \subseteq \tilde{\gamma} \cap \tilde{\gamma}'$ from $\tilde{\gamma}$ and $\tilde{\gamma}'$ such that $\tilde{\gamma} \setminus B$ and $\tilde{\gamma}' \setminus B$ remain total preorders means that we remove from $\tilde{\gamma}$ and $\tilde{\gamma}'$ some pairs $(S, T) \in \tilde{\gamma} \cap \tilde{\gamma}'$ such that there exists a corresponding equivalence class for each quotient order $\Sigma$ with $S, T \in \Sigma$ in both quotient orders of $\succ$ and $\succ'$. So, for any $(S, T) \in B$, an equivalence class $\Sigma$ must exist such that (see Remark 1)

$$ \Sigma_1 \succ \dots \succ \Sigma \succ \dots \succ \Sigma_l, $$

and

$$ \Sigma'_1 \succ' \dots \succ \Sigma \succ' \dots \succ' \Sigma'_m, $$

such that, after the removal of $(S, T) \in B$, two quotient orders are obtained: $\succ = \succ \setminus B$ and $\succ' = \succ' \setminus B$, where

$$ \Sigma_1 \succ \dots \succ \Sigma \setminus \Omega \succ \Omega \succ \dots \succ \Sigma_l, $$

and

$$ \Sigma'_1 \succ' \dots \succ' \Sigma \setminus \Omega \succ' \Omega \succ' \dots \succ' \Sigma'_m, $$

with $S \in \Omega$ and $T \in \Sigma \setminus \Omega$. If $i, j \in N$ are such that $iR\tilde{\gamma}e^j$ and $jR\tilde{\gamma}e^i$, then $\theta\tilde{\gamma}(i) = \theta\tilde{\gamma}(j)$ and $\theta\tilde{\gamma}'(i) = \theta\tilde{\gamma}'(j)$. Now, after $B$ is removed, two cases may arise: case (1) each $\Sigma \setminus \Omega$ and $\Omega$, as above, have the same number of coalitions containing $i$ or $j$, and then $\theta\tilde{\gamma}(i) = \theta\tilde{\gamma}(j)$ and $\theta\tilde{\gamma}'(i) = \theta\tilde{\gamma}'(j)$; case (2) $\Sigma \setminus \Omega$ and $\Omega$ contain a different number of coalitions containing $i$ or $j$, but in this case the highest equivalence class $\Sigma \setminus \Omega$ showing a different number of coalitions for $i$ and $j$ will be the same in both $\succ$ and $\succ'$, so $\theta\tilde{\gamma}(i) >_L \theta\tilde{\gamma}(j) \Leftrightarrow \theta\tilde{\gamma}'(i) >_L \theta\tilde{\gamma}'(j)$. In both cases (1) and (2), it holds that $iR\tilde{\gamma}e^j \Leftrightarrow R\tilde{\gamma}e^i$, which is precisely what is demanded by CAT.

The proof that dual-lex, $L^{(1)}$ solution and $L_*^{(1)}$ solution satisfy CAT follows similar lines and it is left to the reader.
### Proof of statement (iv)

Use the same example of the proof of statement (ii) of Proposition 6 showing that neither CP-majority, $L^{(1)}$ solution nor $L_{*}^{(1)}$ solution satisfy CA.

### Proof of statement (v)

It is obvious that CP-majority does not satisfy IWS. To see that dual-lex does not satisfy IWS, see Section 6 in [4]. The proof that neither $L_{*}^{(1)}$ solution satisfies IWS follows a similar path.

### Proof of statement (vi)

Similar to case (v).

### Proof of statement (vii)

Consider a coalitional ranking $\preceq \in \mathcal{R}(\mathcal{F}(N))$ such that

$$i \sim jk \sim jl \succ j \sim ik \sim il \succ C,$$

where $C$ is an equivalence class containing all the other coalitions not previously shown. It holds that $iP_1^{\sim}j$ and $jP_2^{\sim}i$, while $iI_k^{\sim}j$ for all the other $k$. So, a solution satisfying $k$-DD should rank $i$ strictly more relevant than $j$. It is easy to check that on $\succeq$ CP-majority, lex-cel and dual-lex all rank $j$ strictly more relevant than $i$.

### Proof of statement (viii)

Consider a coalitional ranking $\preceq \in \mathcal{R}(\mathcal{F}(N))$ such that

$$jk \sim jl \succ ik \sim il \sim i \sim ikl \succ C,$$

where $C$ is an equivalence class containing all the other coalitions not previously shown.

One can verify that the CP-majority is such that $iI_{CP}^{\sim}j$. Now, consider two new coalitional rankings $\preceq'$ and $\preceq''$ such that

$$jk \sim jl \succ' ik \sim' il \sim' i \sim' ikl \sim' j \succ C \setminus j,$$

and

$$jk \sim'' jl \sim'' ik \sim'' il \sim'' i \sim'' ikl \sim'' j \succ C \setminus j,$$

where, following the notation of Axiom 10 (CI), $\Sigma = \{j\}$. Notice that $jP_{CP}^{\sim'}i$ while $iP_{CP}^{\sim''}j$, contradicting what is demanded by CI. So the CP-majority does not satisfy CI.

### Proof of statement (ix)

The proof that lex-cel satisfies CI is similar to the proof that $L^{(1)}$ satisfies CI as in Theorem 4, and then it is omitted. Similar for dual-lex. $\square$

<figure><img src="image_2.png" /></figure>
References

[1] Musegaas, M., Borm, P., Quant, M.: Three-valued simple games. Theory and Decision **85**, 201–224 (2018)

[2] Freixas, J.: Banzhaf measures for games with several levels of approval in the input and output. Annals of Operations Research **137**(1), 45–66 (2005)

[3] Freixas, J.: The shapley–shubik power index for games with several levels of approval in the input and output. Decision Support Systems **39**(2), 185–195 (2005)

[4] Bernardi, G., Lucchetti, R., Moretti, S.: Ranking objects from a preference relation over their subsets. Social Choice and Welfare **52**(4), 589–606 (2019)

[5] Haret, A., Khani, H., Moretti, S., Ozturk, M.: Ceteris Paribus Majority for social ranking. In: 27th International Joint Conference on Artificial Intelligence (IJCAI-ECAI-18), Stockholm, Sweden, pp. 303–309 (2018)

[6] Maschler, M., Peleg, B.: A characterization, existence proof and dimension bounds for the kernel of a game. pacific Journal of Mathematics **18**(2), 289–328 (1966)

[7] Isbell, J.R.: A class of simple games. Duke Mathematical Journal **25**, 423–439 (1958)

[8] Taylor, A.D., Zwicker, W.: Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, JSTOR (1999)

[9] Carreras, F., Freixas, J.: Complete simple games. Mathematical Social Sciences **32**(2), 139–155 (1996)

[10] Taylor, A., Zwicker, W.: Weighted voting, multicameral representation, and power. Games and Economic Behavior **5**(1), 170–181 (1993)

[11] Freixas, J., Puente, M.A.: Dimension of complete simple games with minimum. European Journal of Operational Research **188**(2), 555–568 (2008)

[12] Diffo Lambo, L., Moulen, J.: Ordinal equivalence of power notions in voting games. Theory and Decision **53**, 313–325 (2002)

[13] Carreras, F., Freixas, J.: On ordinal equivalence of power measures given by regular semivalues. Mathematical Social Sciences **55**(2), 221–234 (2008)

[14] Courtin, S., Tchantcho, B.: A note on the ordinal equivalence of power indices in games with coalition structure. Theory and Decision **78**, 617–628 (2015)

[15] Algaba, E., Moretti, S., Rémila, E., Solal, P.: Lexicographic solutions for
coalitional rankings. Social Choice and Welfare **57**(4), 817-849 (2021)

[16] Suzuki, T., Horita, M.: Consistent social ranking solutions. Social Choice and Welfare **62**, 549-569 (2024)

[17] Suzuki, T., Horita, M.: Social ranking problem based on rankings of restricted coalitions. In: International Conference on Group Decision and Negotiation, pp. 55-67 (2021). Springer

[18] Allouche, T., Escoffier, B., Moretti, S., Ozturk, M.: Social ranking manipulability for the cp-majority, banzhaf and lexicographic excellence solutions. In: Bessiere, C. (ed.) 29th International Joint Conference on Artificial Intelligence (IJCAI-PRICAI-20), Yokohama, Japan, pp. 17-23 (2021)

[19] Holler, M.J., Nurmi, H.: Power, Voting, and Voting Power: 30 Years After. Springer, Berlin Heidelberg 1982 (2013)

[20] Aleandri, M., Dall'Aglio, M., Fragnelli, V., Moretti, S.: Minimal winning coalitions and orders of criticality. Annals of Operations Research **318**(2), 787-803 (2022)

[21] Aleandri, M., Fragnelli, V., Moretti, S.: In: Leroch, M.A., Rupp, F. (eds.) Lexicographic Ranking Based on Minimal Winning Coalitions, pp. 239-256. Springer, Cham (2023)

[22] Deegan, J., Packel, E.W.: A new index of power for simple n-person games. International Journal of Game Theory **7**, 113-123 (1978)

[23] Karos, D., Peters, H.: Indirect control and power in mutual control structures. Games and Economic Behavior **92**, 150-165 (2015)

[24] Karos, D., Peters, H.: Effectivity and power. Games and Economic Behavior **108**, 363-378 (2018)

[25] Shapley, L.S.: A value for n-person games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games II, pp. 307-317. Princeton University Press, Princeton (1953)

[26] Fritz, F., Staudacher, J., Stefano, M.: Socialranking: Social Ranking Solutions for Power Relations on Coalitions. (2024). R package version 1.2.0, Accessed: 2025-03-21. https://CRAN.R-project.org/package=socialranking