# A new distance between rankings

Jean Dezert, Andrii Shekhovtsov, Wojciech Salabun

► To cite this version:

Jean Dezert, Andrii Shekhovtsov, Wojciech Salabun. A new distance between rankings. Heliyon, 2024, 10 (7), pp.e28265. 10.1016/j.heliyon.2024.e28265. hal-04635767

HAL Id: hal-04635767

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

Submitted on 4 Jul 2024

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

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

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

Research article

# A new distance between rankings

Jean Dezert<sup>a</sup>, Andrii Shekhovtsov<sup>b</sup>, Wojciech Salabun<sup>b,*</sup>

<figure><img src="image_4.png" /></figure>

## ARTICLE INFO

**Keywords:**

Ranking

Distance

F-distance

Spearman's distance

Kemeny's distance

Frobenius' distance

## ABSTRACT

This paper analyzes the behavior of the well-known Spearman's footrule distance (F-distance) to measure the distance between two rankings over the same set of objects. We show that F-distance is not invariant to labeling, and therefore, it suffers from a serious drawback for its use in applications. To circumvent this problem, we propose a new distance between rankings which is invariant under indexing (i.e., labeling) and appears as a good alternative to the direct use of F-distance between rankings, and also the invariant-under-indexing Kemeny's distance as well. We also show how our new distance can work with importance weights. Some simple examples are given to show the interest of our method with respect to the classical one based on F-distance and Kemeny's distance.

## 1. Introduction

In many multi-criteria decision-making (MCDA) problems, it is required to compare several methods to obtain a more reliable solution [26,31]. The problem of comparison of different methods is connected with the problem of measuring the distance or the correlation between rankings obtained using different methods [19,33].

There are many different correlation coefficients proposed to measure the difference between the two rankings. Such coefficients as Kendall Tau [18,29], Spearman's rank correlation coefficient [32], and weighted coefficients such as Weighted Spearman's correlation [6] and Weighted Similarity rank coefficient [28] are often used in the literature to compare the rankings [31,34]. However, those coefficients do not follow the properties of the distance definition: symmetry, separation, and triangular inequality.

In most cases, it is possible to use distance functions, such as Spearman's footrule [2,5], Kemeny's distance [13] or generalized Minkowski distance. However, they are not fulfilling invariance under the indexing principle (IUIP). It means that a calculation of the distance between two rankings could result in different values if a set of labels is changed. This behavior is not desired and not appropriate in most cases [16].

In some works, rankings are presented as an index of the labels set or as ordered labels set [8,25]. Researchers use this method to represent the rankings because it could be considered the most natural [10,21]. However, in this case, calculating the distance between rankings will result in violating invariance under the indexing principle. It is also possible to represent ranking by position [4,3]. Calculating the distance between such rankings will not violate IUIP, but creating ranking by position could be considered unnatural for some people. Therefore, we want to propose a new method for computation of the distances between ranking written by indexes, which will follow the properties of a true metric and satisfy IUIP, as well as axioms presented in [17].

<footnote><sup>a</sup> Department of Information Processing and Systems, The French Aerospace Lab - ONERA, 91120 Palaiseau, France</footnote>

<footnote><sup>b</sup> National Telecommunications Institute, ul. Szachowa 1, Warsaw, 04-894, Poland</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: jean.dezert@onera.fr (J. Dezert), a.shekhovtsov@il-pib.pl (A. Shekhovtsov), w.salabun@il-pib.pl (W. Salabun).</footnote>
The need for such distance metric is underlined with recent works, such as a proposition of WS<sub>dra</sub> metric by [27], which also fulfills the properties of a true metric and utilizes ranking by index to satisfy invariance under indexing principle. However, this metric utilizes an entirely different approach and can not be applied to long ranking vectors. The usage of a new metric is not limited only to measurements between different rankings. Such distance can also power distance-based methods such as TOPSIS [24] to potentially improve the decision-making quality. Additionally, it can be used in other domains besides MCDA, for example, in machine-learning-related algorithms that utilize distance functions, such as clustering [11,13], fuzzy clustering [12] or classification [30], where newly developed distances can greatly improve existing algorithms.

The main contribution of this paper is to propose a new effective method to calculate the distance between rankings, which will be invariant to the labeling of decision alternatives. The proposed approach fulfills IUIP and could be potentially extended and generalized to other distances. Additionally, it follows the properties of a true metric, i.e., symmetry, separation, and triangular inequality. We also prove that our proposed approach satisfies Kemeny's axioms for rankings distance metric [16]. The useful and desired properties of the proposed distance will ensure its applicability not only in the MCDA domain but also for other distance-related problems, such as distance-based machine-learning algorithms.

The rest of the paper is structured as follows. In Section 2, all necessary definitions and notations are provided. In Section 3, we describe the footrule distance proposed by Spearman and describe the problem of labeling invariance. Section 4 describes the invariance under the indexing principle and how it is violated when Spearman's F-distance is used. Next, in Section 5, we propose a new distance that overcomes the IUIP problem, and we compare it to Kemeny's distance. We all discuss Kemeny's axiomatic and extend our new distance for also working with importance weights. Finally, in Section 6, we draw conclusions and propose future work directions.

## 2. Definitions and notations

### 2.1. Distance

Let $X$ be a set. A function $d: X \times X \to \mathbb{R}_+$ is called a distance (or dissimilarity, or metric) on $X$, if the properties (1) - (3) hold [7] (Chap. 1)

1. Symmetry:

$$ \forall x, y \in X, d(x, y) = d(y, x), \qquad (1) $$

2. Separation (identity of indiscernibles):

$$ \forall x, y \in X, d(x, y) = 0 \Leftrightarrow x = y, \qquad (2) $$

3. Triangular inequality:

$$ \forall x, y, z \in X, d(x, z) \le d(x, y) + d(y, z). \qquad (3) $$

A set $X$ endowed with a distance is named a metric space, or a distance space.

There exist many distances proposed in the literature, see [7] for a good survey, but the most common ones are just specific cases of the Minkowski distance [20] of order $p$ (where $p \ge 1$ is an integer) between two points,<fnref n="1" /> $\mathbf{x} \triangleq [x_1, x_2, \dots, x_n]$ and $\mathbf{y} \triangleq [y_1, y_2, \dots, y_n]$ of the space $\mathbb{R}^n$ which is defined by (4)

