Skip to main content
Top
Published in: Social Choice and Welfare 3/2024

Open Access 23-01-2024 | Original Paper

Consistent social ranking solutions

Authors: Takahiro Suzuki, Masahide Horita

Published in: Social Choice and Welfare | Issue 3/2024

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The performance of coalitions is an important measure for evaluating individuals. Sport players, researchers, and firm workers are often judged with their team performances. The social ranking solution (SRS) is a function that maps the ranking on the set of all feasible coalitions (the domain of coalitions) into the ranking of individuals. Importing the axiom of consistency from voting theory, we study consistent SRSs under the variable domains of coalitions. We suppose that there are several domains of coalitions (e.g., a set of research teams made up of only young researchers and a set of research teams including senior researchers), and the individuals are required to be evaluated consistently on each domain of coalition. Such a situation is typical because all the logically possible coalitions are often too huge to deal with. We obtain a new characterization of the lexicographic excellence solution (LES) and its dual (DLES): they are the only SRSs satisfying consistency, neutrality, weak coalitional anonymity, and complete dominance. This characterization is expected to provide a new ground for determining the impacts of individuals based on the lexicographic comparisons of their team performances.
Notes

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

The ordinal social ranking problem (SRP) is the search of the ordinal ranking of individuals based on the ordinal ranking of their coalitions; such as the evaluation of researchers based on their collaborative papers or that of individual workers based on their team performances. While the origin of such a study can be traced back to classic cooperative game theory, like the Shapley value (Shapley 1953), it is only recently that its ordinal counterpart was developed in Moretti and Öztürk (2017). To date, several social ranking solutions (SRSs) for the SRP have been axiomatically characterized. Haret et al. (2019) characterizes ceteris paribus majority (CP majority); Khani et al. (2019) characterizes ordinal Banzhaf index (OBI); and Bernardi et al. (2019) and Algaba et al. (2021) characterize lexicographic excellence solution (LES). The LES is an SRS that evaluates candidates by searching their coalitions from the top to the bottom in the ranking of coalitions. Candidate x is judged to be at least as good as y if it appears more often in the higher ranked coalitions.
The present paper’s contribution lies in importing the idea of consistency from the standard voting theory into the study of the SRP and in giving a new characterization of the LES and dual LES (DLES). Specifically, we characterize the LES and DLES as the only SRSs satisfying consistency (CON), complete dominance (CD), neutrality (N), and weak coalitional anonymity (WCA) (Theorem 1). In the literature on the LES, Bernardi et al. (2019) have characterized the LES by N, coalitional anonymity (CA), monotonicity, and independence from the worst class. Following this, Algaba et al. (2021) weakened CA and M to get a series of characterizations of lexicographic solutions including the LES. Béal et al. (2022) also introduces two new lexicographic solutions with their characterizations.
A novelty of this study is that we consider multiple sets of feasible coalitions (domains of coalitions); in other words, the domain of coalitions on which SRSs is formulated is assumed to be variable. To the best of our knowledge, this is the first analysis of the SRP under variable domains of coalitions. When evaluating researchers, for example, we usually do not consider all the logically possible coalitions, which is often too colossal to deal with and has little practical sense; rather, we usually consider only a small number of existing coalitions from practical viewpoints (ages, affiliations, etc.). Therefore, our model studies the relationship of judgements on such multiple domains of coalitions.
Consistency, in the standard social choice theory, demands that social choices/rankings of a society N should be related properly with those of partitioned societies, \(N_{1}\) and \(N_{2}\) (with \(N_{1} \cap N_{2} = \phi\) and \(N_{1} \cup N_{2} = N\)). However, our CON considers the partition of the domain of coalitions, rather than of a partition of societies. For instance, consider two domains of coalitions as (a) the set of all research teams made up of only young researchers, and (b) the set of all research teams including both young and senior researchers. If a young researcher, x, is ranked above another young researcher, y, under both (a) and (b), then our CON demands that x also be ranked above y based on the ranking of the whole coalitions (the union of (a) and (b)). An interesting consequence of this importation is that the Borda rule, as an SRS, does not satisfy CON (Proposition 2), while CON is often used as a key axiom in the characterization of the Borda rule (Young 1974; Nitzan and Rubinstein 1981; Debord 1992), Approval Voting (Fishburn 1979; Alós-Ferrer 2006), etc.
This paper is organized as follows. In Sect. 2, we develop formal models of the SRS with a variable domain of coalitions. Section 3 provides the characterization of the LES and DLES. Section 4 contains the concluding remarks.

2 Model

In this section, in Sects. 2.1 and 2.2 we introduce the preliminary notations and explain the main concepts, respectively. Section 2.3 shows extra notations (readers can skip this subsection at first and can come back when necessary). Examples of the main concepts as well as various SRSs will be introduced in Sect. 2.4.

2.1 Preliminaries

A binary relation, \(\succsim\), on set A is a subset of \(A \times A\). It is called reflexive if [for any \(a \in A\), \(a \succsim a\)], complete if [for any \(a,b \in A\) with \(a \ne b\), either \(a \succsim b\) or \(b \succsim a\)], and transitive if [for any \(a,b,c \in A\), if \(a \succsim b\) and \(b \succsim c\), then \(a \succsim c\)]. A reflexive, complete, and transitive binary relation, \(\succsim\), on set A is called a weak order. Let \(\mathcal {T}^{A}\) (resp. \(\mathcal {B}^{A}\)) be the set of all weak orders (resp. reflexive and complete binary relations) on A. The asymmetric (resp. symmetric) part of a binary relation, \(\succsim\), is denoted by \(P( \succsim )\) (resp. \(I( \succsim )\)). For a binary relation, \(\succsim\), on set A and a subset \(B \subseteq A\), we denote the restriction of \(\succsim\) to B as \(\succsim |_{B}\). For a weak order \(\succsim\) on set A, the set A is called the underlying set of \(\succsim\), denoted by \(A = {{\,\textrm{und}\,}}(\succsim )\). For a positive integer k, we denote by [k] the set of all positive integers that are less than or equal to k, that is, \([ k] = \{ m \in \mathbb {N}:1 \le m \le k \}\). The union of two disjoint sets A and B with \(A \cap B = \phi\) is often denoted as \(A + B\).

2.2 Main concepts: social ranking solutions

Our model investigates how to order participants when the performances of some (not all) of their coalitions are known. We introduce the formal definitions of central concepts, followed by their interpretations.
  • \(X:= \{ 1,2,\ldots ,n \}\) is the set of all candidates with \(3 \le n < + \infty\).
  • \(\mathcal {X }:=2^{X} \backslash \{ \phi \}\) is the set of all nonempty subsets of X, interpreted as the set of all logically possible coalitions.
  • \(\mathfrak {D }:= \left\{ \text {weak order}\ \succsim : \phi \ne {{\,\textrm{und}\,}}( \succsim ) \subseteq \mathcal {X} \right\}\) is the set of all weak orders whose underlying sets are nonempty subsets of \(\mathcal {X}\). For \(\succsim \in \mathcal {D}\), \({{\,\textrm{und}\,}}( \succsim )\) is called the domain of coalition, interpreted as the set of all feasible coalitions (of \(\succsim\)), and elements of \({{\,\textrm{ptc}\,}}( \succsim ) := \{ x \in X:\exists B \in {{\,\textrm{und}\,}}( \succsim )\ \mathrm {s.t.} \ x \in B \}\) are called the participants of \(\succsim\).
  • A social ranking solution (SRS) R is a function that maps each \(\succsim \in \mathfrak {D}\) to a complete and reflexive binary relation on the set of all participants. Formally, for each \(\succsim \in \mathfrak {D}\), an SRS R returns \(R( \succsim ) \in \mathcal {B}^{{{\,\textrm{ptc}\,}}( \succsim )}\). For the ease of notation, we write \(R( \succsim )\) as \(R_{\succsim }\). Similarly, the asymmetric (resp. symmetric) part of \(R_{\succsim }\) is denoted by \(P_{\succsim }\) (resp. \(I_{\succsim }\)) instead of \(P( R_{\succsim } )\) (resp. \(I( R_{\succsim })\)). We distinguish several SRSs by the upper scripts (\(R^{U},R^{B}\), and so on). The same notation rule applies to them, as well. For instance, we denote \(R^{U}( \succsim ), P( R^{U}( \succsim ))\), and \(I( R^{U}( \succsim ))\) as \(R_{\succsim }^{U},P_{\succsim }^{U},\) and \(I_{\succsim }^{U}\)—respectively.
Given a weak order \(\succsim \in \mathfrak {D}\) (which is interpreted as a performance ranking of the feasible coalitions), an SRS returns a binary relation \(R( \succsim )\) on the set of participants. Our model assumes that \({{\,\textrm{und}\,}}( \succsim )\) is any nonempty subset of \(\mathcal {X}\). This means that the set of all feasible coalitions are considered variable. This is different from most of the previous studies (Moretti and Öztürk 2017; Bernardi et al. 2019; Allouche et al. 2021), which assumes that the underlying set is fixed as \(\mathcal {X}\) (i.e., all the logically possible coalitions are considered in the input order).
In this paper, the sum of two weak orders (with disjoint underlying sets) plays the key role. For \(\succsim _{1}, \succsim _{2} \in \mathfrak {D}\) with \({{\,\textrm{und}\,}}( \succsim _{1} ) \cap {{\,\textrm{und}\,}}( \succsim _{2} ) = \phi\), let
$$\begin{aligned} \succsim _{1} \oplus \succsim _{2}&:= \{ \succsim \in \mathfrak {D:}\ {{\,\textrm{und}\,}}( \succsim ) = {{\,\textrm{und}\,}}( \succsim _{1} ) \cup {{\,\textrm{und}\,}}( \succsim _{2} )\ \text {and} \\&\succsim |_{{{\,\textrm{und}\,}}( \succsim _{i} )} = \succsim _{i}\ \text {for}\ i = 1,2 \}. \end{aligned}$$
When \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), we say that \(\succsim\) is a sum of \(\succsim _{1}\) and \(\succsim _{2}\), and the pair of \(\succsim _{1}\) and \(\succsim _{2}\) is called a partition of \(\succsim\).
Example 1
Suppose \(X = \left\{ 1,2,3,4,5 \right\}\). Then,
(a)
Let \(\succsim _{1}, \succsim _{2},\ldots , \succsim _{5} \in \mathfrak {D}\) as follows:
$$\begin{aligned}&\succsim _{1}: \{1\} \succ \{2 \} \sim \{1,2 \}\\&\succsim _{2}: \{ 1 \} \succ \{2 \}\\&\succsim _{3}: \{ 3,4,5 \} \succ \{ 3,4 \} \succ \{ 4,5 \}\\&\succsim _{4}: \{ 3,4,5 \} \succ \{ 3,4 \}\sim \{1\} \succ \{2\} \succ \{4,5 \} \\&\succsim _{5}: \{ 3,4,5 \} \succ \{ 3,4 \}\sim \{ 1 \}\sim \{ 2 \}\sim \{ 4,5 \} \end{aligned}$$
We describe weak orders by arraying the elements of the underlying set as seen above. For instance, \(\succsim _{1}\) is a weak order such that \(\{ 1 \}\) is ranked above both \(\{ 2 \}\) and \(\{ 1,2 \}\); \(\{ 2 \}\) and \(\{ 1,2 \}\) are indifferent with each other; and the underlying set is \({{\,\textrm{und}\,}}( \succsim _{1} ) = \{ \{ 1 \},\{ 2 \},\{ 1,2 \} \}\). In this style, we do not omit the elements of the underlying set so that we can properly find the underlying set from the description. So, \(\{ 1 \} \succ \{ 2 \}\) is not an abbreviated description of \(\{ 1 \} \succ \{ 2 \}\sim \{ 1,2 \}\). They describe different weak orders with different underlying sets.
It follows that \({{\,\textrm{und}\,}}( \succsim _{2} ) = \{ \{ 1 \},\{ 2 \} \}\) and \({{\,\textrm{und}\,}}( \succsim _{3} ) = \{ \{ 3,4,5 \},\{ 3,4 \},\{ 4,5 \} \}\). Since they are disjoint, \(\succsim _{2} \oplus \succsim _{3}\) is properly defined. By definition of \(\oplus\), one can verify that \(\succsim _{4} \in \succsim _{2} \oplus \succsim _{3}\). But \(\succsim _{5} \notin \succsim _{2} \oplus \succsim _{3}\), because \(\succsim _{5} |_{{{\,\textrm{und}\,}}( \succsim _{2} )}:\{ 1 \}\sim \{ 2 \}\) is different from \(\succsim _{2}:\{ 1 \} \succ \{ 2 \}\). The set of all participants of each \(\succsim _{2}\) and \(\succsim _{3}\) is \({{\,\textrm{ptc}\,}}( \succsim _{2} ) = \{ 1,2 \}\) and \({{\,\textrm{ptc}\,}}( \succsim _{3} ) = \{ 3,4,5 \}\).
 
