A Core-Partition Ranking Solution to Coalitional Ranking Problems

Abstract

A coalitional ranking problem is described by a weak order on the set of nonempty coalitions of a given agent set. A social ranking is a weak order on the set of agents. We consider social rankings that are consistent with stable/core partitions. A partition is stable if there is no coalition better ranked in the coalitional ranking than the rank of the cell of each of its members in the partition. The core-partition social ranking solution assigns to each coalitional ranking problem the set of social rankings such that there is a core-partition satisfying the following condition: a first agent gets a higher rank than a second agent if and only if the cell to which the first agent belongs is better ranked in the coalitional ranking than the cell to which the second agent belongs in the partition. We provide an axiomatic characterization of the core-partition social ranking and an algorithm to compute the associated social rankings.

1 Introduction

The coalitional ranking problem refers to the problem of finding an ordinal ranking over the set of agents (called social ranking), given an ordinal ranking over its power set (called coalitional ranking). Such problems and their social ranking solutions have been recently investigated by Khani et al. (2019), Bernardi et al. (2019), Algaba et al. (2021) and Béal et al. (2022). These studies consider single-valued solutions, that is, social ranking solutions that assign to each coalitional ranking of the considered domain a unique social ranking. In this article, we are interested in set-valued solutions, that is, social ranking solutions that assign to each coalitional ranking problem of the domain a set, possible empty, of social rankings.

A social ranking solution can be viewed either as the ordinal counterpart of a solution for cooperative games with transferable utility – where for each payoff vector, agents are ranked according to the payoff they receive for their participation in the game – or as the inverse of the well-known problem of ranking groups of objects from a ranking over the individual objects (see, e.g., Barberà et al. 2004).

We propose a set-valued social ranking solution derived from a no-blocking condition inherent to the concept of core in many social environments. Precisely, our solution is constructed from the idea that the population of agents can be socially organized into a partition. Given a coalitional ranking problem, a partition is blocked by a coalition if the latter has a strictly higher rank in the coalitional ranking than the cells of the partition to which its members belong. A partition that is not blocked by any coalition is a stable partition or a core-partition. Any partition induces a natural social ranking: an agent is better ranked than a second agent if the cell to which the first agent belongs is better ranked in the coalitional ranking than the cell to which the second agent belongs. A social ranking is a core-partition social ranking if it is induced by a core-partition. The Core-partition social ranking solution introduced in this article assigns to each coalitional ranking the set of all core-partition social rankings. In other words, each selected social ranking is induced by an organization of the population into a partition that cannot be blocked by any coalition.

We consider the domain of all coalitional ranking problems that can be constructed from any finite agent set, that is, a domain of coalitional ranking problems with a variable set of agents. The Core-partition social ranking solution is nonempty-valued on this domain.

Our main result is an axiomatic characterization of the Core-partition social ranking solution which invokes three axioms.

The first axiom is based on a specific expansion of the population of agents. So consider an initial coalitional ranking problem. Assume now that the population is expanded in such a way that the coalition of all newly added agents wins unanimous support: this coalition is the unique maximal coalition in the larger coalitional ranking, the relative ranking between any two original coalitions remains the same, and each other coalition with both new and original agents has an arbitrary ranking. Then, our axiom imposes that the solution set of this new coalitional ranking on a larger set of agents is computed from the solution set of the initial one by putting the set of newcomers at the top of each social ranking of this solution set. In a sense, if a set of newcomers wins unanimous support in a coalitional ranking, then they are socially top-ranked. This axiom both has the flavor of some consistency-type axioms (if one starts from the larger problem and if the coalition of top-ranked agents is removed from it) and of the so-called bracing lemma which also relates the solution sets before and after a similar population expansion. On these points, we refer to Thomson (2011) for more details.

The second axiom is an invariance axiom built from a monotonicity condition. Imagine that in a coalitional ranking problem two disjoint coalitions have the same rank and their union lies in their lower counter set, i.e., the union of these coalitions has a lower rank than their constituent. Hence, the two coalitions have no interest in merging. The axiom indicates that the solution set is invariant to any monotonic transformation of the coalitional ranking induced by an improvement of this union, provided that this union remains in the lower contour set of the two original coalitions. This axiom is reasonable because the (equal) individual performance of these two coalitions is always at least as good as that of their union.

The last axiom is based on a decomposition principle. It specifies the conditions under which the solution set of a coalitional ranking problem can be decomposed as the union of the solution sets of variants of this coalitional ranking when some specific top coalitions of the coalitional ranking are each promoted as the only top coalition, ceteris paribus. Such a decomposition is possible according to the axiom if the set of top coalitions is closed/stable by union of disjoint coalitions.

The rest of the article is organized as follows. Section 2 presents the connections between our model, other approaches to the coalitional ranking problems and other literatures. In particular, we explain what distinguish our approach from some results on hedonic games. Section 3 gives basic notation and definitions. Section 4 presents core-partitions and the core-partition social ranking solution and provides some of their properties. The axiomatic study is contained in Sect. 5. Section 6 proves that the three axioms invoked in our characterization are logically independent. Section 7 provides an intuitive algorithm which computes all core-partitions. Section 8 concludes.

2 Related Literature

On the coalitional ranking problem, Khani et al. (2019) introduce and axiomatically characterize a social ranking solution that is inspired from the Banzhaf index for cooperative voting games (Banzhaf 1964). Bernardi et al. (2019) and Algaba et al. (2021) study lexicographic solutions based on the idea that the most influential agents are those which belong to (small) coalitions ranked in the highest position in the coalitional ranking, and provide several axiomatic characterizations of these solutions. Béal et al. (2022) characterize two other lexicographic solutions: the resulting social rankings are computed from the individual performance of the agents, then, when this performance criterion does not allow to decide between two agents, a collective performance criterion is progressively applied to the coalitions of higher size. As we already underlined, the main differences with our approach are that these solutions are single-valued whereas we consider set-valued solutions and that our framework allows for a variable population of agents.

A coalitional ranking can also be seen as a specific hedonic game. In a hedonic game, each agent is endowed with a preference (a weak order) over the set of coalitions to which it can belong and a popular objective is to find core-partitions. In order to do so, a coalition blocks a partition if all its members prefer this coalition to their respective cell of the partition. A partition is stable if it cannot be blocked by any coalition. A coalitional ranking problem can be considered as a specific hedonic game in which the preferences of any pair of agents agree when they compare two coalitions containing these two agents. This property, introduced in Farrell and Scotchmer (1988),¹ is sufficient for the nonemptiness of the set of core-partitions. The core of a hedonic game has received much attention in the literature. For instance, Banerjee et al. (2001) relax the common ranking property. They introduce two properties of top coalitions, which are sufficient to ensure the nonemptiness of the core of a hedonic game. Iehlé (2007) provides a necessary and sufficient condition under which the core of a hedonic game is nonempty. This condition is based on a concept of pivotal balancedness. Karakaya and Klaus (2017) consider the domain of hedonic games with strict preferences. They offer, among other (im)possibilities results, an axiomatic characterization of the core on the subdomain of hedonic games with a nonempty core in terms on Maskin monotonocity and Coalitional unanimity. In this context, Maskin monotonocity indicates that if a partition is selected by the solution set at some hedonic game, then it is also selected at a hedonic game where this partition improved in the preference ranking of the agents, ceteris paribus. Coalitional unanimity requires that a coalition which is unanimously best for all its members is always part of a partition of the solution set. Even if the literature on hedonic games (with the common ranking property) and our work are build around the concept of core-partitions, the similarities end there. We do not axiomatize the set of core-partitions but the set of social rankings that are consistent with core-partitions in the sense explained in the introduction. As a consequence, even if some axioms from both literatures seem to have the same flavor, they do not deal with the same objects.

The frameworks of hedonic games with the common ranking property and coalitional ranking problems are merged into a new class of coalition formation games by Lucchetti et al. (2022). They focus on core-partitions in various settings in which the agents’ preferences over coalitions depend on both the coalitional ranking and the agents’ position according to a social ranking within each coalition. In one of these settings, these two criteria are used lexicographically: among two coalitions containing an agent, this agent prefers the first coalition to the second if the former is better ranked than the latter in the coalitional ranking or if the two coalitions have the same coalitional rank and the social ranking solution better ranks the agent when it is applied to the first coalition than to the second. In this setting, core-partitions may not exist. The authors provide algorithms which determine core-partitions when they exist.

The concept of preference-approval structure introduced by Brams and Sanver (2009) has some distant link with our approach. A preference-approval structure is a pair consisting of a social ranking over a finite set of alternatives and a subset of approved or acceptable alternatives such that any approved alternative should be ranked strictly higher than any disapproved alternative in the social ranking. A parallel with social rankings induced by partitions can be made as follows. Consider the bipartition that distinguishes the approved alternatives from the disapproved alternatives. If a coalitional ranking were to exist on all non-empty subsets of alternatives, then it would be reasonable to assume that the coalition of approved alternatives is better ranked than the coalition of disapproved alternatives. Then, the condition that any approved alternative should be ranked strictly higher than any disapproved alternative in the social ranking is exactly what our (core)-partition social ranking solution would impose from the aforementioned bipartition and the hypothetical coalitional ranking. Dong et al. (2021) axiomatize a distance function between preference-approval structures. This function is then used in a preference aggregation model where each agent is endowed with its own preference-approval structure.