$$ d_p(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_p \triangleq \left[ \sum_{i=1}^{n} |x_i - y_i|^p \right]^{1/p}. \qquad (4) $$

In practice, the Minkowski distance is used with $p=1$ or $p=2$. For $p=1$ the Minkowski distance is known as the Manhattan distance, or the city-clock distance, which is equal to (5)

$$ d_1(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_1 = \sum_{i=1}^{n} |x_i - y_i|. \qquad (5) $$

For $p=2$ the Minkowski distance is called the Euclidean distance given by (6)

$$ d_2(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_2 = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}. \qquad (6) $$

In the limiting case of $p$ reaching infinity, we obtain the Chebyshev distance (7)

$$ d_{\infty}(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_{\infty} = \max_{i=1, \dots, n} |x_i - y_i|. \qquad (7) $$

<footnote n="1">¹ The symbol $\triangleq$ means equals by definition.</footnote>
## 2.2. Preference order

Let's consider two objects denoted by $x_i$ and $x_j$. If the object $x_i$ is more preferred than object $x_j$, we denote this preference as $x_i > x_j$. If the object $x_i$ is less preferred than object $x_j$, we denote this preference as $x_i < x_j$. If objects $x_i$ and $x_j$ have no preference order, that is, neither preference $x_i > x_j$ or $x_j > x_i$ is valid, then we write $x_i = x_j$ for characterizing the indifference (or ex aequo preferences, or tie) in the choice between $x_i$ and $x_j$.

## 2.3. Reference set

Let $X = \{x_1, \dots, x_n\}$ be a set<fnref n="2" /> of items (or elements, or objects) to be ranked by an expert (either by a human expert opinion or by an artificial expert system). The set $X$ is called the reference set of objects if each object is labeled with a distinct given integer index $i = 1, \dots, n$. Because there are many ways to commit indexes to objects, the reference set is not unique. For instance, if we consider four objects $A, B, C$ and $D$ the reference set can be chosen either as $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$, $Y = \{y_1 = D, y_2 = C, y_3 = B, y_4 = A\}$, or defined by any other choice of permutation of indexes 1, 2, 3 and 4. Note that a reference set is a non-ordered set of elements, which means that the way to list the elements of the reference set does not matter. Hence in this example, the sets with all permutations of indexes $i = 1, 2, 3, 4$ like $\{x_1, x_2, x_3, x_4\}, \{x_2, x_1, x_3, x_4\}, \{x_3, x_2, x_1, x_4\}, \{x_4, x_1, x_2, x_3\}$, etc represent all the same reference set $X$.

## 2.4. Ranking-index and ranking

A ranking-index is an ordered $n$-uple associated to a reference set $X$. We denote it $r_X = (r_X(1), \dots, r_X(n))$, where $r_X(i)$ is the rank (or preference order) associated with the element $x_i$ of $X$. $r_X$ is a total (i.e., strict) ranking index if there is no equality of preference between some elements of $X$, which means that there is no tie in the preferences among some objects of the reference set. The sum of values of a total ranking index of size $n$ is the sum of the first $n$ natural numbers, which is equal to $n(n+1)/2$. A ranking $R_{r_X}(X)$ is a permutation of objects of the set $X$, which is determined by a preference ordering specified by a ranking-index $n$-uple $r_X$. Therefore, a ranking $R_{r_X}(X)$ associated with total ranking-index $r_X$ is a perfectly ordered set of objects. Each ranking of a set $X$ given by an expert $s$ (a source of information) is denoted by $R_{r_{X,s}}(X)$, and its ranking-index by $r_{X,s} = (r_{X,s}(1), \dots, r_{X,s}(n))$, where $r_{X,s}(i)$ is the rank associated with the element $x_i$ by the $s$-th source of information (for $s = 1, 2, \dots, S$). Without loss of generality and by convention, the first element of this ordered set $R_{r_{X,s}}(X)$ will be considered as the most preferred object by the $s$-th expert, the second element will be considered as the second best-preferred object by this expert, etc.

## 2.5. Example 1

Consider the reference set $X = \{x_1, x_2, x_3\}$, and suppose an expert<fnref n="3" /> commits to the element $x_2$ his best preference, to the element $x_3$ his second best preference, and to $x_1$ his last preference. This expert's preference order is denoted as $x_2 > x_3 > x_1$. His corresponding ranking-index is thus written as $r_X = (r_X(1), r_X(2), r_X(3)) = (2, 3, 1)$, where $r_X(1) = 2$ means that the 1st preferred object is $x_2$, $r_X(2) = 3$ means that the 2nd preferred object is $x_3$, and $r_X(3) = 1$ means that the 3rd preferred object is $x_1$. Because $r_X = (2, 3, 1)$, the ranking of $X$ for this expert is thus the ordered set $R_{r_X}(X) = \{x_2, x_3, x_1\}$.

## 2.6. Ranking-index including some ties

When two (or more) objects have the same preference order (i.e., their ranks are ex aequo) we write them as a non-ordered list of their indexes between inner left and right parentheses. For instance, if we consider four objects $A, B, C$ and $D$ and we define the reference set as $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$, then the preference order with one tie between two objects like $A > (B = D) > C$ corresponds to the tied ranking-index $r_X = (1, (2, 4), 3)$ which can also be written equivalently as $r_X = (1, (4, 2), 3)$. This notation means that object $x_1 = A$ is the most preferred object, the objects $x_2 = B$ and $x_4 = D$ have ex aequo second-best preference, and $x_3 = C$ is the least preferred object. In our interpretation and with our notation, the rank of the object $x_1 = A$ is 1, the rank of objects $x_2 = B$ and $x_4 = D$ are both equal to 2 because of the tie they both appear in the second component of the (tied) ranking-index $r_X = (1, (4, 2), 3)$, and the rank of the least preferred object $x_3 = C$ is 3. Note that the sum of rank values of all objects is then $1 + 2 + 2 + 3 = 9$, whereas it would be $1 + 2 + 3 + 4 = 10$ if no tie occurs. The corresponding tied ranking set for this tied preference order $A > (B = D) > C$ is denoted by $R_{r_X}(X) = \{x_1, (x_2, x_4), x_3\}$, and it is worth noting that in this case $R_{r_X}(X)$ is only a partially ordered because of the preference tie between objects $x_2$ and $x_4$.

If we consider another type of tie in preference, say $A > (B = C = D)$ (one tie with three objects), we write $r_X = (1, (2, 3, 4))$. If one considers the other tied preference order $(A = B) > (C = D)$ (two ties with two objects) we write $r_X = ((1, 2), (3, 4))$. In the whole indifference case where the (degenerate, or fully tied) preference order is $A = B = C = D$ (one tie with all the four objects), we write $r_X = ((1, 2, 3, 4))$. Note that the double parentheses notation is very important in order to identify the ties (if any) in the ranking index.

<footnote n="2">² Where referring to a set we implicitly refer to a non-ordered set of the naive set theory [15], otherwise we will specify ordered set whenever necessary.</footnote>

<footnote n="3">³ We omit here the index $s$ of the expert for the simplicity of notation because we consider only one expert in this example.</footnote>
Instead of using our previous interpretation and notations, some users working on ranking problems prefer to commit average rank to objects involved in a tie, for instance if we consider the reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ and a tied preference like $A > (B > D) > C$, they actually consider that both orders $A > B > D > C$ and $A > D > B > C$ are valid simultaneously. In this case, they consider that object $x_1 = A$ has rank 1 being the first/most preferred object, the rank of the object $x_2 = B$ is both 2 and 3 (so they take its middle-rank value 2.5), the rank of the object $x_4 = D$ is also both 2 and 3 (so they take it also its middle value 2.5), and the rank of least preferred object $x_3 = C$ is 4. With this classical method, the sum of ranks of objects is, for this example $1 + 2.5 + 2.5 + 4 = 10$, which is the same as the sum of rank values $1 + 2 + 3 + 4 = 10$ if no tie occurs in the preference order. This second method for dealing with ties is commonly used in practice, but the interpretation of non-integer values for ranks is difficult and questionable because it is clear that based on the sum of these rank values, we cannot discriminate if a preference order is strict/total (i.e., having no tie), or only partial (including ties) contrary to the previous method which is, we think, disputable.

### 3. Spearman $L_1$-distance between rankings

Spearman [32] proposed to use the $L_1$ distance to measure the distance between two ranking indexes. This distance is referred to as Spearman's footrule distance in [9]. It is also known as F-distance in the literature.

#### 3.1. Definition

The F-distance (i.e., Spearman $L_1$-distance) is the sum of the absolute differences between the components of the ranking indexes (i.e., n-uples). Suppose we have two experts providing two ranking-index n-uples $r_{X,1}$ and $r_{X,2}$ defined over the same reference set of objects $X = \{x_1, ..., x_n\}$, then the Spearman's footrule distance between $r_{X,1}$ and $r_{X,2}$ is defined as follows (8):

$$F(r_{X,1}, r_{X,2}) \triangleq \sum_{i=1}^{n} |r_{X,1}(i) - r_{X,2}(i)| \qquad (8)$$

where $r_{X,1}$ and $r_{X,2}$ are total ranking-indexes over the reference set of objects $X$.

The F-distance is nothing but an $L_1$-distance and a metric, and it is possible to compute it in linear time.

#### 3.2. Normalization of the F-distance

The F-distance can be normalized in [0, 1] by dividing $F(r_{X,1}, r_{X,2})$ by its maximum value $F^{\max}(n)$ which is obtained by calculating the F-distance between the two fully contradictory ranking-indexes $r_{X,1} = (1, 2, 3, ..., n-1, n)$ and $r_{X,2} = (n, n-1, ..., 3, 2, 1)$.
The maximum of F-distance is expressed as (9)

$$F^{\max}(n) = \sum_{i=1}^{n} |i - (n + 1 - i)| = \sum_{i=1}^{n} |2i - (n + 1)| \qquad (9)$$

Two cases must be analyzed to calculate $F^{\max}(n)$:

* Case 1: $n$ is an even number

If $n$ is an even number then $n = 2m$, and in this case we have $m = n/2$ and $F^{\max}(n)$ can be decomposed as (10)

$$F^{\max}(n) = \sum_{i=1}^{m} |2i - (2m + 1)| + \sum_{i=m+1}^{2m} |2i - (2m + 1)| \qquad (10)$$

We note that the sums $S_1 = \sum_{i=1}^{m} |2i - (2m + 1)|$ and $S_2 = \sum_{i=m+1}^{2m} |2i - (2m + 1)|$ are actually equal because the terms are equal when index increases in $S_1$ and decreases $S_2$. For instance for the first term (for $i = 1$) of $S_1$ we get $|2 - (2m + 1)| = |-2m + 1|$ and for the last term (for $i = 2m$) of $S_2$ we get $|2(2m) - (2m + 1)| = |2m - 1|$ and these two terms $|-2m + 1|$ and $|2m - 1|$ are equal. For the second term (for $i = 2$) of $S_1$ we get $|4 - (2m + 1)| = |3 - 2m|$ and for the penultimate term (for $i = 2m - 1$) of $S_2$ we get $|2(2m - 1) - (2m + 1)| = |2m - 3|$ and these two terms $|3 - 2m|$ and $|2m - 3|$ are equal, etc. For the last term (for $i = m$) of $S_1$ we get $|2m - (2m + 1)| = |-1| = 1$ and for the first term of $S_2$ we get $|2(m + 1) - (2m + 1)| = |1| = 1$. Therefore, if $n$ is an even number, we have (11)

$$F^{\max}(n) = 2 \cdot \sum_{i=1}^{m} |2i - (2m + 1)| = 2 \cdot S_1 \qquad (11)$$

Because $|2i - (2m + 1)|$ is always an odd number the sum $S_1 = \sum_{i=1}^{m} |2i - (2m + 1)|$ is equal to the sum of the $m$ first odd positive numbers, and it is given by $S_1 = m^2 = (\frac{n}{2})^2 = \frac{n^2}{4}$. Therefore, we finally get for $n = 2m$ (the even number case) (12)

$$F^{\max}(n) = 2 \cdot \frac{n^2}{4} = \frac{n^2}{2} \qquad (12)$$

* Case 2: $n$ is an odd number
If $n$ is an odd number then $n = 2m + 1$, and $F^{\max}(n)$ can always be decomposed as (13)

$$F^{\max}(n) = \sum_{i=1}^{m} |2i - (2m+2)| + \sum_{i=m+2}^{2m+1} |2i - (2m+2)|. \qquad (13)$$

Similarly to the previous case when $n = 2m$, one can also verify that the sum $S_3 = \sum_{i=1}^{m} |2i - (2m+2)|$ and $S_4 = \sum_{i=m+2}^{2m+1} |2i - (2m+2)|$ are equal, and therefore we have (14)

$$F^{\max}(n) = 2 \cdot \sum_{i=1}^{m} |2i - (2m+2)| = 2 \cdot S_3. \qquad (14)$$

Because $|2i - (2m+2)|$ is always an even number the sum $S_3 = \sum_{i=1}^{m} |2i - (2m+1)|$ is equal to the sum of the $m$ first even positive numbers, and it is given by $S_3 = m(m+1)$. Therefore, for $n = 2m+1$ (the odd number case), we get (15)

$$F^{\max}(n) = 2m(m+1). \qquad (15)$$

Because $n = 2m + 1$, one has $m = \frac{1}{2}(n - 1)$. Replacing the expression of $m$ in (15), we get (16)

$$F^{\max}(n) = \frac{1}{2}(n-1)(n+1). \qquad (16)$$

In summary, the normalized Spearman $F$-distance between two rankings $\tilde{F}(r_{X,1}, r_{X,2})$ is given by (17)

$$\tilde{F}(r_{X,1}, r_{X,2}) = \frac{F(r_{X,1}, r_{X,2})}{F^{\max}(n)} = \begin{cases} \frac{2}{n^2} \sum_{i=1}^{n} |r_{X,1}(i) - r_{X,2}(i)|, & (\text{if } n \text{ even}), \\ \frac{2}{(n-1)(n+1)} \sum_{i=1}^{n} |r_{X,1}(i) - r_{X,2}(i)|, & (\text{if } n \text{ odd}). \end{cases} \qquad (17)$$

If the normalized $F$-distance equals one it means two totally different rankings, and if it equals zero it means identical rankings.

### 3.3. Example 2 (with Spearman's $F$-distance)

Consider $n = 4$ different elements (or objects) denoted as $A, B, C$, and $D$ (for example, cars, bikes, houses, wines, or whatever). Suppose that the reference set of objects is chosen as $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$. We consider two experts providing each the ranking-indexes $r_{X,1} = (4, 2, 1, 3)$ and $r_{X,2} = (2, 3, 4, 1)$ expressing their own preference choice of these objects based on some own criteria. The ranking-index $r_{X,1} = (4, 2, 1, 3)$ means that the first expert has the preference order $D > B > A > C$, whereas $r_{X,2} = (2, 3, 4, 1)$ means that the second expert has the preference order $B > C > D > A$. Therefore, the ranked (ordered) sets are respectively equal to $R_{r_{X,1}}(X) = \{x_4, x_2, x_1, x_3\} = \{D, B, A, C\}$ and equal to $R_{r_{X,2}}(X) = \{x_2, x_3, x_4, x_1\} = \{B, C, D, A\}$. The $F$-distance between these two ranking-indexes $r_{X,1}$ and $r_{X,2}$ is (18)

$$F(r_{X,1}, r_{X,2}) = \sum_{i=1}^{4} |r_{X,1}(i) - r_{X,2}(i)| = |4-2| + |2-3| + |1-4| + |3-1| = 2+1+3+2=8, \qquad (18)$$

and (19)

$$\tilde{F}(r_{X,1}, r_{X,2}) = \left(\frac{2}{n^2}\right) \cdot F(r_{X,1}, r_{X,2}) = \frac{2}{16} \cdot 8 = 1. \qquad (19)$$

Because $\tilde{F}_X(r_{X,1}, r_{X,2}) = 1$ (which is the maximum normalized distance), it means that the rankings based on $r_{X,1}$ and $r_{X,2}$ are totally different and inconsistent. A priori, we may consider that this result makes sense because these two rankings, which reflect the preference orders $D > B > A > C$ and $B > C > D > A$, are very different, and because they do not share a same object at the same rank of the preference order because the two rankings are (20) and (21).

$$R_{r_{X,1}}(X) = \{D, B, A, C\}, \qquad (20)$$

$$R_{r_{X,2}}(X) = \{B, C, D, A\}. \qquad (21)$$

However, we can already suspect a problem in this $F$-distance measure because it does not capture well some partial consistencies between preferences orders $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ expressed by the experts. For example, in $\text{Pref}_1$ and in $\text{Pref}_2$ we have the preference $B > A$ satisfied, as well all the preference $D > A$. So it seems counter-intuitive to consider the rankings $R_{r_{X,1}}(X) = \{D, B, A, C\}$ and $R_{r_{X,2}}(X) = \{B, C, D, A\}$ as totally different and fully inconsistent.
### 3.4. Calculation of F-distance when ties occur

In our previous example 2, we considered rankings with no ties, and we did calculate the F-distance based on formula (8) without difficulty. For applying formula (8) when ties occur in the ranking index, we must proceed differently for indexes where a tie occurs. The classical method is to calculate the average value of all indexes involved in a tie and replace the indexes of the tie with their average value (which can be a noninteger index). Then, the formula (8) is used. For instance, if we consider the reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ and the preference order $Pref_1 = B > A > (D = C)$ and the second preference order $Pref_2 = B > (A = C) > D$, then the corresponding ranking-indexes are respectively given by $r_{X,1} = (2, 1, (3, 4))$ and $r_{X,2} = (2, (1, 3), 4)$. Replacing the indexes appearing in ties by their average value, we now consider the modified ranking-indexes $r'_{X,1} = (2, 1, 3.5, 3.5)$ and $r'_{X,2} = (2, 2, 2, 4)$ in the F-distance formula and we obtain (22)

$$F(r_{X,1}, r_{X,2}) = \sum_{i=1}^{4} |r'_{X,1}(i) - r'_{X,2}(i)| = |2 - 2| + |1 - 2| + |3.5 - 2| + |3.5 - 4| = 0 + 1 + 1.5 + 0.5 = 3. \quad (22)$$

This method for dealing with ties in ranking indexes is actually disputable because the interpretation and justification of non-integer indexes are unclear, and the averaging of indexes in ties yields multiplicities of some (integer and noninteger) indexes. We consider that this way of processing ties in ranking indexes is not very satisfying and effective. We will show how the new method proposed in this work solves this problem more effectively.

## 4. Invariance under indexing principle (IUIP)

### 4.1. Counter-example for the F-distance

This very simple F-distance is actually not satisfactory at all because it highly depends on the choice of the indexing of the objects in the reference set, which may yield very different results and conclusions. Based on a very simple counter-example, we show that F-distance does not satisfy the principle of invariance under indexing.

As a very simple counter-example, consider the same four distinct objects A, B, C, and D as in example 2, and define a new reference set as $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$. The experts do not change their preference orders, but the reference set is changed here. Therefore, for expert 1 we still have $Pref_1 \triangleq D > B > A > C$, and $Pref_2 \triangleq B > C > D > A$ for expert 2. The ranking-indexes expressed in the reference set $Y$ are respectively given by $r_{Y,1} = (2, 1, 3, 4)$ because $R_{r_{Y,1}}(Y) = \{y_2, y_1, y_3, y_4\} = \{D, B, A, C\}$, and we have $R_{r_{Y,1}}(Y) = R_{r_{X,1}}(X)$. Similarly, one must take $r_{Y,2} = (1, 4, 2, 3)$ because $R_{r_{Y,2}}(Y) = \{y_1, y_4, y_2, y_3\} = \{B, C, D, A\}$ and we have in this case $R_{r_{Y,2}}(Y) = R_{r_{X,2}}(X)$. If we calculate the F-distance between $r_{Y,1}$ and $r_{Y,2}$ we get (23)

$$F(r_{Y,1}, r_{Y,2}) = \sum_{i=1}^{4} |r_{Y,1}(i) - r_{Y,2}(i)| = |2 - 1| + |1 - 4| + |3 - 2| + |4 - 3| = 1 + 3 + 1 + 1 = 6, \quad (23)$$

and (24)

$$\tilde{F}(r_{Y,1}, r_{Y,2}) = \left(\frac{2}{n^2}\right) \cdot F(r_{Y,1}, r_{Y,2}) = \frac{2}{16} \cdot 6 = 0.75. \quad (24)$$

We see that the normalized F-distance $\tilde{F}(r_{Y,1}, r_{Y,2}) = 0.75$ between these two ranking-indexes $r_{Y,1}$ and $r_{Y,2}$ is different from $\tilde{F}(r_{X,1}, r_{X,2}) = 1$ obtained in (19). This result and behavior are very counter-intuitive because the rankings for each expert expressed in different reference sets contain exactly the same information about the preference orders, and of course, we have the same rankings because $R_{r_{Y,1}}(Y) = R_{r_{X,1}}(X)$ and $R_{r_{Y,2}}(Y) = R_{r_{X,2}}(X)$. So, there is absolutely no rational reason why the distances between these rankings must be different depending on the reference set chosen (either X or Y). Our example 2 and this counter-example represent the same ranking information, just expressed in the different reference sets X and Y, and one sees that we obtain two different results. Which one is correct and makes sense (if any)? Why? This simple counter-example casts in doubt the usefulness of the F-distance for applications requiring the measurement of a distance between two rankings. A good distance measure between two rankings must be independent of the choice of the reference set we are working with, which is referred to as invariance under the indexing principle (IUIP). Clearly, Spearman's F-distance does not satisfy this important principle.

## 5. A new distance between rankings

To overcome the problem of the non-invariance under indexing of the F-distance, we propose a new distance between rankings that satisfies all properties of a metric and satisfies IUIP.

The basic idea of establishing a new distance between rankings is to use all information available in the rankings given by the experts. More precisely, we need to count the different types of preference order in all possible pairwise comparisons between two elements of the reference set under consideration. This is done by calculating the $n \times n$ pairwise Preference-Score Matrix (PSM) based on the ranking given by each expert.

By convention, the row index $i$ of the PSM corresponds to the index of elements $x_i$ on the left side of preference order $x_i > x_j$, and the column index $j$ of the PSM corresponds to the index of the element $x_j$ on the right side of preference order $x_i > x_j$. Hence
we denote a pairwise Preference-Score Matrix $\mathbf{M}_{r_X}(X) = [M_{r_X}(i, j)]$ where its components $M_{r_X}(i, j)$ for $i, j = 1, 2, \dots, n$ are defined as (25)

$$ \mathbf{M}_{r_X}(i, j) = \begin{cases} 1, & \text{if } x_i > x_j, \\ -1, & \text{if } x_i < x_j, \\ 0, & \text{if } x_i = x_j. \end{cases} \tag{25} $$

Note that all components $M_{r_X}(i, i)$ ($i = 1, 2, \dots, n$) of the main diagonal of the matrix $\mathbf{M}_{r_X}$ are always equal to zero. Also, PSM is always an anti-symmetrical matrix by construction because the preference $x_i > x_j$ is equivalent to the preference $x_j < x_i$. Hence if $x_i > x_j$ is true which means $M_{r_X}(i, j) = 1$ then necessarily $x_j > x_i$ is false which means that $x_j < x_i$ is true and thus $M_{r_X}(j, i) = -1$, and the other way around. Consequently, $\mathbf{M}_{r_X}(X)^T = -\mathbf{M}_{r_X}(X)$, and $\mathrm{Tr}(\mathbf{M}_{r_X}(X)) = 0$.

In example 2, $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ and the preference order of expert 1 is $\mathrm{Pref}_1 \triangleq D > B > A > C$. Therefore, we have (26)

$$ \mathbf{M}_{r_{X,1}} = \begin{cases} x_1 = A & x_2 = B & x_3 = C & x_4 = D \\ x_2 = B & x_3 = C & x_4 = D \end{cases} \begin{pmatrix} 0 & -1 & 1 & -1 \\ 1 & 0 & 1 & -1 \\ -1 & -1 & 0 & -1 \\ 1 & 1 & 1 & 0 \end{pmatrix}. \tag{26} $$

The component $\mathbf{M}_{r_{X,1}(1,2)}$ of matrix $\mathbf{M}_{r_{X,1}}$ equals -1 because the preference $x_1 < x_2$ is true, or equivalently the preference $A < B$ is true because in $\mathrm{Pref}_1 \triangleq D > B > A > C$ we have $B > A$ which is equivalent to the preference $A < B$. Other values of components $\mathbf{M}_{r_{X,1}(i,j)}$ are obtained from the definition (25).

In example 2 where the reference set is $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$, the preference order of expert 2 is $\mathrm{Pref}_2 \triangleq B > C > D > A$, and we have (27)

$$ \mathbf{M}_{r_{X,2}} = \begin{cases} x_1 = A & x_2 = B & x_3 = C & x_4 = D \\ x_2 = B & x_3 = C & x_4 = D \end{cases} \begin{pmatrix} 0 & -1 & -1 & -1 \\ 1 & 0 & 1 & 1 \\ 1 & -1 & 0 & 1 \\ 1 & -1 & -1 & 0 \end{pmatrix}. \tag{27} $$

If we consider our simple counter-example using the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$, for expert 1 with ranking $\mathrm{Pref}_1 \triangleq D > B > A > C$ we have now (28)

$$ \mathbf{M}_{r_{Y,1}} = \begin{cases} y_1 = B & y_2 = D & y_3 = A & y_4 = C \\ y_2 = D & y_3 = A & y_4 = C \end{cases} \begin{pmatrix} 0 & -1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ -1 & -1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{pmatrix}. \tag{28} $$

If we consider our simple counter-example of Spearman's F-distance using the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$, for expert 2 with ranking $\mathrm{Pref}_2 \triangleq B > C > D > A$ we have the following PSM (29)

$$ \mathbf{M}_{r_{Y,2}} = \begin{cases} y_1 = B & y_2 = D & y_3 = A & y_4 = C \\ y_2 = D & y_3 = A & y_4 = C \end{cases} \begin{pmatrix} 0 & 1 & 1 & 1 \\ -1 & 0 & 1 & -1 \\ -1 & -1 & 0 & -1 \\ -1 & 1 & 1 & 0 \end{pmatrix}. \tag{29} $$

At this current stage, we have to find a way to measure the distance between the rankings based on the knowledge of the PSM of each expert. The natural idea is to use directly a distance between PSM matrices. In practice, there are many ways to define the distance between two matrices depending on the choice of a norm for the matrix. We first recall Kemeny's distance and then present our new distance and discuss the differences in their results.
## 5.1. Kemeny's distance

In [16], Kemeny used a particular axiomatic approach to define his distance between preferences orderings. More precisely, if we consider two rankings of $N$ objects from which we calculate their associated $n \times n$ ordering matrices<fnref n="4" /> $\mathbf{M}_1 = [M_1(i, j), i, j = 1, \dots, n]$ and $\mathbf{M}_2 = [M_2(i, j), i, j = 1, \dots, n]$ respectively, Kemeny's distance between these two rankings are defined as<fnref n="5" /> (30) [16]

$$d_K(\mathbf{M}_1, \mathbf{M}_2) = \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} |M_1(i, j) - M_2(i, j)|. \quad (30)$$

Kemeny's distance is a true metric invariant to labeling, and it satisfies our Invariance under the indexing principle (IUIP) because, in his axiomatic approach, he includes IUIP as a requested condition to satisfy (see condition 2 of [17], p. 587).

* Example 2 with $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$

In our example 2 when working with reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ and considering the preference orderings $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ we have the ordering matrices (31) and (32)

$$\mathbf{M}_{r_{X,1}} = \begin{bmatrix} 0 & -1 & 1 & -1 \\ 1 & 0 & 1 & -1 \\ -1 & -1 & 0 & -1 \\ 1 & 1 & 1 & 0 \end{bmatrix}, \quad (31)$$

and

$$\mathbf{M}_{r_{X,2}} = \begin{bmatrix} 0 & -1 & -1 & -1 \\ 1 & 0 & 1 & 1 \\ 1 & -1 & 0 & 1 \\ 1 & -1 & -1 & 0 \end{bmatrix}. \quad (32)$$

Applying Kemeny's definition (30) we obtain (33)

$$d_K(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} |M_{r_{X,1}}(i, j) - M_{r_{X,2}}(i, j)| = 6. \quad (33)$$

If we want to work with a normalized Kemeny's distance in [0, 1], then we need to calculate the maximum Kemeny's distance, which is naturally obtained when the two preference orderings are in total contradiction, that is, for instance, when $\text{Pref}_1 \triangleq A > B > C > D$ and $\text{Pref}_2 \triangleq D > C > B > A$. This corresponds to ordering matrices (34) and (35)

$$\mathbf{M}'_{r_{X,1}} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ -1 & 0 & 1 & 1 \\ -1 & -1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{bmatrix}, \quad (34)$$

and

$$\mathbf{M}'_{r_{X,2}} = \begin{bmatrix} 0 & -1 & -1 & -1 \\ 1 & 0 & -1 & -1 \\ 1 & 1 & 0 & -1 \\ 1 & 1 & 1 & 0 \end{bmatrix}. \quad (35)$$

Applying Kemeny's definition (30) we obtain (36)

$$d_K^{\max} = d_K(\mathbf{M}'_{r_{X,1}}, \mathbf{M}'_{r_{X,2}}) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} |M'_{r_{X,1}}(i, j) - M'_{r_{X,2}}(i, j)| = 12. \quad (36)$$

The normalized Kemeny's distance between preference orderings $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ when working on the reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ is finally given by (37)

$$\tilde{d}_K(\mathbf{M}_1, \mathbf{M}_2) = \frac{d_K(\mathbf{M}_1, \mathbf{M}_2)}{d_K^{\max}} = \frac{6}{12} = 0.5 \quad (37)$$

* Example 2 with $Y = \{y_1 = B, y_2 = D, y_3 = C, y_4 = C\}$

<footnote n="4">⁴ Kemeny's ordering matrix coincides with the PSM whose elements are defined by (25).</footnote>

<footnote n="5">⁵ We use the subscript K in our notation to refer to Kemeny.</footnote>
If we consider our example 2 using the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$, for expert 1 with ranking $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ we consider now the ordering matrices (38) and (39)

$$ \mathbf{M}_{r_{Y,1}} = \begin{bmatrix} 0 & -1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ -1 & -1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{bmatrix}, \qquad (38) $$

and

$$ \mathbf{M}_{r_{Y,2}} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ -1 & 0 & 1 & -1 \\ -1 & -1 & 0 & -1 \\ -1 & 1 & 1 & 0 \end{bmatrix}. \qquad (39) $$

Applying Kemeny's definition (30) we obtain (40)

$$ d_K(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}}) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} |M_{r_{Y,1}}(i, j) - M_{r_{Y,2}}(i, j)| = 6. \qquad (40) $$