(b)
One familiar interpretation of \(\succsim _{2}\) and \(\succsim _{3}\) is the ranking of feasible coalitions in two disjoint departments, say sales department \({{\,\textrm{ptc}\,}}( \succsim _{2} ) = \{ 1,2 \}\) and personnel department \({{\,\textrm{ptc}\,}}( \succsim _{3} ) = \{ 3,4,5 \}\) in a firm. Following this, \({{\,\textrm{und}\,}}( \succsim _{2} ) = \{ \{ 1 \},\{ 2 \} \}\) means that the sales department has only one-person coalitions, while \({{\,\textrm{und}\,}}( \succsim _{3} )\) = \(\{ \{ 3,4,5 \},\{ 3,4 \},\{ 4,5 \} \}\) means that the personnel department has two-person or three-person coalitions. One can interpret \(\succsim _{4}\) as the evaluation of the whole coalitions of the two departments because \(\succsim _4 \in \succsim _2 \oplus \succsim _3\). In other words, \(\succsim _2\) and \(\succsim _3\) are interpreted as the restriction of \(\succsim _{4}\) into each of the two departments.
 
(c)
In (b), we describe a case when any feasible coalition is made up within a single department; candidates belonging to different departments do not make feasible coalitions. In general, however, coalitions made up of multiple departments (organizations, institutions, groups, etc.) are often found. Let us add such an example. Interpret \(\{ 1,2,3 \}\) as the set of professors at the department of economics (E-professor[s]) and \(\{ 4,5 \}\) as the set of professors at the department of mathematics (M-professor[s]). Consider a subset of \(X = \{ 1,2,3,4,5 \}\) as a research group, for example, \(\{ 2 \}\) represents a single-researcher group of Professor 2, and \(\{ 1,4,5 \}\) represents the three-researcher group of Professors 1, 4, and 5. Let \(\succsim _{6}, \succsim _{7}, \succsim _{8} \in \mathfrak {D}\) as follows.
$$\begin{aligned}&\succsim _6:\{1,2\} \succ \{1\} \sim \{2\} \sim \{3\} \\&\succsim _7:\{3,5\} \succ \{2,3,4\} \sim \{1,5\} \\&\succsim _8:\{1,2\} \sim \{3,5\} \succ \{1\} \sim \{2\} \sim \{3\} \sim \{2,3,4\} \sim \{1,5\} \end{aligned}$$
Suppose that \(\succsim _6, \succsim _7\), and \(\succsim _8\) represent the contribution ranking of the (feasible, existing) research groups including E-professors. \(\succsim _ 6\) represents the ranking for coalitions including only E-professors (intradisciplinary coalitions), \(\succsim _7\) represents the ranking for coalitions including both E-professors and M-professors (interdisciplinary coalitions), and \(\succsim _8\) represents the ranking of the whole. In this sense, \(\succsim _6\) and \(\succsim _7\) are restrictions of \(\succsim _8\) regarding the interdisciplinary research.
 
(d)
In general, a weak order has multiple partitions (just as a set is usually partitioned in various ways). Recall the context in (c). Suppose that the age of the professors matters rather than their collaboration with other departments. Suppose that the odd numbered professors (1, 3, and 5) are young and the even numbered professors (2 and 4) are seniors. One might, then, be interested to partition \(\succsim _{8}\) into \(\succsim _{9}\) [ranking of coalitions of only young researchers] and \(\succsim _{10}\) [ranking of coalitions including at least one senior researcher] as follows. One can verify that \(\succsim _{8} \in \succsim _{9} \oplus \succsim _{10}\).
$$\begin{aligned}&\succsim _{9}: \{ 3,5 \} \succ \{ 1\}\sim \{ 3\}\sim \{1,5 \} \\&\succsim _{10}: \{ 1,2 \} \succ \{ 2 \}\sim \{ 2,3,4 \}. \end{aligned}$$
 
(e)
In general, two weak orders (with disjoint underlying sets) can have multiple sums. For instance, the following \(\succsim _{11}\) and \(\succsim _{12}\) are also the sums of \(\succsim _{9}\) and \(\succsim _{10}\) (i.e., \(\succsim _{11}, \succsim _{12} \in \succsim _{9} \oplus \succsim _{10}\)).
$$\begin{aligned}&\succsim _{11}: \{ 3,5\} \succ \{ 1\}\sim \{3 \}\sim \{ 1,5\} \succ \{ 1,2\} \succ \{ 2\}\sim \{2,3,4\}\\&\succsim _{12}: \{ 1,2\} \succ \{ 2\}\sim \{ 2,3,4\} \succ \{ 3,5\} \succ \{ 1\}\sim \{ 3\}\sim \{ 1,5\}. \end{aligned}$$
This multiplicity occurs because \(\succsim _9\) and \(\succsim _{10}\) are the rankings of only a part of the whole coalitions, but the element of \(\succsim _9 \oplus \succsim _{10}\) is a ranking of the whole coalitions. Therefore, even if we know \(\succsim _9\) and \(\succsim _{10}\), there is more than one way of ranking \(\{3,5 \}\) (\(\in {{\,\textrm{und}\,}}(\succsim _9)\)) and \(\{ 1,2\}\) (\(\in {{\,\textrm{und}\,}}(\succsim _{10})\)).
 

2.3 Extra notations

For readers’ convenience, extra notations are all introduced in this subsection. They will be referred to when they first appear in the remaining text.
1.
Let \(\Sigma _{1} \succ \Sigma _{2} \succ \cdots \succ \Sigma _{K}\) be the quotient order of \(\succsim \in \mathfrak {D}\) (i.e., each \(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{K}\) is an equivalence class with respect to \(I( \succsim )\)). For \(x \in X\) and \(k = 1,2,\ldots ,K\), let \(x_{k}\) be the number of coalitions in \(\Sigma _{k}\) that contain x; that is, \(x_{k} := | \{ A \in \Sigma _{k}:x \in A \} |\). The K-dimensional vector \(\theta _{\succsim }(x):= ( x_{1},x_{2},\ldots ,x_{K} )\) is called the appearance vector of x (at \(\succsim\)). The sum of the coordination is called the appearance of x (at \(\succsim\)), denoted as \(\Vert \theta _{\succsim }(x) \Vert := x_{1} + x_{2} + \cdots + x_{K}\). Four orders \(\ge _{E}, \ge _{DE}, \ge _{L}\), and \(\ge _{DL}\) are defined as follows: for any K-dimensional vectors \(\mathbbm {x}:=( x_{1},x_{2},\ldots ,x_{K} )\) and \(\mathbbm {y}:=( y_{1},y_{2},\ldots ,y_{K} )\),
  • \(\mathbbm {x} \ge _{E}\mathbbm {y}\) if and only if (\(x_{k} = y_{k}\) for all \(k \in [ K]\)) or (\(\exists k \in [ K]\) such that \(x_{i} = y_{i}\) for all \(i < k\) and \(x_{k} > y_{k}\)).
  • \(\mathbbm {x} \ge _{DE}\mathbbm {y}\) if and only if (\(x_{k} = y_{k}\) for all \(k \in [ K]\)) or (\(\exists k \in [ K]\) such that \(x_{i} = y_{i}\) for all \(i > k\) and \(x_{k} < y_{k}\)).
  • \(\mathbbm {x} \ge _{L}\mathbbm {y}\) if and only if \(\mathbbm {y} \ge _{E}\mathbbm {x}\).
  • \(\mathbbm {x} \ge _{DL}\mathbbm {y}\) if and only if \(\mathbbm {y} \ge _{DE}\mathbbm {x}\).
Furthermore, we write \(\mathbbm {x} >_{E}\mathbbm {y}\) if \(\mathbbm {x} \ge _{E}\mathbbm {y}\) and1\(\lnot ( \mathbbm {y} \ge _{E}\mathbbm {x} )\). \(>_{DE}, >_{L}\), and \(>_{DL}\) are similarly defined. It is straightforward to verify that \(\ge _{E}, \ge _{DE}, \ge _{DL}\), and \(\ge _{DE}\) are transitive. These orders will be used to define the lexicographic SRSs (Definition 2).
 
2.
For \(\succsim \in \mathfrak {D}\) and \(A \subseteq X\), let \({{{\,\textrm{und}\,}}}_{A}( \succsim ) := \{ K \in {{{\,\textrm{und}\,}}}_{A}( \succsim ): A \subseteq K \}\). With a little abuse of notation, when A is a singleton, such as \(A = \{ x \}\), we write \({{{\,\textrm{und}\,}}}_{x}( \succsim )\) instead of \({{{\,\textrm{und}\,}}}_{\{ x \}}( \succsim )\). This notation will be used in many parts.
 
3.
For \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), let
$$\begin{aligned}&d_{\succsim }(x,y) := | \{ (S + x,S + y):\\&S \subseteq X \backslash \{ x,y \},S + x, S + y \in {{\,\textrm{und}\,}}( \succsim ),S + x \succsim S + y \} |,\\ \end{aligned}$$
and
$$\begin{aligned}&\overline{d}_{\succsim }(x,y) := | \{ (S + x,T + y):\\&S,T \subseteq X \backslash \{ x,y \},S + x,T + y \in {{\,\textrm{und}\,}}( \succsim ),S + x \succsim T + y \} |. \end{aligned}$$
These are used in the definitions of the majority rules (Definition 4).
 
4.
For \(\succsim \in \mathfrak {D}\) and its participants \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), we say that x completely dominates y at \(\succsim\) if \({{{\,\textrm{und}\,}}}_{x}( \succsim ) \backslash {{{\,\textrm{und}\,}}}_{y}( \succsim ) \ne \phi\), \({{{\,\textrm{und}\,}}}_{y}( \succsim ) \backslash {{{\,\textrm{und}\,}}}_{x}( \succsim ) \ne \phi\), and \(C \succ D\) for all \(C \in {{{\,\textrm{und}\,}}}_{x}( \succsim ) \backslash {{{\,\textrm{und}\,}}}_{y}( \succsim )\) and \(D \in {{{\,\textrm{und}\,}}}_{y}( \succsim ) \backslash {{{\,\textrm{und}\,}}}_{x}( \succsim )\).
 