Finally, the approach in Piccione and Razin (2009) also shares some similarities to ours. The authors investigate social rankings emerging from core-partitions associated with a coalitional ranking. Nonetheless, there are several differences between the two articles. Firstly, Piccione and Razin (2009) consider coalitional rankings which are strict total orders while we consider weak orders. Secondly, they impose a separability condition on their coalitional rankings: for four disjoints coalitions, if a first coalition is ranked higher that a second coalition and if a third coalition is ranked higher than a fourth coalition, then the union of the first and third coalition is ranked higher than the union of the second and fourth coalition. Contrary to this rather narrow class of coalitional rankings, we allow for all weak orders over the set of nonempty coalitions. Thirdly, the ranking induced by a partition used in Piccione and Razin (2009) is consistent with the ranking of the cells of the partition but they further decide between two agents belonging to the same cell by comparing the corresponding singletons. As a consequence, a social ranking in Piccione and Razin (2009) is always a strict total order on the population of agents while we allow for weak orders. Fourthly, the stability concept adopted by Piccione and Razin (2009) is based on a blocking condition that is weaker than the classical one, so that the set of their stable social rankings is larger than the set of core-partitions. The authors’ main results are a full description of the (nonempty) set of partitions that are stable under all the coalitional rankings in their specific class and an axiomatic characterization of this set.

3 Notation and Definitions

For any finite set A, denote by $\Omega _A$ the set of nonempty subsets of A and by $\mathcal{R}(A)$ the set of weak orders on A, i.e., the set of all reflexive, transitive and complete binary relations on A. Given a weak order $\succsim \in \mathcal{R}(A)$, if A is nonempty, $M(A,\succsim )$ represents its nonempty set of maximal/top elements, i.e., $M(A,\succsim )$ is the greatest/best equivalence class with respect to the quotient order. For any subset B of A, $\succsim _B$ stands for the restriction of $\succsim$ to the subset B, i.e.,

$$\begin{aligned} \forall x, y \in B, \quad x \succsim _B y \Longleftrightarrow x \succsim y. \end{aligned}$$

Let ${\mathbb {N}}$ be the universe of agents and ${\mathcal {F}}$ be the collection of all finite sets of ${\mathbb {N}}$. For any set of agents $N \in \mathcal{F}$, any element of $\Omega _N$ is a called a coalition. A coalitional ranking problem is a pair $(\Omega _N,\succsim )$ where $N \in \mathcal{F}$ is the agent set and $\succsim \in \mathcal{R}(\Omega _N)$ is the coalitional ranking. For two coalitions $S,T\in \Omega _N$, $S\succsim T$ means that S is at least as highly ranked as T in $\succsim$. The asymmetric and symmetric part of $\succsim$ are denoted by $\succ$ and $\sim$ respectively. For a coalitional ranking $\succsim \in \mathcal{R}(\Omega _N)$ and a coalition $S\in \Omega_N$, the lower contour set of $\succsim$ at S is the set

$$\begin{aligned} L(\succsim ,S)=\{T\in \Omega _N: S\succsim T\}. \end{aligned}$$

Denote by

$$\begin{aligned} \mathcal{R}_\Omega = \bigcup _{N \in \mathcal{F}} \mathcal{R}(\Omega _N), \end{aligned}$$

the domain of coalitional rankings. A social ranking on N is a weak order $\gtrdot$ in $\mathcal{R}(N)$. In a similar way as above, > denote the asymmetric part of $\gtrdot$ and $\cdot$ its symmetric part. Denote by

$$\begin{aligned} \mathcal{R}_{{\mathbb {N}}} = \bigcup _{N \in \mathcal{F}} \mathcal{R}(N) \end{aligned}$$

the set of social rankings that one can construct from any finite set of agents of ${\mathbb {N}}$.

For any coalitional ranking problem $(\Omega _N,\succsim ) \in \mathcal{R}_{\Omega }$ and any coalition $S\in \Omega _N$, the coalitional ranking subproblem induced by $(\Omega _N,\succsim ) \in \mathcal{R}_{\Omega }$ and S is the restricted coalitional ranking $\succsim _S$ to the set $\Omega _S$.

A social ranking (set-valued) solution is a correspondence $f: \mathcal{R}_\Omega \rightrightarrows \mathcal{R}_{{\mathbb {N}}}$ which assigns to each coalitional ranking problem $(\Omega _N,\succsim )\in \mathcal{R}_\Omega (N)$ a possibly empty set of social rankings $f(\Omega _N,\succsim ) \subseteq \mathcal{R}(N)$. If $N = \emptyset$, then $\Omega _N = \emptyset$ and $\mathcal{R}(N) = \mathcal{R}(\Omega _N) = \{\emptyset \}$. In such a case, one uses the convention that $f(\Omega _\emptyset , \emptyset ) = \{\emptyset \}$. The social ranking solution f is nonempty-valued on $\mathcal{R}_\Omega$ if it holds that $f(\Omega _N,\succsim ) \not = \emptyset$ for each $(\Omega _N,\succsim )\in \mathcal{R}_\Omega (N)$.

4 Core-Partitions and the Core-Partition Ranking Solution

Core partitions of a coalitional ranking problem

Given $N \in \mathcal{F}$, a partition on N is a set $P=\{P_1,\ldots ,P_k\}$ of mutually disjoint nonempty coalitions that covers N, i.e., P is such that

$$\begin{aligned} \bigcup _{q\in \{1,\ldots ,k\}}P_q =N\quad \text { and }\quad \forall q, r \in \{1, \ldots , k\}, \, q \not = r, \quad P_q\cap P_r = \emptyset . \end{aligned}$$

For a given agent $i\in N$ and a partition P, P(i) stands for the unique coalition/cell in P containing i. Denote by ${\mathcal {P}}(N)$ the set of partitions of N. For any two partitions $P = \{P_1, \ldots , P_{k}\}$ and $P' = \{P'_1, \ldots , P'_{k'}\}$ on N, $P'$ is coarser than P if, for each $P'_q \in P'$, there is a nonempty subset $A_q \subseteq \{1, \ldots , k\}$ such that

$$\begin{aligned} P'_q = \bigcup _{r \in A_q}P_r. \end{aligned}$$

Given a coalitional ranking problem $(\Omega _N,\succsim ) \in \mathcal{R}$ and a partition $P\in {\mathcal {P}}(N)$, one says that P is blocked by coalition $S\in \Omega _N$ if,

$$\begin{aligned} \forall i\in S, \quad S\succ P(i). \end{aligned}$$

In words, P is blocked by S if, for each agent in S, coalition S is ranked higher than the coalition/cell in P containing this agent. The interpretation is that if agents prefer to be assigned to the best possible coalitions, then each one prefers to be in S than in the cell that the partition assigns to each of them. In this sense, P is not stable. A partition P is a core-partition if it is stable, i.e., if it cannot be blocked by any nonempty coalition. Equivalently, P is a core-partition if, for each $S\in \Omega _N$, there is $i\in S$ such that $P(i)\succsim S$. Denote by $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )\subseteq \mathcal{P}(N)$ the set of core-partitions of the coalitional ranking problem $(\Omega _N,\succsim )$.

Example 1

Assume that $N = \{1, 2, 3, 4, 5\}$. Consider the coalitional ranking problem $(\Omega _N, \succsim )$ such that

$$\begin{aligned} \{1, 2\} \sim \{2, 3\} \succ \{4, 5\} \sim \{3, 4\} \succ N \sim \{2\} \sim \{3\} \succ \{1\} \succ S \sim T, \end{aligned}$$

for each other pair of coalitions $\{S, T\}$. This coalitional ranking admits five equivalence classes and

$$\begin{aligned} M(\Omega _N, \succsim ) = \bigl \{ \{1, 2\}, \{2, 3\} \bigr \}. \end{aligned}$$

Its set $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ of core-partitions contains three elements:

$$\begin{aligned} P = \bigl \{\{1, 2\}, \{4, 5\}, \{3\}\bigr \}, \quad P' = \bigl \{\{2, 3\}, \{4, 5\}, \{1\}\bigr \}, \quad P'' = \bigl \{\{1, 2\}, \{3, 4\}, \{5\} \bigr \}. \end{aligned}$$

Example 2

Let $N=\{1,2,\ldots , n\}$, and consider the coalitional ranking problem $(\Omega _N, \succsim )$ where coalitions are ranked according to the smallest index they contain:

$$\begin{aligned} \forall S, T, \in \Omega _N, \quad (S \succsim T) \Longleftrightarrow (\min (S) \le \min (T)). \end{aligned}$$