If we want to work with a normalized Kemeny's distance in [0, 1] then we need to calculate the maximum Kemeny's distance obtained when the two preference orderings are in total contradiction, that is for instance when $\text{Pref}'_1 \triangleq A > B > C > D$ and $\text{Pref}'_2 \triangleq D > C > B > A$. This corresponds to ordering matrices expressed w.r.t. the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$ as follows (41)

$$ \mathbf{M}'_{r_{Y,1}} = \begin{bmatrix} 0 & 1 & -1 & 1 \\ -1 & 0 & -1 & -1 \\ 1 & 1 & 0 & 1 \\ -1 & 1 & -1 & 0 \end{bmatrix}, \qquad (41) $$

and (42)

$$ \mathbf{M}'_{r_{Y,2}} = \begin{bmatrix} 0 & -1 & 1 & -1 \\ 1 & 0 & 1 & 1 \\ -1 & -1 & 0 & -1 \\ 1 & -1 & 1 & 0 \end{bmatrix}. \qquad (42) $$

Applying Kemeny's definition (30) we obtain (43)

$$ d_K^{\max} = d_K(\mathbf{M}'_{r_{Y,1}}, \mathbf{M}'_{r_{Y,2}}) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} |M'_{r_{Y,1}}(i, j) - M'_{r_{Y,2}}(i, j)| = 12. \qquad (43) $$

The normalized Kemeny's distance between preference orderings $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ when working on the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$ is finally given by (44)

$$ \tilde{d}_K(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}}) = \frac{d_K(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}})}{d_K^{\max}} = \frac{6}{12} = 0.5 \qquad (44) $$

We verify that Kemeny's distance is independent of the reference set chosen (i.e. the indexing, or labeling) for the objects because we have for our example 2 (45):

$$ \tilde{d}_K(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = \tilde{d}_K(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}}) = 0.5 \qquad (45) $$

Based on this normalized Kemeny's distance $\tilde{d}_K(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = 0.5$ we cannot establish for sure if the two rankings are more similar, or if they are more dissimilar because the normalized Kemeny's distance 0.5 is just in the middle of interval [0, 1].

## 5.2. A new ranking distance based on Frobenius' norm

Here, we consider the vectorial space $M_n$ of the real square matrices of dimension $n \times n$, and we propose to use the well-known Frobenius' norm, which is one of the most frequent matrix norms used in linear algebra. Frobenius' norm $||\mathbf{M}||_F$ of a square matrix $\mathbf{M} = [M(i, j), i, j = 1, \dots, n] \in M_n$ is defined by (46) [14,23]

$$ ||\mathbf{M}||_F = \sqrt{\sum_{i=1}^{n} \sum_{j=1}^{n} |M(i, j)|^2} = \sqrt{\text{Tr}(\mathbf{M}^T \mathbf{M})}, \qquad (46) $$
where $\mathbf{M}^T$ is the transpose of the matrix $\mathbf{M}$, and Tr(.) is the trace operator for matrix. Based on this norm, the distance between two matrices $\mathbf{M}_1$ and $\mathbf{M}_2$ of the same dimensions is simply defined by<fnref n="6" /> (47)

$$d_F(\mathbf{M}_1, \mathbf{M}_2) = \|\mathbf{M}_1 - \mathbf{M}_2\|_F. \qquad (47)$$

**Theorem.** The Frobenius' distance $d_F(\mathbf{M}_1, \mathbf{M}_2)$ satisfies the invariance under indexing principle.