2.4 SRSs

We introduce several examples of SRSs.
Definition 1
(Trivial SRSs)
(a)
A unanimous SRS, denoted by \(R^{U}\), is an SRS that judges every participant as indifferent; that is, for any \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), \(xI_{\succsim }^{U}y\).
 
(b)
An SRS R is called primitive if for any \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\) such that \(\{ x \},\{ y \} \in {{\,\textrm{und}\,}}( \succsim )\), we have \(xR_{\succsim }y \Leftrightarrow \{ x \} \succsim \{ y \}\).
 
The unanimous/primitive SRSs are originally introduced in Moretti and Öztürk (2017) under the fixed domain of coalitions \({{\,\textrm{und}\,}}( \succsim ) = 2^{X}\). Our definition is its direct extension for the variable domains of coalitions. These are instances of trivial SRSs; the unanimous SRS \(R^{U}\) posits that all participants are indifferent regardless of the input, and a primitive SRS judges each participant by their singletons (collaborative performances with other candidates are not at all considered). Note that the primitive SRS is not unique in the present model; this is because for participant x, its singleton coalition \(\{ x \}\) is not necessarily in \({{\,\textrm{und}\,}}( \succsim )\). In such a case, the condition says almost nothing about the social ranking of x.
Definition 2
(Lexicographic SRSs) [See item 1 of Sect. 2.3 for the definition of \(\ge _{E}, \ge _{DE}, \ge _{L}\), and \(\ge _{DL}\).]
The LES—denoted by \(R^{E}\)—is an SRS such that for all \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), \(xR_{\succsim }^{E}y \Leftrightarrow \theta _{\succsim }(x) \ge _{E} \theta _{\succsim }(y)\). Similarly, dual-lexicographic excellence solution (DLES) \(R^{DE}\), lexicographic least solution (LLS) \(R^{L}\), and dual-lexicographic least solution (DLLS) \(R^{DL}\) are defined by substituting \(\ge _{E}\) with \(\ge _{DE}, \ge _{L}\), and \(\ge _{DL}\)—respectively.
The LES and DLES2 are introduced in Bernardi et al. (2019). When comparing participants x and y, every LES, LLS, DLES, and DLLS sees the appearance vectors in a lexicographic way. The LES (resp. DLES) sees the vectors from the top to the bottom (resp. from the bottom to the top) to look for k such that \(x_{k} \ne y_{k}\) holds for the first time: participant x is judged better than y if \(x_{k} > y_{k}\) (resp. \(x_{k} < y_{k}\)) at such k. The intuition behind this is that the participants that appear more often (resp. less often) in coalitions of high (resp. low) positions should be better. The remaining two, the LLS and DLLS, are the reversals of the LES and DLES, respectively. Note that the LLS and DLLS are not the main targets of our characterization; they do not appear until we verify the independence of the axioms in Sect. 3.3. Nevertheless, we introduce them here because some arguments (Proposition 1) apply to the LLS and DLLS, too.
Definition 3
(The Borda rule) [See item 2 of Sect. 2.3 for the definition of \({{{\,\textrm{und}\,}}}_{x}( \cdot )\).]
We define Borda rule \(R^{B}\) in two plausible styles. No matter which is applied, \(R^{B}\) does not satisfy CON (Proposition 2). For any \(\succsim \in \mathfrak {D}\) and for all \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), \(xR_{\succsim }^{B}y \Leftrightarrow s_{\succsim }(x) \ge s_{\succsim }(y)\), where
  • First definition:
    $$\begin{aligned} \displaystyle s_{\succsim }(x) := \sum _{C \in {{{\,\textrm{und}\,}}}_{x}( \succsim )} \left( \left| \left\{ D \in {{\,\textrm{und}\,}}( \succsim ):C \succsim D \right\} \right| \right) . \end{aligned}$$
  • Second definition:
    $$\begin{aligned} \displaystyle s_{\succsim }(x) := \sum _{C \in {{{\,\textrm{und}\,}}}_{x}( \succsim )} \left( \left| \left\{ D \in {{\,\textrm{und}\,}}( \succsim ):C \succ D \right\} \right| - \left| \left\{ D \in {{\,\textrm{und}\,}}( \succsim ): D \succ C \right\} \right| \right) . \end{aligned}$$
The first and second definitions measure the score in two different styles. In the first definition, the score associated with \(C \in {{{\,\textrm{und}\,}}}_{x}( \succsim )\) is the number of coalitions that are either indifferent with, or ranked lower than C. The score of x at \(\succsim\) (i.e., \(s_{\succsim }( \succsim )\)) is given by taking the sum of all feasible coalitions C including x. In the second definition, the score associated with \(C \in {{{\,\textrm{und}\,}}}_{x}(\succsim)\) is the difference between the number of coalitions ranked below C and the number of coalitions ranked above C.
Within the literature, Borda rule for weak preference profiles has been defined in several ways; each of which coincides with Borda rule in its usual sense when the input is a linear preference profile. Our two definitions are inspired by the ones found in the literature. Our first definition corresponds with that of Fleurbaey (2003) and Terzopoulou and Endriss (2021), while the second definition is closer to the one found in Gärdenfors (1973), Young (1974), and Black (1976).
Definition 4
(Majority rule as SRSs) [See item 3 of Sect. 2.3 for the definition of \(d,\overline{d}\).]
(a)
Ceteris paribus majority (CP majority), denoted by \(R^{CPM}\), is an SRS such that for any \(\succsim \in \mathfrak {D}\, {\text {and}}\, x,y \in {{\,\textrm{ptc}\,}}( \succsim ), \, xR_{\succsim }^{CPM}y \Leftrightarrow d_{\succsim }(x,y) \ge d_{\succsim }(y,x)\).
 
(b)
Round robin majority (RR majority), denoted by \(R^{RRM}\), is an SRS such that for any \(\succsim \in \mathfrak {D}\, {\text {and}} \, x,y \in {{\,\textrm{ptc}\,}}( \succsim ), \, xR_{\succsim }^{RRM}y \Leftrightarrow {\overline{d}}_{\succsim }(x,y) \ge {\overline{d}}_{\succsim }(y,x)\).
 
CP majority (Haret et al. 2019) is an SRS based on CP comparison—that is, to compare the performances of participants with the other teammates being the same. For instance, in comparing participants 1 and 2, it sees the matches between \(\left\{ 1 \right\}\) and \(\left\{ 2 \right\}\), \(\left\{ 1,3 \right\}\) and \(\left\{ 2,3 \right\}\), and, in general, \(\left\{ 1 \right\} \cup S\) and \(\left\{ 2 \right\} \cup S\) for \(S \subseteq X \backslash \left\{ 1,2 \right\}\). CP majority counts the number of victories in CP comparisons and declares that x is socially at least as good as y if x wins y as many times as y wins x. However, RR majority counts the number of victories in all pairs between x’s coalitions (coalitions including x but not y) and y’s coalitions (coalitions including y but not x). From the viewpoint of Fig. 1, CP majority sees only parallel matches, while RR majority also sees diagonal matches.

3 Characterization of LES and DLES

This section provides a characterization of the LES and DLES. Section 3.1 introduces relevant axioms; then, we provide a characterization of the LES and DLES in Sect. 3.2. The independence of each axiom is shown in Sect. 3.3.

3.1 Axioms

Definition 5
(CON) An SRS R is said to satisfy CON if for any \(\succsim , \succsim _{1}, \succsim _{2} \in \mathfrak {D}\) with \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), and participants \(x,y \in {{\,\textrm{ptc}\,}}( \succsim _{1} ) \cap {{\,\textrm{ptc}\,}}( \succsim _{2} )\), if \(xR_{\succsim _{1}}y\) and \(xR_{\succsim _{2}}y\), then \(xR_{\succsim }y\). Furthermore, if \(xR_{\succsim _{1}}y\), \(xR_{\succsim _{2}}y\), and (\(xP_{\succsim _{1}}y\) or \(xP_{\succsim _{2}}y\)), then \(xP_{\succsim }y\).
Simply speaking, CON implies that the social ranking at \(\succsim\) must be consistent with the social rankings at its partitioned weak orders \(\succsim _{1}\) and \(\succsim _{2}\) (where \(\succsim \in \succsim _{1} \oplus \succsim _{2}\)). CON is an analog of standard consistency in social choice theory,3 which demands that the social outcome at a society N must be consistent with the social outcomes at its partitioned sub-societies \(N_{1}\) and \(N_{2}\) (where \(N = N_{1} + N_{2}\)). Nevertheless, the difference between CON and the standard consistency is often more than expected.
The standard consistency is often considered in anonymous contexts. Voters (the elements of N) are not distinguished. Therefore, the ballot profile of society N is usually represented as the list of the numbers of each type of ballot. In such a case, partitioning the ballot profile of society N into partitioned sub-societies, \(N_{1}\) and \(N_{2}\), does not lose any information: the number of a ballot, B, in society, N, is found as the sum of such number for sub-societies, \(N_{1}\) and \(N_{2}\).
In our model, however, the partitions of weak orders is considered. As a result, two weak orders \(\succsim _{1}\) and \(\succsim _{2}\) usually have multiple sums (recall (e) in Example 1). Since CON requires that the social ranking \(R_{\succsim _{1}}\) and \(R_{\succsim _{2}}\) are consistent with \(R_{\succsim }\) for all \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), its requirement can be stronger than what the standard consistency means in the anonymous contexts. This can lead to the fact that the Borda count fails to satisfy CON (Proposition 2). Nevertheless, the multiplicity of the sum of two weak orders do not make the idea completely ruined. We will prove that the lexicographic SRSs surely satisfy CON (Proposition 1). This is attractive especially when the whole coalitions are too large or too mixed, as only the small domain of coalitions are considered (e.g., interdisciplinary research teams or young research teams in Example 1 (d) and (e)). Even in such a case, our results show that the lexicographic SRSs can judge individuals consistently in the above sense.
First of all, Lemmas 1 and 2 identify straightforward but useful facts about the partition of weak orders. When \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), Lemma 1 states the relationship between the quotient orders of \(\succsim , \succsim _{1}\), and \(\succsim _{2}\), and Lemma 2 states the relationship between the appearance vectors of \(\succsim , \succsim _{1}\), and \(\succsim _{2}\).
Lemma 1
Let \(\succsim , \succsim _{1}, \succsim _{2} \in \mathfrak {D}\) with \(\succsim \in \succsim _{1} \oplus \succsim _{2}\). Let \(\Sigma _{1} \succ \Sigma _{2} \succ \cdots \succ \Sigma _{K}\) be the quotient order of \(\succsim\); \(\Sigma _{1}' \succ \Sigma _{2}' \succ \cdots \succ \Sigma _{L}'\) be the quotient order of \(\succsim _{1}\); and \(\Sigma _{1}'' \succ \Sigma _{2}'' \succ \cdots \succ \Sigma _{M}''\) be the quotient order of \(\succsim _{2}\). Then, the following holds.
(a)
For any \(l \in [ L]\), there exists unique \(l^{*} \in [K]\) such that (i) \(\Sigma _{l}' \subseteq \Sigma _{l^{*}}\) and (ii) \(\Sigma _{l}' \cap \Sigma _{k} = \phi\) for all \(k \in [ K] \backslash \{ l^{*} \}\). Furthermore, (iii) \(1^{*}< 2^{*}< \cdots < L^{*}\).
 
(b)
For any \(k \in [ K]\), \(\Sigma _{k}\) is either
 
$$\begin{aligned} \left\{ \begin{array}{ll} \Sigma _{l}' &{} \quad {\text {for some }}\, l \in [ L]{,} \\ \Sigma _{m}'' &{} \quad {\text {for some }} \, m \in [ M]{, or} \\ \Sigma _{l}' \cup \Sigma _{m}'' &{} \quad {\text {for some }} \, l \in [ L] \, \hbox { and } \, m \in [ M]. \end{array}\right. \end{aligned}$$
Proof of Lemma 1
(a)
Since \(\succsim |_{{{\,\textrm{und}\,}}( \succsim _{1} )} = \succsim _{1}\) by \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), if two coalitions are indifferent at \(\succsim _{1}\), then they are also indifferent at \(\succsim\). Therefore, each equivalence class (at \(\succsim _{1}\)) \(\Sigma _{1}',\Sigma _{2}',\ldots ,\Sigma _{L}'\) is contained in one of \(\Sigma _{1},\ldots ,\Sigma _{K}\). Since \(\Sigma _{1},\ldots ,\Sigma _{K}\) are equivalence classes at \(\succsim\), they are disjoint with each other. This discussion proves (i) and (ii). By \(\succsim |_{{{\,\textrm{und}\,}}( \succsim _{1} )} = \succsim _{1}\) again, if a coalition, A, is ranked above B at \(\succsim _{1}\), then A is also ranked above B at \(\succsim\). This implies (iii).
 
(b)
Because of (a), for each \(l \in [ L]\), each \(\Sigma _{1},\ldots ,\Sigma _{K}\) either contains \(\Sigma _{l}'\) or is disjoint with \(\Sigma _{l}'\). By symmetry, the same holds for \(\Sigma _{m}''\) with \(m \in [ M]\). Since \({{\,\textrm{und}\,}}( \succsim ) = {{\,\textrm{und}\,}}( \succsim _{1} ) \cup {{\,\textrm{und}\,}}( \succsim _{2} )\) by \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), we can write \(\Sigma _{k}\) as specified in (b) (recall that each \(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{K}\) is nonempty). \(\square\)
 
Lemma 2
Let \(\delta\) be either ELDE, or DL.
Let \(\succsim , \succsim _{1}, \succsim _{2} \in \mathfrak {D}\) with \(\succsim \in \succsim _{1} \oplus \succsim _{2}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim _{1} ) \cap {{\,\textrm{ptc}\,}}( \succsim _{2} )\).
(a)
Suppose \(\theta _{\succsim _{1}}(x) = \theta _{\succsim _{1}}(y)\). Then, \(\theta _{\succsim }(x) \ge _{\delta } \theta _{\succsim }(y) \Leftrightarrow \theta _{\succsim _{2}}(x) \ge _{\delta }\theta _{\succsim _{2}}(y)\).
 
