Characterization of Scoring Rules with Distances: Application to the Clustering of Rankings

1 Introduction

It is often the case that data is available in the form of rankings (ordered lists of elements that express a preference order), for instance, this is the case of preference information obtained in electronic commerce applications. Clustering is useful in the sense that by producing a (small) number of aggregated rankings we are able to provide a meaningful qualitative description for the entire population. In this work we focus on distance-based methods for clustering that are attractive because they do not make specific assumptions (contrary to probabilistic methods [Critchlow et al., 1991; Lu and Boutilier, 2011] that assume a specific generative model for the rankings).

A distance-based clustering method partitions the elements into clusters, so that the within-cluster distance is minimized;

∗Supported by ANR-14-CE24-0007-01 "CoCoRICo-CoDec".

each cluster can then be associated with a representative element of the partition (the centroid). When considering rankings as elements to be clustered, the issue is to define a meaningful sound distance measure that can be used, as several alternative possibilities exist (for instance, Kendall tau, Spearman or footrule). As noted by a number of researchers [Sculley, 2007; Kumar and Vassilvitskii, 2010], in many applications the distance measure should account for the fact that we may wish to weigh more top positions in the rankings and/or give more importance to specific items.

A related problem is ranking aggregation. Several methods for aggregation have been proposed, notably in the social choice theory community. In particular, in positional scoring rules, each item gets some points from each ranking according to its position. When a distance measure is defined, a natural aggregation method is to look for the ranking that minimizes the sum of the distances with all input rankings.

An interesting question is whether an aggregation method has a corresponding distance that they minimize implicitly: if so, we then say that such distance characterizes the given aggregation method. In this work we show how scoring rules (including some new variants, biased scoring rules) can be characterized. This has practical implications; it allows to perform clustering in a computationally efficient way. Moreover, many of our results involve new generalizations of Spearman distance that account for the importance associated to positions and to items, allowing for greater flexibility.

2 Distance-based Clustering

We have a set of n items or objects and a set of m users or agents. A ranking π is a permutation on the set of available objects. Formally π is a function from {1, ..., n} to {1, ..., n} associating each item with its position (rank). As usual, the set of possible rankings is denoted as Sn. A ranking can be expressed alternatively in an explicit form of a tuple 〈π-1 (1), ..., π-1 (n)〉, with π-1(r) being the r-th most preferred item; for example 〈2, 1, 3〉 is the ranking for which item 2 is the most preferred, then item 1 is preferred, and finally item 3 is the least preferred (this corresponds to π(1)=2, π(2)=1 and π(3)=3).

We consider to have a number of rankings π1,...,πm, associated with different users, and we want to partition them into different clusters. Let f : i→r assign rankings to clusters and d be a distance. Distance-based clustering is the problem of, given a number m of rankings, partitioning them in k clusters (or classes) in order to minimize the within-cluster sum of distances with respect to the "central" rankings ¯π∗ 1 , .., ¯π∗ k of each cluster.

The problem of clustering is frequently tackled in the literature with an iterative algorithm that proceeds in two steps. In the assignment step, each observation is assigned to the cluster whose "mean" yields the least within-cluster distance. In the update step, we calculate the new means to be the centroids of the observations in the new clusters. When items are vectors and the Euclidean distance is used, the problem is that of k-means clustering and the iterative algorithm described above is often called as well k-means 1 .

Following [Kamishima et al., 2005] we adopt the same idea for clustering a set of rankings. We maintain a set of centroids (initialized randomly) and we associate each ranking with the cluster whose centroid is closest, according to a suitable distance d on rankings. We then recompute the centroids for each of the clusters. We alternate between these two actions until the clusters do not change anymore.

Algorithm 1: Distance-based clustering of rankings.

Data: π1, ..., πm (population of rankings given by m users), k (number of clusters)

Randomly initialize the centroids ¯π1, ..., ¯πk ; while there are changes in cluster assignments do Assign each ranking π to the cluster whose distance to the centroid is lower f(πi) := argminr=1,..,k d(πi, ¯πr ) i=1, ..,m; Find the centroid of each cluster ¯πr := arg minπ∈Sn ∑πt:f(πt)=r d(π, πt) r = 1, ..., k; end