**Proof.** Consider a reference set $X = \{x_1, x_2, ..., x_n\}$ of $n$ objects, and another reference set $Y = \{y_1, y_2, ..., y_n\}$ for these $n$ objects, then there is a permutation matrix ($U$) that transforms $X$ into $Y$ [22] such that $\mathbf{y} = \mathbf{U}\mathbf{x}$, where $\mathbf{y} \triangleq [y_1, y_2, ..., y_n]^T$ and $\mathbf{x} \triangleq [x_1, x_2, ..., x_n]^T$ [22]. This permutation matrix $U$ is a unitary orthogonal matrix [23] that verifies $\mathbf{U}^T\mathbf{U} = \mathbf{U}\mathbf{U}^T = \mathbf{I}_{n \times n}$, where $\mathbf{I}_{n \times n}$ is the $n \times n$ identity matrix. If one considers a preference ordering $\text{Pref}_X$ expressed on the reference set $X$ and its corresponding preference ordering $\text{Pref}_Y$ expressed on the reference set $Y$, the corresponding ordering matrices $\mathbf{M}_X$ and $\mathbf{M}_Y$ are similar because they are linked via the orthogonal matrix $\mathbf{U}$. Consequently, we have<fnref n="7" /> (48)

$$\mathbf{M}_Y = \mathbf{U}^{-1}\mathbf{M}_X\mathbf{U} \qquad (48)$$

If we consider two ordering matrices $\mathbf{M}_{Y,1} = \mathbf{U}^{-1}\mathbf{M}_{X,1}\mathbf{U}$ and $\mathbf{M}_{Y,2} = \mathbf{U}^{-1}\mathbf{M}_{X,2}\mathbf{U}$ characterizing two preferences orderings $\text{Pref}_{Y,1}$ and $\text{Pref}_{Y,2}$ defined on the reference set $Y$, we have (49)

$$\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2} = \mathbf{U}^{-1}\mathbf{M}_{X,1}\mathbf{U} - \mathbf{U}^{-1}\mathbf{M}_{X,2}\mathbf{U} = \mathbf{U}^{-1}(\mathbf{M}_{X,1} - \mathbf{M}_{X,2})\mathbf{U} \qquad (49)$$

and its transpose is expressed as (50)

$$(\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})^T = (\mathbf{U}^{-1}(\mathbf{M}_{X,1} - \mathbf{M}_{X,2})\mathbf{U})^T = \mathbf{U}^T(\mathbf{M}_{X,1} - \mathbf{M}_{X,2})^T(\mathbf{U}^{-1})^T \qquad (50)$$

Therefore (51),

$$(\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})^T (\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2}) = \mathbf{U}^T (\mathbf{M}_{X,1} - \mathbf{M}_{X,2})^T (\mathbf{U}^{-1})^T \mathbf{U}^{-1} (\mathbf{M}_{X,1} - \mathbf{M}_{X,2}) \mathbf{U} \qquad (51)$$

Because $\mathbf{U}^T\mathbf{U} = \mathbf{I}_{n \times n}$ ($\mathbf{U}$ being a unitary orthogonal matrix), we have $\mathbf{U}^T = \mathbf{U}^{-1}$ and so $(\mathbf{U}^{-1})^T = (\mathbf{U}^T)^T = \mathbf{U}$, so that $(\mathbf{U}^{-1})^T\mathbf{U}^{-1} = \mathbf{I}_{n \times n}$. Therefore the matrix product $(\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})^T(\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})$ is written as (52)

$$(\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})^T (\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2}) = \mathbf{U}^T (\mathbf{M}_{X,1} - \mathbf{M}_{X,2})^T (\mathbf{M}_{X,1} - \mathbf{M}_{X,2}) \mathbf{U} = \mathbf{U}^{-1} (\mathbf{M}_{X,1} - \mathbf{M}_{X,2})^T (\mathbf{M}_{X,1} - \mathbf{M}_{X,2}) \mathbf{U} \qquad (52)$$

Because the matrices in the trace of a product can be switched without changing the result (which is called the similarity invariance of the trace operator) [23] meaning that $\text{Tr}(\mathbf{A}) = \text{Tr}(\mathbf{P}^{-1}\mathbf{A}\mathbf{P})$ for any square matrix $\mathbf{A}$ and any invertible matrix $\mathbf{P}$ of the same dimensions, we always have (53)

$$\text{Tr}((\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})^T (\mathbf{M}_{Y,1} - \mathbf{M}_{Y,2})) = \text{Tr}(\mathbf{U}^{-1}(\mathbf{M}_{X,1} - \mathbf{M}_{X,2})^T (\mathbf{M}_{X,1} - \mathbf{M}_{X,2})\mathbf{U}) = \text{Tr}((\mathbf{M}_{X,1} - \mathbf{M}_{X,2})^T (\mathbf{M}_{X,1} - \mathbf{M}_{X,2})) \qquad (53)$$

Consequently, we always have (54)

$$d_F(\mathbf{M}_{Y,1}, \mathbf{M}_{Y,2}) = d_F(\mathbf{M}_{X,1}, \mathbf{M}_{X,2}) \qquad (54)$$

This shows that the Frobenius' distance between two preference orderings characterized by their ordering matrices is invariant under indexing, meaning it is independent of the choice of reference set we work with. This completes the proof of the theorem.

* Example 2 with $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$

In our example 2 and when working with reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ we work with PSM $\mathbf{M}_{r_{X,1}}$ given in (31) and $\mathbf{M}_{r_{X,2}}$ given in (32), and we have (55)

$$\mathbf{M}_{r_{X,1}} - \mathbf{M}_{r_{X,2}} = \begin{bmatrix} 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & -2 \\ -2 & 0 & 0 & -2 \\ 0 & 2 & 2 & 0 \end{bmatrix}, \qquad (55)$$

and (56)

$$(\mathbf{M}_{r_{X,1}} - \mathbf{M}_{r_{X,2}})^T = \begin{bmatrix} 0 & 0 & -2 & 0 \\ 0 & 0 & 0 & 2 \\ 2 & 0 & 0 & 2 \\ 0 & -2 & -2 & 0 \end{bmatrix}. \qquad (56)$$

<footnote n="6">⁶ We use the subscript F in our notation to refer to Frobenius.</footnote>

<footnote n="7">⁷ See the definition of similar matrices in [23].</footnote>
Therefore (57),

$$ (\mathbf{M}_{r_{X,1}} - \mathbf{M}_{r_{X,2}})^T (\mathbf{M}_{r_{X,1}} - \mathbf{M}_{r_{X,2}}) = \begin{bmatrix} 4 & 0 & 0 & 4 \\ 0 & 4 & 4 & 0 \\ 0 & 4 & 8 & 0 \\ 4 & 0 & 0 & 8 \end{bmatrix}. \qquad (57) $$

Hence (58)

$$ \mathrm{Tr}((\mathbf{M}_{r_{X,1}} - \mathbf{M}_{r_{X,2}})^T (\mathbf{M}_{r_{X,1}} - \mathbf{M}_{r_{X,2}})) = 4 + 4 + 8 + 8 = 24 \qquad (58) $$

and we finally get (59)

$$ d_F(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = \sqrt{24} \approx 4.8990 \qquad (59) $$

If we want to work with a normalized distance in [0, 1], then we need to calculate the maximum distance that is naturally obtained when the two preference orderings are in total contradiction, that is, for instance, when $\mathrm{Pref}_1' \triangleq A > B > C > D$ and $\mathrm{Pref}_2' \triangleq D > C > B > A$. This corresponds to PSM matrices (60)

$$ \mathbf{M}'_{r_{X,1}} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ -1 & 0 & 1 & 1 \\ -1 & -1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{bmatrix}, \qquad (60) $$

and (61)

$$ \mathbf{M}'_{r_{X,2}} = \begin{bmatrix} 0 & -1 & -1 & -1 \\ 1 & 0 & -1 & -1 \\ 1 & 1 & 0 & -1 \\ 1 & 1 & 1 & 0 \end{bmatrix}. \qquad (61) $$

Hence (62),

$$ \mathbf{M}'_{r_{X,1}} - \mathbf{M}'_{r_{X,2}} = \begin{bmatrix} 0 & 2 & 2 & 2 \\ -2 & 0 & 2 & 2 \\ -2 & -2 & 0 & 2 \\ -2 & -2 & -2 & 0 \end{bmatrix}, \qquad (62) $$

and (63)

$$ (\mathbf{M}'_{r_{X,1}} - \mathbf{M}'_{r_{X,2}})^T = \begin{bmatrix} 0 & -2 & -2 & -2 \\ 2 & 0 & -2 & -2 \\ 2 & 2 & 0 & -2 \\ 2 & 2 & 2 & 0 \end{bmatrix}. \qquad (63) $$

Therefore (64),

$$ (\mathbf{M}'_{r_{X,1}} - \mathbf{M}'_{r_{X,2}})^T (\mathbf{M}'_{r_{X,1}} - \mathbf{M}'_{r_{X,2}}) = \begin{bmatrix} 12 & 8 & 0 & -8 \\ 8 & 12 & 8 & 0 \\ 0 & 8 & 12 & 8 \\ -8 & 0 & 8 & 12 \end{bmatrix}. \qquad (64) $$

Hence (65)

$$ \mathrm{Tr}((\mathbf{M}'_{r_{X,1}} - \mathbf{M}'_{r_{X,2}})^T (\mathbf{M}'_{r_{X,1}} - \mathbf{M}'_{r_{X,2}})) = 12 + 12 + 12 + 12 = 48, \qquad (65) $$

and we finally get<fnref n="8" /> (66)

$$ d_{F,X}^{\max} = d_F(\mathbf{M}'_{r_{X,1}}, \mathbf{M}'_{r_{X,2}}) = \sqrt{48} \approx 6.9282 \qquad (66) $$

The normalized Frobenius' distance between preference orderings $\mathrm{Pref}_1' \triangleq D > B > A > C$ and $\mathrm{Pref}_2' \triangleq B > C > D > A$ when working on the reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ is finally given by (67)

$$ \bar{d}_F(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = \frac{d_F(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}})}{d_{F,X}^{\max}} \approx 0.7071. \qquad (67) $$

<footnote n="8">⁸ The double subscript F, X introduced in $d_{F,X}^{\max}$ is necessary to indicate explicitly the reference set we are working with, i.e., the set X here.</footnote>
• Example 2 with $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$

If we consider our example 2 using the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$, for expert 1 with ranking $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ we consider now the ordering matrices $\mathbf{M}_{r_{Y,1}}$ given by (38), and $\mathbf{M}_{r_{Y,2}}$ given by (39). Applying the distance definition (47) we obtain (68)

$$ \mathbf{M}_{r_{Y,1}} - \mathbf{M}_{r_{Y,2}} = \begin{bmatrix} 0 & -2 & 0 & 0 \\ 2 & 0 & 0 & 2 \\ 0 & 0 & 0 & 2 \\ 0 & -2 & -2 & 0 \end{bmatrix}, \qquad (68) $$

and (69)

$$ (\mathbf{M}_{r_{Y,1}} - \mathbf{M}_{r_{Y,2}})^T = \begin{bmatrix} 0 & 2 & 0 & 0 \\ -2 & 0 & 0 & -2 \\ 0 & 0 & 0 & -2 \\ 0 & 2 & 2 & 0 \end{bmatrix}. \qquad (69) $$

Therefore (70),

$$ (\mathbf{M}_{r_{Y,1}} - \mathbf{M}_{r_{Y,2}})^T (\mathbf{M}_{r_{Y,1}} - \mathbf{M}_{r_{Y,2}}) = \begin{bmatrix} 4 & 0 & 0 & 4 \\ 0 & 8 & 4 & 0 \\ 0 & 4 & 4 & 0 \\ 4 & 0 & 0 & 8 \end{bmatrix}. \qquad (70) $$

Hence (71)

$$ \text{Tr}((\mathbf{M}_{r_{Y,1}} - \mathbf{M}_{r_{Y,2}})^T (\mathbf{M}_{r_{Y,1}} - \mathbf{M}_{r_{Y,2}})) = 4 + 8 + 4 + 8 = 24, \qquad (71) $$

and we finally get (72)

$$ d_F(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}}) = \sqrt{24} \approx 4.8990. \qquad (72) $$

If we want to work with a normalized distance in $[0, 1]$, then we need to calculate the maximum distance obtained when the two preference orderings are in total contradiction, that is, for instance, when $\text{Pref}'_1 \triangleq A > B > C > D$ and $\text{Pref}'_2 \triangleq D > C > B > A$. This corresponds to ordering matrices $\mathbf{M}'_{r_{Y,1}}$ given by (41) and $\mathbf{M}'_{r_{Y,2}}$ given by (42) expressed w.r.t. the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$. Applying the distance definition (47) we obtain (73)

$$ \mathbf{M}'_{r_{Y,1}} - \mathbf{M}'_{r_{Y,2}} = \begin{bmatrix} 0 & 2 & -2 & 2 \\ -2 & 0 & -2 & -2 \\ 2 & 2 & 0 & 2 \\ -2 & 2 & -2 & 0 \end{bmatrix}, \qquad (73) $$

and (74)

$$ (\mathbf{M}'_{r_{Y,1}} - \mathbf{M}'_{r_{Y,2}})^T = \begin{bmatrix} 0 & -2 & 2 & -2 \\ 2 & 0 & 2 & 2 \\ -2 & -2 & 0 & -2 \\ 2 & -2 & 2 & 0 \end{bmatrix}, \qquad (74) $$

and (75)