(b)
Suppose \(\theta _{\succsim _{i}}(x) >_{\delta }\theta _{\succsim _{i}}(y)\) for \(i = 1,2\). Then, \(\theta _{\succsim }(x) >_{\delta }\theta _{\succsim }(y)\).
 
Proof of Lemma 2
The proof for each \(\delta = E,L,DE,DL\) is essentially the same. We prove for \(\delta = E\). Let \(\Sigma _{1} \succ \Sigma _{2} \succ \cdots \succ \Sigma _{K}\) be the quotient order of \(\succsim\); \(\Sigma _{1}' \succ \Sigma _{2}'\succ \cdots\) \(\succ \Sigma _{L}'\) be the quotient order of \(\succsim _{1}\); and \(\Sigma _{1}'' \succ \Sigma _{2}'' \succ \cdots \succ \Sigma _{M}''\) be the quotient order of \(\succsim _{2}\). Also, for \(z = x,y\), we denote the appearance vectors as \(\theta _{\succsim }(z) = ( z_{1},z_{2},\ldots ,z_{K} )\), \(\theta _{\succsim _{1}}(z) = ( z_{1}',z_{2}',\ldots ,z_{L}' )\), and \(\theta _{\succsim _{2}}(z) = ( z_{1}'',z_{2}'',\ldots ,z_{M}'' )\).
For each \(k \in [ K]\) and \(i = 1,2\), let4\(x_{k}^{(i)} := | \{ S \in \Sigma _{k} \cap {{\,\textrm{und}\,}}( \succsim _{i} ):x \in S \} |\) and \(y_{k}^{(i)} := | \{ S \in \Sigma _{k} \cap {{\,\textrm{und}\,}}( \succsim _{i} ):x \in S \} |\). Note that \(x_{k}^{(i)}\) \(( y_{k}^{(i)} )\) counts the number of elements in \({{{\,\textrm{und}\,}}}_{x}( \succsim _{i} )\) (\({{{\,\textrm{und}\,}}}_{y}( \succsim _{i} )\)) in \(\Sigma _{k}\). By (b) in Lemma 1, we have that for \(k \in [ K]\),
$$\begin{aligned} x_k=x_k^{(1)}+x_k^{(2)} \text{ and } y_k=y_k^{(1)}+y_k^{(2)}. \end{aligned}$$
(1)
By (a) in Lemma 1, each \(\Sigma _{1}',\Sigma _{2}',\ldots ,\Sigma _{L}'\) is contained in exactly one of \(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{K}\) and is disjoint with the others. Therefore, \(x^{(1)} := ( x_{1}^{(1)},x_{2}^{(1)},\ldots ,x_{K}^{(1)} )\) is obtained by inserting some 0’s into \(\theta _{\succsim _{1}}(x) = ( x_{1}',x_{2}',\ldots ,x_{L}' )\). Similarly, each \(x^{(2)},y^{(1)},\) and \(y^{(2)}\) are defined5 and they are obtained by inserting some 0’s into \(\theta _{\succsim _{2}}(x),\theta _{\succsim _{1}}(y),\theta _{\succsim _{2}}(y)\), respectively. By the definition of \(\ge _{E}\), we can infer that for \(i = 1,2\),
$$\begin{aligned}&\begin{aligned}&x^{(i)} \star y^{(i)} \Leftrightarrow \theta _{\gtrsim _i}(x) \star \theta _{\gtrsim _i}(y) \\ {}&\text {where } \star \hbox { is any one of} \ge _E,=, \hbox {or} \le _E. \end{aligned} \end{aligned}$$
(2)
Proof of (a): Suppose that \(\theta _{\succsim _{1}}(x) = \theta _{\succsim _{1}}(y)\). By (2), we have that \(x^{(1)} = y^{(1)}\). So, by (1), we have that for each \(k \in [ K]\),
$$\begin{aligned} \begin{aligned}&x_k \star y_k \Leftrightarrow x_k^{(2)} \star y_k^{(2)} \\ {}&\text {where }\star \text{ is } \text{ any } \text{ one } \text{ of } >,=, \hbox {or} <. \end{aligned} \end{aligned}$$
(3)
Therefore, we can infer that \(\theta _{\succsim }(x) \ge _{E}\theta (y) \Leftrightarrow x^{(2)} \ge _{E}y^{(2)}\). By (2), we have that \(\theta _{\succsim }(x) \ge _{E}\theta (y) \Leftrightarrow \theta _{\succsim _{2}}(x) \ge _{E}\theta _{\succsim _{2}}(y)\).
Proof of (b): Suppose that \(\theta _{\succsim _{i}}(x) >_{E}\theta _{\succsim _{i}}(y)\) for \(i = 1,2\). Then, there exists a unique \(l \in [ L]\) such that \(x_{i}' = y_{i}'\) for all \(i < l\) and \(x_{l}' > y_{l}'\). Also, there exists a unique \(m \in [ M]\) such that \(x_{i}'' = y_{i}''\) for all \(i < m\) and \(x_{m}'' > y_{m}''\). By (a) in Lemma 1, there exists \(l^{*},m^{*} \in [ K]\) such that \(\Sigma _{l}' \subseteq \Sigma _{l^{*}}\) and \(\Sigma _{m}'' \subseteq \Sigma _{m^{*}}\). Without loss of generality, we can assume \(l^{*} \le m^{*}\). Then, we can infer that \(x_{k}^{(i)} = y_{k}^{(i)}\) for any \(k < l^{*}\), \(x_{l^{*}}^{(1)} > y_{l^{*}}^{(1)}\), and \(x_{l^{*}}^{(2)} \ge y_{l^{*}}^{(2)}\). Therefore, with (1), we have that \(x_{k} = y_{k}\) for all \(k < l^{*}\) and \(x_{l^{*}} > y_{l^{*}}\). This implies that \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\). \(\square\)
Proposition 1
The LES, LLS, DLES, and DLLS all satisfy CON.
Proof of Proposition 1
To prove that the LES satisfies CON, we need to verify that for any \(\succsim \in \succsim _{1} \oplus \succsim _{2}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim _{1} ) \cap {{\,\textrm{ptc}\,}}( \succsim _{2} )\),
(a)
If \(xI_{\succsim _{1}}^{E}y\) and \(xI_{\succsim _{2}}^{E}y\), then \(xI_{\succsim }^{E}y\).
 
(b)
If \(xI_{\succsim _{1}}^{E}y\) and \(xP_{\succsim _{2}}^{E}y\), then \(xP_{\succsim }^{E}y\).
 
(c)
If \(xP_{\succsim _{1}}^{E}y\) and \(xP_{\succsim _{2}}^{E}y\), then \(xP_{\succsim }^{E}y\).
 
However, these are straightforward corollaries of Lemma 2. For (a): \(xI_{\succsim _{1}}^{E}y\) and \(xI_{\succsim _{2}}^{E}y\) imply \(\theta _{\succsim _{i}}(x) = \theta _{\succsim _{i}}(y)\) for \(i = 1,2\) by the definition of the LES. Therefore, Lemma 2 says that \(\theta _{\succsim }(x) = \theta _{\succsim }(y)\), indicating \(xI_{\succsim }^{E}y\). This proves (a). (b) and (c) are similarly verified by Lemma 2. The LLS, DLES, and DLLS are also similarly verified. \(\square\)
Proposition 2
The Borda rule \(R^{B}\), CP majority, and RR majority do not satisfy CON.
Proof of Proposition 2
Let us give a counterexample.
  • The Borda rule according to the first definition in Definition 3. Let \(x,y,z \in X\) be distinct candidates.
    $$\begin{aligned}&\succsim _1: \{x\} \succ \{y\} \sim \{y, z\} \\ {}&\succsim _{2}:\{ x,y,z \}\\&\succsim :\{ x \}\sim \{ x,y,z \} \succ \{ y \}\sim \{ y,z \}. \end{aligned}$$
    Then, we have \(\succsim \in \succsim _{1} \oplus \succsim _{2}\). However, we obtain that \(yP_{\succsim _{1}}^{B}x\), \(yI_{\succsim _{2}}^{B}x\), and \(xI_{\succsim }^{B}y\). This contradicts CON.
  • The Borda rule according to the second definition in Definition 3. Let \(x,y,z \in X\) be distinct candidates.
    $$\begin{aligned}&\succsim _{1}:\{ z \} \succ _{1}\{ x \}\sim {}_{1}\{ y \}\sim {}_{1}\{ y,z \},\\ {}&\succsim _{2}:\{ z,x \}\sim {}_{2}\{ x,y \},\ \text{ and } \\ {}&\succsim :\{ z \} \succ \{ x \}\sim \{ y \}\sim \{ y,z \} \succ \{ z,x \}\sim \{ x,y \}. \end{aligned}$$
    Then, we have \(\succsim \in \succsim _{1} \oplus \succsim _{2}\). But we obtain that \(xP_{\succsim _{1}}^{B}y\), \(xI_{\succsim _{2}}^{B}y\), and \(yP_{\succsim }^{B}x\). This contradicts CON.
  • CP majority and RR majority: let
    $$\begin{aligned}&\succsim _1: \{x \}\sim \{x,z \}\succsim \{x,y \} \\&\succsim _ 2: \{ y\}\sim \{ y,z\} \succ \{ x,y,z \}\\&\succsim : \{ x\} \sim \{ x,z\} \succ \{ y\}\sim \{ y,z\} \succ \{ x,y\}\sim \{ x,y,z\} \end{aligned}$$
    Then, either under CP majority or RR majority, x is judged indifferent with y under both \(\succsim _{1}\) and \(\succsim _{2}\). But x is ranked above y under \(\succsim\). This contradicts CON. \(\square\)