A well known fact is that Algorithm 1 converges to a local optimum. This is easily proved by showing that both main steps of the algorithm cannot increase the total distances of each data point to the centroid of its cluster. 2

Algorithm 1 requires the specification of a suitable distance measure. Rankings are particular "objects", and there are many different ways to define a distance between two rankings; this is discussed in Section 3.2. Note however, that rank aggregation is often treated as a separate problem, especially in social choice literature, notably in voting methods (an aggregate ranking is obtained without considering an underlying distance measure).

The main contribution of this paper is to study the connection between rank aggregation using scoring rules and ranking distances. We will propose new distances that allow to assign different degrees of importance to positions and to items.

1 Also sometimes called Lloyd's algorithm.

2 Since the distance-based clustering approach returns a local optimum, the algorithmmay be run for a number of times (typically 10 or 20) and store the clustering assignment associated with the lowest sum of distances to the closest centroid.

Since these distances are easy to aggregate (in our terminology, distances that characterize a scoring rule), clustering can be computed very efficiently.

3 Distances and Aggregation

There are a number of ways that can be used to aggregate several rankings into a single one. Some aggregation rules are devised from social choice: the Condorcet method, sorting the items by their Borda score or a generic scoring rule. There are as well many commonly used distance measures for rankings, such as Kendall-tau, footrule or Spearman.

From a theoretical point of view, the interest is to study if, for a given common aggregation rule (such as plurality), there is a distance measure that it is (implicitly) minimized. In this paper we establish a connection between scoring rules (often used in social choice) and their associated distance measures.

3.1 Aggregation with Scoring Rules

An aggregation rule is a mapping g(σ1, ..., σm) from a set of input rankings σ1, ..., σm to a single "best" ranking summarizing the whole population. We allow g to return more than one ranking, to be considered equally good.

Many ways of aggregating rankings arise from the field of social choice, where one needs to make a decision for a group of people, aggregating several (usually different) preferences, expressed as a vote in a ballot. Here we focus on rank aggregation using scoring rules.

A scoring rule associates each position r ∈ {1, ..., n} with a score w(r); scores are weakly decreasing w(1) ≥ ... ≥ w(n). Items are evaluated by summing up the score they are awarded in each ranking v(i)= ∑mu=1 w(πu(i)). In order to form an aggregate ranking, items are sorted according to their total score v(i): the ranking π∗SR obtained by a scoring rule is such that π∗SR(i)<π∗SR(j) if v(i)>v(j) (when ties exist in the overall score, tie-breaking is needed).

Borda count (or Borda rule) is a particular type of scoring rule considering weights defined as w(r)=n-r+1 (the item ranked first gets a score of n points, an item in the second position gets n-1, and so on). We denote with π∗Borda the ranking obtained by following Borda rule. Borda weights are such that Borda counts for element i are v(i) = ∑mu=1 nσu(i)+1 = m(n + 1)- ∑mu=1 σu(i). The optimal ranking π∗Borda according to Borda count is such that i precedes j in π∗Borda , formally expressed as π∗Borda (i) < π∗Borda (j) if ∑mu=1σu(i) < ∑mu=1σu(j) (an item i is ranked better than another item j if the sum of its ranks is lower)

Plurality (sorting items by the number of times that they are ranked first) can be represented as a scoring rule with weights (1, 0, ..., 0); veto, sorting items in decreasing order with respect to the number of times they are ranked in the last position, is represented by weights (1, ..., 1, 0), and topk, that can be modelled as a scoring rule with a weight of 1 in the first k positions and then 0.