Hence S is ranked at the $\min (S)$-th equivalence class of $(\Omega _N, \succsim )$, where the best equivalence class contains all coalitions $S \ni 1$ and the worst equivalence class is the singleton $\{n\}$. For a nonempty coalition $T \subseteq N$, consider $i=\min (T)$. For any $S \ni i$, $S \succsim T$, from which one concludes that $\mathcal{C}\mathcal{P} (\Omega _N, \succsim ) =\mathcal{P}(N)$.

Remark 1

The notion of core-partition has been extensively used in coalition formation games. It is known that for $N \not = \emptyset$, $\mathcal{C}\mathcal{P}(\Omega _N,\succsim ) \not = \emptyset$ (see, e.g., Farrell and Scotchmer, 1988, Banerjee et al. 2001). The computation of $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ and the discussion on the nonemptiness of core partitions (already mentioned in the introduction) are postponed to section 7.

4.1 The Core-partition social ranking solution

Let us now establish a link between partitions and social rankings. Each coalitional ranking problem $(\Omega _N,\succsim ) \in \mathcal{R}_{\Omega }$ and each partition $P \in \mathcal{P}(N)$ induce a social ranking in $\mathcal{R}(N)$ denoted by $\gtrdot _{(\succsim ,P)}$ such that

$$\begin{aligned} \forall i, j \in N, \quad i\gtrdot _{(\succsim ,P)}j \Longleftrightarrow P(i)\succsim P(j). \end{aligned}$$

In words, the agents are ranked consistently with the rank of their cell. We are interested in social rankings that emerge from core-partitions. Formally, a core-partition social ranking for a coalitional ranking problem $(\Omega _N,\succsim ) \in \mathcal{R}_{\Omega }$ is a social ranking $\gtrdot \in \mathcal{R}(N)$ such that there is a core-partition $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ satisfying $\gtrdot =\gtrdot _{(\succsim ,P)}$. Denote by $\mathcal{CSR}$ the social ranking solution which assigns to each coalitional ranking problem $(\Omega _N,\succsim )$ the set of its core-partition social rankings $\mathcal{CSR}(\Omega _N, \succsim )$. By Remark 1, we know that $\mathcal{CSR}$ is nonempty-valued on $\mathcal{R}_{\Omega }.$

Example 3

Consider again Example 1. Using $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$, the set $\mathcal{CSR}(\Omega _N, \succsim )$ of core-partition social rankings is formed by the following social rankings:

$$\begin{aligned} 1 \cdot _{(\succsim , P)} 2>_{(\succsim , P)} 4 \cdot _{(\succsim , P)} 5>_{(\succsim , P)} 3, \quad 2 \cdot _{(\succsim , P')} 3>_{(\succsim , P')} 4 \cdot _{(\succsim , P')} 5 >_{(\succsim , P')} 1, \end{aligned}$$

and

$$\begin{aligned} 1 \cdot _{(\succsim , P'')} 2>_{(\succsim , P'')} 4 \cdot _{(\succsim , P'')} 3 >_{(\succsim , P'')} 5. \end{aligned}$$

For a coalitional ranking problem $(\Omega _N, \succsim ) \in \mathcal{R}_{\Omega }$ and a partition $P\in {\mathcal {P}}(N)$, define

$$\begin{aligned} M_P(\Omega _N, \succsim )=P \cap M(\Omega _N, \succsim ) \end{aligned}$$

as the set of cells of P that belong to the best equivalence class of $(\Omega _N, \succsim )$.

In the following, we establish properties for $M_P(\Omega _N, \succsim )$ and $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ that will be useful for the rest of the article. The first part of Proposition 1 indicates that $M_P(\Omega _N, \succsim )$ is nonempty if P is a core-partition; the second part of Proposition 1 indicates that a core-partition is consistent in the sense that by removing the cells of $M_P(\Omega _N, \succsim )$ from P, we get a core-partition of the coalitional ranking restricted to the set of remaining agents. Even if Part (ii) follows from Proposition 3 in Karakaya and Klaus (2017), we provide a short proof for completeness.

Proposition 1

For each $(\Omega _ N,\succsim )\in { \mathcal R}_{\Omega }$ and each $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$, it holds that:

• (i) for each $S\in M(\Omega _N, \succsim )$, there is $T\in M_P(\Omega _N, \succsim )$ such that $S\cap T\ne \emptyset$. Thus, $M_P(\Omega _N, \succsim )\ne \emptyset$;

• (ii) $P\backslash M_P(\Omega _N, \succsim )\in \mathcal{C}\mathcal{P}\big (N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S),\succsim _{N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)}\big )$.

Proof

Fix any $(N,\succsim )\in \mathcal{R}_\Omega$ and any $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$.

Part (i). Pick any nonempty $S\in M(\Omega _N, \succsim )$ and $P\in \mathcal{C}\mathcal{P}(\Omega _N, \succsim )$. Assume that, for each $T\in M_P(\Omega _N, \succsim )$, $S\cap T=\emptyset$. It results that, for each $i\in S$, P(i) does not belong to $M(\Omega _N, \succsim )$ so that $S\succ P(i)$. This implies that $P \not \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$, a contradiction. Thus, if $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$, then, for each $S\in M(\Omega _N, \succsim )$, there is $T\in M_P(\Omega _N, \succsim )$ such that $S\cap T\ne \emptyset$. It follows that $M_P(\Omega _N, \succsim ) \not = \emptyset$ for $P \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$.

Part (ii). First observe that $P\backslash M_P(\Omega _N, \succsim )$ is a partition of $N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)$, where the set $\cup _{S\in M_P(\Omega _N, \succsim )} S\not = \emptyset$ by point (i) of Proposition 1. The case in which $N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)$ is empty is trivial. So, assume that there is a nonempty coalition $T\subseteq N\backslash (\cup _{S\in M_P(\omega _N, \succsim )}S)$ such that, for each $i\in T$, $T\succ _{N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)} P(i)$, where $P(i) \in P\backslash M_P(\Omega _N, \succsim )$. Obviously, $T, P(i)\subseteq N$, and, for each $i \in T$, $T\succ P(i)$, which yields that P is not a core-partition of $(\Omega _N,\succsim )$, a contradiction. Conclude that $P\backslash M_P(\Omega _N, \succsim )$ is a core-partition of $(N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S),\succsim _{N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)})$. $\square$

Remark 2

Given $(\Omega _N,\succsim )$ and $\gtrdot \in \mathcal{CSR}(\Omega _N,\succsim )$, let $P_{\gtrdot }$ be the partition of N into equivalent classes according to $\gtrdot$, and consider a partition $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ such that $\gtrdot =\gtrdot _{(\succsim ,P)}$. A priori, $P_{\gtrdot }$ and P can be different. For each $S\in P$ and each $i,j\in S$, $P(i)=P(j)$ so that $i\cdot j$. By definition of $P_\gtrdot$, there is $T\in P_\gtrdot$ such that $i,j\in T$. Therefore, $S\subseteq T$, which implies that $P_\gtrdot$ is coarser than any $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ such that $\gtrdot =\gtrdot _{(\succsim ,P)}$. In particular, the best equivalence class $M(N, \gtrdot )$ of $\gtrdot$ is given by:

$$\begin{aligned} M(N, \gtrdot )=\cup _{S\in M_P(\Omega _N \succsim )}S. \end{aligned}$$

Example 4

Assume that $N = \{1, 2, 3, 4, 5\}$. Consider the coalitional ranking problem $(\Omega _N, \succsim )$ such that

$$\begin{aligned} \{1, 2\} \sim \{2, 3\} \sim \{4, 5\} \sim \{3, 4\} \succ N \sim \{2\} \sim \{3\} \succ \{1\} \succ S \sim T, \end{aligned}$$

for each other pair of coalitions $\{S, T\}$. Obviously, the partition

$$\begin{aligned} P = \bigl \{\{1, 2\}, \{4, 5\}, \{3\}\bigl \} \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ), \end{aligned}$$

and the associated core-partition social ranking $\gtrdot _{(\succsim , P)}$ is given by

$$\begin{aligned} 1 \cdot _{(\succsim , P)} 2 \cdot _{(\succsim , P)} 4 \cdot _{(\succsim , P)} 5 >_{(\succsim , P)} 3. \end{aligned}$$

The partition $P_{\gtrdot _{(\succsim , P)}}$ of N induced by the equivalence classes of $\gtrdot _{(\succsim , P)}$ is given by

$$\begin{aligned} P_{\gtrdot _{(\succsim , P)}} = \bigl \{\{1, 2, 4, 5\}, \{3\}\bigr \}, \end{aligned}$$

and $P_{\gtrdot _{(\succsim , P)}}$ is coarser than P.

5 Axiomatic Study

In this section, we introduce three new axioms for a (set-valued) social ranking solution and examine how permissive or restrictive they are by means of examples or by considering a relevant subdomain of the full domain. It turns out that the combination of these axioms characterizes the social ranking solution $\mathcal{CSR}$. As underlined by Thomson (2001), this axiomatic approach is classical and common to many collective choice problems. According to Thomson (2019),