Definition 6
(CD) [See item 4 of Sect. 2.3.] An SRS R is said to satisfy CD if for all \(\succsim \in \mathfrak {D}\) and its candidates \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), if x completely dominates y, then \(xP_{\succsim }y\).
The intuition of CD is straightforward. If every coalition containing x but not y is ranked above those coalitions containing y but not x, then x is socially superior than y. In the previous literature, similar dominance properties have been proposed. Moretti and Öztürk (2017) introduce dominance (DOM), which demands that (1) if x is at least as good as y in every ceteris paribus comparison (x dominates y), x is socially as good as y; and (2) if x dominates y and x wins y in at least one ceteris paribus comparison, then x is socially better than y. Later, Suzuki and Horita (2021) introduce a weaker notion called weak dominance (WDOM); this demands that if x wins y in every ceteris paribus comparison, x is socially better than y. Let us demonstrate the difference between WDOM (DOM) and CD. Suppose \(X = \{ 1,2,3 \}\), and \(\succsim :\{ 1,3 \} \succ \{ 2,3 \} \succ \{ 1 \} \succ \{ 2 \}\). Since 1 wins 2 in every ceteris paribus comparison (i.e., \(\{ 1,3 \} \succ \{ 2,3 \}\) and \(\{ 1 \} \succ \{ 2 \}\)), WDOM implies \(1P_{\succsim }2\). However, 1 does not completely dominate 2; this is because \(\{ 1 \} \in {{{\,\textrm{und}\,}}}_{1}( \succsim ) \backslash {{{\,\textrm{und}\,}}}_{2} ( \succsim )\) is ranked lower than \(\{ 2,3 \} \in {{{\,\textrm{und}\,}}}_{2}( \succsim ) \backslash {{{\,\textrm{und}\,}}}_{1}( \succsim )\). Therefore, CD says nothing about this situation.
Let \(x \in X\). A bijection \(\pi\) on \(\mathcal {X}\) is called x-invariant if for all \(S \in \mathcal {X}\), \([ x \in S \Rightarrow x \in \pi (S) ]\). For \(\succsim \in \mathfrak {D}\) and a bijection \(\pi\) on \(\mathcal {X}\), we define \(\succsim _{\pi }\) as \(\pi (C) \succsim _{\pi }\pi (D) \Leftrightarrow C \succsim D\) for all \(C,D \in \mathcal {X}\). Two notes are in order. First, if a bijection \(\pi\) on \(\mathcal {X}\) is both x-invariant and y-invariant, we say that \(\pi\) is xy-invariant. Second, suppose that a bijection \(\pi\) on \(\mathcal {X}\) is x-invariant. Then, \(\pi\) maps every element of \(\mathcal {Y}:= \{ S \in \mathcal {X:}x \in S \}\) to an element of \(\mathcal {Y}\). Since \(\pi\) is a bijection and \(\mathcal {Y}\) is finite, we have that for all \(S \in \mathcal {X}\), \([ x \in S \Leftrightarrow x \in \pi (S) ]\).
Definition 7
(WCA) An SRS R is said to satisfy WCA if for any \(\succsim \in \mathfrak {D}\), participants \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), and a xy-invariant bijection \(\pi\) on \(\mathcal {X}\), we have \(xR_{\succsim _{\pi }}y \Leftrightarrow xR_{\succsim }y\).
WCA6 was introduced in Algaba et al. (2021) as a weaker version of CA by Bernardi et al. (2019). Let us briefly explain WCA. Suppose that \(\pi\) is xy-invariant bijection on \(\mathcal {X}\). Then, by the note just above Definition 4, we have that for all \(S \in \mathcal {X}\), \(S \cap \left\{ x,y \right\} = \pi (S) \cap \left\{ x,y \right\}\). Thus, the only difference between \(\succsim\) and \(\succsim _{\pi }\) is the teammates of x and y. WCA demands that such change does not affect the ranking between x and y.
For a bijection \(\sigma\) on X and \(\succsim \in \mathfrak {D}\), let \(\sigma ( \succsim )\in \mathfrak {D}\) be such that \(C \succsim D \Leftrightarrow \sigma (C)\sigma (\succsim )\) \(\sigma (D)\) for all \(C,D \in {{\,\textrm{und}\,}}( \succsim )\) (i.e., \(\sigma ( \succsim )\) is a ranking obtained from \(\succsim\) by changing the names of candidates according to \(\sigma\)). The last axiom, neutrality, demands that the name of candidates do not matter.
Definition 8
(N) An SRS R is said to satisfy N if for all \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), it follows that \(xR_{\succsim }y \Leftrightarrow \sigma (x)R_{\sigma ( \succsim )}\sigma (y)\).

3.2 Characterization