$$ (\mathbf{M}'_{r_{Y,1}} - \mathbf{M}'_{r_{Y,2}})^T (\mathbf{M}'_{r_{Y,1}} - \mathbf{M}'_{r_{Y,2}}) = \begin{bmatrix} 12 & 0 & 8 & 8 \\ 0 & 12 & -8 & 8 \\ 8 & -8 & 12 & 0 \\ 8 & 8 & 0 & 12 \end{bmatrix}. \qquad (75) $$

Hence (76)

$$ \text{Tr}((\mathbf{M}'_{r_{Y,1}} - \mathbf{M}'_{r_{Y,2}})^T (\mathbf{M}'_{r_{Y,1}} - \mathbf{M}'_{r_{Y,2}})) = 12 + 12 + 12 + 12 = 48, \qquad (76) $$

and we finally get (77)

$$ d_{F,Y}^{\max} = d_F(\mathbf{M}'_{r_{Y,1}}, \mathbf{M}'_{r_{Y,2}}) = \sqrt{48} \approx 6.9282. \qquad (77) $$

The normalized Frobenius' distance between preference orderings $\text{Pref}_1 \triangleq D > B > A > C$ and $\text{Pref}_2 \triangleq B > C > D > A$ when working on the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$ is finally given by (78)

$$ \tilde{d}(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}}) = \frac{d_F(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}})}{d_{F,Y}^{\max}} \approx 0.7071. \qquad (78) $$
<table><caption>**Table 1**
Relative consistencies in $\mathrm{Pref}_1$ and $\mathrm{Pref}_2$.</caption><thead><tr><th>Pref<sub>1</sub></th><th>Pref<sub>2</sub></th></tr></thead><tbody><tr><td>D &gt;&gt; A</td><td>D &gt; A</td></tr><tr><td>B &gt; A</td><td>B &gt;&gt;&gt; A</td></tr><tr><td>B &gt;&gt; C</td><td>B &gt; C</td></tr></tbody></table>

<table><caption>**Table 2**
Inconsistencies in $\mathrm{Pref}_1$ and $\mathrm{Pref}_2$.</caption><thead><tr><th>Pref<sub>1</sub></th><th>Pref<sub>2</sub></th></tr></thead><tbody><tr><td>D &gt; B</td><td>B &gt;&gt; D</td></tr><tr><td>D &gt;&gt;&gt; C</td><td>C &gt; D</td></tr><tr><td>A &gt; C</td><td>C &gt;&gt; A</td></tr></tbody></table>

We have verified that this new ranking distance based on the Frobenius' norm is independent of the reference set chosen (i.e., the indexing, or labeling) for the objects because we have, for our example 2 (79)

$$ \tilde{d}_F(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = \tilde{d}_F(\mathbf{M}_{r_{Y,1}}, \mathbf{M}_{r_{Y,2}}) \approx 0.7071. \qquad (79) $$

**Remark 1.** It is worth to check that the unitary orthogonal matrix $U$ for the permutation from the reference set $X = \{x_1 = A, x_2 = B, x_3 = C, x_4 = D\}$ to the reference set $Y = \{y_1 = B, y_2 = D, y_3 = A, y_4 = C\}$ is given by (80)

$$ U = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{bmatrix}. \qquad (80) $$

As mentioned in the proof of the Theorem, we can verify that $U^T U = U U^T = I_{4 \times 4}$, and the equalities (81) and (82) hold.

$$ \mathbf{M}_{r_{Y,1}} = U^T \mathbf{M}_{r_{X,1}} U, \qquad (81) $$

$$ \mathbf{M}_{r_{Y,2}} = U^T \mathbf{M}_{r_{X,2}} U. \qquad (82) $$

**Remark 2.** In our example 2, it is interesting to observe that normalized Kemeny's distance and normalized Frobenius' distance between the two rankings of example 2 provide different interpretations about these rankings. Based on normalized Kemeny's distance $\tilde{d}_K(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = 0.5$, it is clear that we cannot assert for sure if the two preference orderings $\mathrm{Pref}_1 \triangleq D > B > A > C$ and $\mathrm{Pref}_2 \triangleq B > C > D > A$ are more similar than dissimilar because the distance 0.5 we get is in the middle of interval $[0, 1]$. However, based on the normalized Frobenius' distance $\tilde{d}_F(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = 0.7071$, we can clearly infer that $\mathrm{Pref}_1$ and $\mathrm{Pref}_2$ are more dissimilar than similar because their $d_F = 0.7071$ distance is closer to 1, than to 0. Which interpretation is correct and makes sense? To answer this question, we must examine the relative consistencies and inconsistencies in $\mathrm{Pref}_1$ and $\mathrm{Pref}_2$ orderings, which are summarized in Tables 1 & 2.

In the Tables 1 & 2, the double $\gg$ notation indicates that there is one object between the left-object side of $\gg$ and its right-object side. For instance, in Table 1, $D \gg A$ means that we have “$D >$ some object $> A$”. Similarly, the triple $\gg\gg$ notation indicates that there are two objects in between.

Based on the Tables 1 & 2, one could argue that preference orderings include three relative consistencies and three inconsistencies, and so we may consider there is no reason to establish that they are more similar than dissimilar. This is what Kemeny's distance tells us with $\tilde{d}_K(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = 0.5$. We think that this reasoning is disputable because we note that the relative consistencies of Table 1 are different. For instance, in Table 1 we have $B > A$ for $\mathrm{Pref}_1$, whereas $B \gg\gg A$ for $\mathrm{Pref}_2$, etc. So, we think it is more reasonable to consider $\mathrm{Pref}_1$ and $\mathrm{Pref}_2$ as more dissimilar than similar, and this is what expresses the Frobenius' distance $\tilde{d}_F(\mathbf{M}_{r_{X,1}}, \mathbf{M}_{r_{X,2}}) = 0.7071$.

### 5.3. On Kemeny's axiomatic

We recall the four axioms used by Kemeny's to justify his distance (see [16], Chap. 2).

**Axiom 1:**

- Axiom 1.1: $d(A, B) \ge 0$, and inequality holds if and only if $A$ and $B$ are same ranking.

- Axiom 1.2: $d(A, B) = d(B, A)$.

- Axiom 1.3: $d(A, B) + d(B, C) \ge d(A, C)$, and the equality holds if and only if the ranking $B$ is between $A$ and $C$.
* **Axiom 2:** If $A'$ results of $A$ by a permutation of objects, and $B'$ results of $B$ by the same permutation of objects, then $d(A', B') = d(A, B)$.

* **Axiom 3:** If two rankings $A$ and $B$ agree except for a set $S$ of $k$ elements, which is a segment of both, then $d(A, B)$ may be computed as if these $k$ objects where the only objects being ranked.

* **Axiom 4:** The minimum positive distance is 1.

Axiom 1 stipulates that the distance must be a true metric, and axiom 2 corresponds to the invariance under the indexing principle. Axioms 1 & 2 are good natural axioms for establishing a distance between rankings. To verify Axiom 1.3, Kemeny's needs to choose a notion of "betweenness". The definition of a distance based on a norm of a matrix is more general and mathematically well defined. This is why we prefer to use the Frobenius' norm of a matrix for establishing the Frobenius' distance between rankings in this study.

Kemeny's Axiom 3 stipulates that if two rankings are in complete agreement at the beginning and at the end of the list and differ only in the middle, then the distance does not change after deleting both the first and the last objects to be ranked [1]. This axiom 3 is not so intuitive in our opinion but is rather a consequence of working with PSM. Obviously, Frobenius' distance $d_F$ satisfies Kemeny's axiom 3 because the matrix $M = M_1 - M_2$ will be a square matrix with all its bordering elements equal to zero because the first elements and the last elements of the rankings are the same for the conditions of rankings expressed in Axiom 3. Consequently, the distance result $d_F$ will depend only of the non-zero elements of $M = M_1 - M_2$ (i.e. the elements of its "interior" sub-matrix $M_{int}$). For instance, if one considers four objects with preferences $Pref_1 = A > B > C > D$ and $Pref_2 = A > C > B > D$ satisfying conditions of Axiom 3, then we have the PSM (83)

$$ M_1 = \begin{bmatrix} 0 & 1 & 1 & 1 \\ -1 & 0 & 1 & 1 \\ -1 & -1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{bmatrix}, \quad M_2 = \begin{bmatrix} 0 & 1 & 1 & 1 \\ -1 & 0 & -1 & 1 \\ -1 & 1 & 0 & 1 \\ -1 & -1 & -1 & 0 \end{bmatrix}. \qquad (83) $$

Hence, $M_1 - M_2$ is the zero-border matrix equal to (84)

$$ M = M_1 - M_2 = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & -2 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} \mathbf{0} & \cdots & \mathbf{0} \\ \vdots & \ddots & \vdots \\ \mathbf{0} & \cdots & \mathbf{0} \end{bmatrix}, \qquad (84) $$

where the interior sub-matrix $M_{int}$ is (85)

$$ M_{int} = \begin{bmatrix} 0 & 2 \\ -2 & 0 \end{bmatrix}. \qquad (85) $$

Therefore (86),

$$ M^T M = \begin{bmatrix} \mathbf{0} & \cdots & \mathbf{0} \\ \vdots & \ddots & \vdots \\ \mathbf{0} & \cdots & \mathbf{0} \end{bmatrix}. \qquad (86) $$

Clearly, $\mathrm{Tr}(M^T M) = \mathrm{Tr}(M_{int}^T M_{int})$, and Frobenius' distance is $d_F(M_1, M_2) = \sqrt{\mathrm{Tr}(M^T M)} = \sqrt{\mathrm{Tr}(M_{int}^T M_{int})}$. This proves that the Frobenius' distance between $M_1$ and $M_2$ does not change after deleting both the first and the last objects to be ranked because it depends only on interior sub-matrix $M_{int}$ which is nothing but the PSM of objects in the middle of rankings that have swapped.

As written by Kemeny himself in [16] (p. 10), the axiom 4 is "in the nature of a convention". This axiom 4 has been chosen to fit with Kemeny's distance definition, but it is actually arbitrary and disputable. It is worth noting that this minimal Kemeny's positive distance of 1 is obtained only between a strict (i.e., proper) ranking and a tied ranking as shown by Kemeny's in his example for the 3-objects case (see Fig. 2 of [16], p. 17, and next in this paper on Fig. 1). We can also justify the Frobenius' distance between rankings by modifying the arbitrary Kemeny's axiom 4 in order to fit with the Frobenius' distance definition as well, and thus requiring that the minimum positive distance is $\sqrt{2}$ (because $\sqrt{2}$ is the minimum positive Frobenius' distance between the simple preference $A > B$ and the tie $A = B$). This would not be more arbitrary than the choice made by Kemeny for his axiom 4. Or if we prefer, we can scale (i.e. divide) the Frobenius's distance by the factor $\sqrt{2}$ to satisfy Kemeny's axiom 4, and we can work with $\frac{1}{\sqrt{2}} d_F(M_1, M_2)$ instead of Kemeny's distance without violating Kemeny's axiomatic.

Consequently, Kemeny's statement about the unicity of his distance verifying his axiomatic is wrong because the $(\sqrt{2}$-scaled) Frobenius' distance also satisfies his axiomatic. The justification of Frobenius' distance between rankings has the same axiomatic strength as Kemeny's approach, and it cannot be disputed or discarded based on Kemeny's axiomatic argumentation.

## 5.4. Comparison of Frobenius' distance with Kemeny's distance

**Comparison 1.** We use Kemeny's example [16] (p. 17) for ranking three objects. Kemeny's result is shown in Fig. 1. We recall the equivalence between Kemeny's notation for preference ordering and our notations in Table 3.
<table><caption>**Table 3**
Equivalence between Kemeny's notation and ours.</caption><thead><tr><th>Preference #</th><th>Kemeny's notation</th><th>our notation</th></tr></thead><tbody><tr><td>P<sub>1</sub></td><td><table><tr><td>a</td><td>b</td><td>c</td></tr></table></td><td>a &gt; b &gt; c</td></tr><tr><td>P<sub>2</sub></td><td><table><tr><td>a</td><td>b &minus; c</td></tr></table></td><td>a &gt; (b = c)</td></tr><tr><td>P<sub>3</sub></td><td><table><tr><td>a</td><td>c</td><td>b</td></tr></table></td><td>a &gt; c &gt; b</td></tr><tr><td>P<sub>4</sub></td><td><table><tr><td>a &minus; c</td><td>b</td></tr></table></td><td>(a = c) &gt; b</td></tr><tr><td>P<sub>5</sub></td><td><table><tr><td>c</td><td>a</td><td>b</td></tr></table></td><td>c &gt; a &gt; b</td></tr><tr><td>P<sub>6</sub></td><td><table><tr><td>c</td><td>a &minus; b</td></tr></table></td><td>c &gt; (a = b)</td></tr><tr><td>P<sub>7</sub></td><td><table><tr><td>c</td><td>b</td><td>a</td></tr></table></td><td>c &gt; b &gt; a</td></tr><tr><td>P<sub>8</sub></td><td><table><tr><td>b &minus; c</td><td>a</td></tr></table></td><td>(b = c) &gt; a</td></tr><tr><td>P<sub>9</sub></td><td><table><tr><td>b</td><td>c</td><td>a</td></tr></table></td><td>b &gt; c &gt; a</td></tr><tr><td>P<sub>10</sub></td><td><table><tr><td>b</td><td>a &minus; c</td></tr></table></td><td>b &gt; (a = c)</td></tr><tr><td>P<sub>11</sub></td><td><table><tr><td>b</td><td>a</td><td>c</td></tr></table></td><td>b &gt; a &gt; c</td></tr><tr><td>P<sub>12</sub></td><td><table><tr><td>a &minus; b</td><td>c</td></tr></table></td><td>(a = b) &gt; c</td></tr><tr><td>P<sub>13</sub></td><td><table><tr><td>a &minus; b &minus; c</td></tr></table></td><td>a = b = c</td></tr></tbody></table>

For convenience and for comparison with Frobenius' distances in our study, additional links from point (i.e. preference) $P_1$ to preferences $P_4$, $P_5$, $P_6$ and $P_7$ with their Kemeny's distances have been also included on Fig. 1, as well as distances from $P_2$ to $P_4$, $P_5$, $P_6$ and $P_7$. For symmetrical reasons, other links between other preferences are not necessary to be shown.

The same representation based on Frobenius' distance is shown on Fig. 2.

The comparison of Figs. 1 & 2 shows the differences between Kemeny's and Frobenius' distances. What is remarkable is that Kemeny's distance from one point to another always equals the sum of the values of the path between the two points, whose sum is minimal. For instance, $d_K(P_1, P_{13}) = d_K(P_1, P_2) + d_K(P_2, P_{13}) = 1 + 2 = 3$, which means that the triangular inequality condition is an equality condition. Using Frobenius' distance, the triangular inequality holds because $d_F(P_1, P_{13}) = 2.44 < d_F(P_1, P_2) + d_F(P_2, P_{13}) = \sqrt{2} + 2 = 3.4142$. Similarly, $d_K(P_2, P_6) = d_K(P_2, P_{13}) + d_K(P_{13}, P_6) = 2 + 2 = 4$, whereas $d_F(P_2, P_6) = 3.46 < d_F(P_2, P_{13}) + d_F(P_{13}, P_6) = 2 + 2 = 4$. Other verifications can be easily done using most distance values shown in Figs. 1 & 2. We think that this behavior of Frobenius' distance is more reasonable than Kemeny's distance.

Note that “normalized figures” can be obtained by dividing the $d_K$ values of each link of Fig. 1 by $d_K^{\max} = 6$, and by dividing the $d_F$ values of each link of Fig. 2 by $d_F^{\max} \approx 4.8990$. The normalized distances (Kemeny's and Frobenius') between all possible rankings of three objects are shown in Figs. 3 and 4 for convenience.

**Comparison 2.** To assess the differences between normalized Kemeny's distance $\tilde{d}_K(\cdot, \cdot)$ and the normalized Frobenius' distance $\tilde{d}_F(\cdot, \cdot)$, we make a comparative analysis when considering the strict preference ordering $\text{Pref}_1 \triangleq A > B > C > D$ with respect to all possible (i.e. 24) strict preferences $\text{Pref}_2$ generated from all possible permutations of 4 elements. The results are listed in Table 4.

<footnote n="9">⁹ For simplicity and for limiting the number of cases to browse, we do not consider all possible ties that can occur.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 1. Kemeny's distances for 3 rankings.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 2. Frobenius' distances for 3 rankings.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Fig. 3. All possible normalized Kemeny's distances for 3 rankings.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 4. All possible normalized Frobenius' distances for 3 rankings.</figcaption></figure>

From Table 4, we observe the different distances we obtain with Kemeny's distance and Frobenius' distance except in the total consistency case for which $\bar{d}_K(M_1, M_2) = \bar{d}_F(M_1, M_2) = 0$ and in the total contradictions case for which $\bar{d}_K(M_1, M_2) = \bar{d}_F(M_1, M_2) = 1$. This result makes sense, and it is naturally expected. We observe also that we always have $\bar{d}_K(M_1, M_2) \le \bar{d}_F(M_1, M_2)$. The choice between Kemeny's distance and Frobenius' distance for measuring the distance between rankings is not clear at this stage of our study for the applications because both distances $d_K$ and $d_F$ verify Kemeny's axioms 1, 2 & 3, and they differ only in the arbitrary convention for the axiom 4. Only evaluation of these distances on real applications may help to choose between $d_K$ and $d_F$ distances in practice.
<caption>**Table 4**</caption>

Comparison of $\tilde{d}_K(\dots)$ and $\tilde{d}_F(\dots)$ between preference orderings $\text{Pref}_1$ and $\text{Pref}_2$.

<table><thead><tr><th>Pref<sub>1</sub></th><th>Pref<sub>2</sub></th><th>d̃<sub>K</sub>(..)</th><th>d̃<sub>F</sub>(..)</th></tr></thead><tbody><tr><td>A &gt; B &gt; C &gt; D</td><td>A &gt; B &gt; C &gt; D</td><td>0</td><td>0</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>A &gt; B &gt; D &gt; C</td><td>0.1667</td><td>0.4082</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>A &gt; C &gt; B &gt; D</td><td>0.1667</td><td>0.4082</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>A &gt; C &gt; D &gt; B</td><td>0.3333</td><td>0.5774</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>A &gt; D &gt; B &gt; C</td><td>0.3333</td><td>0.5774</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>A &gt; D &gt; C &gt; B</td><td>0.5000</td><td>0.7071</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>B &gt; A &gt; C &gt; D</td><td>0.1667</td><td>0.4082</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>B &gt; A &gt; D &gt; C</td><td>0.3333</td><td>0.5774</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>B &gt; C &gt; A &gt; D</td><td>0.3333</td><td>0.5774</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>B &gt; C &gt; D &gt; A</td><td>0.5000</td><td>0.7071</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>B &gt; D &gt; A &gt; C</td><td>0.5000</td><td>0.7071</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>B &gt; D &gt; C &gt; A</td><td>0.6667</td><td>0.8165</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>C &gt; A &gt; B &gt; D</td><td>0.3333</td><td>0.5774</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>C &gt; A &gt; D &gt; B</td><td>0.5000</td><td>0.7071</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>C &gt; B &gt; A &gt; D</td><td>0.5000</td><td>0.7071</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>C &gt; B &gt; D &gt; A</td><td>0.6667</td><td>0.8165</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>C &gt; D &gt; A &gt; B</td><td>0.6667</td><td>0.8165</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>C &gt; D &gt; B &gt; A</td><td>0.8333</td><td>0.9129</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>D &gt; A &gt; B &gt; C</td><td>0.5000</td><td>0.7071</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>D &gt; A &gt; C &gt; B</td><td>0.6667</td><td>0.8165</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>D &gt; B &gt; A &gt; C</td><td>0.6667</td><td>0.8165</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>D &gt; B &gt; C &gt; A</td><td>0.8333</td><td>0.9129</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>D &gt; C &gt; A &gt; B</td><td>0.8333</td><td>0.9129</td></tr><tr><td>A &gt; B &gt; C &gt; D</td><td>D &gt; C &gt; B &gt; A</td><td>1</td><td>1</td></tr></tbody></table>

## 5.5. Dealing with ties

Because of how the proposed approach handles the ranking thanks to the Preference-Score Matrix, the ties do not create any problems here. When some alternatives in the ranking are in ties, the Preference-Score Matrix will be filled with 0 on specific positions when the alternatives are equal. Then, the procedure remains the same. Distances between rankings, including ties, are shown in Figs. 1 & 2 for the three objects ranking example.

## 5.6. Extension with weights

It is also possible to extend this approach with positive importance weights to calculate weighted distance, which could be useful in some cases. For example, to calculate the distance between two ranking of $n$ values, we first have to define a weights vector $w$ with (87)

$$ w = [w_1, w_2, \dots, w_n]^T. \tag{87} $$

The choice of importance weights vector $w$ is generally left to the user. For example, weights vector (88) was successfully used in weighted similarity correlation coefficient [28], which, however, does not follow IUIP. The sum of this progression could be calculated according to (89).

$$ w^{(2)} = [2^{-1}, 2^{-2}, \dots, 2^{-n}]^T, \tag{88} $$

$$ \sum_{i=1}^{n} w^{(2)}(i) = 2^{-1} + 2^{-2} + \dots + 2^{-n} = 1 - 2^{-n}. \tag{89} $$

By convention, $w_1$ is the weight for the best-preferred object, $w_2$ is the weight for the 2nd best-preferred object, etc. The sum of the weights is not necessarily equal to one. This does not matter if we work with normalized weighted Frobenius' distance.

Suppose we have a chosen a reference set $X$ of $n$ objects and two preferences orderings $\text{Pref}_1$ and $\text{Pref}_2$ from which the ordering matrices $M_{X,1}$ and $M_{X,2}$ are derived. From $M_{X,1}$ and $M_{X,2}$ we calculate the scoring vector $s_{X,1}$ and $s_{X,2}$ defined by (90)

$$ s_{X,1} = \begin{bmatrix} \sum_{j=1}^{n} M_{X,1}(1, j) \\ \vdots \\ \sum_{j=1}^{n} M_{X,1}(n, j) \end{bmatrix}, \tag{90} $$

and (91)
$$s_{X,2} = \begin{bmatrix} \sum_{j=1}^{n} M_{X,2}(1,j) \\ \vdots \\ \sum_{j=1}^{n} M_{X,2}(n,j) \end{bmatrix}. \qquad (91)$$

We can sort each value of score vector $s_{X,1}$ and $s_{X,2}$ by their decreasing sorting to obtain the respective sorted vectors $s_{X,1}^{\text{sorted}}$ and $s_{X,2}^{\text{sorted}}$ in order to identify the position of the weight $w_i$ we must assign to each value. This is called the weighting assignment of score values, which is characterized by the weighting vectors $w_{X,1}$ and $w_{X,2}$. Because the score vector $s_{X,1}$ can always be obtained from the (decreasing) sorted score vector $s_{X,1}^{\text{sorted}}$ by a unitary permutation matrix $V_{X,1}$ such that $s_{X,1} = V_{X,1}s_{X,1}^{\text{sorted}}$, and similarly because $s_{X,2} = V_{X,2}s_{X,2}^{\text{sorted}}$ with a $n \times n$ unitary permutation matrix $V_{X,2}$, the weighting vectors $w_{X,1}$ and $w_{X,2}$ are obtained respectively by (92) and (93)

$$\mathbf{w}_{X,1} = \mathbf{V}_{X,1}\mathbf{w}, \qquad (92)$$

$$\mathbf{w}_{X,2} = \mathbf{V}_{X,2}\mathbf{w}. \qquad (93)$$

From weights vectors $\mathbf{w}_{X,1}$ and $\mathbf{w}_{X,2}$ we build weighting diagonal matrices $\mathbf{W}_{X,1}$ and $\mathbf{W}_{X,2}$ defined by (94) and (95)

$$\mathbf{W}_{X,1} = \text{diag}(\mathbf{w}_{X,1}), \qquad (94)$$

$$\mathbf{W}_{X,2} = \text{diag}(\mathbf{w}_{X,2}). \qquad (95)$$

The notation diag($\mathbf{w}_{X,k}$) for $k = 1, 2$ represents the square diagonal matrix having its main diagonal terms equal to the elements of vector $\mathbf{w}_{X,k}$, and all its non-diagonal elements equal zero. The weighted Frobenius' distance between rankings is simply defined by the distance between weighted ordering matrices $\mathbf{W}_{X,1}\mathbf{M}_{X,1}$ and $\mathbf{W}_{X,2}\mathbf{M}_{X,2}$ which is mathematically expressed as (96)

$$d_{F,w}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2}) = \left[ \text{Tr}((\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})^T (\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})) \right]^{\frac{1}{2}}. \qquad (96)$$