The axiomatic analysis holds a central place in economic design. It allows us to go beyond current practice and hypothetical examples. It provides explicit arguments for the use of particular allocation rules in terms of meaningful criteria of good behavior (...)

Our axioms are naturally part of this approach. They discuss the consequences of modifications of the two components of the coalitional ranking problem: an expansion of the population of agents and relevant changes in the considered coalitional ranking. The agents have frequently to face such modifications in group decision making situations. So consider the full domain $\mathcal{R}_\Omega$ and let $f: \mathcal{R}_\Omega \rightrightarrows \mathcal{R}_{{\mathbb {N}}}$ be any such social ranking solution.

The first axiom is based on a specific expansion of the population of agents. So consider an initial coalitional ranking problem, say $(N\backslash S,\succsim ')$. Assume now that the population is expanded in such a way that the coalition S of all newly added agents wins unanimous support: S is the unique maximal coalition in the larger coalitional ranking $(N,\succsim )$, the relative ranking between any two original coalitions remains the same, and the other coalitions have an arbitrary ranking (except that they do not belong to the best equivalent class). Hence, the restriction $\succsim _{N\backslash S}$ of $\succsim$ to the original population $N\backslash S$ coincides with $\succsim '$. Then, our axiom imposes that the solution set of this new coalitional ranking problem $(N,\succsim )$ is computed from the solution set of the initial problem $(N\backslash S,\succsim ')$ by adding to each selected social ranking for $(N\backslash S,\succsim ')$ the members of S as the only maximal elements.

To state formally this axiom, a definition is needed. For each $(\Omega _N,\succsim )\in \mathcal{R}_{\Omega }$, each $S\in \Omega _N$ and each $\gtrdot \in \mathcal{R}(N\backslash S)$, denote by $\gtrdot ^{+S}\in \mathcal{R}(N)$ the social ranking on N obtained from $\gtrdot$ by adding S as the set of maximal elements, i.e. $M(N, \gtrdot ^{+S})=\{S\}$, and, for each $i,j\in N\backslash S$, $i\gtrdot ^{+S}j$ if and only if $i\gtrdot j$.

Unanimous extension (UE) For each $(\Omega _N,\succsim )\in \mathcal{R}_{\Omega }$ such that $M(\Omega _N, \succsim )=\{S\}$, it holds that

$$\begin{aligned} f(\Omega _N,\succsim )=\big \{\gtrdot ^{+S}:\gtrdot \in f(\Omega _{N\backslash S},\succsim _{N\backslash S})\big \}. \end{aligned}$$

In order to state the next axiom, we introduce a new operation on a coalitional ranking problem $(\Omega _N, \succsim ) \in \mathcal{R}_{\Omega }$. For a given coalition $S\in \Omega _N$, we say that an alternative coalitional ranking problem $(\Omega _N, \succsim ') \in \mathcal{R}_{\Omega }$ is induced from $(\Omega _N, \succsim )$ by a S -improvement if the two following conditions hold:

$\bullet$ $L(\succsim ,S)\subseteq L(\succsim ',S)$;

$\bullet$ $\forall R,T\in \Omega _N\backslash \{S\}$, $R\succsim ' T \Longleftrightarrow R\succsim T$.

In words, the position of S (weakly) improves while the relative ranking of any other pair of coalitions is unchanged.

The next axiom relies on a principle of invariance of the solution set to some improving move. Consider a situation where two disjoint coalitions have the same rank and their union has a lower rank. Then, this principle of invariance indicates that improving the rank of this union, ceteris paribus, does not alter the solution set, provided than the new rank of the union has still a rank not higher than that of the two original coalitions. For social choice functions, this principle is related in a certain way to the Maskin monotonicity principle (Maskin 1999). Loosely speaking, this Maskin monotonicity indicates that if an alternative is selected in a certain problem, then it is also selected in a related problem obtained when some elements from which the alternative is constructed improved, ceteris paribus. In our case, this principle applies to specific problems where two disjoint coalitions have the same rank, their union is lower ranked, and the improving move is bounded from above by the equivalence class to which these two disjoint coalitions belong.

Invariance to merger upgrading (IMU) For each $(\Omega _ N,\succsim )\in \mathcal{R}_{\Omega _N}$, each pair of coalitions $\{ S,T\} \subseteq \Omega _N$ such that $S\cap T=\emptyset$, $S\sim T$ and $(S\cup T)\in L(\succsim ,S)$, and each $(\Omega _N, \succsim ') \in \mathcal{R}_{\Omega _N}$ induced from $(\Omega _N, \succsim )$ by a $(S\cup T)$-improvement where $(S\cup T)\in L(\succsim ',S)$, it holds that $f(\Omega _N,\succsim )= f(\Omega _N,\succsim ')$.

Example 5

Consider Example 4. If one takes $S=\{1,2\}$ and $T=\{3,4\}$ then $S\cap T=\emptyset$, $S\sim T$ and $(S\cup T)\in L(\succsim ,S)$. Note that $S,T \in M(\Omega _N, \succsim )$. Consider $(\Omega _N, \succsim ')$ induced from $(\Omega _N, \succsim )$ by improving $S\cup T=\{1,2,3,4\}$ up to the best equivalence class so that

$$\begin{aligned} \{1, 2\} \sim ' \{1,2,3,4\} \sim ' \{2, 3\} \sim ' \{4, 5\} \sim ' \{3, 4\} \succ ' N \sim ' \{2\} \sim ' \{3\} \succ ' \{1\} \succ ' S \sim ' T, \end{aligned}$$

for each other pair of coalitions $\{S, T\}$. Now if f satisfies (IMU), then $f(\Omega _N,\succsim )= f(\Omega _N,\succsim ')$.

Note also that one can also improve $\{2,3,4,5\}$ and $\{1,2,4,5\}$ in the same way by considering respectively $S=\{2,3\} \sim T=\{4,5\}$, and $S=\{1,2\} \sim T=\{4,5\}$.

The last axiom implements a decomposition property. It specifies situations where the solution set of a coalitional ranking problem can be expressed as the union of the solution sets of coalitional ranking problems built from the original one and containing a unique maximal element. The situations where such a decomposition is possible is related to the structure of the set of maximal elements of the coalitional ranking problem. A subset of coalitions $\mathcal{C} \subseteq \Omega _N$ is stable by union of disjoint elements if for any pair of coalitions $\{S, T\} \subseteq \mathcal{C}$ such that $S \cap T = \emptyset$, then $S \cup T \in \mathcal{C}$.² Assume that the set of maximal coalitions of a coalitional ranking problem is stable by union of disjoint elements. In such a situation, the axiom indicates that the solution set coincides with the union of the solution sets of variants of the original coalitional ranking problem obtained, for each maximal coalition intersecting all other maximal coalitions, by putting this maximal coalition as the unique maximal coalition, ceteris paribus.

For each $(\Omega _N, \succsim ) \in \mathcal{R}_{\Omega }$ define

$$\begin{aligned} I_M(\Omega _N, \succsim )=\big \{ S\in M(\Omega _N, \succsim ): S\cap T\ne \emptyset ,\forall T\in M(\Omega _N, \succsim )\big \}, \end{aligned}$$

as the set of intersecting coalitions in $M(\Omega _N, \succsim )$. Now, for each $(\Omega _ N,\succsim )\in \mathcal{R}_{\Omega }$ and each $S\in I_M(\Omega _N, \succsim )$, denote by $(\Omega _N, \succsim ^S)$ the unique coalitional ranking problem induced from $(\Omega _N,\succsim )$ by a S-improvement such that $M(\Omega _N, \succsim ^S)=\{S\}$.

Remark 3

If $M(\Omega _N, \succsim )$ is stable by union of disjoint elements, then $I_M(\Omega _N, \succsim ) \not = \emptyset$.

Decomposition by top upgrading (DTU) Consider any $(\Omega _N,\succsim )\in \mathcal{R}_{\Omega }$ such that $M(\Omega _N, \succsim )$ is stable by union of disjoint elements. Then, it holds that

$$\begin{aligned} f(\Omega _N,\succsim ) = \bigcup _{T\in I_M(\Omega _N, \succsim )}f(\Omega _N,\succsim ^T). \end{aligned}$$

Example 6

Consider again Example 4. Applying the three improvements presented in Example 5 brings the following coalitional ranking:

$$\begin{aligned}{} & {} \{1, 2\} \sim ^* \{1,2,3,4\} \sim ^* \{1,2,4,5\} \sim ^* \{2,3,4,5\} \sim ^* \{2, 3\} \sim ^* \{4, 5\} \sim ^* \{3, 4\} \\{} & {} \quad \succ ^* N \sim ^* \{2\} \sim ^* \{3\} \succ ^* \{1\}, \end{aligned}$$

and $\{1\} \succ ^* S \sim ^* T$ for each other pair of coalitions $\{S, T\}$. Remark that $M(\Omega _N, \succsim ^*)$ is stable by union of disjoint elements and that

$$\begin{aligned} I_M(\Omega _N, \succsim ^*) =\{\{1,2,3,4\},\{1,2,4,5\},\{2,3,4,5\}\}. \end{aligned}$$

Hence if f satisfies (DTU), then $f(\Omega _N,\succsim ^*)= f(\Omega _N,(\succsim ^*)^{\{1,2,3,4\}}) \cup f(\Omega _N,(\succsim ^*)^{\{1,2,4,5\}}) \cup f(\Omega _N,(\succsim ^*)^{\{2,3,4,5\}})$.

The next result states that the combination of Unanimous extension, Invariance to merger upgrading and Decomposition by top upgrading characterizes the core-partition social ranking solution $\mathcal{CSR}$.

Proposition 2

The social ranking solution $\mathcal CSR$ is the unique solution on $\mathcal{R}_{\Omega }$ satisfying Unanimous extension (UE), Invariance to merger upgrading (IMU), and Decomposition by top upgrading (DTU).

Proof

The proof is divided into two parts (a) and (b).

(a) One shows that $\mathcal CSR$ satisfies the above three axioms. Pick any $(\Omega _N,\succsim )\in \mathcal{R}_{\Omega }$.

Unanimous extension Assume that $M(\Omega _N, \succsim )=\{S\}$ for some $S\in \Omega _N$. To show:

$$\begin{aligned} \mathcal{CSR}(\Omega _N,\succsim )=\bigl \{\gtrdot ^{+S}: \, \gtrdot \in \mathcal{CSR}(\Omega _{N \backslash S},\succsim _{N \backslash S})\bigr \} \end{aligned}$$

(1)

To this end, it is sufficient to show that $P \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ if and only if P is of the form $P= \{S\} \cup P'$ where $P' \in \mathcal{C}\mathcal{P}(\Omega _{ N\backslash S},\succsim _{N\backslash S})$. For the “if part”, consider such a partition $P \in \mathcal{P}(N)$ and any $T \in \Omega _N$. Two cases can be distinguished:

$\bullet$ if $T \cap S \ne \emptyset$, pick $i \in T \cap S$. One obtains $P(i)=S \succsim T$ because $S \in M(\Omega _N, \succsim )$;

$\bullet$ if $T \cap S = \emptyset$, then $T \in \Omega _{N \backslash S}$. Because $P'$ is a core-partition of $(\Omega _{N \backslash S},\succsim _{N \backslash S})$, there is $i \in T$ such that $P'(i)\succsim _{N\backslash S}T$. Hence, $P(i)=P'(i)\succsim T$.

From the above two cases, conclude that P cannot be blocked by T, and so $P \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$.

For the “only if part”, by part (i) of Proposition 1, $M_P(\Omega _N, \succsim )\cap M(\Omega _N, \succsim )\ne \emptyset$ so that $S \in P$ and $M_P(\Omega , \succsim )=\{S\}$. Part (ii) of Proposition 1 implies that $P'=P\backslash \{S\} \in \mathcal{C}\mathcal{P}(\Omega _{N \backslash S},\succsim _{N\backslash S})$, as desired.

Now, if $P = \{S\} \cup P' \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ for some $P' \in \mathcal{C}\mathcal{P}(\Omega _{N \backslash S},\succsim _{N\backslash S})$, then its associated social ranking $\gtrdot _{(\succsim ,P)}$ belongs to $\mathcal{CSR}(\Omega _N,\succsim )$ and obviously $\gtrdot _{(\succsim ,P)}=\gtrdot _{(\succsim _{N \backslash S},P')}^{+S}$. Reciprocally, $P' \in \mathcal{C}\mathcal{P}(N\backslash S,\succsim _{N\backslash S})$ gives rise to a unique social ranking $\gtrdot _{(\succsim _{N \backslash S},P')}^{} \in \mathcal{CSR}(N\backslash S,\succsim _{N\backslash S})$ from which the social ranking $\gtrdot _{(\succsim _{N \backslash S},P')}^{+S} = \gtrdot _{(\succsim , P)}$ is a core-partition social ranking of $\mathcal{CSR}(\Omega _N,\succsim )$. Thus, (1) holds, as desired.

Invariance to merger upgrading Consider a pair $\{S,T\} \subseteq \Omega _N$ such that $S\cap T=\emptyset$, $S\sim T$ and $(S\cup T)\in L(\succsim ,S)$, and any coalitional ranking problem $(\Omega _N, \succsim ')\in \mathcal{R}_\Omega$ induced from $\succsim$ by a $(S\cup T)$-improvement with $(S\cup T)\in L(\succsim ',S)$. To show: $\mathcal{CSR}(\Omega _N,\succsim ) = \mathcal{CSR}(\Omega _N,\succsim ')$. One proceeds by double inclusion.

$\bullet$ $\mathcal{CSR}(\Omega _N,\succsim ) \subseteq \mathcal{CSR}(\Omega _N,\succsim ')$. By definition of $\mathcal{CSR}$, it suffices to show that $\mathcal{C}\mathcal{P}(\Omega _N,\succsim ) \subseteq \mathcal{C}\mathcal{P}(\Omega _N,\succsim ')$. Pick any $P\in \mathcal{C}\mathcal{P}(N,\succsim )$, which means that, for each $R\in \Omega _N$, there is $i\in R$ such that $P(i)\succsim R$. For each $R\in \Omega _N\backslash \{(S\cup T)\}$, note that $P(i)\succsim R$ implies $P(i) \succsim ' R$ because $S \cup T$ is the only improved coalition in the coalitional ranking $\succsim '$. If $R=S\cup T$, then, since there is $i\in S$ such that $P(i)\succsim S$ and $(S\cup T)\in L(\succsim ,S)\cap L(\succsim ',S)$, one obtains $P(i)\succsim ' S \succsim ' (S\cup T)$, whether $P(i)=S \cup T$ or not. Hence, $P\in \mathcal{C}\mathcal{P}(N,\succsim ')$.

$\bullet$ $\mathcal{CSR}(\Omega _N,\succsim ) \supseteq \mathcal{CSR}(\Omega _N,\succsim ')$. Pick any $\gtrdot \in \mathcal{CSR}(\Omega ,\succsim ')$ and any $P' \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ')$ such that $\gtrdot =\gtrdot _{(\succsim ',P')}$. If $S\cup T \notin P'$, then define $P=P'$; and if $S\cup T \in P'$, then define $P=\left( P'\backslash \{S \cup T\}\right) \cup \{S\} \cup \{T \}$. Because $S \cup T \in P'$ only happens when $S \sim 'T \sim ' S\cup T$, one necessarily has $\gtrdot _{(\succsim ,P)}=\gtrdot _{(\succsim ',P')}$. Let us show that $P \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ so that $\gtrdot \in \mathcal{CSR}(\Omega _N,\succsim )$. For each $R\in \Omega _N$, there is $i\in R$ such that $P'(i)\succsim ' R$. If $P'(i) \ne S\cup T$, then $P(i)=P'(i) \succsim R$, whether $R=S\cup T$ or not. If $P'(i)=S \cup T$, then either $i\in S$ or $i\in T$ so that $P(i)=S$ or $P(i)=T$. By definition of $\succsim '$, $S\cup T \in L(\succsim ',S) = L(\succsim ',T)$ so that, in both cases, $P(i)\succsim 'S\cup T=P'(i) \succsim ' R$, which implies that $P(i)\succsim R$. Hence, for each $R\in \Omega _N$, there is $i\in R$ such that $P(i)\succsim R$. Conclude that $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ so that $\gtrdot =\gtrdot _{(\succsim ',P')} = \gtrdot _{(\succsim ,P)} \in \mathcal{CSR} (\Omega _N,\succsim )$.

Decomposition by top upgrading Assume that $M(\Omega _N, \succsim )$ is stable by union of disjoint elements. To show:

$$\begin{aligned} \mathcal{CSR}(\Omega _N,\succsim ) = \bigcup _{T\in I_M(\Omega _N, \succsim )}\mathcal{CSR}(\Omega _N,\succsim ^T). \end{aligned}$$

(2)

One proceeds by double inclusion.

$\bullet$ $\mathcal{CSR}(\Omega _N,\succsim ) \subseteq \cup _{T\in I_M(\Omega _N, \succsim )}\mathcal{CSR}(\Omega _N,\succsim ^T)$. Pick any $\gtrdot \in \mathcal{CSR}(\Omega _N,\succsim )$ and any $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ associated with $\gtrdot \in \mathcal{CSR}(\Omega _N,\succsim )$, i.e., $\gtrdot =\gtrdot _{(\succsim ,P)}$. It suffices to show that there is $T \in I_M(\Omega _N, \succsim )$ and $P' \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ^T)$ such that $\gtrdot _{(\succsim ^T,P')}=\gtrdot _{(\succsim ,P)}$. Denote by T the union of the possibly several elements in $M_P(\Omega _N, \succsim )$ and define $P'$ as the partition obtained from P by replacing the elements of $M_P(\Omega _N, \succsim )$ by their union T. Because $M(\Omega _N, \succsim )$ is stable by union of disjoint elements, $T \in M(\Omega _N, \succsim )$. Clearly, $M_{P'}(\Omega _N, \succsim )=\{T\}$, $\gtrdot _{(\succsim ,P')}=\gtrdot _{(\succsim ,P)}$ and $P'\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$. It remains to show that $T \in I_M(\Omega , \succsim )$ and that $P' \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ^T)$. The first claim results from part (i) of Proposition 1 and the definition of $I_M(\Omega , \succsim )$. For the second claim, pick any $S \in \Omega _N$. Because $P\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$, there is $i \in S$ such that $P(i)\succsim S$. If $i \in T$, then $T=P'(i)\succsim ^T S$. If $i \notin T$, then $P'(i)=P(i) \notin M(\Omega _N, \succsim )$. By definition of $\succsim ^T$ and the fact that $P' \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$, one obtains $P'(i) \succsim ^T S$. Hence, $P' \in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ^T)$.

$\bullet$ $\mathcal{CSR}(\Omega _N,\succsim ) \supseteq \cup _{T\in I_M(\Omega _N, \succsim )}\mathcal{CSR}(\Omega _N,\succsim ^T)$. Precisely, one establishes that, for each $T \in I_M(\Omega _N, \succsim )$, $\mathcal{C}\mathcal{P}(\Omega _N,\succsim ^T)\subseteq \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ so that $\mathcal{CSR}(\Omega _N,\succsim ^T) \subseteq \mathcal{CSR}(\Omega _N,\succsim )$. For each $P'\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ^T)$, $M_{P'}(\Omega _N, \succsim ^T)=\{T\} \subseteq M(\Omega _N, \succsim )$ where the inclusion follows from the fact that $T \in I_M(\Omega _N, \succsim )$. Furthermore, $T \in I_M(\Omega _N, \succsim )$ implies $M_{P'}(\Omega _N, \succsim )=\{T\}$. Because, $P'\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim ^T)$, for each $S \in \Omega _N$, there is $i \in S$ such that $P'(i) \succsim ^T S$. If $S \cap T \ne \emptyset$, one picks $i \in S\cap T$ and $P'(i)=T \in M(\Omega _N, \succsim )$ so that $P'(i)\succsim S$. If $S \cap T = \emptyset$, then $P'(i)\ne T$, so that $P'(i) \succsim S$ by definition of $\succsim ^T$. This yields that $P'\in \mathcal{C}\mathcal{P}(\Omega ,\succsim )$, as desired.

(b) One shows that if a social ranking solution f satisfies Unanimous extension, Invariance to merger upgrading and Decomposition by top upgrading, then $f = \mathcal{CSR}$. So, consider such a social ranking solution f. To prove that $f = \mathcal{CSR}$, one proceeds by induction on the number $n\ge 0$ of agents in a coalitional ranking problem.

Initialization. For $N = \emptyset$, by convention $f(\Omega _{\emptyset }, \emptyset ) = \mathcal{CSR} (\Omega _{\emptyset }, \emptyset ) = \{\emptyset \}.$ For $N = \{i\}$ for some $i \in {\mathbb {N}}$, and for the (unique) coalitional ranking $\succsim$ on $\Omega _{\{i\}}$, $\{i\} \succsim \{i\}$, one applies Unanimous extension to f:

$$\begin{aligned} f(\Omega _{\{i\}}, \succsim ) = \bigl \{\emptyset ^{+ \{i\} }: \{\emptyset \} = f(\Omega _{\emptyset }, \emptyset )\bigr \} = \{\cdot \}, \end{aligned}$$

meaning that $i \cdot i$. Obviously, $\mathcal{CSR}(\Omega _{\{i\}}, \succsim ) = \{\cdot \}$, so that $f(\Omega _{\{i\}}, \succsim ) = \mathcal{CSR}(\Omega _{\{i\}}, \succsim )$.

Induction hypothesis. Assume that $f(\Omega _N,\succsim )=\mathcal{CSR}(\Omega _N,\succsim )$ holds for any $(\Omega ,\succsim ) \in \mathcal{R}_{\Omega _N}$ such that $n < k$ for some integer $k\ge 1$.

Induction step. Consider any coalitional ranking problem $(\Omega _N,\succsim ) \in \mathcal{R}_{\Omega }$ such that $n=k$. If $M(\Omega _N, \succsim )$ is not stable by union of disjoints elements, $M(\Omega _N, \succsim )$ contains disjoint coalitions S and T such that $S\cup T$ is not in $M(\Omega _N, \succsim )$. Then, construct the coalitional ranking problem $(\Omega _N, \succsim ')$ induced from $(\Omega _N, \succsim )$ by the $(S\cup T)$-improvement such that $S\cup T\in M(\Omega _N, \succsim ')$. Because f and $\mathcal CSR$ satisfy Invariance to merger upgrading, $f(\Omega _N,\succsim ')=f(\Omega _N,\succsim )$ and $\mathcal{CSR}(\Omega _N,\succsim ')=\mathcal{CSR}(\Omega _N,\succsim )$. Continue in this fashion to eventually construct a coalitional ranking problem $(\Omega _N, \succsim ^*)$ such that, for each $S,T\in M(\Omega _N, \succsim ^*)$ where $S\cap T=\emptyset$, $S\cup T\in M(\Omega _N, \succsim ^*)$ so that $M(\Omega _N, \succsim ^*)$ is stable by union of disjoint elements. Because $\Omega _N$ is a finite set, the (unique) coalitional ranking problem $(\Omega _N, \succsim ^*)$ is reached after a finite number of steps. If $M(\Omega _N, \succsim )$ is stable by union of disjoint elements, no operation is required and $\succsim = \succsim ^*$. Then, by successive applications of Invariance to merger upgrading, one obtains:

$$\begin{aligned} f(\Omega _N,\succsim ^*)=f(\Omega _N,\succsim )\quad \text { and }\quad \mathcal{CSR}(\Omega _N,\succsim ^*)=\mathcal{CSR}(\Omega _N,\succsim ). \end{aligned}$$

(3)

Furthermore, by Remark 3, $I_M( \Omega _N, \succsim ^*) \not = \emptyset$. Thus, the conditions underlying Decomposition by top upgrading are met in $(\Omega _N,\succsim ^*)$. Now, consider any $S\in I_M(\Omega _N, \succsim ^*)$ and construct the coalitional ranking problem $(\Omega _N, \succsim ^{*S})$ induced from $(\Omega _N, \succsim ^*)$ by the S-improvement such that $M(\Omega _N, \succsim ^{*S})=\{S\}$. Applying Unanimous extension to both f and $\mathcal{CSR}$ and the induction hypothesis, one gets:

$$\begin{aligned} f(\Omega _N,\succsim ^{*S})&{\mathop {=}\limits ^{\tiny \text{ UE }}}&\big \{\gtrdot ^{+S}:\gtrdot \in f(\Omega _{ N\backslash S},\succsim ^{*S}_{N\backslash S})\big \} \nonumber \\&{\mathop {=}\limits ^{\tiny \text{ Ind. } \text{ Hypo. }}}&\big \{\gtrdot ^{+S}:\gtrdot \in \mathcal{CSR}(\Omega _{N\backslash S},\succsim ^{*S}_{N\backslash S})\big \} \nonumber \\&{\mathop {=}\limits ^{\tiny (\text{1 })}}&\mathcal{CSR}(\Omega _N,\succsim ^{*S}) \end{aligned}$$

(4)

Because S was arbitrarily chosen in $I_M(\Omega _N, \succsim ^*)$, applying Decomposition by top upgrading to both f and $\mathcal{CSR}$ and using the equalities (3)-(4) yield that

$$\begin{aligned} f(\Omega _N,\succsim )&{\mathop {=}\limits ^{\tiny (3)}}&f(\Omega _N,\succsim ^*) \nonumber \\&{\mathop {=}\limits ^{\tiny \text{ DTU }}}&\bigcup _{S\in I_M(\Omega _N, \succsim ^*)}f(\Omega _N,\succsim ^{*S}) \nonumber \\&{\mathop {=}\limits ^{\tiny (4)}}&\bigcup _{S\in I_M(\Omega _N, \succsim ^*)}\mathcal{CSR}(\Omega _N,\succsim ^{*S}) \nonumber \\&{\mathop {=}\limits ^{\tiny (\text{2 })}}&\mathcal{CSR}(\Omega _N,\succsim ^*) \nonumber \\&{\mathop {=}\limits ^{\tiny (3)}}&\mathcal{CSR}(\Omega _N,\succsim ), \nonumber \end{aligned}$$

which completes the induction step.

The statement of Proposition 2 follows from (a) and (b). $\square$

The steps used in the uniqueness part (b) of the previous proof are illustrated in the following example.

Example 7

Consider Example 4. As in Example 5, by successive merger upgrading, we get the following coalitional ranking:

$$\begin{aligned}{} & {} \{1, 2\} \sim ^* \{1,2,3,4\} \sim ^* \{1,2,4,5\} \sim ^* \{2,3,4,5\} \sim ^* \{2, 3\} \sim ^* \{4, 5\} \sim ^* \{3, 4\} \\{} & {} \quad \succ ^* N \sim ^* \{2\} \sim ^* \{3\} \succ ^* \{1\}, \end{aligned}$$

and $\{1\} \succ ^* S \sim ^* T$ for each other pair of coalitions $\{S, T\}$. Hence, by successive applications of Invariance to merger upgrading, one obtains that $f(\Omega _N,\succsim )=f(\Omega _N,\succsim ^{*})$.

As seen in Example 6, $M(\Omega _N,\succsim ^{*})$ is stable by union of disjoint elements so that

$$\begin{aligned} f(\Omega _N,\succsim ^*)= f(\Omega _N,(\succsim ^*)^{\{1,2,3,4\}}) \cup f(\Omega _N,(\succsim ^*)^{\{1,2,4,5\}}) \cup f(\Omega _N,(\succsim ^*)^{\{2,3,4,5\}}). \end{aligned}$$

Each member of this union gives rise to a unique social ranking by applying Unanimous extension, because $M(\Omega _N, \succsim ^S)=\{S\}$ and S contains all but one agent. For instance:

$$\begin{aligned} f(\Omega _N,(\succsim ^*)^{\{1,2,3,4\}})=\big \{\gtrdot ^{+\{1,2,3,4\}}:\gtrdot \in f(\Omega _{\{5\}},\succsim _{\{5\}})\big \}=\{1\cdot 2 \cdot 3 \cdot 4 > 5\}. \end{aligned}$$

The three social rankings composing $f(\Omega _N,\succsim )$ correspond to the following three core-partitions of $(\Omega _N,\succsim )$: $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )=\{P^1,P^2,P^3\}$ where $P^1 = \bigl \{\{1, 2\}, \{3, 4\}, \{5\}\bigl \}$, $P^2 = \bigl \{\{1,2\}, \{4, 5\}, \{3\}\bigl \}$ and $P^3 = \bigl \{\{2,3\}, \{4, 5\}, \{1\}\bigl \}$.

Remark 4

Note that on the subdomain of coalitional rankings that are strict total orders, Unanimous extension fully characterizes $\mathcal{CSR}$. On this subdomain, one easily verifies that $\mathcal{CSR}$ is single-valued. This means that the two other axioms invoked in Proposition 2 are key to dealing with ties in the equivalent classes that often arise in less specific coalitional rankings.

The logical independence of the axioms used in Proposition 2 is shown in the following section.

6 Logical Independence of the Axioms

Unanimous extension is not satisfied Consider the constant solution $f^C$ which assigns to each coalitional ranking problem the equivalence social relation $\cdot$, that is all agents belong to the same equivalence class:

$$\begin{aligned} \forall (\Omega _N, \succsim ) \in \mathcal{R}_{\Omega }, \quad f^C(\Omega _N, \succsim ) = \{ \cdot \}. \end{aligned}$$

Because the image $f^C(\mathcal{R}_{\Omega })$ is the equivalence relation $\cdot$, it obviously satisfies Invariance to merger upgrading, and Decomposition by top upgrading. But $f^C$ violates Unanimous extension for the following reason: the social ranking $\gtrdot ^{+S}$ used to define the solution set $f^C(\Omega _N, \succsim )$ whenever $M(\Omega _N, \succsim )$ is a singleton, contains at least two distinct equivalence classes when $S \not = N$.

Invariance to merger upgrading is not satisfied Pick any $(\Omega _N, \succsim ) \in \mathcal{R}_{\Omega }$ and define $I (\Omega _N, \succsim )$ as:

$$\begin{aligned}{} & {} I (\Omega _N, \succsim ) = \bigl \{S \in \Omega _N: \forall T \in \Omega _N, (S \sim T \Rightarrow S \cap T \not = \emptyset ) \wedge (T \succ S \Rightarrow (\exists R \in \Omega _N\\{} & {} \quad , (R \sim T) \wedge (R \cap T) = \emptyset )) \bigr \}. \end{aligned}$$

Note that $I (\Omega _N, \succsim ) \not =\emptyset$. Consider the social ranking solution $f^I$ defined recursively as follows:

$$\begin{aligned} \forall (\Omega _N, \succsim ) \in \mathcal{R}_{\Omega }, \quad f^I (\Omega _N, \succsim ) = \bigcup _{S \in I(\Omega _N, \succsim )} \bigl \{ \gtrdot ^{+S}: \, \gtrdot ^{} \in f^I (\Omega _{N \setminus S}, \succsim _{N \setminus S}) \bigr \}. \end{aligned}$$

In case $M (\Omega _N, \succsim ) = \{S\}$, then $I (\Omega _N, \succsim ) = \{S\}$ and so

$$\begin{aligned} f^{I} (\Omega _N, \succsim ) = \{ \gtrdot ^{+S}: \, \gtrdot ^{} \in f^I (\Omega _{N \setminus S}, \succsim _{N \setminus S}) \bigr \}, \end{aligned}$$

which is the definition of Unanimous extension. Thus, $f^I$ indeed satisfies this axiom. In case $M (\Omega _N, \succsim )$ is stable by union of disjoint elements, $I (\Omega _N, \succsim ) = I_M (\Omega _N, \succsim )$. For each $S \in I_M (\Omega _N, \succsim )$, $(\Omega _N, \succsim ^{S})$ is such that $M(\Omega _N, \succsim ^{S}) = \{S\} = I(\Omega _N, \succsim ^{S})$. Note also that $\succsim _{N \setminus S}^{S} = \succsim _{N \setminus S}$, so that

$$\begin{aligned} f^I (\Omega _N, \succsim ^{S} )= & {} \bigl \{ \gtrdot ^{+S}: \, \gtrdot ^{} \in f^I (\Omega _{N \setminus S}, \succsim _{N \setminus S}^{S})\bigr \} \nonumber \\= & {} \bigl \{ \gtrdot ^{+S}: \, \gtrdot ^{} \in f^I (\Omega _{N \setminus S}, \succsim _{N \setminus S}^{})\bigr \}. \nonumber \end{aligned}$$

Consequently,

$$\begin{aligned} f^{I} (\Omega _N, \succsim ) = \bigcup _{S \in I_M(\Omega _N, \succsim )} f^I (\Omega _N, \succsim ^{S} ), \end{aligned}$$

which shows that $f^I$ satisfies Decomposition by top upgrading. To show that $f^I$ violates Invariance to merger upgrading, consider the coalitional ranking problem $(\Omega _N, \succsim )$ with $N=\{1,2,3\}$ and defined as:

$$\begin{aligned} \{2\} \sim \{3\} \succ \{2, 3\} \sim \{1\} \succ \{1, 2, 3\} \succ \{1, 3\} \sim \{1, 2\}. \end{aligned}$$

It follows that $I (\Omega _N, \succsim ) = \{\{1, 2, 3\} \},$ and so $f^I(\Omega _N, \succsim ) = \{\cdot \}$, i.e., $1\cdot 2\cdot 3.$ Now, consider the coalitional ranking problem $(\Omega _N, \succsim ')$ defined as:

$$\begin{aligned} \{2\} \sim ' \{3\} \sim ' \{2, 3\} \succ ' \{1\} \succ ' \{1, 2, 3\} \succ ' \{1, 3\} \sim ' \{1, 2\}. \end{aligned}$$

The coalitional ranking problem $(\Omega _N, \succsim ')$ is an improvement from $(\Omega _N, \succsim )$ induced by $\{2, 3\}$ that satisfies the conditions of Invariance to merger upgrading. One has $I (\Omega _N, \succsim ') = \{\{2, 3\}\}$. By definition of $f^{I}$ and the fact that it satisfies Unanimous extension,

$$\begin{aligned} f^{I} (\Omega _N, \succsim ') = \{ 2 \cdot 3 > 1\} \not = f^{I} (\Omega _N, \succsim ), \end{aligned}$$

a violation of Invariance to merger upgrading.

Decomposition by top upgrading is not satisfied Consider the following solution

$$\begin{aligned} \forall (\Omega _N, \succsim ) \in \mathcal{R}, \quad f^{\ell }(\Omega _N,\succsim )=\mathcal{CSR}(N,\ell (\succsim )), \end{aligned}$$

where $\ell : {\mathcal {R}}(\Omega _N)\rightarrow {\mathcal {R}}(\Omega _N)$ is defined as

$$\begin{aligned} S \ell (\succsim ) T \Longleftrightarrow \bigl ((S \succ T) \text{ or } (S \sim T \text{ and } |S| \leqslant |T|)\bigr ). \end{aligned}$$

The solution $f^{\ell }$ satisfies Unanimous extension and Invariance to merger upgrading but not Decomposition by top upgrading. Indeed, if $M(\Omega _N, \succsim )=\{S\}$, then $M(\Omega _N, \ell (\succsim ))=\{S\}$ and

$$\begin{aligned} f^{\ell }(\Omega _N,\succsim )= & {} \mathcal{CSR}(\Omega _N,\ell (\succsim )) \nonumber \\= & {} \{\gtrdot ^{+S}:\gtrdot \in \mathcal{CSR}(\Omega _{N\backslash S},\ell (\succsim )_{N\backslash S})\} \nonumber \\= & {} \{\gtrdot ^{+S}:\gtrdot \in \mathcal{CSR}(\Omega _{N\backslash S},\ell (\succsim _{N\backslash S}))\}\nonumber \\= & {} \{\gtrdot ^{+S}:\gtrdot \in f^{\ell } (\Omega _{N\backslash S},\succsim _{N\backslash S})\}, \nonumber \end{aligned}$$

which shows that $f^{\ell }$ satisfies Unanimous extension. Next, if $S,T\in \Omega _N$ are such that $S\cap T=\emptyset$, $S\sim T$ and $(S\cup T)\in L(\succsim ,S)$, then for any $(\Omega _N, \succsim ') \in \mathcal{R}(\Omega _N)$ induced from $\succsim$ by a $(S\cup T)$-improvement with $(S\cup T)\in L(\succsim ',S)$, it holds that $\ell (\succsim ')$ is induced from $\ell (\succsim )$ by a $(S\cup T)$-improvement with $(S\cup T)\in L(\ell (\succsim '),S)$. Thus, $f^{\ell }$ satisfies Invariance to merger upgrading due to the fact that $\mathcal{CSR}$ satisfies it. Finally, consider the coalitional ranking problem $(\Omega _N,\succsim )$ with $N=\{1,2\}$ and defined as $\{1\}\sim \{1,2\} \succ \{2\}$, then $\succsim '=\ell (\succsim )$ is as follows: $\{1\} \succ ' \{1,2\} \succ ' \{2\}$. On the one hand, by definition of $f^{\ell }$, one has:

$$\begin{aligned} f^{\ell } (\Omega _N,\succsim )= \mathcal{CSR}(\Omega _N,\succsim ') = \{\gtrdot \}, \end{aligned}$$

where $M(N, \gtrdot )=\{1\}$. On the other hand, $M(\Omega _N, \succsim ) = \{\{1\},\{1,2\}\}$ is stable by union of disjoint elements and $I_M(\Omega _N, \succsim )= M(\Omega _N, \succsim )$, so that $\cup _{S\in I_M(\Omega _N, \succsim )}f^{\ell }(\Omega _N,\succsim ^S)=\{\gtrdot ,\gtrdot '\}$, where $\gtrdot '$ is such that $M(N, \gtrdot ')=\{1,2\}$. This contradicts Decomposition by top upgrading.

7 Computing All Core-Partitions

This section is devoted to the computation of the core-partitions of a coalitional ranking problem $(\Omega _N,\succsim )$ from which the set of social rankings $\mathcal{CSR}(\Omega _N,\succsim )$ is obtained. A non-deterministic algorithm is proposed, which computes all core-partitions of a coalitional ranking problem. In particular, this algorithm permits to conclude that the set of all core-partitions of a coalitional ranking problem is nonempty. As noted in Remark 1, this nonemptiness property has already been shown by Farrell and Scotchmer (1988) in another context. The idea behind the forthcoming algorithm is described informally in the proof of Theorem 1 in Farrell and Scotchmer (1988) and in the proof of Theorem 1 in Banerjee et al. (2001) in a slightly more general context. It is also given in Lucchetti et al. (2022). Hence, we only give a proof of Proposition 3 below for completeness. In turn, this property implies that $\mathcal{CSR}$ is nonempty-valued on $\mathcal{R}_{\Omega }$. The algorithm is as follows.

Proposition 3

For each $(\Omega _N,\succsim )\in \mathcal{R}_{\Omega }$, the set of outcomes of the above non-deterministic algorithm is exactly $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$.

Proof

Firstly, remark that the execution of the algorithm always terminates after a finite number of steps since N is a finite set.

Secondly, we prove that each $P = \{P_1, \ldots , P_k\}\in \mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ is obtained as some output of the algorithm. Denote by t the number of equivalent classes of $\succsim$ and order them according to the quotient order: $M(\Omega _N, \succsim )$ is the equivalent class 1 and so on. Define the mapping $\pi :\{1,\dots ,k\}\longrightarrow \{1,\dots ,t\}$ such that $P_i$ belongs to equivalent class $\pi (i)$ according to $\succsim$. Note that $P_i\succsim P_j$ if and only if $\pi (i)\le \pi (j)$. By Remark 2, the pre-image $\pi ^{-1}(1)$ is nonempty and each cell $P_i$ such that $i \in \pi ^{-1}(1)$ can be chosen in the inner loop $3-5$ of the algorithm to form the output P while $\eta =N$: these cells define the set $\cup _{i \in \pi ^{-1}(1)}P_i=\cup _{S\in M_P(\Omega _N, \succsim ,)}S$. Then, according to the second part of Proposition 1, we have

$$\begin{aligned} P\backslash M_P(\Omega _N, \succsim )\in \mathcal{C}\mathcal{P}\big (N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S),\succsim _{N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)}\big ). \end{aligned}$$

As a consequence, starting from $\eta = N\backslash (\cup _{S\in M_P(\Omega _N, \succsim )}S)$, each coalition $P_i\in P\backslash M_P(\Omega _N, \succsim )$ is such that $\pi (i)>1$ and may be chosen recursively at step 3 or 4 by the algorithm.

Thirdly, we prove that each output of the algorithm belongs to $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$. So, assume $P=\{P_1,\ldots ,P_k\} \in \mathcal{P} (N)$ is some output of the algorithm. By construction, P is a partition of N, whatever the choices made in steps 3 and 4. As above, consider $\pi : \{1,\ldots ,k\} \rightarrow \{1,\dots ,t\}$ so that $P_i$ belongs to equivalent class $\pi (i)$ according to $\succsim$. Pick any $S\in \Omega _N$. Consider $i_0\in \{1,\ldots ,k\}$ such that $\pi (i_0)=\min \{\pi (i): P_i \cap S \ne \emptyset \}$; the minimizer $i_0$ is possibly not unique. Let us show that $P_{i_0}\succsim S$. By construction, $P_{i_0}$ enters P at step 3 or 4 for a given $\eta \subseteq N$. By definition of $i_0$, for each $i \in \{1,\ldots ,k\}$ such that $P_i \cap S \ne \emptyset$, $P_i$ enters P later in the algorithm. Hence, each $j \in S$ belongs to a $P_i = P(j)$ such that $\pi (i) \ge \pi (i_0)$ so that $S\in \Omega _\eta$. By definition of the algorithm, we have $P_{i_0} \in M(\Omega _{\eta }, \succsim _{\eta })$ in $(\Omega _\eta ,\succsim _{\eta })$. Together with $S\in \Omega _\eta$, this implies that $P_{i_0}\succsim _{\eta } S$, and so $P_{i_0}\succsim S$. Conclude that each $j \in P_{i_0}\cap S$ satisfies $P(j) \succsim S$, which means that S cannot block P, as desired. $\square$

Example 8

The key steps of the algorithm can be represented schematically by its decision tree. Each node, other than a leaf, is labeled by the set $\eta$ corresponding to the steps 1 and 6 from which a choice is made in step 3 and 4. These choices correspond to the label of each arrow. Each leaf computes the output of the algorithm. Consider Example 1. Recall that $N = \{1, 2, 3, 4, 5\}$ and

$$\begin{aligned} \{1, 2\} \sim \{2, 3\} \succ \{4, 5\} \sim \{3, 4\} \succ N \sim \{2\} \sim \{3\} \succ \{1\} \succ S \sim T, \end{aligned}$$

for each other pair of coalitions $\{S, T\}$. The set $\mathcal{C}\mathcal{P}(\Omega _N,\succsim )$ of core-partitions contains three elements:

$$\begin{aligned} P = \bigl \{\{1, 2\}, \{4, 5\}, \{3\}\bigr \}, \quad P' = \bigl \{\{2, 3\}, \{4, 5\}, \{1\}\bigr \}, \quad P'' = \bigl \{\{1, 2\}, \{3, 4\}, \{5\} \bigr \}. \end{aligned}$$

Fig. 1 draws the associated decision tree.

Fig. 1

Decision tree of the algorithm applied to Example 1

8 Conclusion

Other stability concepts identifying subsets of “stable” partitions have been designed for hedonic games (see Aziz and Savani 2016). A possible research agenda would be to replicate our approach for these alternative stability concepts, i.e. adapting the concept to coalitional ranking problems and finding an axiomatic characterization of the social ranking induced by the corresponding stable partitions.