Our primary result dictates that the four axioms characterize the LES and DLES (Theorem 1). Three lemmas (Lemmas 34, and 5) are provided for the proof of Theorem 1. Lemmas 3 and 4 state that if an SRS satisfies the four axioms (while CD is not necessary in Lemma 3), then the social ranking is determined by the appearance vectors \(\theta _{\succsim }(x)\) and \(\theta _{\succsim }(y)\). Lemma 3 is on the indifference case, and Lemma 4 is on the strict case. Lemma 5 is a technical lemma guaranteeing that the two cases considered in Lemma 4 are exhaustive.
Lemma 3
Let R be an SRS satisfying CON, N, and WCA. For any \(\succsim \in \mathfrak {D}\) with \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), we have \(\theta _{\succsim }(x) = \theta _{\succsim }(y) \Rightarrow xI_{\succsim }y.\)
Proof of Lemma 3
Fix any \(x,y \in X\). We will prove that for any \(\succsim \in \mathfrak {D}\) with \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), \([ \theta _{\succsim }(x) = \theta _{\succsim }(y) \Rightarrow xI_{\succsim }y ]\). The proof is made by induction on \(\Vert \theta _{\succsim }(x) \Vert\), that is, the appearance of x (recall item 1 in Sect. 2.3). Note that \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\) is equivalent to \(\Vert \theta _{\succsim }(x) \Vert ,\Vert \theta _{\succsim }(y) \Vert \ge 1\). Also, \(\theta _{\succsim }(x) = \theta _{\succsim }(y)\) implies \(\Vert \theta _{\succsim }(x) \Vert = \Vert \theta _{\succsim }(y) \Vert\). Therefore, we will prove that for any \(\succsim \in \mathfrak {D}\) with \(\Vert \theta _{\succsim }(x) \Vert \ge 1\), \([ \theta _{\succsim }(x) = \theta _{\succsim }(y) \Rightarrow xI_{\succsim }y ]\).
Suppose \(\Vert \theta _{\succsim }(x) \Vert = 1\) and \(\theta _{\succsim }(x) = \theta _{\succsim }(y)\). This means that exactly one element in \({{\,\textrm{und}\,}}( \succsim )\) contains x (denote the element as A), exactly one element in \({{\,\textrm{und}\,}}( \succsim )\) contains y (denote the element as B), and \(A\sim B\). If \(A = B\), it contains both x and y. Because no other coalition in \({{\,\textrm{und}\,}}( \succsim )\) contains x or y, exchange of x and y at \(\succsim\) does not change \(\succsim\) at all. By N (and since \(R_{\succsim }\) is complete), we have \(xI_{\succsim }y\). Suppose \(A \ne B\). Let \(\succsim ' \in \mathfrak {D}\) be the weak order obtained from \(\succsim\) by substituting A and B with \(\{ x \}\) and \(\{ y \}\), respectively. By WCA, we have \({R_{\succsim } |}_{\{ x,y \}} = {R_{\succsim '} |}_{\{ x,y \}}\). We can prove again that transposing x and y at \(\succsim '\) does not change \(\succsim '\) at all. Therefore, N demands \(xI_{\succsim '}y\). With \({R_{\succsim } |}_{\{ x,y \}} = {R_{\succsim '} |}_{\{ x,y \}}\), we obtain \(xI_{\succsim }y\).
Suppose that \([ \theta _{\succsim '}(x) = \theta _{\succsim '}(y) \Rightarrow xI_{\succsim '}y ]\) holds for all \(\succsim '\in \mathfrak {D}\) with \(1 \le \Vert \theta _{\succsim '}(x) \Vert \le k\). Let \(\succsim \in \mathfrak {D}\) with \(\Vert \theta _{\succsim }(x) \Vert = k + 1\) and \(\theta _{\succsim }(x) = \theta _{\succsim }(y)\). Fix any \(A \in {{{\,\textrm{und}\,}}}_{x}( \succsim )\). If \(y \in A\), let \(\succsim _{1}:A\) (i.e., \(\succsim _{1}\) is a trivial weak order on \(\{ A \}\)) and \(\succsim _{2} := {\succsim |}_{{{\,\textrm{und}\,}}( \succsim ) \backslash \{ A \}}\). Then, \(\theta _{\succsim _{1}}(x) = \theta _{\succsim _{1}}(y)( = (1) )\). By (a) in Lemma 2, \(\theta _{\succsim _{2}}(x) = \theta _{\succsim _{2}}(y)\). By assumption of induction, we have \(xI_{\succsim _{1}}y\) and \(xI_{\succsim _{2}}y\). By CON, we have \(xI_{\succsim }y\). Suppose \(y \notin A\). Then, since \(\theta _{\succsim }(x) = \theta _{\succsim }(y)\), there exists \(B \in {{\,\textrm{und}\,}}( \succsim )\) such that \(x \notin B \ni y\) and \(A\sim B\). Let \(\succsim _{1}:A\sim B\) and \(\succsim _{2} := {\succsim |}_{{{\,\textrm{und}\,}}( \succsim ) \backslash \{ A,B \}}\). Again, we have \(\theta _{\succsim _{1}}(x) = \theta _{\succsim _{1}}(y)( = (1) )\). By (a) in Lemma 2, \(\theta _{\succsim _{2}}(x) = \theta _{\succsim _{2}}(y)\). By assumption of induction, we have \(xI_{\succsim _{1}}y\) and \(xI_{\succsim _{2}}y\). By CON, we have \(xI_{\succsim }y\). \(\square\)
Lemma 4
Let \(\succsim _{*}:\{ 1,2 \} \succ \{ 1 \}\). Let R be an SRS satisfying CON, N, WCA, and CD.
(a)
Suppose that \(1P_{\succsim ^{*}}2\). Then, for any \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), we have \([ \theta _{\succsim }(x) >_{E}{} \theta _{\succsim }(y) \Rightarrow xP_{\succsim }y ]\).
 
(b)
Suppose that \(2P_{\succsim ^{*}}1\). Then, for any \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), we have \([ \theta _{\succsim }(x) >_{DE}{}\theta _{\succsim }(y) \Rightarrow xP_{\succsim }y ]\).
 
Proof of Lemma 4
Since (a) and (b) are verified similarly, we prove (a). Fix any \(x,y \in X\). Note that \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\) is equivalent to \(\Vert \theta _{\succsim }(x) \Vert , \Vert \theta _{\succsim }(y) \Vert \ge 1\). Therefore, we are supposed to prove the following: for any \(\succsim \in \mathfrak {D}\) with \(\Vert \theta _{\succsim }(x) \Vert ,\Vert \theta _{\succsim }(y) \Vert \ge 1\), \([ \theta _{\succsim }(x) >_{E}\theta _{\succsim }(y) \Rightarrow xP_{\succsim }y ]\). We will prove this by induction on \(\Vert \theta _{\succsim }(x) \Vert + \Vert \theta _{\succsim }(y) \Vert\). We will first prove Claims 1 and 2, which cover the case of \(\Vert \theta _{\succsim }(x) \Vert + \Vert \theta _{\succsim }(y) \Vert \le 3\), and then prove the induction step. Let \(z \in X \backslash \{ x,y \}\). \(\square\)
Let us begin with two preliminary claims.
Claim 1
If \(\left\| \theta _{\succsim }(x) \right\| = 1\) and \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\), then \(xP_{\succsim }y\).
Proof of Claim 1
\(\Vert \theta _{\succsim }(x) \Vert = 1\) and \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\) can hold only if the unique element of \({{{\,\textrm{und}\,}}}_{x}( \succsim )\) is ranked strictly above any element of \({{{\,\textrm{und}\,}}}_{y}( \succsim )\) (otherwise, it must be that \(\theta _{\succsim }(y) \ge _{E}\theta _{\succsim }(x)\)). Therefore, x completely dominates y. By CD, we have that \(xP_{\succsim }y\). \(\square\)
Claim 2
If \(\Vert \theta _{\succsim }(x) \Vert = 2\), \(\Vert \theta _{\succsim }(y) \Vert = 1\), and \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\), then \(xP_{\succsim }y\).
Proof of Claim 2
we consider two possibilities, (i) at least one coalition in \({{\,\textrm{und}\,}}( \succsim )\) contains both x and y, and (ii) there is no such coalition.
(i)
Let \(A \in {{\,\textrm{und}\,}}( \succsim )\) be such that \(x,y \in A\). Because \(\Vert \theta _{\succsim }(x) \Vert = 2\) and \(\Vert \theta _{\succsim }(y) \Vert = 1\), there exists \(B \in {{\,\textrm{und}\,}}( \succsim )\) such that \(x \in B\) and \(y \notin B\). Because \(\Vert \theta _{\succsim }(y) \Vert = 1\), at least one of \(\{ x,y \}\) and \(\{ x,y,z \}\) is not in \({{\,\textrm{und}\,}}( \succsim )\). Let C be such element—that is,
$$\begin{aligned} \displaystyle C =\left\{ \begin{array}{ll} \{ x,y \} &{} \quad \textrm{if}\ \{ x,y \} \notin {{\,\textrm{und}\,}}( \succsim ) \\ \{ x,y,z \} &{} \quad \textrm{otherwise}. \end{array}\right. \end{aligned}$$
In other words, C is a coalition such that \(\{ x,y \} \subseteq C\) and \(C \notin {{\,\textrm{und}\,}}( \succsim )\). Now, let \(\succsim _{1}:C\). Let us construct \(\succsim _{2} \in \succsim \oplus \succsim _{1}\) by putting C above any element of \({{\,\textrm{und}\,}}\)(\(\succsim\)). Then, by N, we have \(xR_{\succsim _{1}}y \Leftrightarrow yR_{\succsim _{1}}x\). Because \(R_{\succsim _{1}}\) is complete by the definition of SRS, it follows that \(xI_{\succsim _{1}}y\). Therefore, CON implies that \({R_{\succsim _{2}} |}_{\{ x,y \}} = {R_{\succsim } |}_{\{ x,y \}}\). However, let \(\succsim _{3}:C \succ B\) and \(\succsim _{4} := {\succsim _{2} |}_{{{\,\textrm{und}\,}}( \succsim _{2} ) \backslash \{ B,C \}}\). By WCA and \(1P_{\succsim _{*}}2\), we have \(xP_{\succsim _{3}}y\). By N, we have \(xI_{\succsim _{4}}y\). Because \(\succsim _{2} \in \succsim _{3} \oplus \succsim _{4}\), CON implies that \(xP_{\succsim _{2}}y\). Because we have already shown that \({R_{\succsim _{2}} |}_{\{ x,y \}} = {R_{\succsim } |}_{\{ x,y \}}\), this implies that \(xP_{\succsim }y\).
 
(ii)
Suppose that no element of \({{\,\textrm{und}\,}}( \succsim )\) contains both x and y. Because \(\Vert \theta _{\succsim }(x) \Vert = 2\) and \(\Vert \theta _{\succsim }(y) \Vert = 1\), \({{{\,\textrm{und}\,}}}_{x}( \succsim )\) has two elements and \({{{\,\textrm{und}\,}}}_{y}( \succsim )\) has exactly one element. Let us denote them as \({{{\,\textrm{und}\,}}}_{x}( \succsim ) = \{ A,B \}\) and \({{{\,\textrm{und}\,}}}_{y}( \succsim ) = \{ A' \}\). Furthermore, let \(C := \{ x,y \}\). Because no element of \({{\,\textrm{und}\,}}( \succsim )\) contains both x and y, it follows that \(C \notin {{\,\textrm{und}\,}}( \succsim )\). Because \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\), we have either \(A \succsim A'\) or \(B \succsim A'\). Without loss of generality, assume \(A \succsim A'\). Now, let \(\succsim _{1}:C\). Let us construct \(\succsim _{2} \in \succsim \oplus \succsim _{1}\) by putting C above any element of \({{\,\textrm{und}\,}}( \succsim _{1} )\). [The remaining part is almost the same as (i)]. By N, we have \(xI_{\succsim _{1}}y\). Therefore, CON implies that \({R_{\succsim _{2}} |}_{\{ x,y \}} = {R_{\succsim } |}_{\{ x,y \}}\). However, let \(\succsim _{3}:C \succ B\) and \(\succsim _{4} := {\succsim _{2} |}_{{{\,\textrm{und}\,}}( \succsim _{2} ) \backslash \{ B,C \}}\). By WCA and \(1P_{\succsim _{*}}2\), we have \(xP_{\succsim _{3}}y\). By N, we have \(xI_{\succsim _{4}}y\). Because \(\succsim _{2} \in \succsim _{3} \oplus \succsim _{4}\), CON implies that \(xP_{\succsim _{2}}y\). As we have already shown that \({R_{\succsim _{2}} |}_{\{ x,y \}} = {R_{\succsim } |}_{\{ x,y \}}\), this implies that \(xP_{\succsim }y\). \(\square\)
 

3.2.1 Induction step

Assume that for any \(\succsim \in \mathfrak {D}\) with \(\Vert \theta _{\succsim }(x) \Vert ,\Vert \theta _{\succsim }(y) \Vert \ge 1\) and \(\Vert \theta _{\succsim }(x) \Vert + \Vert \theta _{\succsim }(y) \Vert \le s\), \([ \theta _{\succsim }(x) >_{E}\theta _{\succsim }(y) \Rightarrow xP_{\succsim }y ]\). Claims 1 and 2 cover the whole case of \(s \le 3\) (i.e., \(( \Vert \theta _{\succsim }(x) \Vert ,\Vert \theta _{\succsim }(y) \Vert ) = (1,1),(1,2),(2,1)\)). Therefore, we can assume \(s \ge 3\) to prove the induction step.
Let \(\succsim \in \mathfrak {D}\) with \(\Vert \theta _{\succsim }(x) \Vert ,\Vert \theta _{\succsim }(y) \Vert \ge 1\), \(\Vert \theta _{\succsim }(x) \Vert + \Vert \theta _{\succsim }(y) \Vert = s + 1( \ge 4)\), and \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\). We prove \(xP_{\succsim }y\). By Claims 1 and 2, we have only to prove the case of \(\Vert \theta _{\succsim }(x) \Vert ,\Vert \theta _{\succsim }(y) \Vert \ge 2\). Let \(\Sigma _{1} \succ \Sigma _{2} \succ \cdots \succ \Sigma _{K}\) be the quotient order of \(\succsim\).
(i)
Suppose that there exists k with \(x_{k},y_{k} > 0\). If there exists \(D_{1} \in \Sigma _{k}\) such that \(x,y \in D_{1}\), let \(\succsim _{1}:D_{1}\). Otherwise, \(x_{k},y_{k} > 0\) implies that \(D_{2},D_{3} \in \Sigma _{k}\) exist such that \(y \notin D_{2} \ni x\) and \(x \notin D_{3} \ni y\). In this case, let \(\succsim _{1}:D_{2}\sim D_{3}\). In either case, we have \(\theta _{\succsim _{1}}(x) = \theta _{\succsim _{1}}(y)\). Therefore, Lemma 3 says that \(xI_{\succsim _{1}}y\). Let \(\succsim _{2} := {\succsim |}_{{{\,\textrm{und}\,}}( \succsim ) \backslash {{\,\textrm{und}\,}}( \succsim _{1} )}\). Because \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\), (b) in Lemma 2 says that \(\theta _{\succsim _{2}}(x) >_{E}\theta _{\succsim _{2}}(y)\). By the assumption of induction, we have \(xP_{\succsim _{2}}y\). Because \(\succsim \in \succsim _{1} \oplus \succsim _{2}\), CON implies that \(xP_{\succsim }y\).
 
(ii)
Suppose that for any \(k \in [ K]\), either \(x_{k} = 0\) or \(y_{k} = 0\). In this case, \(\{ x,y \} \notin {{\,\textrm{und}\,}}( \succsim )\). Let \(\succsim _{1}:\{ x,y \}\). Lemma 3 states that \(xI_{\succsim _{1}}y\). Let \(\succsim _{2} \in \succsim \oplus \succsim _{1}\). CON says that \(R_{\succsim } |_{\{ x,y \}} = R_{\succsim _{2}} |_{\{ x,y \}}\).
 