It can be easily verified that this weighted Frobenius' distance is also invariant to indexing. This verification is left to the reader.<fnref n="10" />

If one wants to use the Frobenius' distance with the normalized weights, it is possible either by using normalized weights $\tilde{w}_i$, where $\tilde{w}_i = \frac{w_i}{\sum_{i=1}^{n} w_i}$ or using the Equation (97), which utilizes the sum of the non-normalized weights to normalize the distance after the weighting. Both methods are equivalent and provide same results.

$$d_{F,\tilde{w}}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2}) = \left[ \text{Tr}((\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})^T (\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})) \right]^{\frac{1}{2}} / \sum_{i=1}^{n} \mathbf{w}(i) \qquad (97)$$

In particular case of using weights $\mathbf{w}^{(2)}$ (88) the sum can be expressed as (89), therefore the Equation (97) has the form of (98).

$$d_{F,\tilde{w}}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2}) = \left[ \text{Tr}((\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})^T (\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})) \right]^{\frac{1}{2}} / (1 - 2^{-n}) \qquad (98)$$

## 5.7. Example 3: $d_{F,w}$ calculation between rankings

To show in detail how to calculate the weighted Frobenius' distance between rankings, we consider for simplicity two preference orderings of three objects A, B and C chosen as $\text{Pref}_1 \triangleq A > B > C$ and $\text{Pref}_2 \triangleq A > C > B$. We show how the calculations are done based on the two reference sets $X = \{x_1 = A, x_2 = B, x_3 = C\}$ and $Y = \{y_1 = B, y_2 = C, y_3 = A\}$ to calculate $d_{F,w}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2})$ and $d_{F,w}(\mathbf{M}_{Y,1}, \mathbf{M}_{Y,2})$.

**Case 1:** Using reference set $X = \{x_1 = A, x_2 = B, x_3 = C\}$

With the reference set $X = \{x_1 = A, x_2 = B, x_3 = C\}$ and for the preferences $\text{Pref}_1 \triangleq A > B > C$ and $\text{Pref}_2 \triangleq A > C > B$, we obtain the following ordering matrices (i.e. PSM) $\mathbf{M}_{X,1}$ (99) and $\mathbf{M}_{X,2}$ (100) with their scores $s_{X,1}$ and $s_{X,2}$

$$\mathbf{M}_{X,1} = \begin{bmatrix} 0 & 1 & 1 \\ -1 & 0 & 1 \\ -1 & -1 & 0 \end{bmatrix}, \quad \text{and} \quad s_{X,1} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix}, \qquad (99)$$

