key: cord-1035074-2zvj2oi4
authors: Algaba, Encarnación; Moretti, Stefano; Rémila, Eric; Solal, Philippe
title: Lexicographic solutions for coalitional rankings
date: 2021-06-07
journal: Soc Choice Welfare
DOI: 10.1007/s00355-021-01340-z
sha: 2614baafec6e92688296bf7582481b2e4857d4e8
doc_id: 1035074
cord_uid: 2zvj2oi4

In many real world situations, the design of social rankings over agents or items from a given raking over groups or coalitions, to which these agents or items belong to, is of big interest. With this aim, we revise the lexicographic excellence solution and introduce two novel solutions which, moreover, take into account the size of the groups. We present some desirable axioms which are interpreted in this context. Next, a comparable axiomatization of these three solutions is established, revealing the main differences among the two new social rankings and the lexicographic excellence solution. Finally, we apply the three social rankings under study to a real scenario. Specifically, the performance of some football players of Paris Saint-Germain during the UEFA Champions League according to these three rules is analyzed.

One of the main issues in situations where people work in teams is to evaluate the marginal productivity of teams members. Nevertheless, any practical attempt to measure the individual contribution of teams members clashes against the complex and multi-attribute nature of the problem to compare groups. As a relevant example, consider ranking of sportsmen (Vilain and Kolkovsky 2016) . While the problem of how to rank players or teams in tournament situations is of primary importance for sport competitions, and it has received a lot of attention in the game theoretic literature -for instance, focusing on the strategic behavior of competitors who want to manipulate the outcome of a tournament (Csató 2019c (Csató , 2020a (Csató , b, 2021 Dagaev and Sonin 2018; Pauly 2014; Vong 2017) , or providing some impossibility results for rankings in generalized tournaments (Csató 2019a, b) -there have been only few attempts to compare each player's contributions to the success of their own team (Vilain and Kolkovsky 2016) . Recently, some approaches using coalitional games and power indices have been applied to assess the performance of sportsmen based on outcomes of their team (Hernández-Lamoneda and Sánchez-Sánchez 2010; Hiller 2015) . Classical power indices, like the Shapley value/index (Shapley 1953) , are computed from such coalitional games to convert the performance of coalitions into an individual attribution representing each player's role in the team during the championship. Unfortunately, the high number of coalitions compared to the number of squads in a team actually playing matches, as well as the relatively low number of points (or goals) scored and conceded in each match, make the results obtained by the application of the Shapley value (Shapley 1953) very sensible to small fluctuations of team's outcome and very limited to the quantitative information provided by points and goals (Vilain and Kolkovsky 2016) . We argue that an ordinal approach based on rankings over coalitions is more effective in order to take hardly quantifiable attributes of performance (e.g., the ability to make a difference against strong teams, the leadership attitude during a match, or several other productivity dimensions related to the number of supporters, attraction of sponsors, etc.) into account and, at the same time, make the results about each player's contributions more robust to small fluctuations in the data.Of course, this kind of considerations about the robustness of the results hold in general for other sports and extend the discussion to other arguments in favor of more appropriate score-rates in relation to outcome uncertainty in sport competitions (Scarf et al. 2019) .

As far as we know, a notion of social ranking solution, defined as a mapping assigning to each ranking over subsets or coalitions of a set N a ranking over the single elements of N, has been introduced only recently in Moretti (2015) using a classical solution concept for cooperative games: the Banzhaf index (Banzhaf 1965) . However, in order to preserve the same ranking over N for all the characteristic functions representing the same ranking over the coalitions, the solution based on the Banzhaf index in Moretti (2015) must be applied to a very restricted domain. Differently, in Moretti and Öztürk (2017) , the authors analyze the individual ranking problem given a ranking over coalitions using a property-driven approach, showing that no social ranking solution satisfies a given set of attractive axioms. Following this approach, some social ranking solutions have been recently introduced in the literature. In Haret et al. (2018) , a social ranking solution has been proposed where two individuals are compared using information from subsets under a ceteris paribus principle (i.e., comparing coalitions which only differ for one single member). Another social ranking solution based on the idea of ordinal marginal contributions has been recently introduced and axiomatically characterized in Khani et al. (2019) . For a recent application of social ranking solutions as a qualitative approach to formalize the process to infer a norm system from the agents' preferences, see Serramia et al. (2020) .

A very relevant social ranking solution for our analysis is the lexicographic excellence (lex-cel) solution introduced in Bernardi et al. (2019) which is based on a lexicographic comparison of vectors representing the "positions" of single elements over a ranking of non-empty coalitions, and taking care to reward single elements that appear more frequently in the highest positions in the coalitional ranking.

In Bernardi et al. (2019) the authors show that the lex-cel solution is the unique social ranking solution that satisfies four appealing properties. The first one is Neutrality (N), a classical anonymity condition affirming that a social ranking solution should not depend on the individuals' identities. A second property, called Coalitional Anonymity (CA), requires that the relative ranking of two agents i and j should only depend on the relative positions of groups containing either i or j but not both. The third property is a tie-breaking condition based on a Monotonicity (M) principle saying that increasing the ranking of a coalition should break ties in favour of the members of the coalition. Finally, the fourth property, called Independence from the Worst Class (IWC), states that the relative position of elements of coalitions not in the lowest positions is more crucial.

In this paper we study new properties based on the idea of Coalitional Anonymity and Monotonicity that, in combination with Neutrality and Independence from the Worst Set axiom, axiomatically characterize new social ranking solutions more suitable for specific applications.

More precisely, on the one hand we provide a weaker version of the CA axiom with the objective to define a new axiom, called Weak Coalitional Anonymity (WCA), that restricts the invariance of the relative ranking of two agents i and j to coalitional rankings where the two agents appear in the same positions independently on whether they appear together or not. We argue that such a weaker property allows to focus on specific pieces of information about groups interaction that are more relevant in practice. We also weaken the WCA axiom focusing on the invariance with respect to permutations of coalitions containing the two agents that maintain the same position and the same size too. This axiom is called Super Weak Coalitional Anonymity (SWCA).

On the other hand, we strengthen the Monotonicity axiom with the objective to focus on more pertinent improvements of coalitions that should be considered to break ties. In one case, captured in the Improving Path Monotonicity (IPM) axiom, ties between two agents i and j are broken in favour of i when the number of coalitions containing i but not j improving their position is larger than the corresponding number of coalitions deteriorating their position. We argue that the IPM condition is useful to break ties when a history of improving and deteriorating contributions of individuals to coalitions is available. Alternatively, we strengthen the Monotonicity axiom adopting a tie-breaking criterion based on the size of the smallest improving coalition, a principle that leads to the axiom of Path Monotonicity with Priority to the Smallest Coalition (PMPSC) (or to it's weaker version also considering the number of improving and deteriorating coalitions, called Weak Path Monotonicity with Priority to the Smallest Coalition (WPMPSC)).

As main theoretical contributions, we first provide two alternative axiomatic characterizations of the lex-cel solution. The first one uses N, IWC, WCA and M. The second one consists of keeping N and WCA, removing M and IWC and adding IPM. Therefore, in the presence of N and WCA, IPM implies M and IWC. Then, we introduce and characterize two novel social ranking solutions, both incorporating the effect of the size of coalitions within the notion of lex-cel comparisons. The first solution (namely, L (1) ; see Definition 3) is uniquely identified by the combination of axioms N, IWC, SWCA and PMPSC, whereas the second one (namely, L (2) ; see Definition 4) is characterized by the combination of axioms N, IWC, SWCA, IPM and WPMPSC. Both solutions, L (1) and L (2) , embody the lexicographic principle of the lex-cel solution aimed at rewarding the excellence of coalitions, but they also consider their size, promoting smaller coalitions. More precisely, both solutions are based on a double lexicographic comparison of single elements' positions over the equivalence classes of a coalitional ranking: first, considering the frequency of single elements from the best equivalence class to the worst one; second, within an equivalence class, counting the number of coalitions of each size and taking care to reward the smaller ones. So, to determine the ranking of two single elements, the L (1) solution applies the lexicographic comparison with respect to the coalitional size in the best equivalence class presenting a difference in the number of coalitions of equal size containing one or the other element. Differently, the L (2) solution determines the ranking of two single elements based on either their respective frequency in the best equivalence class presenting a difference in the total number of coalitions containing one or the other element, or, their lexicographic comparison with respect to the coalitional size in the best equivalence class presenting the same number of coalitions containing one or the other element.

The roadmap of the paper is as follows. We start in the next section with some preliminary notation and notions. Then, in Sect. 3, we introduce the main properties used in this study and we discuss their possible interpretation and some logical dependencies. In Sect. 4, we derive some preliminary results about the combination of some of the axioms that will be useful for the following property-driven analysis of social ranking solutions. Section 5 is devoted to the main results of the paper in terms of axiomatic characterizations of the social ranking solutions. Section 6 is dedicated to the logical independence of the axioms used in the characterization results. Section 7 provides an illustration of the solutions applied to the comparison of football players in a real scenario. Section 8 concludes.

Let A be a finite set. The notation |A| stands for the cardinality of A.

. A preorder on A is a reflexive and transitive binary relation on A. A preorder that is also total is a total preorder.

Let N be a fixed and finite set of n agents. A coalition of agents is any subset of N. Denote by N the collection of the 2 n − 1 nonempty coalitions of N. A coalitional ranking on N is a total preorder ≿ on N . For any pair of coalitions S and T of N , S ≿ T means that S is at least as highly ranked as coalition T. We denote by ≻ the asymmetric part of ≿ and by ∼ its symmetric part.

The quotient set is the set of all equivalence classes E ≿ 1 , … , E ≿ k , k ∈ {1, … , 2 n − 1} , of ≿ . It is denoted by N ∕ ∼ and is totally ordered by the induced quotient relation ≻ * . Without loss of generality, assume that:

Let R N be the set of coalitional rankings that one can construct from the set of nonempty coalitions N , and let R N be the set of total preorders or rankings on N.

A social ranking solution on R N is a function f ∶ R N ⟶ R N which assigns to each coalitional ranking ≿∈ R N a unique ranking/total preorder f (≿) ∈ R N . We denote by ≻ f (≿) the asymmetric part of f (≿) and by ∼ f (≿) its symmetric part.

In this section, we introduce a set of properties that a solution should satisfy, and we discuss their interpretation along the lines of their possible application to the problem of ranking football players. Bernardi et al. (2019) introduce an axiom of coalitional anonymity. Let ∶ N ⟶ N be a permutation on the elements of N ; −1 stands for its inverse, and N denotes the set of such permutations. For each pair {i, j} of distinct agents in N, Bernardi et al. (2019) consider permutations on the subsets of coalitions containing neither i nor j. Denote by N⧵{i,j} this set of permutations. Coalitional Anonymity (CA) A social ranking solution f on R N satisfies Coalitional Anonymity if for each pair {i, j} of distinct agents in N, each ≿∈ R N , each permutation ∈ N⧵{i,j} and each alternative coalitional ranking ≿ � ∈ R N such that it holds that

The CA axiom says that the ranking between two agents i and j should be independent of the position in the ranking of coalitions containing both i and j, or neither i nor j, and invariant under a rearrangement preserving the relative comparisons of coalitions containing only one element between i and j. For the sake of the example of ranking football players, the CA property says that the relative ranking between two players i and j should be computed looking exclusively to the performance of coalitions containing either i or j (but not both), i.e. those coalitions where the pivotal role of the two players is evident from the score of the teams, and only the average team performance counts, no matter with whom the outcome is reached. For

instance, if we want to compare i and j within two distinct championships where, once extracted the ranking of such relevant coalitions containing only i or j, we observe that the two players appear in the same position but in different coalitions, then the ranking of the two players should be preserved over the two championships.

For more examples and interpretations related to this property see Bernardi et al. (2019) . One can argue that demanding the independence from the position of coalitions containing both i and j, or neither i nor j, is too strong. In this direction, one can weaken this condition imposing that the ranking between two players i and j is the same over two coalitional rankings if all positions of i and j are maintained over the two coalitional rankings.

Therefore, we introduce two new axioms of coalitional anonymity which are weaker than the CA one. To this end, we need some definitions.

Given a permutation ∈ N and a coalitional ranking ≿∈ R N , we define the coalitional ranking ≿ ∈ R N as follows: To contextualize the WCA axiom, suppose we want to compare two football attackers 1 and 2 based on their performance together and with a third attacker 3 under two alternative attacking game-patterns. Based on the outcome of matches when the team adopts a defensive tactic aimed at not conceding goals, a plausible coalitional ranking should consider low-size combinations of attackers more important, e.g. 1 , 1 ≻ 2 ≻ 12 ≻ 23 ≻ 13 ≻ 123 ≻ 3 , whereas a more offensive pattern could end-up in a coalitional ranking where larger combinations of attackers should be rewarded, e.g., 13

(1) = 13, (2) = 23, (12) = 123, (13) = 1, (23) = 2, (3) = 3 , so that ≻ is agent 1 and agent 2 invariant). Nevertheless, the two players 1 and 2 cover the same

positions over two coalitional rankings, the only change being the team-mates (so, over both coalitional rankings, player 1 results to be in the top-coalition, 2 is in the second-best one, both 1 and 2 in the third one and so on). As a consequence, there is no significant reason to expect a different ranking of 1 and 2 under two gamepatterns, and the WCA axiom states that 1 and 2 should be ranked in the same way over the two coalitional rankings corresponding to the two tactics. Next, we further weaken the WCA property by imposing that the invariance of the ranking of two players only occurs when the size of coalitions remain the same, other than the position of the two players in the coalitional ranking as for the WCA property.

Super Weak Coalitional Anonymity (SWCA) A social ranking solution f on R N satisfies Super Weak Coalitional Anonymity if for each pair {i, j} of distinct agents in N, each ≿∈ R N and each size invariant permutation ∈ * N which is also agent i and agent j invariant, it holds that: So, following the contextualizing example used for the WCA axiom, the SWCA axiom says that the invariance requested by WCA actually should be required only over permutations of coalitions that are also size invariant: this is particularly meaningful to compare football players when we are assuming that an equivalence of performance of individuals i and j may occur, under the same game-pattern tactic, when also the size of coalitions in the ranking is preserved, other than their positions with respect to i and j.

It must be clear that:

But the implication in the other direction does not hold true, as shown by the following example.

Example 1 Consider the social ranking solution f defined as:

On the one hand, for each permutation ∈ N which is size invariant, agent 1 invariant and agent 2 invariant, we necessarily have (N) = N and

. From this observation, we easily conclude that f satisfies Super Weak Coalitional Anonymity. On the other hand, if we consider a coalitional ranking ≿ such that Because is agent 1 invariant and agent 2 invariant, we conclude that f violates Weak Coalitional Anonymity.

It may be less immediate to see that Weak Coalitional Anonymity is a weaker axiom than Coalitional Anonymity, that is:

To show the above implication, it is convenient to reformulate the axiom of Coalitional Anonymity.

N⧵{i,j} and each alternative coalitional ranking ≿ � ∈ R N such that it holds that Proof Assume first that f satisfies the statement of Lemma 1. To see that f satisfies Coalitional Anonymity, it suffices to define (2) as the identity permutation.

Reciprocally, assume that f satisfies Coalitional Anonymity. Consider any pair {i, j} of distinct agents in N, any coalitional ranking ≿∈ R N , any pair of permutations { (1) , (2) } ⊆ 2 N⧵{i,j} and any alternative coalitional ranking ≿ � ∈ R N such that:

Next, consider another coalitional ranking ≿ ′′ satisfying the condition of Coalitional Anonymity with respect to (1) , that is 2 :

(1)

2 Such a coalitional ranking ≿ ′′ exists. To see this, consider the permutation ∈ N such that, for each S ∩ {i, j} = {i} , (S) = (1) (S ⧵ {i}) ∪ {i} , and (S) = S otherwise. Then, take ≿ �� =≿ and we are done.

On the other hand, (2) is rewritten as:

By (4) and (5) and the fact that (1) ( (1) ) −1 (S) = S , we obtain:

Thus, by Coalitional Anonymity, Combining the above equivalence with (3), we obtain:

showing that Coalitional Anonymity implies the statement of Lemma 1. This completes the proof of Lemma 1.

We are now prepared to prove that Weak Coalitional Anonymity is a weaker axiom than Coalitional Anonymity.

Proof Consider any social ranking solution f on R N satisfying Coalitional Anonymity. Consider any social ranking ≿∈ R N , any pair of distinct agents {i, j} ⊆ N and any permutation ∈ N which is agent i and agent j invariant. To show:

From , construct two permutations (1) and (2) in N⧵{i,j} as follows:

By definition of ≿ , we have:

we obtain:

Because f satisfies Coalitional Anonymity, by Lemma 1 we conclude that:

which completes the proof of Proposition 1.

Instead, it is possible to find a social ranking solution that satisfies WCA but not CA, as shown in the following example.

Example 2 Consider the social ranking solution f defined as:

On the one hand, for each permutation ∈ N which is agent 1 invariant and agent 2 invariant, we have:

From this and from the definition of f, we conclude that the latter satisfies Weak Coalitional Anonymity. On the other hand, take the permutation ∈ N such that:

Pick any coalitional ranking ≿ satisfying 3(a). By definition, we have

And, by definition of , we have:

. By definition of f we get:

If we take the identity permutation id ∈ 2 N⧵{1,2} , the above equivalence can be rewritten as:

It follows that id and ≿ satisfy the conditions of Coalitional Anonymity. By Coalitional Anonymity, we obtain:

which contradicts (6).

Let ∶ N ⟶ N be a permutation of the elements of N , −1 stands for its inverse, and N denotes the set of such permutations. For each S ∈ N , (S) denotes the subset of agents

Given a permutation ∈ N and a coalitional ranking ≿∈ R N , we define the coalitional ranking ≿ ∈ R N in the following way:

A social ranking solution f on R N satisfies Neutrality if for each ≿∈ R N and each ∈ N , it holds that:

The interpretation of the Neutrality axiom is trivial: any assessment of individual contributions should not depend on the name of football players (or on other personal attributes like the squad number, or the bank account).

1. A permutation can be viewed as a particular size invariant permutation in * N by considering the sets (S) , S ∈ N . With this convention, we have ≿ =≿ . 2. As a consequence of the previous point, if we consider the composition • , this means that is viewed as a permutation in * N .

On the other hand,

Thus, as asserted. 4. Assume that and pick any ∈ N . We have:

For the next axiom, already introduced in Bernardi et al. (2019), we need a definition. Consider any coalitional ranking ≿∈ R N . We say that the coalitional ranking

Because ≿ is a total preorder this is equivalent to say that:

Recall that the induced quotient relation ≻ * of coalitional ranking ≿∈ R N is such that:

A social ranking solution f on R N satisfies Independence from the Worst Class if for each ≿∈ R N and each refine-

The IWC axiom states that the performance of agents in coalitions placed in the highest positions is more important. So, if a decision about the (strict) ranking between two agents is taken, changing the relative ranking of coalitions in the lowest equivalence class should not affect the decision. This axiom is very interesting in the context of football players where, in general, the performance of a consistent number of coalitions of a squad cannot be really evaluated due to a lack of information (players of certain groups rarely play together or for very small fractions of time, or simply because the game-patterns implemented by the team management does not allow for such combinations of players; see Example 7 in this respect). In these cases, one possibility is to place coalitions

missing an evaluation in the last equivalence class of the coalitional ranking. Then, the IWC property states that such coalitions do not count if a decision concerning the comparison between two players has been already taken based on the performance of coalitions in higher positions. Ranking solutions should apply to different coalitional rankings in a coherent way. In this respect, moving from a coalitional ranking to a slightly different one, next axioms impose a restriction on how the individual ranking should change according to alternative notions of monotonicity. The next notation is central to construct a monotonicity principle.

Let ≿ and ≿ ′ be two coalitional rankings in R N and a coalition S 0 ∈ N . We say that ≿ ′ is obtained from ≿ through S 0 , if:

The next notion of monotonicity is a standard assumption that can be resumed in the very general principle that improving the performance of a coalition of individuals S ⊆ N should advocate in favour of the individuals in S to break ties among individuals (see Bernardi et al. (2019) for more details).

A social ranking solution f on R N satisfies Monotonicity if for each pair {i, j} ⊆ N of distinct agents, each coalition S 0 containing i but not j, each pair {≿, ≿ � } of coalitional rankings such that ≿ ′ is S 0 improving with respect to ≿ , it holds that:

However, in more dynamic frameworks where the interactions and the performance of coalitions evolve rapidly in time, it could be meaningful to look at a sequence of modifications of the position of coalitions applying in favour or to the detriment of a single individual i and without affecting another individual j.

Consider two coalitional rankings ≿ and ≿ ′ in R N and two distinct agents i and j. An ij -path between ≿ and ≿ ′ is a sequence (≿ ) t =−r of coalitional rankings in R N such that:

1. ≿ −r =≿ and ≿ t =≿ � ; 2. there is an associated sequence (S ) t−1 =−r of coalitions in N such that, for each ∈ {−r, … , t − 1} , S ∩ {i, j} = {i}; 3. for each ∈ {−r, … , −1} , ≿ +1 is S improving with respect to ≿ ; 4. for each ∈ {0, … , t − 1} , ≿ +1 is S deteriorating with respect to ≿ ;

5. each coalition S , ∈ {−r, … , t − 1} , belongs to the same equivalence class of ≿ 0 ;

Example 3 Consider the coalition ranking ≿ on N = {1, 2, 3} such that:

We construct the 23-path

Therefore, the coalitional ranking ≿ 0 is S −1 improving with respect to ≿ −1 =≿ , the coalitional ranking ≿ 1 is S 0 deteriorating with respect to ≿ 0 , and the coalitional ranking ≿ 2 is S 1 deteriorating with respect to ≿ 1 . Finally, note that the coalitions involved in the 23-path belong to the same equivalence class of ≿ 0 , namely E ≿ 0 1 .

The next three axioms are based on the notion of ij-paths. The first axiom, called Improving path monotonicity, reflects the following principle. Suppose that an ij-path exists between two coalitional rankings ≿ and ≿ ′ such that there are more improving moves than deteriorating ones. So, the number of improving moves prevails over the number of deteriorating moves. The principle says that if agent i is at least highly ranked than agent j in f (≿) , then i should be strictly better ranked than j in f (≿ � ).

A social ranking solution f on R N satisfies Improving path monotonicity if for each pair {i, j} ⊆ N of distinct agents and each ij-path (≿ ) t =−r ⊆ R N such that r > t , it holds that:

Remark 2 It must be noted that for IPM and for the two following axioms of path monotonicity, the order on which the coalitions are used to construct the path does not matter, provided that, along the path, the index of each improving coalition is lower than the index of each deteriorating coalition. So, the only relevant parameters are the set of improving coalitions and the set of deteriorating coalitions, with a priority in the path for the improving coalitions.

Consider for instance a football team management that must update the information about groups' performance after each match of championship. Suppose that, at the original time t 0 (beginning of the championship season), a player i is at least as strong as another individual j based on a given social ranking solution applied to the current coalitional ranking. Now, based on the new evaluation

after the new match, the team management recognizes that a coalition containing individual i (but not j) improves the position in the coalitional ranking. Match after match, the team management take a record of all the improvements of coalitions containing i (but not j), as well as the record of coalitions that eventually deteriorate their position, with respect to an original coalitional ranking used as a reference. It's then extremely tempting to take into account this history of improvements or deteriorations to end up with an individual comparison keeping into account players pivotal role along the championship season. One simple way to do it is to look at the number of improvements r and deteriorations t of a player i and, at the end of the season, break an eventual tie between i and j in the original ranking (the previous season) according to the comparison between r and t (in favour of i if r > t ), provided that all improvements and deteriorations are performed on a comparable ordinal scale, i.e., all improvements of coalitions end up in the same equivalence class of some benchmark ranking ≿ 0 ; and all deteriorations of coalitions start from this equivalence class of ≿ 0 as well (see Point 5 in the definition of ij-path). This intuition brings to the above IPM axiom.

Note that Improving Path Monotonicity is a stronger axiom than Monotonicity, that is, To see this, it suffices to set r = 1 and t = 0 in the ij-path.

Of course IPM is not the only way to break possible ties in the original coalitonal ranking. Under some dominant game-pattern tactic adopted by the team, the team management could argue that it is not the number of improving or deteriorating moves that makes the difference between two equivalent players, but actually the size of the smallest coalition generating an improvement (leading to definition of the PMPSC axiom below), or that such a size-based criterion to break ties should apply only if the number of improving moves equals the number of deteriorating ones (leading to the WPMPSC axiom below).

More precisely, the next axiom focuses on the size of the coalitions we use in an ij-path and not on the number of improving moves compared to the deteriorating moves. Assume that two coalitional rankings ≿ and ≿ ′ are connected through an ij-path. Assume further that among the coalitions we use in the improving moves, one of them, say the first one S −r , contains strictly less elements than the coalitions we use in the deteriorating moves. The principle indicates that if agent i is at least highly ranked than agent j in f (≿) , then i becomes strictly better ranked than j in f (≿ � ) . Reciprocally, assume that S t−1 contains strictly less elements than each coalition we use in the improving moves. The principle indicates that if agent j is at least highly ranked than agent i in f (≿) , then j becomes strictly better ranked than i in f (≿ � To see this, it suffices to set r = 1 and t = 0 in the definition of an ij-path. Note also that neither Path Monotonicity with Priority to the Smallest Coalition implies Improving Path Monotonicity nor it is implied by Improving Path Monotonicity. The last axiom is a weak version of Path Monotonicity with Priority to the Smallest Coalition. It only says something when an ij-path contains an equal number of improving and deteriorating moves. In such a case, a priority is still given to the smallest coalition. 

Given a coalitional ranking ≿∈ R N and an agent i ∈ N , we construct the matrix M ≿,i of size (n, k) where each entry M ≿,i pq denotes the number of coalitions of size p ∈ {1, … , n} containing i in the equivalence class E ≿ q , q ∈ {1, … , k} . For each p, it holds that:

For each pair {i, j} ⊆ N , each equivalence class E ≿ q and each size p ∈ {1, … , n} , define the subsets of coalitions:

We have:

Path Monotonicity with Priority to the Smallest Coalition ⟹ Monotonicity .

if (≿) Case 3 S ∈ E j,ī,p q . This case is similar to the previous case.

From the above three cases, we deduce that

By the fact that ( • ≿,ij ) is a bijective function as a composition of two bijective functions, we obtain the desired result:

By point 4 of Remark 1, which proves that the quotient order ≻ * • ≿,ij coincides with the quotient order ≻ * . Thus, we obtain the desired result (≿ ≿,ij ) =≿.

Proof Let f be as hypothesized. Pick any coalitional ranking ≿∈ R N and any two distinct agents i and j in N such that M ≿,i = M ≿,j . First, consider the permutation ∈ N such that (i) = j , (j) = i and ( ) = for each ∈ N ⧵ {i, j} . Next, consider a size invariant permutation ≿,ij ∈ * N as in Definition 1. By Super Weak Coalitional Anonymity, By Neutrality, and so, by definition of , jf ((≿ ≿,ij ) )i . By Lemma 2, (≿ ≿,ij ) =≿ . Therefore, we conclude that and so i ∼ f (≿) j , which completes the proof of Proposition 2.

Step 2 of the proof of Theorem 1) by using Neutrality and Coalitional Anonymity.

Proposition 3 (Bernardi et al. (2019) ) Let f be a social ranking solution R N satisfying Neutrality and Coalitional Anonymity. For each ≿∈ R N , it holds that:

To understand the differences between both results, recall that Coalitional Anonymity is a stronger axiom than Super Weak Coalitional Anonymity. As a consequence,

[if (≿ ≿,ij 

Bernardi et al. (2019) can assume a weaker condition on M ≿,i and M ≿,j than ours to obtain the indifference between i and j. In the present case, the condition is weaker than the condition M ≿,i pq = M ≿,j pq . On the other hand, because our axiom of Super Weak Coalitional Anonymity is weaker than the axiom of Coalitional Anonymity, we need to assume a stronger condition on M ≿,i and M ≿,j to obtain the indifference between i and j. Nevertheless, it turns out that Coalitional Anonymity can be replaced by the weaker axiom of Weak Coalitional Anonymity in the statement of Proposition 3.

The proof of Proposition 4 follows similar steps as the proofs of Lemma 2 and Proposition 2, and so is omitted. The main difference is that we have to consider bijections of the following form:

where These bijections exist since, by hypothesis, where, similarly as before, Therefore, Proposition 4 is stronger than Proposition 3 obtained in Bernardi et al. (2019) .

We introduce three social ranking solutions for coalitional rankings. One of them is the Lexicographic excellence solution studied in Bernardi et al. (2019) , the two other are new.

In the sequel, for each q ∈ {1, … , k} , the notation M ≿,i q stands for the sum of the elements M ≿,i pq , p ∈ {1, … , n} , that is

The Lexicographic excellence solution L on R N is defined as:

In words, agent i has a strictly better ranking than agent j in a coalitional ranking ≿ if, starting from the best equivalence class E ≿ 1 , one can find an equivalence class E ≿ q 0 where the number of coalitions containing i is strictly greater than the number of coalitions containing j. Otherwise, if for each equivalence class E ≿ q , q ∈ {1, … , k} , the number of coalitions containing i is equal to the number of coalitions containing j, then both agents have the same rank under L. The Lexicographic excellence solution does not take into account the size of the coalitions to which an agent is a member. The next two solutions incorporate a size effect.

In words, for any two distinct agents i and j, we explore the first equivalence class E ≿ 1 . If, for each coalition of size p ∈ {1, … , n} , the number of coalitions containing i is equal to the number of coalitions containing j, then we move to the next equivalence class E ≿ 2 . We repeat the exploration until we reach an equivalence class E ≿ p 0 q 0 , agent i has a strictly better rank than agent j in the coalitional ranking ≿ . Otherwise, if for each equivalence class E ≿ q , q ∈ {1, … , k} , and each coalition size p ∈ {1, … , n} , the number of coalitions containing i is equal to the number of coalitions containing j, then L (1) indicates that both agents have the same rank in the coalitional ranking ≿.

The solution L (2) on R N is defined as follows: i ≻ L (2) (≿) j if there is (p 0 , q 0 ) ∈ {1, … , n} × {1, … , k − 1} such that:

In words, for any two distinct agents i and j, we explore the first equivalence class E ≿ 1 . If, for each coalition size p ∈ {1, … , n} , the number of coalitions containing i is equal to the number of coalitions containing j, then we move to the next equivalence class E ≿ 2 . We repeat the exploration until we reach an equivalence class E ≿ q 0 and a coalition size p 0 ∈ {1, … , n} such that the number M ≿,i p 0 q 0 of coalitions of size p 0 containing i is different from the number M ≿,j p 0 q 0 of coalitions of size p 0 containing j. At this step (which corresponds to point 2 of the definition), two cases can be distinguished:

(2.1) the number M ≿,i q 0 of coalitions containing i is different from the number of coalitions M

q 0 , then agent i has a strictly better rank than agent j in the coalitional ranking ≿;

(

, agent i has a strictly better rank than agent j in the coalitional ranking ≿.

Otherwise, that is, if such a pair (p 0 , q 0 ) does not exist in ≿ , the two matrices M ≿,i and M ≿,j are identical, and L (2) indicates that i and j are equivalent agents in the coalitional ranking ≿.

To fix the ideas, the next example shows a coalitional ranking where the three solutions L, L (1) and L (2) generate different rankings on the elements of N.

Example 4 Consider the coalitional ranking ≿∈ R N with N = {1, 2, 3, 4} such that for any other S ⊆ N not previously listed in the ranking and such that and Then, By Definition 2, we have that 2 ≻ L (≿) 1 ∼ L (≿) 3 ≻ L (≿) 4 , whereas, by Definition 3, we have 1 ≻ L (1) (≿) 2 ≻ L (1) (≿) 3 ≻ L (1) (≿) 4 and, finally, by Definition 4, 2 ≻ L (2) (≿) 1 ≻ L (2) (≿) 3 ≻ L (2) (≿) 4.

The main result of the paper provides comparable axiomatizations of the above three social ranking solutions. In particular, point 1(a) in Theorem 1 below provides a stronger axiomatic characterization of the lex-cel solution L than the one contained in Theorem 1 in Bernardi et al. (2019) .

1. The social ranking solution L is the unique solution on R N satisfying Neutrality, Weak Coalitional Anonymity (WCA), and one of the following set of axioms:

(a) Independence from the Worst Class (IWC) and Monotonicity (M); (b) Improving Path Monotonicity (IPM).

Proof Point 1.a. The proof is similar to step 3 in Theorem 1 in Bernardi et al. (2019) except that Proposition 4 is used instead of Proposition 3. So, the details of the proof are omitted. Point 1.b. Obviously, the solution L also satisfies Improving Path Monotonicity. Conversely, consider a solution f on R N that satisfies Neutrality, Weak Coalitional Anonymity, and Improving Path Monotonicity. Pick any two distinct agents i and j in N and a coalitional ranking ≿∈ R N such that i ≻ L (≿) j . For the rest of the proof, recall that the sets of coalitions E j,ī q and E j,ī q are defined as follows:

Because i ≻ L (≿) j , there exists an integer q 0 such that, for each q < q 0 , it holds that

This implies the following facts:

Next, consider an ij-path (≿ ) t =−r satisfying the following conditions:

q , there exists a unique ∈ {−r, … , −1} such that S = S , the coalitional ranking ≿ +1 is S improving with respect to ≿ and S ∈ E ≿ 0 q 0 ; 3. to complete the ij-path, note that:

where the last equality follows from the above point 2. of the ij-path. Therefore, there is a one-to-one mapping from which one can define the deteriorating moves. Precisely, for each coalition S = (T) , there exists an integer ∈ {0, … , t − 1} such that S = S and ≿ +1 is S deteriorating with respect to ≿ . Furthermore, thanks to the existence of , one can force that S ∼ +1 T.

From facts (b) and (c), we get r < t . By construction, the last coalitional ranking ≿ t of the ij-path satisfies:

Thus, by Proposition 4, we have i ∼ f (≿ t ) j.

By considering the reverse ij-path, i.e., the ij-path from ≿ t to ≿ −r =≿ , we get an improving path since t > r . By Improving Path Monotonicity, it follows that i ≻ f (≿ −r ) j , i.e., i ≻ f (≿) j . All in all, we have shown that:

Finally, if i ∼ L (≿) j , then, by Proposition 4, it holds that i ∼ f (≿) j . Conclude that f coincides with L, the desired result.

To prove point 2 and point 3, we will use another procedure that we detail below. First, we need a definition. Define the following lexicographic order ≤ L on the pairs (p,

where n is the number of agents and k is the number of equivalence classes in a coalition ranking ≿∈ R Ω N .

Procedure. Consider any coalitional ranking ≿∈ R Ω N and any two distinct agents i and j in N. Assume that M ≿,i ≠ M ≿,j . Pick the least pair (p 0 , q 0 ) with respect to ≤ L such that M ≿,i

p 0 ,q 0 . From ≿ , construct another coalitional ranking ≿ ′ containing q 0 + 1 equivalence classes with the following induced quotient order ≻ � * :

where By construction, for each q ≤ q 0 , the q-th column of M ≿ ′ ,i is equal to the q-th column of M ≿ ′ ,j . Thus, by (7), it holds that:

In particular, by construction and definition of (p 0 , q 0 ), (≿) . Consider any two distinct agents i and j in N. Several cases arise.

Case 2.1 M ≿,i = M ≿,j . By Proposition 2, i ∼ f (≿) j and i ∼ L (1) (≿) j.

Priority to the Smallest Coalition. By Weak Path Monotonicity with Priority to the Smallest Coalition, From Cases 3.1-3.2, we hereby conclude that i ∼ f (≿ �� ) j implies i ≻ f (≿ � ) j . By construction, ≿ is a refinement of ≿ ′ obtained from the last equivalence class E ≿ � q 0 +1 that we divide into the equivalence classes E ≿ q 0 +1 , … , E ≿ k . Thus, by Independence from the Worst Class, In short, we have shown the following implication:

From this point on, the proof is similar to the last part of the proof of point 2, and so is omitted. We finally obtain f (≿) = L (2) (≿) . This completes the proof of point 3.

We prove that the axioms used in points 1(a), 1(b), 2 and 3 of Theorem 1 are logically independent. Without loss of generality, assume in the sequel that N = {1, … , n}.

Neutrality is not satisfied. 

Because the solution f I violates Monotonicity, it also violates Path Monotonicity with Priority to the Smallest Coalition.

Weak Path Monotonicity with Priority to the Smallest Coalition is not satisfied. The solution L satisfies Neutrality, Super Weak Coalitional Anonymity, Improving Path Monotonicity, Independence from the Worst Class, but violates Weak Path Monotonicity with Priority to the Smallest Coalition because it is not influenced by the size of the coalitions involved in an ij-path. Furthermore, if the number of improving moves is equal to the number of deteriorating moves along an ij-path, then the relative ranking of the pair {i, j} is not changed under L.

Independence from the Worst Class is not satisfied. We introduce the transpose of the solution L (1) which relies on the same principle as L (1) except that it first explores the lines of the matrices M ≿,i , i ∈ N , instead of their columns. This results in the following solution (L (1) ) T defined as follows:

The social ranking solution (L (1) ) T satisfies Neutrality, (Super) Weak Coalitional Anonymity, Path Monotonicity with Priority to the Smallest Coalition, but obviously violates Independence from the Worst Class.

(Super) Weak Coalitional Anonymity is not satisfied. From L (1) and L (2) , we construct two associated social ranking solutions. To this end, for each ≿∈ R N and each i ∈ N , define as the set of agents belonging in a coalition of size two containing i in the best equivalence class of ≿ . For each r ∈ {1, 2} , let L (r) * be the social ranking solution on R N defined as follows: i ≻ L (r)

and, i ∼ L (r) * (≿) j otherwise. Note that these solutions induce total preorders on the agent set, as required by the definition of a social ranking solution.

For each r ∈ {1, 2} , L (r) * satisfies all the axioms satisfied by L (r) except Super Weak Coalitional Anonymity. To see this, consider a coalitional ranking ≿∈ R 

tional Anonymity is violated. In particular, this implies that each L (r) * does not satisfy Weak Coalitional Anonymity. We also note that L (1) * satisfies Neutrality, Independence from the Worst Class, Improving Path Monotonicity, and so Monotonicity, but violates Super Weak Coalitional Anonymity, and so violates Weak Coalitional Anonymity. Thus, Neutrality, Independence from the Worst Class and Monotonicity do not imply Weak Coalitional Anonymity. This remark is useful to show the logical independence of point 1(a).

As an example of application of the different social ranking solutions introduced in this paper, we analyze the performance of four attacking players of the Paris Saint Germain (PSG) team during the eight matches of Champions League played during the season 2019/2020 (temporarily suspended on March 2020 for the covid-19 emergency). At this time, the PSG boss Thomas Tuchel faces a selection dilemma when he must select among the four attacking stars Di María (D), Icardi (I), Mbappé (M) and Neymar (N). Attempting to provide a ranking of the individual contributions of the four players during the last eight matches of Champions League, we considered all different subsets of the four stars, and we assessed some relevant parameters like the total number of points scored p, the number of goals scored s and the one of goals conceded c by those groups when employed together in a match. These parameters are reported in Table 1. A coalitional ranking has been computed according to a lexicographic comparison of vectors (p, s, −c) . The negative sign for parameter c represents the fact that a smaller number of goals conceded is preferred; furthermore, all coalitions not employed during these matches have been provided with vectors (0, 0, 0) and then classified in the worst equivalence class of the coalitional ranking. Therefore we obtain:

for each other S ⊆ {D, I, M, N} (which are all in the same worst equivalence class). In such a case, we have that 

The importance about of ranking groups/agents has been arisen in numerous areas and it is of big interest in many settings. The subject of ranking sets over the set of all subsets of an agent set N as a modeling tool for choice from a ranking over the single elements of the set N has been exhaustively studied in the literature (see, for instance, Kannai and Peleg (1984) or Barberà et al. (2004) for a survey).

In this paper, we focus on ranking the single elements of the set N from a ranking of the subsets of N, i.e., we focus on how to categorize agents or items taking into account the classification of groups.

In Bernardi et al. (2019) , the authors introduced the Lexicographic excellence (lex-cel) solution based on the idea of a lexicographic comparison of vectors where the individuals that are in the more highly scored groups are rewarded. However, in certain contexts, it would be more advisable considering to participate in excellent groups with a determined size. Integrate this feature in the idea of lexicographic excellence solution can enrich and improve the output in certain frameworks. With this purpose, we formulate desirable principles in the given context, and look for identifying social rankings satisfying combinations of them. Next, two novel social rankings are presented. Unlike of the lexicographic excellence solution, these two new solutions incorporate the effect of the size of coalitions on them. Finally, a new characterization for the lex-cell solution is given, and to highlight the essential difference among this solution and the two new solutions, comparable characterizations of these three solutions is provided. A summary of the axiomatic characterization of the solutions studied in this paper, together with the results provided by the analysis of the logical independence of the axioms used in such characterizations, is presented in Table 2 .

As we already noticed, the IWC axiom penalizes the elements that are members of worst groups. Although ranking individuals based on their excellence is, in general, appealing, one could argue that a dual formulation of the IWC axiom rewarding mediocrity could be more appropriate, for instance, if the objective of a social ranking is triggering a competition at the lowest level (e.g., to boost the reserve players for a promotion to the first team). In this direction, already introduced in Bernardi et al. (2019), a new axiom, Independence of the Best Class (IBC), can be formulated by considering, in the definition of the IWC axiom, any refinement obtained from the first equivalence class of a coalitional ranking, instead of any refinement from the last equivalence class. In words, the IBC axiom implies that the performance of agents in coalitions placed in the best position is less important. Thus, if a decision about the (strict) ranking between two agents is taken according to a solution satisfying the IBC axiom, any change in the relative ranking of coalitions in the best equivalence class should be ignored (see Bernardi et al. (2019) for more details). Of course, such solutions would not satisfy any more the axioms involving the notion of ij-path introduced in this paper. To characterize such solutions, it suffices to introduce new axioms of path monotonicity by considering first the sequence of deteriorating coalitions, and then the sequence of improving coalitions.

However, there are many other challenging aspects that we will analyze in future research. In fact, a more realistic assumption, in many contexts, would be to consider a set of feasible coalitions F of N instead of the set of all subsets of N. To illustrate it, consider a network of associated editors in the editorial boards of journals in a Table 2 A summary of the axioms that are satisfied by the social ranking solutions considered in this paper certain area. Usually, there are some associated editors who are members of the editorial board of several journals in the field. This network has the structure of a union stable system as introduced in Algaba et al. (2000) where the editorial boards of associated editors in the considered set of journals form the basis of a union stable system or the so called supports. It would be of interest, for instance, to have a tool to analyze editorial board members performance, where set rankings come into play because journals need to rank sets based on their individual rankings and also the inverse problem how to rank associated editors of a certain set of journals according to the coalitional ranking over their editorial boards. More specifically, starting from a ranking over the elements of N to obtain a ranking of the set of feasible coalitions of N and also the inverse problem as dealt with this paper when the domain is F . Therefore, it will be specially appealing to look for social rankings when the set of feasible coalitions has a special structure, for instance, as mentioned in the above example, when focusing on union stable systems which are the more general structures reflecting communication and constitute a refinement of hypergraphs (see Algaba et al. (2004) ) and an extension of the set of connected coalitions of an undirected graph, or of the set of winning coalitions in a voting game as studied in Algaba et al. (2019) (see also Algaba et al. (2015) ) or of the particular class of antimatroids (see Dilworth (1940) and Edelman and Jamison (1985) ) which would take into account the hierarchical features in the set of feasible coalitions, or the more particular case derived from the conjunctive or disjunctive approach (see Gilles et al. (1992) and van den Brink (1997) ). Also, it will be compelling to consider structures which integrate, simultaneously, both communication and hierarchical properties as accessible union stable systems (see Algaba et al. (2018) ), among others. So, given a set of feasible coalitions, further research will include the presentation of rankings in this context, as well as the analysis of how the properties of the set of feasible coalitions could influence the axioms which characterize them.

Accordingly, we would have a new coalitional ranking ≿ ′ such that for all other S (which are all in the same worst equivalence class). Now, we have that So, now, I and D are ranked indifferently according to L (i.e., I ∼ L(≿ � ) D )

The position value for union stable systems

The position value in communication structures

Harsanyi power solutions for games on union stable systems

Network structures with hierarchy and communication

Harsanyi power solutions for cooperative games on voting structures

Weighted voting doesn't work: a mathematical analysis

Ranking sets of objects. Handbook of utility theory

Ranking objects from a preference relation over their subsets

An impossibility theorem for paired comparisons

Some impossibilities of ranking in generalized tournaments

UEFA Champions League entry has not satisfied strategy proofness in three seasons

The incentive (in)compatibility of group-based qualification systems

When neither team wants to win: a flaw of recent UEFA qualification rules

Tournament design: How operations research can improve sports rules

Winning by losing: incentive incompatibility in multiple qualifiers

Lattices with unique irreducible decompositions

The theory of convex geometries

Games with permission structures: the conjunctive approach

Ceteris paribus majority for social ranking

Rankings and values for team games

The importance of players in teams of the German Bundesliga in the season 2012/2013 -A cooperative game theory approach

A note on the extension of an order on a set to the power set

An ordinal banzhaf index for social ranking

An axiomatic approach to social ranking under coalitional power relations

Some axiomatic and algorithmic perspectives on the social ranking problem

Can strategizing in round-robin subtournaments be avoided?

On outcome uncertainty and scoring rates in sport: the case of international rugby union

A qualitative approach to composing valuealigned norm systems

A value for n-person games

An Axiomatization of the disjunctive permission value for games with a permission structure

Estimating individual productivity in football

Strategic manipulation in tournament games

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations

We would like to thank two anonymous referees and an associate editor for specific comments that led to substantial improvements of an earlier version of the paper. Financial support from research programs IDEX Lyon from University of Lyon (project IN-DEPTH ) within the "programme Investissements d'Avenir" (ANR-16-IDEX-0005), "Mathématiques de la décision pour l'ingénierie physique et sociale" (MODMAD), the Ministerio de Ciencia, Innovación y Universidades (MCIU), the Agencia Estatal de Investigación (AEI), the Fondo Europeo de Desarrollo Regional (FEDER) under the project PGC2018-097965-B-I00, and from the ANR project THEMIS (ANR-20-CE23-0018) is gratefully acknowledged.

 ≿,j . Without loss of generality, assume first that i ≻ L (1) (≿) j and let the pair (p 0 , q 0 ) ∈ {1, … , n} × {1, … , k − 1} as given in Definition 3. Note that the choice of (p 0 , q 0 ) in Definition 3 is unique and corresponds to the choice of the least pair (p 0 , q 0 ) with respect to ≤ L such that M ≿,i p 0 ,q 0 ≠ M ≿,j p 0 ,q 0 in the Procedure. By definition of the rule L (1) , i ≻ L (1) (≿) j means M ≿,i p 0 ,q 0 > M ≿,j p 0 ,q 0 . From ≿ , we construct ≿ ′ and ≿ ′′ as indicated in the Procedure. Because the coalitional ranking ≿ ′′ is such that M ≿ �� ,i = M ≿ �� ,j , apply Proposition 2 to conclude that i ∼ f (≿ �� ) j . Next, note that there exists an ij-path (≿ ) t =−r from ≿ ′′ to ≿ ′ satisfying the condition of Path monotonicity with priority to the smallest coalition. Indeed, from ≿ ′′ , first use the set of coalitions involved in point (a) of the Procedure to define improving moves. Set ≿ −r =≿ �� . The first successor of ≿ ′′ along the path is a coalitional ranking ≿ −r+1 obtained by moving one of the M ≿ � ,i p 0 ,q 0 − M ≿ � ,j p 0 ,q 0 coalitions of size p 0 from the equivalence class E ≿ �� q 0 +1 to the equivalence class E ≿ ′′ q 0 . This constitutes the first improving move along the path. From ≿ −r+1 , continue in this manner for each coalition of size p 0 , and then for each coalition of size p > p 0 involved in point (a). We reach a coalitional ranking ≿ 0 where all coalitions involved in improving moves (the coalitions considered in point (a)) now belong to the same equivalence class E ≿ 0 q 0 . Along this part of the sequence, coalitions involved in point (b) of the Procedure have not be moved and so also belong to. From ≿ 1 , continue in this way until all coalitions in point (b) have been exhausted. At this step, ≿ ′ is reached. Because there is no coalition of size strictly less than p 0 involved in the ij-path, the latter satisfies the condition of Path Monotonicity with Priority to the Smallest Coalition. By Path Monotonicity with Priority to the Smallest Coalition, we have: By construction, ≿ is a refinement of ≿ ′ obtained from the last equivalence classThus, by Independence from the Worst Class, In short, we have shown the following implication:Reciprocally, consider the case i ≻ f (≿) j . For the sake of contradiction, assume first that i ∼ L (1) (≿) j . By Definition 3 of L (1) , M ≿,i = M ≿,j . By Proposition 2, we obtain i ∼ f (≿) j , which contradicts the fact that i ≻ f (≿) j . The relation j ≻ L (1) (≿) i is also impossible since we have just seen above that j ≻ L (1) (≿) i implies j ≻ f (≿) i . The only possibility is thus i ≻ L (1) (≿) We conclude that ≿ f (≿) =≿ L (1) (≿) . This completes the proof of point 2.Point 3. The fact that L (2) satisfies Neutrality, Super Weak Coalitional Anonymity, Independence from the Worst Class, Improving Path Monotonicity and Weak Path Monotonicity with Priority to the Smallest Coalition follows directly from the definition of L (2) . Regarding the uniqueness part, consider any solution f on R Ω N satisfying Neutrality, Super Weak Coalitional Anonymity, Independence from the Worst Class, Improving Path Monotonicity and Weak Path Monotonicity with Priority to the Smallest Coalition. Pick any coalitional ranking ≿∈ R . To show: f (≿) = L (2) (≿) . Consider any two distinct agents i and j in N. In a similar way as in point 2., if M ≿,i = M ≿,j , then, by Proposition 2, i ∼ f (≿) j and i ∼ L (2) (≿) j . So, assume that M ≿,i ≠ M ≿,j . Without loss of generality, assume first that i ≻ L (2) (≿) j and let the pair (p 0 , q 0 ) ∈ {1, … , n} × {1, … , k − 1} as given in the Procedure. From ≿ , we construct ≿ ′ and ≿ ′′ as in the Procedure. Again, because the coalitional ranking ≿ ′′ is such that M ≿ �� ,i = M ≿ �� ,j , apply Proposition 2 to conclude that i ∼ f (≿ �� ) j . At this step, by Definition 4 of the rule L (2) , two cases arise. From this observation, we deduce that there is an ij-path from ≿ ′′ to ≿ ′ satisfying the conditions of Improving Path Monotonicity, that is an ij-path (≿ ) t =−r such that the number of improving moves is strictly greater than the number of deteriorating moves. Indeed, and as in point 2., start from ≿ ′′ and use the set of coalitions involved in point (a) to define improving moves up to the coalitional ranking ≿ 0 . In the coalitional ranking ≿ 0 , all coalitions involved in improving moves (the coalitions considered in point (a)) now belong to the same equivalence class E ≿ 0 q 0 . Along this part of the sequence, coalitions involved in point (b) have not be moved and so also belong to E ≿ 0 q 0 . Then, from ≿ 0 use the set of coalitions involved in point (b) to define deteriorating moves up to the coalitional ranking ≿ ′ . Because M ≿ ′ ,i q 0 > M ≿ ′ ,j q 0 , the number of improving moves using coalitions as in point (a) is strictly greater than the number of moves using coalitions as in point (b), as specified by Improving Path Monotonicity. By Improving Path Monotonicity, we obtain:p 0 q 0 as in point 2.2 of Definition 4. Note that this pair (p 0 , q 0 ) corresponds to one chosen above. Once again, we have M ≿ � ,i q 0 = M ≿ � ,j q 0 . By points (a) and (b) of the construction of ≿ ′′ and (9), it follows that the number of improving moves is necessarily equal to the number of deteriorating moves along the ij-path. Furthermore, there is no coalition of size strictly less than p 0 involved in the ij-path. Therefore the ij-path associated with the Procedure satisfies the conditions of Weak Path Monotonicity with