Because of \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\), there exists \(k \in [ K]\), such that \(x_{i} = 0\) for all \(i < k\) and \(x_{k} > 0\). Let \(D \in {{{\,\textrm{und}\,}}}_{x}( \succsim ) \cap \Sigma _{k}\). Because of the assumption of (ii), we have \(y_{k} = 0\). Furthermore, because \(x_{i} = 0\) for all \(i < k\) and \(\theta _{\succsim }(x) >_{E}\theta _{\succsim }(y)\), it follows that any element of \({{{\,\textrm{und}\,}}}_{y}( \succsim )\) is ranked below D at \(\succsim\). Let \(\succsim _{3} := {\succsim _{2} |}_{\{ D \} \cup {{{\,\textrm{und}\,}}}_{y}( \succsim _{2} )}\) and \(\succsim _{4} := {\succsim _{2} |}_{{{\,\textrm{und}\,}}( \succsim _{2} ) \backslash {{\,\textrm{und}\,}}( \succsim _{3} )}\). By the above discussion, it follows that \(\theta _{\succsim _{3}}(x) >_{E}\theta _{\succsim _{3}}(y)\) and \(\Vert \theta _{\succsim _{3}}(x) \Vert + \Vert \theta _{\succsim _{3}}(y) \Vert < \Vert \theta _{\succsim }(x) \Vert + \Vert \theta _{\succsim }(y) \Vert\). By the assumption of induction, we have \(xP_{\succsim _{3}}y\). It also follows that \(\theta _{\succsim _{4}}(x) \ge _{E}\theta _{\succsim _{4}}(y)\) and \(\Vert \theta _{\succsim _{4}}(x) \Vert + \Vert \theta _{\succsim _{4}}(y) \Vert < \Vert \theta _{\succsim }(x) \Vert + \Vert \theta _{\succsim }(y) \Vert\). By the assumption of induction (and Lemma 3), we have \(xR_{\succsim _{4}}y\). By CON, we have \(xP_{\succsim _{2}}y\). Because of \(R_{\succsim }|_{\{ x,y \}} = R_{\succsim _{2}} |_{\{ x,y \}}\), this means that \(xP_{\succsim }y\). \(\blacksquare\)
Lemma 5
Let \(\succsim _{*}:\{ 1,2 \} \succ \{ 1 \}\). Let R be an SRS satisfying CON, N, WCA, and CD. Then, \(1I_{\succsim _{*}}2\) never holds.
Proof of Lemma 5
Let
$$\begin{aligned}&\succsim _{*}: \{ 1,2 \} \succ \{ 1 \}, \\&\succsim _{1}:\{ 1,2,3 \} \succ \{ 1 \} \\&\succsim _{2}:\{ 1,2,3 \} \succ \{ 2 \},\ \text{ and }\\&\succsim _{3}:\{ 1,2 \}\sim \{ 1,2,3 \} \succ \{ 1 \} \succ \{ 2 \}. \end{aligned}$$
Suppose to the contrary that \(1I_{\succsim _{*}}2\). By WCA, we also have that \(1I_{\succsim _{1}}2\). By N, we have that \(1I_{\succsim _{2}}2\). Since \(\succsim _{3} \in \succsim _{*} \oplus \succsim _{2}\), CON implies that \(1I_{\succsim _{3}}2\).
However, let
$$\begin{aligned}&\succsim _{4}:\{ 1,2 \}\sim \{ 1,2,3 \},\ \text{ and }\\&\succsim _{5}:\{ 1 \} \succ \{ 2 \}. \end{aligned}$$
By N, we have \(1I_{\succsim _{4}}2\). By CD, we have \(1P_{\succsim _{5}}2\). Because \(\succsim _{3} \in \succsim _{4} \oplus \succsim _{5}\), CON implies that \(1P_{\succsim _{3}}2\). This contradicts \(1I_{\succsim _{3}}2\). \(\square\)
Now, we are ready to show the main result.
Theorem 1
An SRS satisfies CON, CD, N, and WCA if and only if it is the LES or DLES.
Proof of Theorem 1
We have already shown that the LES and DLES satisfy CON (Proposition 1). They trivially satisfy N and CD. Recall that the outcomes of the
LES and DLES are determined by the appearance vectors, and the appearance vectors are calculated by counting the number of each individual in each equivalence class. Therefore, the ranking between x and y does not change when the input ranking \(\succsim\) is shifted into \(\succsim _{\pi }\) by the xy-invariant bijection (i.e., \(\theta _{\succsim }(x) = \theta _{\succsim _{\pi }}(x)\) and \(\theta _{\succsim }(y) = \theta _{\succsim _{\pi }}(y)\) for any xy-invariant bijection of X). This means that the LES and DLES satisfy WCA.
We will now prove the “only if” part of the theorem. Let R be any SRS satisfying CON, CD, N, and WCA. Let \(\succsim _{*}:\left\{ 1,2 \right\} \succ \left\{ 1 \right\}\). By Lemma 5 (and since \(R_{\succsim }\) is complete), there are only two possibilities: \(1P_{\succsim _{*}}2\) or \(2P_{\succsim _{*}}1\). We will prove that if the former (latter) holds, R is the LES (DLES).
Suppose that \(1P_{\succsim _{*}}2\). Then, by Lemma 3 and (a) in Lemma 4, we can say that for any \(\succsim \in \mathfrak {D}\) with \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), \(\theta _{\succsim }(x) \ge _{E}\theta _{\succsim }(y) \Leftrightarrow xR_{\succsim }y\). Therefore, R is the LES. Suppose that \(2P_{\succsim _{*}}1\). Then, by Lemma 3 and (b) in Lemma 4, we can say that for any \(\succsim \in \mathfrak {D}\) with \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\), \(\theta _{\succsim }(x) \ge _{DE}\theta _{\succsim } (y) \Leftrightarrow xR_{\succsim }y\). Therefore, R is the DLES. \(\square\)

3.3 Independence of the axioms

We will introduce several other SRSs to show the independence of the axioms.

3.3.1 Extra notation

For \(\succsim \in \mathfrak {D}\) with quotient order \(\Sigma _{1} \succ \Sigma _{2} \succ \cdots \succ \Sigma _{K}\) and \(x \in X\), let \(\tau _{\succsim }(x) := \left( {\overline{x}}_{1},{\overline{x}}_{2},\ldots ,{\overline{x}}_{K} \right)\), where for \(k \in [ K]\), let
$$\begin{aligned} \bar{x}_k:= {\left\{ \begin{array}{ll} \displaystyle \min _{C \in \Sigma _k \cap {{\,\textrm{und}\,}}_x(\succsim )} |C| &{} \text{ if } \Sigma _k \cap {{\,\textrm{und}\,}}_x(\succsim ) \ne \phi , \\ |X|+1 &{} \text{ if } \Sigma _k \cap {{\,\textrm{und}\,}}_x(\succsim )=\phi . \end{array}\right. } \end{aligned}$$
(4)
In other words, if \(\Sigma _{k} \cap {{{\,\textrm{und}\,}}}_{x}( \succsim ) \ne \phi\) (i.e., if there is at least one coalition in \(\Sigma _{k}\) that contains x), then \({\overline{x}}_{k}\) represents the smallest cardinality of those coalitions. Otherwise, if \(\Sigma _{k} \cap {{{\,\textrm{und}\,}}}_{x}( \succsim ) = \phi\), then \({\overline{x}}_{k}\) is \(|X| + 1\), which is higher than the cardinality of any other coalitions.

3.3.2 Two SRSs are introduced

  • The LES with tie-breaking according to ex ante linear ordering \(R^{EEO}\)
Let \(\vartriangleright\) be a linear order on X. For all \(\succsim \in \mathfrak {D}\),
$$\begin{aligned} xR_{\succsim }^{EEO}y \Leftrightarrow \left[ xP_{\succsim }^{E}y\ \text{ or }\ \left( xI_{\succsim }^{E}y\ \text{ and }\ x \vartriangleright y \right) \right] . \end{aligned}$$
  • The LES with tie-breaking according to coalition size \(R^{ECS}\)
Define \(R^{ECS}\) as for all \(\succsim \in \mathfrak {D}\), then
$$\begin{aligned} xR_{\succsim }^{ECS}y \Leftrightarrow \left[ xP_{\succsim }^{E}y\ \text{ or }\ \left( xI_{\succsim }^{E}y\ \text{ and }\ \tau _{\succsim }(x) \ge _{L}\tau _{\succsim }(y) \right) \right] . \end{aligned}$$
Both \(R^{EEO}\) and \(R^{ECS}\) are interpreted as a variety of the LES equipped with a tie-breaking system. Let \(\succsim \in \mathfrak {D}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim )\). If \(xP_{\succsim }^{E}y\) (i.e., if x is ranked above y by the LES), then x is also ranked above y by either under \(R^{EEO}\) and \(R^{ECS}\). Their difference appears only when \(xI_{\succsim }^{E}y\) (i.e., x and y are indifferent by the LES). In such a case, \(R^{EEO}\) and \(R^{ECS}\) breaks the tie according to \(\vartriangleright\) and \(\tau _{\succsim }\), respectively. The tie-breaking by \(R^{EEO}\) is simply made by the given linear order \(\vartriangleright\). The tie-breaking by \(R^{ECS}\) is made by seeing whether \(\tau _{\succsim }(x) \ge _{L}\tau _{\succsim }(y)\) holds. In general, \(\tau _{\succsim }(x) >_{L}\tau _{\succsim }(y)\) holds if there exists \(k \in [ K]\) such that \({\overline{x}}_{i} = {\overline{y}}_{i}\) for all \(i < k\) and \({\overline{x}}_{k} < {\overline{y}}_{k}\). Then, \({\overline{x}}_{k} < {\overline{y}}_{k}\) means that x can be ranked at \(\Sigma _{k}\) with only \({\overline{x}}_{k} - 1\) colleagues, but y cannot. In this sense, the intuition of \(R^{EES}\) is that if two coalitions demonstrate the same achievement, then the members in the smaller coalition are more competent than those in the larger. Let us demonstrate them with an example.
Let \(X = \{ 1,2,3 \}\) and \(\succsim :\{ 1,2 \} \succ \{ 1 \}\sim \{ 2,3 \}\). Then, we have that \(\theta _{\succsim }(1) = \theta _{\succsim }(2) = (1,1)\), \(\theta _{\succsim }(3) = (0,1)\), \(\tau _{\succsim }(1) = (2,1)\), \(\tau _{\succsim }(2) = (2,2)\), and \(\tau _{\succsim }(3) = (4,2)\). Since \(1I_{\succsim }^{E}2\) and \(\tau _{\succsim }(1) >_{L}\tau _{\succsim }(2)\), \(1P_{\succsim }^{ECS}2\). This is because the second component of \(\tau _{\succsim }(1)\) is smaller than that of \(\tau _{\succsim }(2)\).
Proposition 3
The four axioms in Theorem 1 are logically independent:
  • \(R^{ECS}\) satisfies the four axioms except for WCA.
  • \(R^{EEO}\) satisfies the four axioms except for N.
  • \(R^{U}\), \(R^{L}\), and \(R^{DL}\) satisfy the four axioms except for CD.
  • \(R^{RRM}\) satisfies the four axioms except for CON.
Proof of Proposition 3
On \(R^{ECS}.\) It clearly satisfies N and CD; however, \(R^{ECS}\) does not satisfy WCA: \(\succsim :\{ 1,2 \} \succ \{ 1 \}\sim \{ 2,3 \}\) and \(\succsim ':\{ 1,2 \} \succ \{ 1 \}\sim \{ 2 \}\). Then, we have \(1P_{\succsim }^{ECS}2\) and \(1I_{\succsim '}^{ECS}2\). This contradicts WCA.
Finally, let us prove that \(R^{ECS}\) satisfies CON. Since \(R^{E}\) is complete and reflexive, the definition of \(R^{ECS}\) implies the following:
$$\begin{aligned} \begin{aligned}&x P_{\succsim }^{E C S} y \Leftrightarrow \left[ x P_{\succsim }^E y \text{ or } \left( x I_{\succsim }^E y \text{ and } \tau _{\succsim }(x) >_L \tau _{\succsim }(y)\right) \right] \\&x I_{\succsim }^{E C S} y \Leftrightarrow \left[ x I_{\succsim }^E y \text{ and } \tau _{\succsim }(x)=\tau _{\succsim }(y)\right] . \end{aligned} \end{aligned}$$
(5)
Suppose that \(\succsim , \succsim _{1}, \succsim _{2} \in \mathfrak {D}\) with \(\succsim \in \succsim _{1} \oplus \succsim _{2}\) and \(x,y \in {{\,\textrm{ptc}\,}}( \succsim _{1} ) \cap {{\,\textrm{ptc}\,}}( \succsim _{2} )\). We must prove the following:
(a)
\(xI_{\succsim _{1}}^{ECS}y\) and \(xP_{\succsim _{2}}^{ECS}\) imply \(xP_{\succsim }^{ECS}y\).
 