$$\mathbf{M}_{X,2} = \begin{bmatrix} 0 & 1 & 1 \\ -1 & 0 & -1 \\ -1 & 1 & 0 \end{bmatrix}, \quad \text{and} \quad s_{X,2} = \begin{bmatrix} 2 \\ -2 \\ 0 \end{bmatrix}. \qquad (100)$$

<footnote n="10">¹⁰ Verify that $d_{F,w}(\mathbf{M}_{Y,1}, \mathbf{M}_{Y,2}) = d_{F,w}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2})$ by taking into account that $\mathbf{M}_{Y,i} = U^{-1}\mathbf{M}_{X,i}U$ and $\mathbf{W}_{Y,i} = U^{-1}\mathbf{W}_{X,i}U$ for $i = 1, 2$ and that $U$ is a unitary permutation matrix such that $U^T U = I_{n \times n}$.</footnote>
Sorting elements of score vectors $s_{X,1}$ and $s_{X,2}$ by descending order yields<fnref n="11" /> (101)

$$s_{X,1}^{\text{sorted}} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix}, \quad \text{and} \quad s_{X,2}^{\text{sorted}} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix}. \qquad (101)$$

The unitary permutation matrices $V_{X,1}$ and $V_{X,2}$ are respectively given by (102) and (103)

$$V_{X,1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = I_{3 \times 3}, \qquad (102)$$

and

$$V_{X,2} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}. \qquad (103)$$

Suppose that the importance weights vector is chosen as in (88) with $n=3$, that is (104)

$$\boldsymbol{w} = [w_1 = 1/2, w_2 = 1/4, w_3 = 1/8]^T. \qquad (104)$$

The weighting vectors $w_{X,1}$ and $w_{X,2}$ are given by formulas (92) - (93), and we get (105) and (106) respectively:

$$w_{X,1} = V_{X,1} w = I_{3 \times 3} w = w = \begin{bmatrix} 1/2 \\ 1/4 \\ 1/8 \end{bmatrix}, \qquad (105)$$

$$w_{X,2} = V_{X,2} w = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1/2 \\ 1/4 \\ 1/8 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 1/8 \\ 1/4 \end{bmatrix}. \qquad (106)$$

Based on $w_{X,1}$ and $w_{X,2}$ one gets the weighting matrices (107) and (108):

$$W_{X,1} = \text{diag}(w_{X,1}) = \begin{bmatrix} w_1 & 0 & 0 \\ 0 & w_2 & 0 \\ 0 & 0 & w_3 \end{bmatrix} = \begin{bmatrix} 1/2 & 0 & 0 \\ 0 & 1/4 & 0 \\ 0 & 0 & 1/8 \end{bmatrix}, \qquad (107)$$

$$W_{X,2} = \text{diag}(w_{X,2}) = \begin{bmatrix} w_1 & 0 & 0 \\ 0 & w_3 & 0 \\ 0 & 0 & w_2 \end{bmatrix} = \begin{bmatrix} 1/2 & 0 & 0 \\ 0 & 1/8 & 0 \\ 0 & 0 & 1/4 \end{bmatrix}. \qquad (108)$$

The matrix products $W_{X,1}M_{X,1}$ and $W_{X,2}M_{X,2}$ are (109) and (110) respectively:

$$W_{X,1} M_{X,1} = \begin{bmatrix} 0 & 1/2 & 1/2 \\ -1/4 & 0 & 1/4 \\ -1/8 & -1/8 & 0 \end{bmatrix}, \qquad (109)$$

and

$$W_{X,2} M_{X,2} = \begin{bmatrix} 0 & 1/2 & 1/2 \\ -1/8 & 0 & -1/8 \\ -1/4 & 1/4 & 0 \end{bmatrix}. \qquad (110)$$

Their difference is (111)

$$W_{X,1} M_{X,1} - W_{X,2} M_{X,2} = \begin{bmatrix} 0 & 0 & 0 \\ -1/8 & 0 & 3/8 \\ 1/8 & -3/8 & 0 \end{bmatrix}, \qquad (111)$$

and we have (112)

$$(W_{X,1} M_{X,1} - W_{X,2} M_{X,2})^T (W_{X,1} M_{X,1} - W_{X,2} M_{X,2}) \approx \begin{bmatrix} 0.0312 & -0.0469 & -0.0469 \\ -0.0469 & 0.1406 & 0 \\ -0.0469 & 0 & 0.1406 \end{bmatrix}. \qquad (112)$$

The trace of this matrix is (113)

<footnote n="11">¹¹ In this example $s_{X,1}^{\text{sorted}} = s_{X,1}$ because the elements of $s_{X,1}$ are already in (vertical) descending order.</footnote>
$$ \mathrm{Tr}((\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})^T (\mathbf{W}_{X,1}\mathbf{M}_{X,1} - \mathbf{W}_{X,2}\mathbf{M}_{X,2})) \approx 0.3125. \quad (113) $$

Finally, we get the weighted Frobenius' distance value (114)

$$ d_{F,w}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2}) = \sqrt{0.3125} \approx 0.5590. \quad (114) $$

If we need to obtain the Frobenius' distance with normalized weights we apply the Equation (97) to get (115):

$$ d_{F,w}(\mathbf{M}_{X,1}, \mathbf{M}_{X,2}) = \frac{\sqrt{0.3125}}{1 - 2^{-3}} \approx \frac{\sqrt{0.3125}}{0.8750} \approx 0.6389. \quad (115) $$

**Case 2:** Using reference set $Y = \{y_1 = B, y_2 = C, y_3 = A\}$

Suppose that we work with the same preference orderings $\mathrm{Pref}_1 \triangleq A > B > C$ and $\mathrm{Pref}_2 \triangleq A > C > B$ with the reference set $Y = \{y_1 = B, y_2 = C, y_3 = A\}$. We get the following ordering matrices (i.e. PSM) $\mathbf{M}_{Y,1}$ and $\mathbf{M}_{Y,2}$ with their scores $s_{Y,1}$ and $s_{Y,2}$: (116) and (117) respectively

$$ \mathbf{M}_{Y,1} = \begin{bmatrix} 0 & 1 & -1 \\ -1 & 0 & -1 \\ 1 & 1 & 0 \end{bmatrix}, \quad \text{and} \quad s_{Y,1} = \begin{bmatrix} 0 \\ -2 \\ 2 \end{bmatrix}, \quad (116) $$

$$ \mathbf{M}_{Y,2} = \begin{bmatrix} 0 & -1 & -1 \\ 1 & 0 & -1 \\ 1 & 1 & 0 \end{bmatrix}, \quad \text{and} \quad s_{Y,2} = \begin{bmatrix} -2 \\ 0 \\ 2 \end{bmatrix}. \quad (117) $$

Sorting elements of score vectors $s_{Y,1}$ and $s_{Y,2}$ by descending order yields (118)

$$ s_{Y,1}^{\mathrm{sorted}} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix}, \quad \text{and} \quad s_{Y,2}^{\mathrm{sorted}} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix}. \quad (118) $$

The unitary permutation matrices $V_{Y,1}$ and $V_{Y,2}$ are respectively given by (119) and (120)

$$ V_{Y,1} = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}, \quad (119) $$

and

$$ V_{Y,2} = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}. \quad (120) $$

The weighting vectors $w_{Y,1}$ and $w_{Y,2}$ are given by formulas (92) - (93) (with replacing $X$ by $Y$ in notations), and we get using the same importance weights vector $w = [w_1 = 1/2, w_2 = 1/4, w_3 = 1/8]^T$ (121) and (122)

$$ w_{Y,1} = V_{Y,1}w = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1/2 \\ 1/4 \\ 1/8 \end{bmatrix} = \begin{bmatrix} 1/4 \\ 1/8 \\ 1/2 \end{bmatrix}, \quad (121) $$

$$ w_{Y,2} = V_{Y,2}w = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1/2 \\ 1/4 \\ 1/8 \end{bmatrix} = \begin{bmatrix} 1/8 \\ 1/4 \\ 1/2 \end{bmatrix}. \quad (122) $$

Based on $w_{Y,1}$ and $w_{Y,2}$ one gets the weighting matrices (123) and (124)

$$ W_{Y,1} = \mathrm{diag}(w_{Y,1}) = \begin{bmatrix} w_2 & 0 & 0 \\ 0 & w_3 & 0 \\ 0 & 0 & w_1 \end{bmatrix} = \begin{bmatrix} 1/4 & 0 & 0 \\ 0 & 1/8 & 0 \\ 0 & 0 & 1/2 \end{bmatrix}, \quad (123) $$

$$ W_{Y,2} = \mathrm{diag}(w_{Y,2}) = \begin{bmatrix} w_3 & 0 & 0 \\ 0 & w_2 & 0 \\ 0 & 0 & w_1 \end{bmatrix} = \begin{bmatrix} 1/8 & 0 & 0 \\ 0 & 1/4 & 0 \\ 0 & 0 & 1/2 \end{bmatrix}. \quad (124) $$

The matrix products $W_{Y,1}M_{Y,1}$ (125) and $W_{Y,2}M_{Y,2}$ (126)

$$ W_{Y,1}M_{Y,1} = \begin{bmatrix} 0 & 1/4 & -1/4 \\ -1/8 & 0 & -1/8 \\ 1/2 & 1/2 & 0 \end{bmatrix}. \quad (125) $$

and
$$ W_{Y,2} M_{Y,2} = \begin{bmatrix} 0 & -1/8 & -1/8 \\ 1/4 & 0 & -1/4 \\ 1/2 & 1/2 & 0 \end{bmatrix}. \qquad (126) $$

Their difference is (127)

$$ W_{Y,1} M_{Y,1} - W_{Y,2} M_{Y,2} = \begin{bmatrix} 0 & 3/8 & -1/8 \\ -3/8 & 0 & 1/8 \\ 0 & 0 & 0 \end{bmatrix}, \qquad (127) $$

and we have (128)

$$ (W_{Y,1} M_{Y,1} - W_{Y,2} M_{Y,2})^T (W_{Y,1} M_{Y,1} - W_{Y,2} M_{Y,2}) \approx \begin{bmatrix} 0.1406 & 0 & -0.0469 \\ 0 & 0.1406 & -0.0469 \\ -0.0469 & -0.0469 & 0.0312 \end{bmatrix}. \qquad (128) $$

The trace of this matrix is (129)

$$ \mathrm{Tr}((W_{Y,1} M_{Y,1} - W_{Y,2} M_{Y,2})^T (W_{Y,1} M_{Y,1} - W_{Y,2} M_{Y,2})) \approx 0.3125. \qquad (129) $$

Finally we get (130)

$$ d_{F,w}(M_{Y,1}, M_{Y,2}) = \sqrt{0.3125} \approx 0.5590. \qquad (130) $$

Or if we need to have distance with normalized weights (131):

$$ d_{F,w}(M_{Y,1}, M_{Y,2}) = \frac{\sqrt{0.3125}}{1 - 2^{-3}} \approx \frac{\sqrt{0.3125}}{0.8750} \approx 0.6389. \qquad (131) $$

We have $d_{F,w}(M_{Y,1}, M_{Y,2}) = d_{F,w}(M_{X,1}, M_{X,2})$, which shows that the IUIP indeed works with this weighted Frobenius' distance as expected (see Theorem). Moreover we can check that $M_{Y,i} = U^{-1}M_{X,i}U$ and $W_{Y,i} = U^{-1}W_{X,i}U$ for $i=1,2$ using the unitary matrix $U$ characterizing the permutation from the reference set $X$ to the reference set $Y$, which is given in this example by (132)

$$ U = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}. \qquad (132) $$

## 5.8. Example 4: $d_{F,w}$ between tied rankings

We briefly show an example where ties occur in the preference orderings. We still consider 3 objects A, B and C with preference orderings $\text{Pref}_1 \triangleq (A=C) > B$ and $\text{Pref}_2 \triangleq C > (A=B)$. We work with the reference set $X = \{x_1 = A, x_2 = B, x_3 = C\}$. Because there are 3 objects, we work a priori with importance weights vector $\mathbf{w} = [w_1, w_2, w_3]^T$, and as previously we take $\mathbf{w} = [w_1 = 1/2, w_2 = 1/4, w_3 = 1/8]^T$. In this example, we have (133) and (134)

$$ M_{X,1} = \begin{bmatrix} 0 & 1 & 0 \\ -1 & 0 & -1 \\ 0 & 1 & 0 \end{bmatrix}, \quad \text{and} \quad s_{X,1} = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix}, \qquad (133) $$

$$ M_{X,2} = \begin{bmatrix} 0 & 1 & 1 \\ -1 & 0 & 0 \\ -1 & 0 & 0 \end{bmatrix}, \quad \text{and} \quad s_{X,2} = \begin{bmatrix} 2 \\ -1 \\ -1 \end{bmatrix}. \qquad (134) $$

Sorting elements of score vectors $s_{X,1}$ and $s_{X,2}$ by descending order yields (135)

$$ s_{X,1}^{\text{sorted}} = \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix}, \quad \text{and} \quad s_{X,2}^{\text{sorted}} = \begin{bmatrix} 2 \\ -1 \\ -1 \end{bmatrix}. \qquad (135) $$

Because of ties, the previous method cannot be directly applied, and some additional manipulations have to be done to make correctly the weighting assignment of score values when some score values are equal. For this, we must adapt the values of the importance weights vector $\mathbf{w}$ to take into account the multiplicity of score values in their descending order. This adaptation is needed for each preference ordering where ties occur. More precisely, in our example, one sees that the unitary permutation matrix $V_{X,1}$ such that $s_{X,1} = V_{X,1} s_{X,1}^{\text{sorted}}$ is not unique and the two matrices $V_{X,1}^a$ or $V_{X,1}^b$ can be chosen (136)