We propose a new aggregation method, that we call biased scoring rule parametrized by two vectors z1, .., zn (between 0 and 1, a multiplicative bias distorting each item's score) and φ1, . . . , φn (representing an additive bias associated to each item). Each item i receives a contribution ziw(σu(i)) to its score for each ranking σu plus an overall bonus φi:

This allows to "tweak" a scoring role in order to give some advantage to some items, or penalize others. Obviously when zi =1 for all i, and φi is the same for all items, aggregation with vBSR reduces to an unbiased scoring rule. If w(r) = n-r+1, then we have a biased Borda count.

3.2 Distance Measures for Rankings

Distance measures characterize how different two rankings are; different distances might pose more strength on specific aspects: penalizing the displacements in different ways. For a given distance measure d the total distance from a given ranking π to a set of rankings σ1, ..., σm is D(π; σ1, ..., σm) = ∑mu=1 d(π, σu). A distance function between rankings naturally leads to a way to generating an aggregate ranking; the ranking minimizing this score is chosen as aggregated ranking for the population: π∗ =argminπ D(π, σ1, ..., σm).

We recall hereafter the usual definition of metric and common generalizations relaxing some of the properties. Note that, while the term distance is often used as a synonym for metric, in the following, we use the former to loosely mean any function that quantifies the difference between elements (rankings in our case), and we explicitly state which distances are metric.

Definition 1. A function d : X × X → R is a metric on X iff it satisfies the following properties:

• d(x, y)≥0 (non negativity),
• d(x, y)=0 iff x=y (identity of the indiscernibles),
• d(x, y)=d(y, x) (symmetry) and
• d(x, y)+d(y, z) ≥ d(x, z) (triangular inequality).

Moreover we have the following relaxations:

• A pseudometric d relaxes the identity of the indiscernibles (d(x, x) = 0 but it may hold d(x, y) = 0 for y ̸= x);
• A quasimetric relaxes symmetry;
• A semimetric relaxes the triangular inequality;
• A function satisfying non-negativity and d(x, x)=0 is a premetric.

We are interested in distance measures on rankings; ranking distances d are defined on the Sn (the set of permutation of n elements). Common distance measures for rankings are Kendall tau (counting the number of disagreements in terms of pairs between two rankings), footrule 3 (measuring the total displacement of all elements) and Spearman.

In this paper we focus on Spearman distance, because as will discussed below in Section 4, it is connected to the aggregation using Borda count. The Spearman distance is defined as taking the squares of the differences:

3 Also known as Spearman's footrule.

An interesting observation, that we will use several times in our proofs, is that Spearman can be expressed as follows:

While footrule and Kendall-tau distance are metrics, Spearman distance does not satisfy the triangular inequality and is a semimetric. It can be turned into a metric if we take the root of sum of the squares of the differences between positions.

The traditional definition of Spearman distance treats all positions in the same way. Following [Dwork et al., 2001; Kumar and Vassilvitskii, 2010], in order to allow to put more emphasis on some ranks we define a generalization of Spearman distance, that we call positional Spearman, giving different weights to rank positions, computed as

parametrized by a vector w. We will often use the observation that dPS can be rewritten as

where Z w n = 2 ∑nr=1 w(r)2 depends only on the weights w and the number of items n.

Observation 1. dPS is a semimetric if the weights w are strictly decreasing; otherwise it is a pseudo-semimetric.

Consider, for instance, w = (3, 2, 2, 1), two rankings that differ only by the fact that items on the second and third position are inverted are associated with null distance according to w: dPS(〈1, 2, 3, 4〉, 〈1, 3, 2, 4〉)=0.

4 Connection between AggregationMethods and Distance Minimization

The general aggregation problem is that of finding the ranking (permutation of items) that minimizes a given distance measure with respect to several other given rankings σ1, ..., σm given.

Definition 2. A distance function d(π, σ) on rankings characterizes a ranking aggregation g(σ1, ..., σm) iff it holds

In case the aggregation function returns multiple rankings 4 , then all such rankings should achieve the same minimal value D∗ =minπ D(π; σ1, ..., σm), and, conversely, if there are several rankings associated with minimum sum-ofdistances D∗ , these must be returned by g.

We now establish 5 theoretical connections between distance minimization and scoring rules. In particular, we establish connections between the newly proposed positional Spearman distance (see above in Section 3.2) and aggregation using scoring rules, and between a distance giving different weights to items and aggregation using biased scoring rules (defined above in Section 3.1).

First of all, rank aggregation with Borda count and minimization of Spearman produce the same aggregated ranking.

Proposition 1. [Marden, 1996]

The Spearman distance characterizes the Borda rule: π∗Borda = arg minπ∈Sn ∑mu=1 dS(π, σu).

We have noted before that Spearman distance, as defined in Equation 3, is not a metric, as triangular inequalities does not hold. One might wonder if it is possible to "tweak" the Spearman distance to find a metric characterizing Borda. We prove, however, that this is not possible.

Proposition 2. There is no metric characterizing Borda rule.

Proof : Let d be a semimetric between rankings. We prove that if d characterizes Borda rule, then it cannot satisfy the triangular inequality. Consider the following population of rankings: σ1 = 〈1, 2, 3〉 and σ2 = 〈3, 1, 2〉. Application of Borda gives the following scores to items: v(1) = 5, v(2) = 3, v(3) = 4 yielding the optimal ranking π∗ = 〈1, 3, 2〉. If d characterizes Borda rule, then it must hold that D(π∗ ; σ1, σ2) < D(π; σ1, σ2), for any π ∈ Sn, π ̸= π∗ . In particular, π∗ must compare favorably with respect to σ1: ∑u=1,2 d(π∗ , σu) < ∑u=1,2 d(σ1, σu). Since d is a semimetric, we must have d(π∗ ,σ1)=d(σ1,π∗ ) and d(σ1,σ1)=0; it then follows that d(σ1, π∗ ) + d(π∗ , σ2) < d(σ1, σ2).

We now extend this result to scoring rules assigning arbitrary weights to positions. We derive a novel connection between scoring rules and our proposed positional Spearman distance. Note, however, that the scoring vector must (in addition of being non incresing) not assign the same weights to more than one position.

4 For example, due to ties in the score obtained with Borda count.

5 We provide proofs for selected statements. Proofs for all propositions will be provided in a longer version of the paper.

Proposition 3. Assume a scoring rule with strictly decreasing weights w(r) > w(s) if r < s with r, s ∈ {1, ..., n}. The positional Spearman distance with weights w characterizes the scoring rule with the same weights; π∗SR = arg minπ∈Sn ∑mu=1 dPS(π, σu).

Proof : The optimal ranking π∗SR wrt a scoring rule with weights w is such that i precedes j in π∗ iff v(i) ≥ v(j), or equivalently iff ∑mu=1 w(σu(i)) ≥ ∑mu=1 w(σu(j)). The ranking with minimum total distance wrt positional Spearman is (we use Equation 6):

The π maximizing the expression above is such that w(π(i)) ≥ w(π(j)) if ∑mu=1 w(σu(i)) ≥ ∑mu=1 w(σu(j)). If w is striclty decreasing this gives π∗SR.

The previous observations only holds for scoring rules with distinct weights. This means that the association fails, notably, for plurality, veto and top-k, that can be represented, respectively, as scoring rules with weights (1, 0, ..., 0), (0, ..., 0, 1) and with a weight vector with 1 in the first k positions and then 0s everywhere. We therefore look for an alternative characterization for these rules, in order to define some distance measures that they implicitly minimize.

Using plurality in our framework for clustering intuitively means to put together rankings based on the first preferred item. If the number of clusters is lower than the number of distinct items placed first in any ranking, aggregation will be made by ordering items according to the number of "votes" (number of rankings placing an item first); when assigning rankings to clusters, a ranking with item i in the first position will be assigned to the cluster whose centroid put item i in the highest position. The following premetric dPL captures this behavior

Note that dPL is not symmetric. Furthemore, for a given π there are many π′ such that d(π, π′ )=0; in fact, any σ such that σ-1(1)=π-1(1): for example dPL(〈1,2,3〉,〈1,3,2〉)=0. Therefore dPL is neither a metric nor a semimetric. It holds dPL(π, π)=0 for any π and dPL(π, σ)≥0 for any π, σ, but not the triangular inequality; thus dPL is a premetric.

We now present our result about the characterization of plurality: we prove that the ranking obtained by aggregating the rankings σ1, ..., σm using plurality minimizes the sum of distances DPL(π; σ1, ..., σm) = ∑mt=1 dPL(π, σt).

Proposition 4. The distance dPL characterizes plurality as a method for aggregation of rankings.

Proof : α1 i =|{σ :σ(i)=1}| is the number of input rankings among σ1, ..., σm in which item i is ranked first. It follows

∑mt=1 dPL(π, σt)= ∑ni=1α1 i π(i) -m. Therefore we have

The permutation π∗ is such that π∗ (i) < π∗ (j) (i ranked before j) if α1 i > α1 j ; this is exactly the result of aggregation when using plurality.

One can wonder if there is another distance that can characterize plurality, with additional properties such as symmetry. In fact, we show that this is not possible.

Proposition 5. There is no semimetric and no quasi metric (hence there is no metric) characterizing plurality.

Proof : Consider a population of two rankings σ1 = 〈1, 2, 3〉 and σ2 = 〈2, 3, 1〉. According to plurality, the best rankings obtained by aggregating σ1 and σ2 are σ1 itself and the ranking 〈2, 1, 3〉. Now, consider a premetric d and assume that it characterizes plurality. Since σ2 is not a optimal ranking according to plurality, the sum of the distances between σ1 and the population must be strictly lower than the sum of the distances from σ2

from which (since d(π, π)=0, d being a premetric) it follows d(σ1, σ2) < d(σ2, σ1), hence any d characterizing plurality cannot be symmetric.

For veto, we can define a premetric, analogous to the one we defined for plurality, but that looks for the position of the lowest ranked items. We similarly characterize aggregation with respect to the top-k elements.

Proposition 6. The pseudo-distance dV T characterizes the veto rule.

Proposition 7. The following premetric 6 characterizes the top-k aggregation rule.

Note that dtopk is the same as dPL when k = 1. From the fact that top-k aggregation subsumes plurality, and from Proposition 5, it immediately follows that there is no semimetric, no quasi metric and no metric, characterizing top-k.

In order to characterize biased scoring rules, we introduce another kind of generalization of Spearman, allowing to give different weights zi, φi to items. Item-weighting positional Spearman is defined (Compare with Equation 4 and 6) as:

where Z w n = 2 ∑ni=1 w(i) depends only on w and n. The role of the zi, φi is to weigh more the important items. Note that dIPS(π, σ) = dPS(π, σ) if all weights zi are set to 1 and all φi to zero.

We now establish the connection between dIPS and the biased scoring rules presented before.

6 The constant addend - n(n+1) 2 is used in order to satisfy d(π, π) = 0, i.e. to obtain a premetric.

Proposition 8. The Item-weighted Positional Spearman distance dIPS with strictly decreasing weights (w1, ...,wn), arbitrary (z1, ..., zn), and (φ1/m, ..., φn/m) characterizes a biased scoring rule with (w1, ...,wn), (z1, ..., zn) and (φ1, ..., φn); with m being the number of input rankings.

Note that dIPS is not even a premetric, as dIPS(π, π) can (and will often) yield a value different than zero. dIPS is symmetric only if the bias terms φi are zero; it is nonnegative assuming the zi bounded by 1 and the φi non negative. A much "nicer" distance function (in the case φi = 0) is the following ˆ dIPS(π, σ) = ∑ni=1 zi[w(π(i)) - w(σ(i))]2 that is a semimetric; notice that ˆ dIP S (π, σ) = dIP S (π, σ)- dIPS(π, π)-dIPS(σ, σ). However, we could not find a characterization for this distance, and its optimization seems to be rather hard.

The theoretical results are summarized in Table 1.

5 Incomplete Rankings

In realistic cases it will be often the case that only a subset of items are ranked. Formally a partial ranking σ is defined on a restricted domain D(σ) (the items involved in the partial ranking), with l = |D(σ)| be the length. Given a partial ranking σ, we use Sn(σ) for the set of consistent full rankings.

In our setting, aggregation produces a full ranking, while the distance measures how far a partial ranking is from each centroid. Given a partial ranking, we consider a probability distribution over the rankings that are consistent with such partial ranking. According to order statistics, and as noticed by [Kamishima and Akaho, 2009], given a partial ranking σ, under the uniform distribution the expected rank of an item i is n+1 l+1 σ(i) if i ∈ D(σ). If i is not ranked in σ (i ̸∈ D(σ)), its expected rank is n+1 2 . Expected Borda count ranks items by increasing order of their sum of expected ranks.

The expected Spearman distance is naturally defined in the case of an uniform prior as (there are n! l! complete rankings consistent with a partial ranking of length l):

Proposition 9. [Kamishima and Akaho, 2009] dE(S) characterizes expected Borda count.

We now generalize scoring rules and the positional Spearman distance to partial rankings. Assuming an uniform distribution over the complete orders consistent with an observed partial order σ, the expectation E[v(i)] of the score of an item i is obtaining by averaging over the score obtained by i in all complete consistent orders; E[vSR(i)] = ∑ˆσ∈Sn(σ) l! n! w(ˆσ(i)). The expected scoring rule ranks items according to E[v(i)]; similarly we can define the expected biased scoring rule (refer to Equation 2), with E[vBSR(i)] = φi + ziE[vSR(i)].

We introduce the expected positional Spearman distance dE(PS)(π, σ) = l! n! ∑ˆσ∈Sn(σ) dPS(π, ˆσ) and dE(IPS) in an analogous way: dE(IPS)(π, σ)= l! n! ∑ˆσ∈Sn(σ) dIPS(π, ˆσ).

Proposition 10.

• dE(PS) characterizes the expected scoring rule,
• dE(IPS) characterizes the expected biased scoring rule.

While expected Borda can be computed efficiently, its associated distance dE(S) is computationally expensive to compute (and the same is true for dE(PS) and dE(IPS)), as one would need to consider the set of all full rankings consistent with partial one. As efficient heuristics to compute d(π, σ), where one or both between π and σ are partial, we can consider, following [Kamishima and Akaho, 2009], to compute the classic Spearman distance dS on the full rankings obtained by considering only items in D(π)∩D(σ) (we call this reduced Spearman) or to substitute, when dealing with partial rankings, ranks with expected ranks in Eq. 3 (Spearman ER). Finally we consider an approximation based on sampling a set of consistent full ranking (Sampling Spearman).

6 Application to Clustering

We perform a number of experiments in order to illustrate the use of distance-based clustering in a variety of settings. Algorithm 1 is performed using a scoring rule as aggregation method; the appropriate distance is used to assign rankings to clusters. In the experiments below we consider the sushi dataset 7 ; 5000 users have been asked to rank a set of items (sushis) [Kamishima et al., 2005] from the most to the least preferred. Note that the number of clusters is viewed as an input parameter by the clustering algorithm. We choose different values in different experiments for illustration purposes (in each experiment, all methods are given the same input). The problem of assessing the best number of clusters is a different and orthogonal problem.

Full rank data. The weight vector w can have a large impact on the clustering obtained using dPS. We consider convex sequences as weights w such that the difference between consecutive weights is a geometric series; i.e. wi-wi+1 = γ · (wi+1-wi+2) where factor γ control the steepness of the sequence; for γ=1 we have Borda. Figure 1 shows the sensitivity of clustering to the weight w used by positional Spearman, for different values of γ (with 5 clusters): we evaluate the difference of the clustering obtained with that would be obtained with Borda (straight line) and Plurality (dotted line); the difference between clusterings is measured as one minus the Rand index. When γ increases the clusters becomes increasingly similar to that obtained by Plurality and less to Borda (γ≈1.8 is a sort of "middle ground"). It is also interesting to note that, at least for this dataset, "steeper" scoring rules tends to have a larger fraction of the population concentrated in one single cluster: at the extreme, when using plurality and dPL around 50% of the rankings are assigned to the same cluster; with Borda the fraction is only about 27%.

Incomplete rank data. In the second experiment, we first perform clustering with Borda/Spearman, and this is considered as reference (our "ground truth"). We then randomly remove a number of items from each ranking (obtaining partial rankings), and perform clustering using expected Borda and (as the exact probabilistic method is not feasible) three distances on partial rankings (reduced Spearman, spearman with Expected Ranks, and sampling Spearman). As evaluation measure, we compute the ratio between the distance of each point to its assigned centroid calculated with Spearman using the full rankings and that of the reference . We observed that the heuristic methods works almost as well as the more demanding approach based on sampling (Figure 2).

Recommendation under uncertain availability. We consider the following problem: we need to assign users to k = 5 clusters; each item (sushi) has a constant i.i.d. probability of being available (0.5 in our tests). Each user's preferences are encoded by her ranking; the "utility" is represented by a scoring rule 8 (assumed the same for all users). In each centroid the top item among those available is recommended to each user in the cluster. We need to assign users to clusters before knowing which items will be available. Clustering with the combination scoring rule and positional Spearman (both using w) achieves the highest value of per-user-average expected social welfare (5.47), scoring rule w together with classic Spearman yields 4.41 and Borda/Spearman 4.40; aggregation without clustering would yield a dismal 3.58.

7 Available at http://www.kamishima.net/sushi/.

8 In this test, w is a geometric sequence: wr =10 · ar-1 (r being the position in the ranking; a=0.5).

We now modify the setting associating each item with a cost, so that the utility a recommendation i to a user is w(σ(i)) (where σ is the user's ranking) minus its cost. We perform clustering on a number of instances, with randomly generated costs associated to items (results are averaged over several runs). In this setting, with 2 clusters, the biased scoring rule (with weights w for positions, multiplicative biases set to zero, zi = 0, and the additive biases φ set to the cost with negative sign), together with its characterizing distance dIPS achieves 2.38 of expected social welfare; biased scoring rule with dPS achieves 2.31, the unbiased scoring rule (using w) yields 2.20 and aggregation without clustering 1.3.

Computation time Clustering with distance measures associated to scoring rules is particularly efficient. By exploiting our characterization of scoring rules, the aggregation step (computing the centroid of a cluster) becomes very efficient: running time is O(n logn) with respect to the number of items (we need to count the scores associated to each item and then to sort them). In our tests, clustering using plurality was fastest (less than 1 second) and biased scoring rules are the slowest (convergence obtained in around 3s with 2 clusters and 8s for 5); a case aside is Sampling Spearman that is approximately 10 times slower 9 .

7 Conclusion

We provided a taxonomy of distance measures that characterize scoring rules as aggregation method. We extended the result about the connection between Borda rule and minimization of Spearman distances to scoring rules; we also consider the case of plurality, veto and top-k. We introduced a new family of aggregation rules, called biased scoring rules, giving an advantage to specific items, and show how they can be characterized. We provided experimental tests showing how these distance measures can be applied in clustering.

Axiomatic treatment of the median ranking from a point of view of social choice is given in [Barth´elemy and Monjardet, 1981]. The idea of looking aggregation techniques in terms of minimization of distances is known as distance rationalizability in social choice theory [Elkind et al., 2009]. The difference is that here we are interested in aggregations that produce a ranking, while in social choice the aggregation produces one or more winners (the elected candidates).

Because of its connection with the Condorcert property, Kemeny aggregation (minimization of Kendall tau) is often advocated. Since Kemeny aggregation is NP-hard problem, several researchers proposed heuristic methods, including the Markov chains of [Dwork et al., 2001]. Other researchers also considered extending common distances in some ways. In [Sculley, 2007] methods of ranking aggregation are extended in order to exploit similarity information between ranked items. The generalized distance functions presented in [Kumar and Vassilvitskii, 2010] are a rich generalization of footrule and Kendall whose expressivity is similar to the distances proposed here. Here, we focus on Spearman distances, because of the connection with scoring rules, clustering is very efficient to compute; this contrasts to Kemeny aggregation that can be computed exactly only in trivial cases.

9 Unoptimized implementation in MATLAB with off-the-shelf computing equipment.