(b)
\(x{P_{\succsim }}_{1}^{ECS}y\) and \(xP_{\succsim _{2}}^{ECS}y\) imply \(xP_{\succsim }^{ECS}y\).
 
(c)
\(xI_{\succsim _{1}}^{ECS}y\) and \(xI_{\succsim _{2}}^{ECS}y\) imply \(xI_{\succsim }^{ECS}y\).
 
For (a), [\(xI_{\succsim _{1}}^{ECS}y\) and \(xP_{\succsim _{2}}^{ECS}\)] implies that [\(xI_{\succsim _{1}}^{E}y\) and \(xP_{\succsim _{2}}^{E}y\)] by (1). Because \(R^{E}\) satisfies CON (Proposition 1), we have \(xP_{\succsim }^{E}y\). This implies that \(xP_{\succsim }^{ECS}y\).
For (b), [\(xP_{\succsim _{1}}^{ECS}y\) and \(xP_{\succsim _{2}}^{ECS}\)] implies that [\(xP_{\succsim _{1}}^{E}y\) and \(xP_{\succsim _{2}}^{E}y\)] by (1). Because \(R^{E}\) satisfies CON (Proposition 1), we have \(xP_{\succsim }^{E}y\). This implies that \(xP_{\succsim }^{ECS}y\).
For (c), suppose that \(xI_{\succsim _{1}}^{ECS}y\) and \(xI_{\succsim _{2}}^{ECS}y\). By (1), we have \(xI_{\succsim _{1}}^{E}y\) and \(xI_{\succsim _{2}}^{E}y\). Because \(R^{E}\) satisfies CON (Proposition 1), we have \(xI_{\succsim }^{E}y\). Therefore, we are supposed to verify that \(\tau _{\succsim }(x) = \tau _{\succsim }(y)\) (given that \(\tau _{\succsim _{i}}(x) = \tau _{\succsim _{i}}(y)\) for \(i = 1,2\)). This is done similarly as the proof of (a) in Lemma 2. Let
$$\begin{aligned} \overline{x}_{k}^{(i)} := \left\{ \begin{array}{ll} \displaystyle \min _{C \in \Sigma _{k} \cap {{{\,\textrm{und}\,}}}_{x}( \succsim _{i} )} |C| &{} \quad \textrm{if}\ \Sigma _{k} \cap {{{\,\textrm{und}\,}}}_{x}( \succsim _{i} ) \ne \phi , \\ |X| + 1&{} \quad \textrm{if}\ \Sigma _{k} \cap {{{\,\textrm{und}\,}}}_{x}( \succsim _{i} ) = \phi . \end{array} \right. \end{aligned}$$
(i.e., substituting \(\succsim\) with \(\succsim _{i}\) in (4)). \({\overline{y}}_{k}^{(i)}\) is defined in the same way. By (b) in Lemma 1, we have that for \(k \in [ K]\),
$$\begin{aligned} \bar{x}_k=\min \left\{ \bar{x}_k^{(1)}, \bar{x}_k^{(2)}\right\} \text{ and } \bar{y}_k=\min \left\{ \bar{y}_k^{(1)}, \bar{y}_k^{(2)}\right\} \end{aligned}$$
(6)
Suppose that \(\tau _{\succsim _{1}}(x) = \tau _{\succsim _{1}}(y)\). By (a) in Lemma 1, each \(\Sigma _{1}',\Sigma _{2}',\ldots ,\Sigma _{L}'\) is contained in exactly one of \(\Sigma _{1},\Sigma _{2},\ldots ,\Sigma _{K}\) and is disjoint with the others. When \(\Sigma _{l}' \subseteq \Sigma _{k}\), one can find that \({\overline{x}}_{k}^{(1)} = {\overline{y}}_{k}^{(1)}\). In the same way, by \(\tau _{\succsim _{i}}(x) = \tau _{\succsim _{i}}(y)\) (\(i = 1,2\)), we can infer that \({\overline{x}}_{k}^{(i)} = {\overline{y}}_{k}^{(i)}\) for all \(k \in [ K]\) and \(i = 1,2\). By (6), we have that \(\tau _{\succsim }(x) = \tau _{\succsim }(y)\).
On \(R^{EEO}\): As the tie-breaking is done by a fixed linear order, it does not satisfy N. \(R^{EEO}\) clearly satisfies CD and WCA. \(R^{EEO}\) satisfies CON. This is similarly verified as \(R^{ECS}\).
On \(R^{U}\), \(R^{L}\), and \(R^{DL}\): Let \(\succsim :\{ 1 \} \succ \{ 2 \}\). Then, \(1I_{\succsim }^{U}2\), \(1I_{\succsim }^{L}2\), and \(1I_{\succsim }^{DL}2\). This contradicts CD. \(R^{U}\) clearly satisfies N, WCA, and CON. \(R^{L}\) and \(R^{DL}\) clearly satisfy N and WCA. They satisfy CON (Proposition 1).
On \(R^{RRM}\): It clearly satisfies N, WCA, and CD. But it does not satisfy CON (Proposition 2). \(\square\)

4 Concluding remarks

This paper introduces consistent SRSs with variable domains of coalitions. We consider a situation where there are several (mutually disjoint) domains of coalitions, and a consistent series of ordinal rankings of participants are required. Our characterization result (Theorem 1) reveals the merits of using the LES and DLES in such situations. It is worth noting that the Borda rule and majority rules as SRSs (as defined in Sect. 2.4) are not consistent (Proposition 2) while the LES, DLES, and some of its variants are found to be consistent (Proposition 3). These results imply the connection between the lexicographic type SRSs and consistency. Our model considers the partition of a weak order into two weak orders with disjoint underlying sets (i.e., \(\succsim _{1} \oplus \succsim _{2}\) was defined only when \({{\,\textrm{und}\,}}( \succsim _{1} ) \cap {{\,\textrm{und}\,}}( \succsim _{2} ) = \phi\)). This assumption sounds natural when several disjoint families of coalitions matter (as in (c) and (d) in Example 1). In general, however, a research team can appear in different rankings of coalitions (e.g., the ranking within journals of economics and the ranking within journals of mathematics). Extending the consistency axiom into such complex situations can be an interesting future topic.

Acknowledgements

This work was supported by JSPS KAKENHI Grant No. JP21K14222.

Declarations

Conflict of interest

The authors declare that they have no conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://​creativecommons.​org/​licenses/​by/​4.​0/​.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Footnotes
1
We denote by \(\lnot\) the negation of a statement.
 
2
It is called dual lexicographic solution in Bernardi et al. (2019).
 
3
Among them, the closest to ours is Smith (1973), and Nitzan and Rubinstein (1981), which is designed for ranking-valued procedures rather than set-valued procedures.
 
4
The authors thank an anonymous reviewer for a comment that inspired us to introduce the vectors \(x^{(i)}\) and \(y^{(i)}\), which simplified the proof.
 
5
Formally, \(x^{(i)} = ( x_{1}^{(i)},x_{2}^{(i)},\ldots , x_{K}^{(i)} )\) and \(y^{(i)} = ( y_{1}^{(i)},y_{2}^{(i)},\ldots ,y_{K}^{(i)} )\) for each \(i = 1,2\).
 
6
Our definition of WCA is a direct extension of Algaba et al. (2021) into our model (where the variable domains of coalitions are considered).
 
Literature
go back to reference Algaba E, Moretti S, Rémila E, Solal P (2021) Lexicographic solutions for coalitional rankings. Springer, BerlinCrossRef Algaba E, Moretti S, Rémila E, Solal P (2021) Lexicographic solutions for coalitional rankings. Springer, BerlinCrossRef
go back to reference Allouche T, Escoffier B, Moretti S, Öztürk M (2021) Social ranking manipulability for the CP-majority, Banzhaf and lexicographic excellence solutions. In: Proceedings of the 29th international joint conference on artificial intelligence (IJCAI-20), pp 17–23 Allouche T, Escoffier B, Moretti S, Öztürk M (2021) Social ranking manipulability for the CP-majority, Banzhaf and lexicographic excellence solutions. In: Proceedings of the 29th international joint conference on artificial intelligence (IJCAI-20), pp 17–23
go back to reference Fishburn PC (1979) Symmetric and consistent aggregation with dichotomous voting. In: Laffont J-J (ed) Aggregation and revelation of preferences. North-Holland, Amsterdam, pp 201–218 Fishburn PC (1979) Symmetric and consistent aggregation with dichotomous voting. In: Laffont J-J (ed) Aggregation and revelation of preferences. North-Holland, Amsterdam, pp 201–218
go back to reference Haret A, Khani H, Moretti S, Ozturk M (2019) Ceteris paribus Majority for social ranking. In: 27th international joint conference on artificial intelligence (IJCAI-ECAI-18), July 2018, Stock Sweden, pp 303–309 Haret A, Khani H, Moretti S, Ozturk M (2019) Ceteris paribus Majority for social ranking. In: 27th international joint conference on artificial intelligence (IJCAI-ECAI-18), July 2018, Stock Sweden, pp 303–309
go back to reference Khani H, Moretti S, Ozturk M (2019) An ordinal Banzhaf index for social ranking. In: 28th international joint conference on artificial intelligence (IJCAI 2019), Aug 2019. Macao, China, pp 378–384 Khani H, Moretti S, Ozturk M (2019) An ordinal Banzhaf index for social ranking. In: 28th international joint conference on artificial intelligence (IJCAI 2019), Aug 2019. Macao, China, pp 378–384
go back to reference Moretti S, Öztürk M (2017) Some axiomatic and algorithmic perspectives on the social ranking problem. In: Rothe J (ed) Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics). Springer, Cham, pp 166–181 Moretti S, Öztürk M (2017) Some axiomatic and algorithmic perspectives on the social ranking problem. In: Rothe J (ed) Lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics). Springer, Cham, pp 166–181
go back to reference Suzuki T, Horita M (2021) Social ranking problem based on rankings of restricted coalitions. In: Morais DC, Fang L, Horita M (eds) Contemporary issues in group decision and negotiation. GDN 2021. Lecture notes in business information processing. Springer, Cham, pp 55–67 Suzuki T, Horita M (2021) Social ranking problem based on rankings of restricted coalitions. In: Morais DC, Fang L, Horita M (eds) Contemporary issues in group decision and negotiation. GDN 2021. Lecture notes in business information processing. Springer, Cham, pp 55–67
go back to reference Young HP (1974) An axiomatization of Borda’s rule. J Econ Theory 9(1):43–52CrossRef Young HP (1974) An axiomatization of Borda’s rule. J Econ Theory 9(1):43–52CrossRef
Metadata
Title
Consistent social ranking solutions
Authors
Takahiro Suzuki
Masahide Horita
Publication date
23-01-2024
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 3/2024
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-023-01502-1

Other articles of this Issue 3/2024

Social Choice and Welfare 3/2024 Go to the issue