$$ V_{X,1}^a = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}, \quad \text{and} \quad V_{X,1}^b = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}. \qquad (136) $$
Similarly, the unitary permutation $V_{X,2}$ such that $s_{X,2} = V_{X,2}s_{X,2}^{sorted}$ is not unique because of the tie, and the two matrices $V_{X,2}^a$ or $V_{X,2}^b$ can also be chosen (137)

$$ V_{X,2}^a = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad \text{and} \quad V_{X,2}^b = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}. \qquad (137) $$

The adaptation (i.e., modification) of importance vector $w = [w_1, w_2, w_3]^T$ is necessary to apply to calculate the weighted Frobenius' distance. This is done using the multiplicity of score values and their ranks in the $s_{X,1}^{sorted}$ and $s_{X,2}^{sorted}$ vectors. More precisely, because the multiplicity of the first best score (its value is 1) in $s_{X,1}^{sorted}$ the vector $w = [w_1, w_2, w_3]^T$ must be replaced by $w' = [w_1, w_2, w_3]^T$. Also because of the multiplicity of the second best score (its value is -1) in $s_{X,2}^{sorted}$ the vector $w = [w_1, w_2, w_3]^T$ must be replaced by $w'' = [w_1, w_2, w_3]^T$. With these adaptations, we get (138) and (139)

$$ w_{X,1} = V_{X,1}^a w' = V_{X,1}^b w' = \begin{bmatrix} 1/2 \\ 1/4 \\ 1/2 \end{bmatrix}, \qquad (138) $$

$$ w_{X,2} = V_{X,2}^a w'' = V_{X,2}^b w'' = \begin{bmatrix} 1/2 \\ 1/4 \\ 1/4 \end{bmatrix} \qquad (139) $$

Based on $w_{X,1}$ and $w_{X,2}$ one gets the weighting matrices (140) and (141) respectively

$$ W_{X,1} = \operatorname{diag}(w_{X,1}) = \begin{bmatrix} w_1 & 0 & 0 \\ 0 & w_2 & 0 \\ 0 & 0 & w_1 \end{bmatrix} = \begin{bmatrix} 1/2 & 0 & 0 \\ 0 & 1/4 & 0 \\ 0 & 0 & 1/2 \end{bmatrix}, \qquad (140) $$

$$ W_{X,2} = \operatorname{diag}(w_{X,2}) = \begin{bmatrix} w_1 & 0 & 0 \\ 0 & w_2 & 0 \\ 0 & 0 & w_2 \end{bmatrix} = \begin{bmatrix} 1/2 & 0 & 0 \\ 0 & 1/4 & 0 \\ 0 & 0 & 1/4 \end{bmatrix}. \qquad (141) $$

The matrix products $W_{X,1}M_{X,1}$ and $W_{X,2}M_{X,2}$ are (142)

$$ W_{X,1}M_{X,1} = \begin{bmatrix} 0 & 1/2 & 0 \\ -1/4 & 0 & -1/4 \\ 0 & 1/2 & 0 \end{bmatrix}, \qquad (142) $$

and (143)

$$ W_{X,2}M_{X,2} = \begin{bmatrix} 0 & 1/2 & 1/2 \\ -1/4 & 0 & 0 \\ -1/4 & 0 & 0 \end{bmatrix}. \qquad (143) $$

Their difference is (144)

$$ W_{X,1}M_{X,1} - W_{X,2}M_{X,2} = \begin{bmatrix} 0 & 0 & -1/2 \\ 0 & 0 & -1/4 \\ 1/4 & 1/2 & 0 \end{bmatrix}, \qquad (144) $$

and we have (145)

$$ (W_{X,1}M_{X,1} - W_{X,2}M_{X,2})^T(W_{X,1}M_{X,1} - W_{X,2}M_{X,2}) \approx \begin{bmatrix} 1/16 & 1/8 & 0 \\ 1/8 & 1/4 & 0 \\ 0 & 0 & (1/4) + (1/16) \end{bmatrix}. \qquad (145) $$

The trace of this matrix is (146)

$$ \operatorname{Tr}((W_{X,1}M_{X,1} - W_{X,2}M_{X,2})^T(W_{X,1}M_{X,1} - W_{X,2}M_{X,2})) = (1/16) + (1/4) + (1/4) + (1/16) = (1/8) + (1/2) = 0.625. \qquad (146) $$

Finally, we get the weighted Frobenius' distance value (147)

$$ d_{F,w}(M_{X,1}, M_{X,2}) = \sqrt{0.625} \approx 0.7906, \qquad (147) $$

and if it is required to have a distance with normalized weights, we can calculate it as follows (148):

$$ d_{F,w}(M_{X,1}, M_{X,2}) = \frac{d_{F,w}(M_{X,1}, M_{X,2})}{1 - 2^{-3}} = \frac{\sqrt{0.625}}{0.8750} = 0.9035 \qquad (148) $$
Therefore, we see that weighted Frobenius' distance can be calculated even if the preference orderings include ties, but the calculation is a bit more complicated than with strict preference orderings because of the necessity of adapting the importance weights vectors for taking into account the multiplicity of score values in the score vectors (if any). This adaptation can, however, be done automatically in the correct programming code of this method.

**Note.** It is worth noting that $d_{F,w}$ provides the same result as $d_F$ when all the components of importance weights vector $w$ are equal to one. This can be easily verified in our examples 3 and 4, taking $w = [1, 1, 1]^T$ and comparing with the result that we obtain using Frobenius' distance formula (47). For example 3 we get $d_F = d_{F,w}=[1,1,1]^T = 2.8284$, and for example 4 we get $d_F = d_{F,w}=[1,1,1]^T = 2$. It is also worth noting that when working with the normalized distances, the normalization of weights has no impact on the result because one always has (149):

$$ \tilde{d}_{F,\tilde{w}} = \frac{d_{F,\tilde{w}}}{d_{F,\tilde{w}}^{\max}} = \frac{d_{F,w}/(\sum_{i=1}^{n} w(i))}{d_{F,w}^{\max}/(\sum_{i=1}^{n} w(i))} = \frac{d_{F,w}}{d_{F,w}^{\max}} = \tilde{d}_{F,w}. \qquad (149) $$

## 6. Conclusion and perspectives

In this paper, we proposed a new effective distance between rankings based on the Frobenius' norm of the square matrix, which satisfies the invariance under the indexing principle, i.e., it returns the same results with no regard to the order of labels in evaluated sets. The approach is mainly intended to use rankings represented as indexes of the ordered set, which is a more natural way for most people. However, it can also be used with rankings represented by values and provides stable results. Moreover, the proposed approach can deal with ties and can be extended to calculate the weighted distance between two rankings. We have also shown the difference between Frobenius' distance and Kemeny's distance, although they are based on the same definition of ordering matrices.

In future works, we plan to examine how this approach performs in real-life decision-making problems and compare the Frobenius' distance with Kemeny's distance and correlation coefficients used in the literature. Because of the useful properties of the Frobenius' distance, it could be potentially used in distance-based machine-learning algorithms, such as clustering or classification, therefore it would be interesting to investigate such applications too. Another interesting direction of future research is preparing the simulation to check how specific changes in the ranking will influence distance. Finally, it would be very interesting to see if it is possible to extend this approach to uncertain and incomplete rankings.

## CRediT authorship contribution statement

**Jean Dezert:** Writing – original draft, Visualization, Validation, Supervision, Software, Methodology, Investigation, Formal analysis, Conceptualization.
**Andrii Shekhovtsov:** Writing – review & editing, Writing – original draft, Visualization, Validation, Software, Methodology, Investigation, Formal analysis, Conceptualization.
**Wojciech Salabun:** Writing – review & editing, Writing – original draft, Validation, Supervision, Project administration, Methodology, Investigation, Funding acquisition, Formal analysis, Conceptualization.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

## References

[1] A. Albano, A. Plaia, Element weighted Kemeny distance for ranking data, Electron. J. Appl. Stat. Anal. 14 (2021) 117-145.

[2] J. Alfaro, A. Cifuentes, On the performance of portfolios based on ESG ratings, J. Impact ESG Invest. (2023).

[3] H. Arora, A. Naithani, Significance of topsis approach to madm in computing exponential divergence measures for pythagorean fuzzy sets, Decis. Mak. Appl. Manag. Eng. 5 (2022) 246-263.

[4] S. Bandyopadhyay, Comparison among multi-criteria decision analysis techniques: a novel method, Prog. Artif. Intell. 10 (2021) 195-216.

[5] D.K. Bukovšek, B. Mojškerc, On the exact region determined by Spearman's footrule and Gini's gamma, J. Comput. Appl. Math. 410 (2022) 114212.

[6] J. Pinto da Costa, C. Soares, A weighted rank measure of correlation, Aust. N. Z. J. Stat. 47 (2005) 515-529.

[7] E. Deza, M. Deza, Encyclopedia of Distances, Springer-Verlag, 2009.

[8] J. Dezert, A. Tchamova, D. Han, J.M. Tacnet, The SPOTIS rank reversal free method for multi-criteria decision-making support, in: 2020 IEEE 23rd International Conference on Information Fusion (FUSION), IEEE, 2020, pp. 1-8.

[9] P. Diaconis, R.L. Graham, Spearman's footrule as a measure of disarray, J. R. Stat. Soc., Ser. B, Methodol. 39 (1977) 262-268.

[10] F. Diao, G. Wei, Edas method for multiple attribute group decision making under spherical fuzzy environment, Int. J. Knowl. Based Intell. Eng. Syst. 26 (2022) 175-188.

[11] P. D'Urso, L. De Giovanni, L. Federico, V. Vitale, Fuzzy clustering of spatial interval-valued data, Spat. Stat. 57 (2023) 100764.

[12] P. D'urso, R. Massari, Fuzzy clustering of mixed data, Inf. Sci. 505 (2019) 513-534.

[13] P. D'Urso, V. Vitale, A Kemeny distance-based robust fuzzy clustering for preference data, J. Classif. 39 (2022) 600-647.

[14] G. Golub, C.F. Van Loan, Matrix computations, Matrix Comput. 5 (1996) 55.

[15] P.R. Halmos, Naive Set Theory, van Nostrand, 1960.

[16] J.G. Kemeny, J.L. Snell, Mathematical Models in the Social Sciences. Chap. II, Ginn, Boston, 1962.

[17] J.G. Kemeny, Mathematics without numbers, Daedalus 88 (1959) 577-591.
[18] M.G. Kendall, A new measure of rank correlation, Biometrika 30 (1938) 81-93.

[19] Q. Liu, TOPSIS model for evaluating the corporate environmental performance under intuitionistic fuzzy environment, Int. J. Knowl. Based Intell. Eng. Syst. 26 (2022) 149-157.

[20] H. Minkowski, Geometrie der Zahlen, BG Teubner, 1910.

[21] T.K. Paul, M. Pal, C. Jana, Multi-attribute decision making method using advanced pythagorean fuzzy weighted geometric operator and their applications for real estate company selection, Heliyon 7 (2021).

[22] K.B. Petersen, M.S. Pedersen, et al., The Matrix Cookbook, vol. 7, Technical University of Denmark, 2008, p. 510.

[23] R.A. Horn, C.R. Johnson, Matrix Analysis, Cambridge University Press, 2012.

[24] H. Rana, M. Umer, U. Hassan, U. Asgher, F. Silva-Aravena, N. Ehsan, Application of fuzzy topsis for prioritization of patients on elective surgeries waiting list-a novel multi-criteria decision-making approach, Decis. Mak. Appl. Manag. Eng. 6 (2023) 603-630.

[25] L. Rivero Gutiérrez, M.A. De Vicente Oliva, A. Romero-Ania, Economic, ecological and social analysis based on DEA and MCDA for the management of the Madrid urban public transportation system, Mathematics 10 (2022) 172.

[26] S.K. Sahoo, S.S. Goswami, A comprehensive review of multiple criteria decision-making (mdcm) methods: advancements, applications, and future directions, Decis. Mak. Adv. 1 (2023) 25-48.

[27] W. Sałabun, A. Shekhovtsov, An innovative drastic metric for ranking similarity in decision-making problems, Ann. Comput. Sci. Inf. Syst. 35 (2023) 731-738.

[28] W. Sałabun, K. Urbaniak, A new coefficient of rankings similarity in decision-making problems, in: Science-ICCS 2020: 20th International Conference, Proceedings, Part II 20, Amsterdam, the Netherlands, June 3-5, 2020, Springer, 2020, pp. 632-645.

[29] N.J. Salkind, Encyclopedia of Measurement and Statistics, SAGE Publications, 2006.

[30] M. Sciandra, A. Plaia, et al., Classification trees for preference data: a distance-based approach, in: Proceedings of the 29th International Workshop on Statistical Modelling, IWSM, 2014, pp. 149-152.

[31] A. Shekhovtsov, J. Więckowski, B. Kizielewicz, W. Sałabun, Towards reliable decision-making in the green urban transport domain, Facta Univ., Ser. Mech. Eng. 20 (2022) 381-398.

[32] C. Spearman, The proof and measurement of association between two things, Am. J. Psychol. (AJP) 100 (1961) 441-471.

[33] J. Wieckowski, Z. Szyjewski, Practical study of selected multi-criteria methods comparison, Proc. Comput. Sci. 207 (2022) 4565-4573.

[34] S. Xie, J. Zhang, TOPSIS-based comprehensive measure of variable importance in predictive modelling, Expert Syst. Appl. (2023) 120682.