The General Stability of Ranking Houming Chen
H. V. Jagadish
University of Michigan Ann Arbor, Michigan, USA [email protected]
University of Michigan Ann Arbor, Michigan, USA [email protected]
arXiv:2607.01546v1 [cs.DB] 1 Jul 2026
ABSTRACT Rankings derived from weighted scoring functions are widely used in settings such as university rankings and employment candidate evaluations. Since ranking weights are often chosen by organizations or analysts, ranking stability asks whether a reported ranking persists under reasonable weight changes. Prior work on stable rankings formalizes this idea through volume-based stability, which measures the fraction of the weight space that induces the target ranking exactly. This exact-match requirement can be too blunt: once a perturbed weight vector produces a different ranking, exact stability gives it no credit, whether the change replaces the top-ranked item or only swaps two nearly tied lower-ranked items. We propose general stability, a distance-based generalization that aggregates ranking regions according to a user-defined distance from the target ranking. This lets users specify which ranking changes matter in the application, while recovering exact stability as a special case. Our algorithmic focus is stability computation: given a reported or user-specified ranking and a distance function, estimate its general-stability score. We give a two-dimensional sweep algorithm and an unbiased multidimensional sampler that extend exactstability methods, and analyze why sampling can scale poorly as the dimension grows. Motivated by this scaling challenge, we identify quasiconvex distance functions as a tractable subclass and introduce Conv-SC, which reduces stability computation for this subclass to convex-volume approximation, where randomized polynomialtime methods are available. Experiments on eight real datasets and generated instances show that distance-sensitive stability gives informative real-data results, that our estimators are accurate and practical, and that Conv-SC improves scaling with dimension for quasiconvex distance functions.
1
INTRODUCTION
Rankings are widely used in settings such as university evaluation, job hiring, and public review websites. For instance, organizations such as U.S. News and Quacquarelli Symonds rank universities, and the resulting rankings can influence public perception and institutional decisions. Such rankings are commonly produced by scoring each item on several attributes, assigning weights to those attributes, and then sorting items by their weighted scores. The choice of weights reflects a judgment about the relative importance of attributes, and is not driven by the data. Different reasonable choices of weights can lead to different rankings. This raises a robustness question: does the reported ranking reflect a stable pattern in the data, or does it depend on a narrowly limited choice of weights? If small changes in the weights lead to very different outcomes, the reported ranking provides weak support
for a robust conclusion. It may also raise concerns that the reported weights might have been cherry-picked for a particular outcome. Prior work formalizes this idea through volume-based stability [3], which measures the fractional volume of the weight space that induces a target ranking. We refer to this original notion as exact stability. The following example illustrates the intuition: a ranking is robust when nearby weights support the same conclusion, and fragile when changes lead to different rankings. Example 1. Consider a hiring committee ranking candidates by a weighted sum of two criteria: an aptitude score 𝑥 1 and an experience score 𝑥 2 . Suppose three candidates have scores shown in Table 1. Cand.
𝑥1
𝑥2
A B C
97 99 84
95 89 94
Weights and Corresponding Final Scores (0.5, 0.5) (0.6, 0.4) (0.7, 0.3) (0.8, 0.2) 96 94 89
96.2 95 88
96.4 96 87
96.6 97 86
Table 1: The aptitude and experience scores of three candidates, and their corresponding final scores for different weight vectors. A scoring function 𝑓 (𝑥 1, 𝑥 2 ) = 𝑤 1𝑥 1 + 𝑤 2𝑥 2 is used to compute the final scores. With weights (𝑤 1, 𝑤 2 ) = (0.6, 0.4), the ranking is 𝐴 > 𝐵 > 𝐶. Nearby weights such as (0.5, 0.5) and (0.7, 0.3) induce the same ranking, while a larger change such as (0.8, 0.2) flips the top two candidates and produces 𝐵 > 𝐴 > 𝐶. In the left panel of Figure 1, the region inducing 𝐴 > 𝐵 > 𝐶 is relatively large; exact stability is precisely the volume fraction of this region in the weight space. However, a small exact-stability region does not by itself tell us all we need to know. It may be that tiny changes in the weights lead to substantially different rankings, a serious robustness problem. Or, it may be that the nearby weight space is split among rankings that differ only by minor swaps. The distinction becomes clearer in the following example. Example 2. In the recruiting scenario described in Example 1, suppose we have six candidates with scores shown in Table 2. Candidates
𝑥1
𝑥2
Candidates
𝑥1
𝑥2
A B C
100 90 90
98 97 86
D E F
81 77 90
94 88 76
Table 2: The aptitude and experience scores of six candidates. The ranking regions of these candidates are illustrated in the right panel of Figure 1. Consider the ranking 𝐴 > 𝐵 > 𝐶 > 𝐷 > 𝐸 > 𝐹 , which corresponds to the thin region in the middle of the figure. Under exact stability, this ranking is unstable because its own region has
provides exact-stability algorithms in two dimensions and a randomized sampling method for higher dimensions [3]; we extend this computational framework to general stability. Despite using this sampling-based algorithm, the computational complexity of computing exact stability and general stability can still grow quickly under a fixed error tolerance. The sampling method can be efficient when the stability value is moderate, but it becomes a rare-event estimator when the relevant region has very small volume. Furthermore, general stability may require accounting for many rankings near the target ranking, which can further increase the cost. Conv-SC. To address this computation problem, we propose a novel algorithm named Conv-SC, which leverages a Markov Chain Monte Carlo (MCMC) sampling technique known as the hit-andrun method [43, 51]. Conv-SC is not a general-purpose solution for every distance function. Rather, it applies to distance functions satisfying a property we term quasiconvexity; this class includes the 0/∞ distance that induces exact stability and the first differing position distance discussed later in the paper. The key insight behind Conv-SC is that, although computing the volume of a general region in high-dimensional space is #𝑃hard [26], efficient randomized algorithms exist for approximating the volume of convex bodies in polynomial time [25, 31]. However, these algorithms require the region of interest to be convex. In general cases, applying these polynomial-time algorithms is challenging due to the lack of convexity. By identifying the notion of quasiconvexity for distance functions, we prove that if a distance function is quasiconvex, then the union of all ranking regions within a given distance forms a convex set. This key property enables us to recast the stability computation problem as the computation of convex volumes, which can be efficiently approximated in polynomial time using existing randomized algorithms. For this restricted class of distance functions, Conv-SC offers a route to polynomial-time stability computation through convexvolume approximation. It is not meant to replace the general sampler in all settings; rather, it addresses the complementary structured regime where the relevant stability sets are convex and sampling may be slowed by small-volume events. Section 6 formalizes quasiconvexity and gives examples.
small volume. However, the neighboring regions do not drastically change the rankings. Moving the weights to one side gives 𝐴 > 𝐵 > 𝐷 > 𝐶 > 𝐸 > 𝐹 , which preserves the top two candidates and only swaps 𝐶 and 𝐷. Moving the weights to the other side gives 𝐴 > 𝐵 > 𝐶 > 𝐷 > 𝐹 > 𝐸, which preserves the first four candidates and only swaps the last two. These perturbations are different from an unstable case where a small change replaces the leading candidate or substantially rearranges the top of the list.
Figure 1: Ranking regions for the motivating examples. Left: Example 1, where 𝐴 > 𝐵 > 𝐶 occupies a relatively large region. Right: Example 2, where 𝐴 > 𝐵 > 𝐶 > 𝐷 > 𝐸 > 𝐹 has a small exact region but is adjacent to rankings that preserve the main conclusions. Large changes under small weight perturbations indicate fragility and may make the chosen weights appear cherry-picked. Small changes, however, can still support a reliable conclusion if much of the nearby weight space induces rankings that are not too dissimilar. From Exact Stability to General Stability. The examples above motivate replacing exact stability with a similarity-aware measure. We introduce general stability, a distance-based generalization. Instead of measuring the volume of only the target region, general stability also incorporates the volumes of regions that induce rankings close to the target, with each region weighted according to a user-defined similarity metric. The similarity metric should be specified depending on which ranking changes matter in the application. For example, a user may care mostly about preserving the top-ranked items, or may want to distinguish a small local swap from a large rearrangement of the ranking. Different choices of similarity metrics encode these judgments. If we assign distance 0 to identical rankings and ∞ to all other rankings, general stability reduces to exact stability. Stability as a Robustness Measure. It is important to clarify how stability should be interpreted. Stability is a robustness measure for a given ranking, not an objective that determines which ranking is best. A highly stable ranking is not necessarily the most appropriate ranking for an application; it only means that the ranking is not sensitive to reasonable changes in the weights. Therefore, the algorithmic task in this paper is to evaluate the robustness of a reported or user-specified ranking by computing its stability score, rather than optimizing over rankings to maximize stability. Computing Stability. This computation is challenging, especially in high dimensions, because it involves estimating the volumes of multiple high-dimensional ranking regions. Prior work
Summary of Our Contributions Our main contributions are as follows: (1) We introduce and formalize the concept of general stability for rankings, which incorporates user-defined distance functions into stability analysis. The stability of a ranking includes contributions from neighboring similar rankings. (2) We study practical distance functions that distinguish small ranking changes from large ones and allow users to specify which parts of the ranking matter most. (3) We extend prior exact-stability computation methods [3] to general stability, including both two-dimensional region enumeration and multidimensional sampling. (4) We propose a novel algorithm, Conv-SC, for stability computation with quasiconvex distance functions. Quasiconvexity turns the set of weight vectors that induce rankings close 2
to the target into a convex body. Although estimating the volume of a general body is hard, volumes of convex bodies can be approximated efficiently, and Conv-SC exploits this structure in cases where direct sampling becomes a rare-event computation. (5) We experimentally evaluate general stability on synthetic and real datasets, showing that distance-based stability can distinguish rankings that exact stability treats identically and identify real cases where exact stability is small while general stability remains high. We also compare Conv-SC with sampling under a fixed accuracy target, showing that Conv-SC can be faster for small exact-stability regions.
sector corresponding to a unique ranking. Our goal is to generalize this observation to higher dimensions. For any pair of items 𝑡𝑖 , 𝑡 𝑗 ∈ D, item 𝑡𝑖 ranks before 𝑡 𝑗 under the ranking induced by 𝑓w if and only if 𝑓w (𝑡𝑖 ) > 𝑓w (𝑡 𝑗 ), which is equivalent to 𝑑 ∑︁ 𝑤𝑘 𝑡𝑖 [𝑘] − 𝑡 𝑗 [𝑘] > 0. 𝑘=1
The corresponding equality defines a hyperplane through the origin; its two half-spaces determine which of 𝑡𝑖 and 𝑡 𝑗 is ranked first. Therefore, each ranking region is a 𝑑-dimensional cone-like region formed by the intersection of the positive orthant of the closed unit ball with the finite number of half-spaces defined by these hyperplanes for all pairs of items in D.
2 PROBLEM SETUP 2.1 Preliminaries
2.3
The Stability of a Ranking
We consider a database D = {𝑡 1, 𝑡 2, . . . , 𝑡𝑛 } of 𝑛 items. Each item 𝑡𝑖 ∈ D is described by a vector of 𝑑 scoring attributes:
The stability of a ranking is the volume of its ranking region divided by the volume of the positive orthant of the closed unit ball.
𝑡𝑖 = ⟨𝑡𝑖 [1], 𝑡𝑖 [2], . . . , 𝑡𝑖 [𝑑]⟩.
Definition 2 (The Stability of 𝔯 at D). Let 𝔯 be a ranking on D. Then the stability of 𝔯 at D is 𝑉 𝑜𝑙 (R D (𝔯)) 𝑆𝑡𝑎𝑏 D (𝔯) = (1) 𝑉 𝑜𝑙 (W)
Without loss of generality, these attributes are assumed to lie in [0, 1] and are standardized to have equal variance. A ranking 𝔯 is a bijective mapping from D to {1, 2, . . . , 𝑛}. 𝔯(𝑡𝑖 ) indicates the rank of 𝑡𝑖 , and 𝔯 −1 (𝑘) denotes the item in the 𝑘-th position. We focus on rankings induced by linear scoring functions.
In some situations, the user might want to set up an acceptable region W ∗ ⊂ W, which represents the set of weight vectors considered acceptable for the application. In such cases, the definition of stability could be modified to 𝑉 𝑜𝑙 (R ∗D (𝔯)) 𝑆𝑡𝑎𝑏 D (𝔯) = (2) 𝑉 𝑜𝑙 (W ∗ ) where R ∗D (𝔯) = R D (𝔯) ∩ W ∗
Definition 1 (Ranking Induced by a Linear Scoring Function). A linear scoring function is a mapping 𝑓w : R𝑑 → R defined by 𝑑 ∑︁ 𝑓w (𝑡) = 𝑤𝑖 𝑡 [𝑖], 𝑖=1
where w = ⟨𝑤 1, 𝑤 2, . . . , 𝑤𝑑 ⟩ has 𝑤𝑖 ≥ 0 for all 𝑖 and ∥w∥ 2 ≤ 1. Equivalently, w lies in the positive orthant of the closed unit ball in R𝑑 , following the weight-space convention in prior stability work [3]. Since positive rescaling of w does not change the induced ranking, this domain should be viewed as a convenient representative of weight directions; other normalizations, such as the simplex ∥w∥ 1 = 1, can be handled by replacing W or W ∗ . The ranking ∇ 𝑓w (D) is obtained by ordering the items in D in descending order of their scores 𝑓w (𝑡).
2.4
Let ℜ D denote the set of all possible rankings generated by linear scoring functions on the database D. Then, we can define a distance function on ℜ D , which measures the dissimilarity of rankings. The distance function 𝑑𝑖𝑠𝑡 quantifies the dissimilarity between two rankings. Specifically, a larger value of 𝑑𝑖𝑠𝑡 (𝔯1, 𝔯2 ) indicates a greater degree of difference between the rankings 𝔯1 and 𝔯2 . In this paper, we require the distance function to satisfy two properties, as illustrated in the definition below. (Note that these properties are not enough to make 𝑑𝑖𝑠𝑡 a metric: we do not require the triangle inequality, and two distinct rankings may have distance 0.)
Let W be the set of all feasible weight vectors. For a ranking 𝔯 of D, we denote the set of weight vectors that yield 𝔯 as: R D (𝔯) = w ∈ W ∇ 𝑓w (D) = 𝔯 .
2.2
The General Stability of a Ranking
Ranking Regions
Definition 3 (A distance function for rankings). A distance function for rankings on D is a function 𝑑𝑖𝑠𝑡 : ℜ D ×ℜ D → R∪{+∞}, which satisfies the following properties: (1) For any 𝔯 ∈ ℜ D , 𝑑𝑖𝑠𝑡 (𝔯, 𝔯) = 0 (2) For any 𝔯1, 𝔯2 ∈ ℜ D , 𝑑𝑖𝑠𝑡 (𝔯1, 𝔯2 ) = 𝑑𝑖𝑠𝑡 (𝔯2, 𝔯1 ) ≥ 0
For most choices of w, no two items receive exactly the same score, and w induces a unique ranking. As w varies over W, all weight vectors that produce the same ranking naturally form a ranking region. The exceptional weight vectors that create ties lie on the boundaries between ranking regions. These boundaries are contained in finitely many hyperplanes and have measure zero under the continuous weight-space measures considered here, so adding or removing boundary points does not change any stability value; implementations may break ties arbitrarily. We now examine the geometry of these ranking regions. First, consider the 2D example from Example 1. There, W (the unit quarter disk) is divided into sectors by rays through the origin, each
Then, we define the general stability of a ranking 𝔯0 at D with a distance function 𝑑𝑖𝑠𝑡 as follows: Definition 4 (The General Stability of 𝔯0 at D with a distance function 𝑑𝑖𝑠𝑡). Let 𝔯0 be a ranking on D. Then the general
3
stability of 𝔯0 at D with respect to 𝑑𝑖𝑠𝑡 is ∑︁ 1 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) = 𝑉 𝑜𝑙 (R D (𝔯))𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, 𝔯)) 𝑉 𝑜𝑙 (W)
difference in general stability aligns with our discussion in the introduction section. We can notice that 𝔯0 is in proximity to two rankings with considerable ranking regions, but 𝔯3 is far from those two rankings, so it is reasonable to consider 𝔯0 as more stable than 𝔯3 .
𝔯 ∈ℜD
(3)
2.4.1 Stability is Just a Special Case of General Stability. Consider a simple distance function defined as follows.
where 𝑑𝑖𝑠𝑡 is a distance function defined by the user. The user might want to set up an acceptable region W ∗ ⊂ W. Then, for each ranking 𝔯, we define R ∗D (𝔯) = R D (𝔯) ∩ W ∗ and let ℜ∗D denote the set of all possible rankings generated by linear scoring functions with weights in W ∗ . Then, the definition of general stability could be modified to
Definition 6 (0/∞ distance function). The 0/∞ distance function 𝑑𝑖𝑠𝑡 0/∞ is a distance function between rankings such that for any 𝔯1, 𝔯2 ∈ ℜ D , ( 0, if 𝔯1 = 𝔯2 𝑑𝑖𝑠𝑡 0/∞ (𝔯1, 𝔯2 ) = +∞ if 𝔯1 ≠ 𝔯2
Definition 5 (The General Stability of 𝔯0 at D with a distance function 𝑑𝑖𝑠𝑡 within an acceptable region W ∗ ). ∑︁ 1 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) = 𝑉 𝑜𝑙 (R ∗D (𝔯))𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, 𝔯)) 𝑉 𝑜𝑙 (W ∗ ) ∗
It is easy to check that 𝑑𝑖𝑠𝑡 0/∞ satisfies the properties listed in Definition 3. With this distance function, the general stability 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 reduces to the exact stability defined in [3].
𝔯 ∈ℜD
(4)
2.4.2 Why exponential function? We utilize 𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, 𝔯)) as weights for volumes of ranking regions in Definition 4 and 5. This approach elegantly ensures that the weight of the volume of the ranking of interest itself is 1, so that exact stability as defined in [3] is just a special case of the general stability. The exponential form should be interpreted as a monotone similarity kernel: the scale of 𝑑𝑖𝑠𝑡 controls how quickly credit decays as rankings become less similar. It is important to note that users have the flexibility to define their own distance function. If a user prefers not to have weights decrease exponentially with distance, they can manually incorporate a log function into their original distance function.
This slightly overloads the notation 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 ; when the acceptable region is relevant, it is assumed to be clear from context. The idea is straightforward: in evaluating the general stability of a ranking, we do not just look at the volume of its own region in weight space. Rather, we take into account the volumes of all rankings in the acceptable region W ∗ . Specifically, we compute the weighted sum of the volumes of all ranking regions, where the weights decrease exponentially as the distances between the ranking of interest and other rankings increase. The definition guarantees that the weight of the volume of the ranking of interest itself is 1, and the farther a ranking is from the ranking of interest, the less impact it will have on the general stability of the ranking of interest. Consider the following example:
2.5
We refer to the task of computing the stability value of a given ranking as stability computation. This task is called stability verification in prior work [3]; we use the term computation to emphasize that the output is a stability score rather than a binary certificate.
Example 3. Suppose we have four possible rankings denoted as 𝔯0 , 𝔯1 , 𝔯2 , 𝔯3 in an acceptable region W ∗ , where 𝑉 𝑜𝑙 (W ∗ ) = 10. The volumes of the regions corresponding to these four rankings are 2, 3, 3, and 2, respectively. Additionally, 𝑑𝑖𝑠𝑡 (𝔯0, 𝔯1 ) = 𝑑𝑖𝑠𝑡 (𝔯0, 𝔯2 ) = 1, 𝑑𝑖𝑠𝑡 (𝔯1, 𝔯3 ) = 𝑑𝑖𝑠𝑡 (𝔯2, 𝔯3 ) = 4, and 𝑑𝑖𝑠𝑡 (𝔯0, 𝔯3 ) = 5. Figure 2 presents the rankings and their distances as a graph.
Problem 1 (stability computation). Given a dataset D with 𝑛 items over 𝑑 scoring attributes, an acceptable region W ∗ ⊂ W, a ranking 𝔯 of D, and a distance function 𝑑𝑖𝑠𝑡, compute the general stability 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯).
𝔯1 1
𝑉 =3
𝔯0
3
4
𝑉 =2 1
𝔯2
PRACTICAL DISTANCE FUNCTIONS
In Section 1, we argued that exact stability can be too blunt because it treats all non-identical rankings as equally different. General stability addresses this issue by incorporating a user-defined distance between rankings into stability computation. However, merely defining general stability is not enough. The distance function must reflect which ranking changes matter in the application. For example, the 0/∞ distance function reduces general stability to exact stability and therefore preserves the same exact-match behavior. In this section, we introduce several practical distance functions for rankings.
𝔯3
5
𝑉 =2
The Algorithmic Problem - Stability Computation
4
𝑉 =3
Figure 2: Graph representation of the rankings and distances in Example 3. If we adhere to the conventional stability definition, we find the stability values for both 𝔯0 and 𝔯3 are 0.2. This is not ideal, according to our discussion in the introduction section. Nevertheless, the general stability of 𝔯0 and 𝔯3 varies significantly, according to the definition, 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) = 0.2 + 0.6𝑒 −1 + 0.2𝑒 −5 = 0.4221 while 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯3 ) = 0.2 + 0.6𝑒 −4 + 0.2𝑒 −5 = 0.2123. This
3.1
Desirable Properties of Distance Functions
An effective distance function for ranking should satisfy certain properties. First, it should provide meaningful measurements of the differences between rankings, offering a spectrum of distance 4
values rather than a binary distinction. This allows for nuanced assessments of similarity, acknowledging that rankings can be similar to varying degrees. Second, discrepancies at higher ranks should be weighted more heavily than those at lower ranks, reflecting the greater importance often associated with top-ranked items. For example, shifts in the top 10 universities are more impactful than changes among those ranked beyond 100.
3.2
The Spearman’s Footrule distance measures the sum of absolute differences in positions: ∑︁ |𝔯1 (𝑡) − 𝔯2 (𝑡)| . dist𝐹 (𝔯1, 𝔯2 ) = 𝑡∈D
3.3.2 Position Weights. While Kendall’s Tau and Spearman’s Footrule distances effectively capture overall dissimilarity, they treat discrepancies at all ranks equally. To emphasize discrepancies at higher ranks, Kumar and Vassilvitskii [33] introduced position-weighted versions of Kendall’s Tau and Spearman’s Footrule distances. These distances assign weights to each rank position, allowing higher ranks to contribute more to the overall distance.
First Differing Position Distance
Based on these criteria, we first propose a simple distance function: the first differing position distance, denoted as 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 . This function assigns smaller distances to rankings that agree on more top-ranked items, capturing that early agreements matter more.
Definition 3.2 (Position-Weighted Kendall’s Tau and Spearman’s Footrule Distance [33]). Let Δ = (𝛿 1, 𝛿 2, . . . , 𝛿𝑛 ) be a sequence of non-increasing weights with 1 = 𝛿 1 ≥ 𝛿 2 ≥ · · · ≥ 𝛿𝑛 ≥ 0. Define Í the cumulative weight function 𝑝 (𝑖) = 𝑖𝑘=1 𝛿𝑘 . For each item 𝑡𝑖 , set 𝑝 𝔯1 (𝑡𝑖 ) − 𝑝 𝔯2 (𝑡𝑖 ) 𝑝¯ (𝑡𝑖 ) = . 𝔯1 (𝑡𝑖 ) − 𝔯2 (𝑡𝑖 ) When 𝔯1 (𝑡𝑖 ) = 𝔯2 (𝑡𝑖 ), we use the convention 𝑝¯ (𝑡𝑖 ) = 𝛿 𝔯1 (𝑡𝑖 ) . Then, the position-weighted Kendall’s Tau distance is defined as ∑︁ dist𝐾Δ (𝔯1, 𝔯2 ) = 𝑝¯ (𝑡𝑖 ) 𝑝¯ (𝑡 𝑗 ) · 𝔯2 (𝑡𝑖 ) > 𝔯2 (𝑡 𝑗 ) .
Definition 3.1 (First Differing Position Distance). Given two rankings 𝔯1 and 𝔯2 over 𝑛 items, let 𝑘 = min{𝑖 | 𝔯1−1 (𝑖) ≠ 𝔯2−1 (𝑖)} when the two rankings are not identical. The distance 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 is defined as: ( 0, if 𝔯1 = 𝔯2, 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯1, 𝔯2 ) = 1 𝑘 , otherwise. For example, consider the rankings 𝔯1 = (𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓 ) and 𝔯2 = (𝑎, 𝑏, 𝑐, 𝑓 , 𝑑, 𝑒). The first three positions are identical in both rankings. The first difference occurs at position 4, where 𝔯1−1 (4) = 𝑑 and 𝔯2−1 (4) = 𝑓 . Applying the distance function: 1 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯1, 𝔯2 ) = . 4 Thus, the distance between 𝔯1 and 𝔯2 is 1/4, indicating that they are relatively similar since they agree on the top three items. While 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 captures the significance of early agreements, it has limitations. It considers only the position of the first difference and ignores the extent of later disagreement. Thus, it cannot distinguish between rankings that diverge similarly at the first differing position but have varying degrees of overall dissimilarity.
3.3
(𝑡𝑖 ,𝑡 𝑗 ) ∈ D 𝔯1 (𝑡𝑖 ) <𝔯1 (𝑡 𝑗 )
The position-weighted Spearman’s Footrule distance is defined as dist𝐹 Δ (𝔯1, 𝔯2 ) =
𝑛 ∑︁
𝑝¯ (𝑡𝑖 )
𝑖=1
𝔯∑︁ 1 (𝑡𝑖 )
2 𝑖 ∑︁ 𝑝¯ 𝔯1−1 ( 𝑗) − 𝑝¯ 𝔯2−1 ( 𝑗) .
𝔯 (𝑡 )
𝑗=1
𝑗=1
3.3.3 Exponential Position Weights. A remaining issue is the choice of the weight sequence Δ. To naturally emphasize higher ranks, we propose using exponentially decreasing weights: 𝛿𝑘 = 𝛿 𝑘 −1,
for 𝑘 = 1, 2, . . . , 𝑛,
where 0 < 𝛿 < 1. This choice yields the weight vector (1, 𝛿, 𝛿 2, . . . ), ensuring that each subsequent position receives exponentially less weight. In the later parts of this paper, we use the notation 𝐾𝛿 or 𝐹𝛿 to denote the position-weighted Kendall’s Tau/Spearman Footrule distance with exponential weight (1, 𝛿, 𝛿 2, ...). For example, 𝐾0.5 denotes the position-weighted Kendall’s Tau distance with weight vector (1, 0.5, 0.25, ...). These exponentially weighted distance functions effectively capture the significance of top ranks and account for partial similarities between rankings.
Exponentially Position-Weighted Kendall’s Tau and Spearman’s Footrule Distances
Addressing the limitations of 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 , we introduce two more sophisticated distance functions: the exponentially position-weighted versions of Kendall’s Tau and Spearman’s Footrule distances. These functions are derived from classical distance functions and provide a more informative and nuanced measure of dissimilarity, as well as satisfy the properties we discussed in Section 3.1.
3.4
Other Distance Functions
It is also important to note that users are not restricted to the distance functions discussed above. There could be other useful distance functions that meaningfully measure differences between rankings. The stability-computation algorithms in the following sections are compatible with any distance function that satisfies Definition 3. Therefore, users can design their own distance functions to suit their specific needs.
3.3.1 Classical Kendall’s Tau and Spearman’s Footrule Distances. Kendall’s Tau and Spearman’s Footrule are established metrics for quantifying the dissimilarity between two rankings. Given two rankings 𝔯1, 𝔯2 over a set of items D, the Kendall’s Tau distance counts the number of pairwise disagreements: ∑︁ dist𝐾 (𝔯1, 𝔯2 ) = 1 𝔯2 (𝑡𝑖 ) > 𝔯2 (𝑡 𝑗 ) , (𝑡𝑖 ,𝑡 𝑗 ) ∈ D × D 𝔯1 (𝑡𝑖 ) <𝔯1 (𝑡 𝑗 )
where 1[·] is the indicator function.
5
4
5
2D STABILITY COMPUTATION
Like [3], we first consider the special case 𝑑 = 2, where the scoring function has the form 𝑓𝑤® (𝑡) = 𝑤 1𝑡 [1] + 𝑤 2𝑡 [2]
When dealing with general distance functions, we can extend the stability-computation algorithms proposed by [3]. As we discussed in Section 2.2, each ranking region is a 𝑑-dimensional cone-like region whose boundary is determined by pairwise comparison hyperplanes. Since accurately calculating the volumes of highdimensional polyhedra is #𝑃-hard [26], [3] employs Monte-Carlo methods to approximate the stability of a target ranking. We extend their method to make it suitable for general stability.
(5)
The direction of a weight vector can be represented by one angle. We use the convention 𝜃 = arctan(𝑤 1 /𝑤 2 ), so 𝜃 = 0 corresponds to ranking only by the second attribute and 𝜃 = 𝜋/2 corresponds to ranking only by the first attribute. Under this convention, the acceptable region W ∗ is an angular interval [𝜃 min, 𝜃 max ]. In 2D, ordering exchanges partition the angular space into intervals, and all weights in one interval induce the same ranking [3]. For general stability, we sweep these intervals and add each interval’s angular width with weight exp(−𝑑𝑖𝑠𝑡 (𝔯0, 𝔯)). For a pair of items (𝑡𝑖 , 𝑡 𝑗 ), the exchange angle is determined by 𝑤 1 𝑡𝑖 [1] − 𝑡 𝑗 [1] + 𝑤 2 𝑡𝑖 [2] − 𝑡 𝑗 [2] = 0.
5.1
An Unbiased Sampler on W ∗
To estimate the volumes of the truncated cone-like ranking regions inside W ∗ using rejection sampling, we need samples of weights from W ∗ . These samples must be unbiased, i.e., the probability that a sample falls into each ranking region is proportional to the volume of that region. Formally, for each 𝔯 ∈ ℜ D , an unbiased sample 𝑊 should satisfy: 𝑉 𝑜𝑙 (R ∗D (𝔯)) 𝑃 (𝑊 ∈ R ∗D (𝔯)) = 𝑉 𝑜𝑙 (W ∗ ) An unbiased sampler satisfying this property was proposed in [3]. It generates samples from W ∗ in time linear in the dimension. We will directly adopt their sampler in our method.
Equivalently, for each pair we compute 𝑡 𝑗 [2] − 𝑡𝑖 [2] , 𝑏 (𝑖,𝑗 ) = 𝑡𝑖 [1] − 𝑡 𝑗 [1]. 𝑎 (𝑖,𝑗 ) = 𝑡𝑖 [1] − 𝑡 𝑗 [1] The list 𝐿 of all such tuples has size Θ(𝑛 2 ). Sorting 𝐿 orders the exchange angles, and the sweep in Algorithm 1 accumulates the weighted contribution of each interval.
5.2
Stability Computation
The 𝐺𝑆𝐶𝑚𝑑 algorithm described in Algorithm 2 is a direct extension of the stability oracle described in [3]. It offers an unbiased estimation of the general stability of a given target ranking 𝔯0 based on a fixed number of unbiased samples taken from W ∗ . Let 𝐷𝑑𝑖𝑠𝑡 (𝑛, 𝑑) denote the time needed to evaluate the contribution of one sampled weight for the chosen distance function 𝑑𝑖𝑠𝑡, including any ranking information required for that evaluation. This cost is distance-dependent. For distances such as 𝑑𝑖𝑠𝑡 0/∞ , one may only need to test whether the sampled weight preserves the target ranking, which can avoid constructing a complete sorted ranking. For other distances, such as Kendall’s tau or Spearman’s footrule, evaluating the contribution may require computing a full induced ranking. In the following analysis, 𝐷𝑑𝑖𝑠𝑡 (𝑛, 𝑑) abstracts this per-sample evaluation cost.
Algorithm 1: 𝐺𝑆𝐶 2𝑑 : 2D general stability computation Data: Dataset D, target ranking 𝔯0 , interval W ∗ = [𝜃 min, 𝜃 max ], distance 𝑑𝑖𝑠𝑡, and exchange list 𝐿 Result: the general stability 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) 1 𝑠𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦 ← 0; 2 Generate an initial ranking 𝔯 by sorting items at an angle just larger than 𝜃 min ; 3 𝑎𝑛𝑔𝑙𝑒 ← 𝜃 min ; 4 𝑙𝑎𝑠𝑡_𝑑𝑖𝑠𝑡 ← 𝑑𝑖𝑠𝑡 (𝔯0 , 𝔯); 5 Sort 𝐿 according to the value of 𝑎 (𝑖,𝑗 ) in ascending order; 6 for each ((𝑖, 𝑗), 𝑎 (𝑖,𝑗 ) , 𝑏 (𝑖,𝑗 ) ) ∈ 𝐿 do 7 if 𝑎𝑟𝑐𝑡𝑎𝑛(𝑎 (𝑖,𝑗 ) ) ≤ 𝜃 min then continue; 8 if 𝑎𝑟𝑐𝑡𝑎𝑛(𝑎 (𝑖,𝑗 ) ) ≥ 𝜃 max then break; 9 𝑠𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦+ = (𝑎𝑟𝑐𝑡𝑎𝑛(𝑎 (𝑖,𝑗 ) ) − 𝑎𝑛𝑔𝑙𝑒)𝑒𝑥𝑝 (−𝑙𝑎𝑠𝑡_𝑑𝑖𝑠𝑡); 10 𝑎𝑛𝑔𝑙𝑒 ← 𝑎𝑟𝑐𝑡𝑎𝑛(𝑎 (𝑖,𝑗 ) ); 11 swap the position of 𝑡𝑖 and 𝑡 𝑗 in 𝔯; 12 𝑙𝑎𝑠𝑡_𝑑𝑖𝑠𝑡 ← 𝑑𝑖𝑠𝑡 (𝔯0, 𝔯); 13 end 14 𝑠𝑡𝑎𝑏𝑖𝑙𝑖𝑡𝑦+ = (𝜃 max − 𝑎𝑛𝑔𝑙𝑒)𝑒𝑥𝑝 (−𝑙𝑎𝑠𝑡_𝑑𝑖𝑠𝑡);
Algorithm 2: 𝐺𝑆𝐶𝑚𝑑 : Multidimensional general stability estimator Data: A target ranking 𝔯0 , a distance function 𝑑𝑖𝑠𝑡, and a sample budget 𝑁 Result: An unbiased estimation 𝑠ˆ of 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) 1 𝑠 ← 0; 2 for 𝑖 = 1, ..., 𝑁 do 3 draw an unbiased sample 𝑊𝑖 from W ∗ ; 4 𝑠 ← 𝑠 + 𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, ∇ 𝑓𝑊𝑖 (D))); 5 end 6 return 𝑠ˆ = 𝑠/𝑁 ;
𝑠𝑡𝑎𝑏𝑖𝑙𝑖𝑡 𝑦
15
MULTIDIMENSIONAL STABILITY COMPUTATION
return 𝜃 max −𝜃 min ;
Generating the initial rank takes Θ(𝑛 log 𝑛), and sorting 𝐿 takes Θ(𝑛 2 log 𝑛). The main for loop in 𝐺𝑆𝐶 2𝑑 runs for Θ(𝑛 2 ) iterations. Assuming 𝑑𝑖𝑠𝑡 takes 𝐷 time to compute, the total time complexity of 𝐺𝑆𝐶 2𝑑 is 𝑂 (𝑛 2 (𝐷 + log 𝑛)).
The estimator is unbiased because each sample falls in a ranking region with probability equal to that region’s volume fraction in 6
W ∗ . Therefore, ∑︁ 𝑉 𝑜𝑙 (R ∗ (𝔯)) D 𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, 𝔯)) = 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ). 𝐸 [ˆ𝑠] = 𝑉 𝑜𝑙 (W ∗ )
5.3.2 Time and Accuracy. The special case of 𝑑𝑖𝑠𝑡 0/∞ gives a lowerbound witness: the sample budget can be as large as a constant multiple of 1−𝑠 𝑠 for fixed 𝜖 and 𝛼. The general variance bound gives the matching upper bound: for every distance function considered here, it suffices to take a sample budget at most a constant multiple of 1−𝑠 𝑠 for fixed 𝜖 and 𝛼. Therefore, the worst-case sample complexity of 𝐺𝑆𝐶𝑚𝑑 , over the admissible distance functions in this framework, is 1−𝑠 𝑁 =Θ , 𝑠 with constants depending on 𝜖 and 𝛼. This does not mean that every distance function or dataset requires many samples; when the stability value is moderate, 𝐺𝑆𝐶𝑚𝑑 can be very efficient in practice. The bound identifies the complementary rare-event regime: as 𝑠 gets smaller, fixed error and failure guarantees need more samples.
𝔯 ∈ℜD
When taking 𝑑𝑖𝑠𝑡 0/∞ as the distance function, 𝐺𝑆𝐶𝑚𝑑 will be equivalent to stability oracle 𝑆 proposed in [3].
5.3 𝐺𝑆𝐶𝑚𝑑 with Fixed Error and Failure Probability The 𝐺𝑆𝐶𝑚𝑑 algorithm inherently involves a trade-off between computational time and accuracy. As more samples are drawn from W ∗ , the estimate 𝑠ˆ becomes more accurate; however, the computational time increases proportionally, since 𝐺𝑆𝐶𝑚𝑑 runs in 𝑂 (𝑁 𝐷𝑑𝑖𝑠𝑡 (𝑛, 𝑑)) time under the per-sample cost notation above. In practice, users often specify an allowable error threshold 𝜖 and a failure probability 𝛼, expecting the algorithm to produce an estimate within (1 ± 𝜖)𝑠 of the true value 𝑠 = 𝑆𝑡𝑎𝑏 D, 𝑑𝑖𝑠𝑡 (𝔯0 ) with probability at least 1 − 𝛼. In this subsection, we analyze the time-accuracy trade-off in 𝐺𝑆𝐶𝑚𝑑 , introduce a method to run 𝐺𝑆𝐶𝑚𝑑 with fixed error and failure probability, and examine its sample complexity. Since the total runtime is obtained by multiplying the sample budget by 𝐷𝑑𝑖𝑠𝑡 (𝑛, 𝑑), exponential sample complexity immediately yields exponential runtime up to this per-sample evaluation factor.
5.3.3 Run 𝐺𝑆𝐶𝑚𝑑 with Fixed Error and Failure Probability. The sample bound above depends on the unknown stability value 𝑠. In practice, we use an adaptive implementation that updates the estimate after each sample, forms an empirical lower bound 𝐿𝐵 on 𝑠, and then substitutes 𝐿𝐵 into the sufficient sample-size bound. This gives the stopping rule in Algorithm 3. The rule is conservative when 𝐿𝐵 is below the true stability value; if the maximum sample budget is reached first, the algorithm returns the current estimate.
5.3.1 Sample Size. To achieve an 𝜖-approximation of 𝑠 with failure probability at most 𝛼, we need to determine the minimum sample size 𝑁 such that:
Algorithm 3: 𝐺𝑆𝐶𝑚𝑑 with adaptive sample budget Data: Target ranking 𝔯0 , distance 𝑑𝑖𝑠𝑡, error 𝜖, failure probability 𝛼, and budget 𝑁 max . Result: An unbiased estimation of 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) 1 𝑠 ← 0; 2 𝑁 ← 0; 3 while 𝑁 < 𝑁 max do 4 draw an unbiased sample 𝑓𝑤 from W ∗ ; 5 𝑠 ← 𝑠 + 𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, ∇ 𝑓𝑤 (D))) ; 6 𝑁 ← 𝑁 + 1; 7 𝑠ˆ ← 𝑠/𝑁 ; √︃ 𝑠ˆ ) 𝑠ˆ 8 𝐿𝐵 ← max{1e−20, 𝑠ˆ − (1− 𝑁 𝛼 };
𝑃 (|𝑠ˆ − 𝑠 | < 𝜖𝑠) ≥ 1 − 𝛼 . Special Case: 𝑑𝑖𝑠𝑡 0/∞ . When using 𝑑𝑖𝑠𝑡 0/∞ , 𝑠ˆ follows a binomial distribution Binomial(𝑁 , 𝑠). The normal approximation to the binomial distribution allows us to estimate the required sample size: 𝑁 =
𝑧
𝛼/2 2 1 − 𝑠
, 𝜖 𝑠 This special case shows that, for the class of distance functions considered in this paper, there exist valid inputs for which estimating 𝑠 to a fixed relative error requires a sample budget proportional to (1 − 𝑠)/𝑠, up to constants depending on 𝜖 and 𝛼.
𝑁𝑟𝑒𝑞 ← 𝜖 21𝛼 1−𝐿𝐵 𝐿𝐵 ; 10 if 𝑁 ≥ 𝑁𝑟𝑒𝑞 then break; 11 end ˆ 12 return 𝑠; 9
General Case. For a general distance function, let one sample contribution be 𝑋 = exp(−𝑑𝑖𝑠𝑡 (𝔯0, ∇ 𝑓𝑊 (D))). Since 0 ≤ 𝑋 ≤ 1 and 𝐸 [𝑋 ] = 𝑠, we have 𝐸 [𝑋 2 ] ≤ 𝐸 [𝑋 ] = 𝑠, so 𝑠 − 𝑠2 . 𝑁 Applying Chebyshev’s inequality, we find: Var[ˆ𝑠] ≤
5.3.4 Why 𝐺𝑆𝐶𝑚𝑑 is Not Polynomial. We now use the samplecomplexity bound above to explain why 𝐺𝑆𝐶𝑚𝑑 is not polynomial in the worst case when the dimension 𝑑 is part of the input. The key point is that the sample budget depends on (1 − 𝑠)/𝑠. Thus, it is enough to show that there are valid inputs for which the target stability 𝑠 is exponentially small in 𝑑. We prove this using the special case 𝑑𝑖𝑠𝑡 0/∞ . Under this distance, 𝐺𝑆𝐶𝑚𝑑 estimates exact stability: a sample contributes 1 if it induces the target ranking and 0 otherwise. Therefore, the stability of a ranking is the volume fraction of its own ranking region in W ∗ .
Var[ˆ𝑠] (1 − 𝑠) ≤ 𝜖 2𝑠 2 𝑁 𝜖 2𝑠 Thus, to ensure 𝑃 (|𝑠ˆ − 𝑠 | ≥ 𝜖𝑠) ≤ 𝛼, it suffices to have 𝑃 (|𝑠ˆ − 𝑠 | ≥ 𝜖𝑠) ≤
𝑁 =
(1 − 𝑠) 𝛼𝜖 2𝑠
7
6
Proposition 5. For every fixed dimension 𝑑, there exist databases D with 𝑛 tuples in 𝑑 dimensions whose positive weight space contains Ω(𝑛 2(𝑑 −1) ) nonempty ranking regions.
POLYNOMIAL STABILITY COMPUTATION FOR QUASICONVEX DISTANCE FUNCTIONS
Both the stability computation method proposed in [3] and the 𝐺𝑆𝐶𝑚𝑑 we proposed in the last section are sampling-based in multidimensional settings. They are broadly applicable, but under a fixed relative-error guarantee their sample complexity can become large when the stability value is small. In this section, we propose a novel algorithm, Conv-SC, for this structured rare-event regime. Conv-SC can perform stability computation in polynomial time under fixed error tolerance and failure probability, provided that the distance function satisfies the quasiconvexity requirement and the acceptable region W ∗ is convex. This is a structural restriction on the distance function, not a requirement for general stability itself: distances such as the position-weighted Kendall’s Tau and Spearman’s Footrule distances from Section 3.3 are useful for the general sampling-based methods, but are not quasiconvex in general. Notably, 𝑑𝑖𝑠𝑡 0/∞ satisfies the quasiconvexity requirement.
Proof. We use Cover’s result on linearly inducible orderings [21]. Let 𝑄 (𝑛, 𝑑) be the number of distinct orderings of 𝑛 points in general position in R𝑑 that can be induced by linear projections 𝑤 · 𝑡𝑖 , as 𝑤 ranges over all directions in R𝑑 . [21] gives the recurrence 𝑄 (𝑛, 𝑑) = 𝑄 (𝑛 − 1, 𝑑) + (𝑛 − 1)𝑄 (𝑛 − 1, 𝑑 − 1), with the base cases 𝑄 (𝑛, 1) = 2 and 𝑄 (2, 𝑑) = 2. This recurrence implies, by induction on 𝑑, that for each fixed 𝑑, 𝑄 (𝑛, 𝑑) is a polynomial in 𝑛 of degree 2(𝑑 − 1). Hence 𝑄 (𝑛, 𝑑) = Θ(𝑛 2(𝑑 −1) ) for fixed 𝑑. These projection-induced orderings are exactly the ranking regions generated by the pairwise comparison hyperplanes 𝐻𝑖 𝑗 = {𝑤 ∈ R𝑑 : 𝑤 · (𝑡𝑖 − 𝑡 𝑗 ) = 0}. On one side of 𝐻𝑖 𝑗 , 𝑡𝑖 has a larger score than 𝑡 𝑗 ; on the other side, 𝑡 𝑗 has a larger score than 𝑡𝑖 . The count in [21] is over all directions, while our weight space is the positive orthant of the unit ball. The 2𝑑 coordinate orthants partition the directions in R𝑑 , so at least one orthant contains a 1/2𝑑 fraction of the ranking regions. By flipping coordinate signs of all tuples if necessary, we may map that orthant to the positive orthant without changing the number of regions inside it. Therefore, for each fixed 𝑑, the positive orthant contains Ω(𝑛 2(𝑑 −1) ) nonempty ranking regions. The hidden constant in this Ω(·) notation may depend on 𝑑. □
6.1
Motivation: Efficient Volume Computation of Convex Bodies
Computing the exact volume of high-dimensional polyhedra is #𝑃-hard [26], meaning that no known polynomial-time algorithms exist for this task. However, efficient randomized algorithms can approximate the volume of convex bodies within a fixed error tolerance in polynomial time. Dyer, Frieze, and Kannan [25] first proposed such an algorithm with a fixed error bound. By leveraging the hit-and-run sampling method [43], a Markov chain Monte Carlo technique that uniformly samples points within a convex set, Kannan, Lovász, and Simonovits [31] improved the computation time to 𝑂 ∗ (𝑑 5 ), where 𝑑 is the number of dimensions, and the “softO” notation 𝑂 ∗ suppresses logarithmic factors like log 𝑑 and other parameters such as the error bound 𝜖. The theoretical guarantee assumes access to a randomized convex-volume approximation routine with the stated accuracy guarantee. A key requirement for applying these algorithms is that the body must be convex. In our context, each ranking region is indeed convex. However, calculating the general stability requires computing the volumes of multiple ranking regions. Since the number of these regions grows exponentially with the number of dimensions, even efficiently approximating each individual volume leads to an overall exponential time complexity. To overcome this challenge, we propose a novel approach. Instead of computing the volume of each ranking region separately, we group regions based on their distances to the ranking of interest. We then compute the combined volume of all ranking regions that are within a certain distance 𝑟 from the ranking of interest. We introduce the concept of quasiconvexity. If a distance function is quasiconvex, then the union of ranking regions within a distance 𝑟 forms a convex set. This property allows us to apply the hitand-run method to efficiently calculate the general stability. In the following subsections, we will formally define quasiconvexity and present the related algorithms.
Take W ∗ = W. The proposition implies that, for these databases, W is partitioned into Ω(𝑛 2(𝑑 −1) ) nonempty ranking regions. Hence at least one ranking region has volume fraction 𝑠 = 𝑂 (𝑛 −2(𝑑 −1) ). For 𝑑𝑖𝑠𝑡 0/∞ , this volume fraction is exactly the stability of the corresponding ranking. Thus, we are not assuming that 𝑠 is small for every input; rather, the proposition constructs valid inputs for which at least one target ranking has 𝑠 = 𝑂 (𝑛 −2(𝑑 −1) ). For sufficiently large 𝑛, this gives 𝑠 ≤ 1/2, and therefore (1 − 𝑠)/𝑠 ≥ 1/(2𝑠). Substituting this constructed small value of 𝑠 into the worstcase sample-complexity bound gives 1−𝑠 𝑁 =Θ = Ω(𝑛 2(𝑑 −1) ) 𝑠 for fixed 𝜖 and 𝛼. This lower bound is not polynomial in the combined input parameters 𝑛 and 𝑑: for any fixed polynomial degree in 𝑛, choose 𝑑 large enough that 2(𝑑 − 1) exceeds that degree, and then let 𝑛 grow. Thus, when 𝑑 is allowed to vary, 𝐺𝑆𝐶𝑚𝑑 can require non-polynomially many samples. Since the total runtime is the sample budget multiplied by the per-sample evaluation cost 𝐷𝑑𝑖𝑠𝑡 (𝑛, 𝑑), the algorithm is not polynomial-time in the worst case under a fixed relative-error guarantee.
8
6.2
Quasiconvexity of Distance Functions
differing position. For 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 , the level set for agreement through the first 𝑘 − 1 positions can be written using linear constraints that place each prefix item above every remaining item, yielding 𝑂 (𝑘𝑛) ranking constraints at level 𝑘. We list the possible values of 𝑑𝑖𝑠𝑡 in increasing order as 𝑅 = {𝑟 0, 𝑟 1, ..., 𝑟𝑘 }, where 0 = 𝑟 0 < 𝑟 1 < · · · < 𝑟𝑘 . For each level, let 𝐶𝑖 = 𝐵𝑑𝑖𝑠𝑡 (𝔯0, 𝑟𝑖 ) ∩ W ∗ denote the feasible part of the distance ball. Grouping ranking regions by their distance to 𝔯0 gives: ∑︁ 1 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) = 𝑉 𝑜𝑙 (R ∗D (𝔯))𝑒𝑥𝑝 (−𝑑𝑖𝑠𝑡 (𝔯0, 𝔯)) 𝑉 𝑜𝑙 (W ∗ ) ∗
Definition 11 (Quasiconvex distance function). A distance function 𝑑𝑖𝑠𝑡 for rankings on D is quasiconvex if and only if it satisfies the following property: for any 𝑤 0, 𝑤 1, 𝑤 2 ∈ R𝑑 and 𝜆 ∈ (0, 1), 𝑑𝑖𝑠𝑡 (∇ 𝑓𝑤® (D), ∇ 𝑓−−−−−−−−−−−−→ (D)) 0
𝜆𝑤1 +(1−𝜆) 𝑤2
≤ max{𝑑𝑖𝑠𝑡 (∇ 𝑓𝑤® (D), ∇ 𝑓𝑤® (D)), 𝑑𝑖𝑠𝑡 (∇ 𝑓𝑤® (D), ∇ 𝑓𝑤® (D))} 0
1
0
2
The reason that we define quasiconvexity is that it exhibits the following important property:
𝔯 ∈ℜD
Proposition 1. If a distance function 𝑑𝑖𝑠𝑡 is quasiconvex, then for any linearly inducible ranking 𝔯 and real number 𝑟 , the closed ball 𝐵𝑑𝑖𝑠𝑡 (𝔯, 𝑟 ) := {𝑤 ∈ R𝑑 |𝑑𝑖𝑠𝑡 (𝔯, ∇ 𝑓𝑤® (D)) ≤ 𝑟 } is convex.
𝑘 ∑︁ ∑︁ 1 𝑒𝑥𝑝 (−𝑟𝑖 ) 𝑉 𝑜𝑙 (R ∗D (𝔯)) ∗ 𝑉 𝑜𝑙 (W ) 𝑖=0 𝔯,𝑑𝑖𝑠𝑡 (𝔯0 ,𝔯)=𝑟𝑖 1 = 𝑉 𝑜𝑙 (𝐶 0 ) ∗ 𝑉 𝑜𝑙 (W ) 𝑘 ∑︁ 𝑒𝑥𝑝 (−𝑟𝑖 ) [𝑉 𝑜𝑙 (𝐶𝑖 ) − 𝑉 𝑜𝑙 (𝐶𝑖 −1 )] +
=
Proof. For any 𝑤 1, 𝑤 2 ∈ 𝐵𝑑𝑖𝑠𝑡 (𝔯, 𝑟 ) and 0 < 𝑡 < 1, choose 𝑤 0 such that 𝔯 = ∇ 𝑓𝑤® (D). By quasiconvexity, 0
𝑑𝑖𝑠𝑡 (𝔯, ∇ 𝑓−−−−−−−−−−−−→ (D)) 𝑡 𝑤1 +(1−𝑡 ) 𝑤2
≤ max{𝑑𝑖𝑠𝑡 (𝔯, ∇ 𝑓𝑤® (D)), 𝑑𝑖𝑠𝑡 (𝔯, ∇ 𝑓𝑤® (D))} ≤ 𝑟 . 1
Thus 𝑡𝑤 1 + (1 − 𝑡)𝑤 2 ∈ 𝐵𝑑𝑖𝑠𝑡 (𝔯, 𝑟 ).
6.3
𝑖=1
2
According to Proposition 1, each 𝐵𝑑𝑖𝑠𝑡 (𝔯0, 𝑟𝑖 ) is convex. Since W ∗ is also assumed to be convex, each feasible level set 𝐶𝑖 = 𝐵𝑑𝑖𝑠𝑡 (𝔯0, 𝑟𝑖 )∩W ∗ is convex as well. Therefore, each level-set volume can be approximated in polynomial time for fixed accuracy. The overall cost is polynomial in the dimension for each convex body and scales with the number of distance levels that are evaluated. For distances such as 𝑑𝑖𝑠𝑡 0/∞ and 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 , this level-set dependence is small enough to make the method practical. The algorithm is shown below in Algorithm 4. Before calling the volume routine, Conv-SC computes a wellconditioned interior point when the convex body is represented by linear ranking constraints and the unit ball. In the 0/∞ case, this amounts to finding the largest ball centered at 𝑐 that remains inside the target ranking region:
□
Quasiconvex Distance Functions
It is easy to check that 𝑑𝑖𝑠𝑡 0/∞ is quasiconvex. Now, we show that the first differing position distance (𝑑𝑖𝑠𝑡𝑝𝑜𝑠 ) from Definition 3.1 is also quasiconvex. These examples illustrate the class targeted by Conv-SC; not all practical ranking distances are quasiconvex. Proposition 2. 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 is quasiconvex. Proof. Let 𝑤 0, 𝑤 1, 𝑤 2 ∈ R𝑑 and 𝜆 ∈ (0, 1), and let 𝔯𝑖 = ∇ 𝑓𝑤𝑖 (D) for 𝑖 = 0, 1, 2. If 𝔯1 = 𝔯2 = 𝔯0 , then all pairwise score inequalities in 𝔯0 are preserved by 𝜆𝑤 1 + (1 − 𝜆)𝑤 2 , so the desired inequality is immediate. Otherwise, let 𝑘 be the first position at which either 𝔯1 or 𝔯2 differs from 𝔯0 . Then the first 𝑘 − 1 items of all three rankings are the same and in the same order, and 1 ≤ max{𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯0, 𝔯1 ), 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯0, 𝔯2 )}. 𝑘 Let 𝑡𝑚 = 𝔯0−1 (𝑚) for 𝑚 < 𝑘. For any 𝑚 < 𝑘 and any item 𝑥 outside the first 𝑚 positions, both 𝑤 1 and 𝑤 2 rank 𝑡𝑚 above 𝑥. Since score differences are linear in the weight vector,
maximize subject to
Thus ∇ 𝑓𝜆𝑤1 +(1−𝜆) 𝑤2 (D) preserves the first 𝑘 − 1 positions of 𝔯0 . Its first differing position from 𝔯0 is no earlier than 𝑘, so 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯0, ∇ 𝑓𝜆𝑤1 +(1−𝜆) 𝑤2 (D)) 1 ≤ max{𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯0, 𝔯1 ), 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 (𝔯0, 𝔯2 )}. 𝑘 □
6.4
for adjacent 𝑡𝑎 ≻ 𝑡𝑏 ,
It is enough to constrain adjacent pairs in the target order: if all adjacent score inequalities hold, then all pairwise inequalities follow by transitivity of the scalar scores. This is a second-order cone program and can be solved in polynomial time by standard interiorpoint methods [13]. The resulting 𝜌 gives a certified inner-ball radius for the convex-volume routine. In practice, constructing the volume oracle requires a strict interior point for each convex body. If this point is too close to the boundary, the inner ball may be tiny and the random walk may mix slowly. The max-margin step above addresses this issue for the 0/∞ distance. For other quasiconvex distances such as 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 , the same idea applies once the level set is written as linear constraints.
(𝜆𝑤 1 + (1 − 𝜆)𝑤 2 ) · (𝑡𝑚 − 𝑥) > 0.
≤
𝜌 𝑐 𝑗 ≥ 𝜌 for all 𝑗, 𝑐 · (𝑡𝑎 − 𝑡𝑏 ) ≥ 𝜌 ∥𝑡𝑎 − 𝑡𝑏 ∥ 2 ∥𝑐 ∥ 2 + 𝜌 ≤ 1.
The Conv-SC Algorithm
We denote the randomized convex-body volume routine by V. For any convex set 𝑆 in R𝑑 , V(𝑆) estimates the volume of 𝑆 in 𝑂 ∗ (𝑑 5 ) time for fixed accuracy parameters. Conv-SC is most useful when the quasiconvex distance function has a compact set of relevant distance levels. For example, 𝑑𝑖𝑠𝑡 0/∞ has only two possible values, and 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 has one level for each first
7
EXPERIMENTS
We experimentally evaluated both the modeling benefits and the computational costs of general stability. For the former, real-world case studies and minor-swap sensitivity checks showed that exact stability can be misleadingly brittle and that distance-sensitive stability better preserves meaningful ranking similarity. For the 9
Score Exact 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 𝐾0.5 𝐹 0.5 Exact 1.000 0.391 0.288 0.275 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 0.391 1.000 0.969 0.968 𝐾0.5 0.288 0.969 1.000 0.998 𝐹 0.5 0.275 0.968 0.998 1.000 Table 3: Correlation matrix for stability scores on sampled target rankings from the eight real datasets. The distancesensitive scores are strongly related to one another, while exact stability is substantially less correlated with them.
Algorithm 4: Conv-SC for quasiconvex distance functions Data: Ranking 𝔯0 , distance 𝑑𝑖𝑠𝑡, and convex acceptable region W ∗ Result: An estimate of 𝑆𝑡𝑎𝑏 D,𝑑𝑖𝑠𝑡 (𝔯0 ) 1 𝑣𝑜𝑙𝑢𝑚𝑒 ← 0; 2 𝑠 ← 0; 3 for each 𝑟 𝑖 do 4 𝑛𝑒𝑤_𝑣𝑜𝑙𝑢𝑚𝑒 ← V(𝐵𝑑𝑖𝑠𝑡 (𝔯0, 𝑟𝑖 ) ∩ W ∗ ) ; 5 𝑠+ = (𝑛𝑒𝑤_𝑣𝑜𝑙𝑢𝑚𝑒 − 𝑣𝑜𝑙𝑢𝑚𝑒)𝑒𝑥𝑝 (−𝑟𝑖 ) ; 6 𝑣𝑜𝑙𝑢𝑚𝑒 ← 𝑛𝑒𝑤_𝑣𝑜𝑙𝑢𝑚𝑒; 7 end ∗ 8 return 𝑠/𝑉 𝑜𝑙 (W );
the random-weight baseline (6.0 × 10−5 ), so the exact score suggests that the ranking is highly fragile. In contrast, the top-sensitive Kendall stability is 0.9179, above its baseline of 0.8856. The local perturbation results explain this difference. At perturbation radius 0.05, the full ranking is reproduced only 3.9% of the time. However, the top-5 set is preserved in essentially every sample. Thus, for this case, the instability captured by exact stability comes almost entirely from changes below the leading universities. This example illustrates why exact stability alone can be too brittle for interpreting real ranked lists. The exact score treats every non-identical ordering as equally different, whereas a suitable distance-sensitive score identifies that the top-ranked items remain stable and that most changes occur lower in the list.
latter, we found that the approximation methods achieve practical accuracy and runtime for distance-sensitive stability scores on real datasets. Furthermore, we show that Conv-SC realizes its intended advantage: for convex stability regions, it turns the highdimensional exact-stability computation into a polynomial-time convex-volume approximation task.
7.1
Experimental Setup and Datasets
Hardware and platform. The experiments were conducted using an Intel i7-12700F processor, 16 GB memory, running Linux. The algorithms were implemented in C++ 17, and the program was compiled in 𝑔𝑐𝑐 with optimization level O3. Conv-SC uses Volesti [17] for convex-body volume approximation. Datasets. The real-data experiments use eight datasets: QS World University Rankings 2024–2026 [42], Times Higher Education (THE) 2016 [48], Center for World University Rankings (CWUR) 2015 [16], CSMetrics 2016 [22], the 2023 Global Multidimensional Poverty Index (MPI) [49], CSRankings 2024 [23], NBA 2023–24 [9], and the Environmental Performance Index (EPI) 2024 [50]. The numbers of numeric indicators used in our processed tasks are 6 for QS, 5 for THE, 8 for CWUR, 2 for CSMetrics, 10 for MPI, 4 for CSRankings, 5 for NBA, and 6 for EPI. Selected experiments use generated datasets as controls.
7.2
7.3
Sensitivity to Minor Ranking Changes
As a lightweight check of the same effect across datasets, we take top-10 sampled target rankings, swap one adjacent pair in the lower half, and measure the normalized average change E[|𝑆 (𝔯) − 𝑆 (𝔯 ′ )|]/E[𝑆 (𝔯)]. Averaged over the eight real datasets, this value is 0.766 for exact stability, while the distance-sensitive scores are close to zero: 8.36×10−3 for 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 , 5.30×10−4 for 𝐾0.5 , and 8.65×10−4 for 𝐹 0.5 . Thus, exact stability changes substantially under a minor lower-half swap, whereas distance-sensitive scores barely move.
7.4
Error Analysis for 𝐺𝑆𝐶𝑚𝑑 and Conv-SC
𝐺𝑆𝐶𝑚𝑑 and Conv-SC are approximation methods: they do not return the ground-truth stability value, but an estimate whose accuracy is controlled by a user-specified error tolerance. The theoretical analysis guarantees that, with high probability, the relative error is below the requested tolerance. This guarantee is promising in theory, but it does not show what the approximation error looks like in practice, or how large the observed errors usually are relative to the requested tolerance. This investigation requires tasks where the ground-truth stability value is known. For general multidimensional inputs this value is unavailable, but in 2D, 𝐺𝑆𝐶 2𝑑 computes the ground-truth value under the 0/∞ distance. We use these 2D ground-truth values to compare fixed-error 𝐺𝑆𝐶𝑚𝑑 and Conv-SC estimates. The main check uses requested relative-error tolerance 𝜖 = 0.3, i.e., 30%, and failure probability 𝛼 = 0.1. The observed errors are usually much smaller than the requested 30% tolerance, for both generated 2D tasks and real two-attribute projections. Table 4 reports the real-data aggregates. Tightening the requested bound to 𝜖 = 0.05 on generated 2D tasks further reduced the mean errors to 1.4% for 𝐺𝑆𝐶𝑚𝑑 and 3.2% for Conv-SC.
Real-World Ranking Investigation
General stability was introduced because exact stability only checks whether the entire ranking is reproduced exactly. We therefore ask whether exact stability and distance-sensitive general stability agree on real datasets. For each dataset, we consider top-𝑛 rankings with 𝑛 = 10, 20, 30, 50, 100, normalize the selected attributes, and sample target rankings from random positive weights. For each target ranking, exact stability, 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 stability, 𝐾0.5 stability, and 𝐹 0.5 stability are estimated from the same random weight samples. Table 3 reports the resulting correlation matrix. CWUR patents top 30. In this dataset, items are universities and the candidate set consists of the 30 universities with the highest patent score in CWUR. We keep the eight CWUR attributes and use the equal-weight ranking as the target. The target begins with Harvard, MIT, Stanford, Johns Hopkins, and UC Berkeley. Under exact stability, Conv-SC estimates that this full top-30 ordering occupies only about 6.15 × 10−6 of the feasible weight space, below 10
Dataset 𝐺𝑆𝐶𝑚𝑑 Conv-SC Relative error Avg. Std. Max. Avg. Std. Max. MPI 6.5% 5.4% 19.6% 8.1% 6.3% 24.5% CWUR 6.6% 4.6% 16.0% 5.9% 4.9% 19.1% CSMetrics 2.4% 2.0% 5.2% 2.1% 1.3% 3.9% THE 7.5% 5.7% 20.2% 6.5% 4.7% 16.2% QS 7.3% 4.2% 15.9% 6.9% 4.0% 16.3% CSRank. 6.4% 3.1% 10.7% 8.6% 6.8% 21.1% NBA 6.3% 2.5% 9.2% 12.5% 9.5% 26.0% EPI 7.0% 5.1% 23.0% 8.3% 7.6% 24.7% All 6.6% 4.9% 23.0% 7.5% 6.3% 26.0% Table 4: Real-data accuracy check on 2D projections under the tie-aware 0/∞ distance. Ground-truth values are computed by 𝐺𝑆𝐶 2𝑑 . Entries report average, standard deviation, and maximum relative error in percent. The requested tolerance is 𝜖 = 0.3, i.e., 30%.
Dataset CSMetrics QS THE CWUR MPI CSRank. NBA EPI
Attributes Measured/Predicted Faculty/Citations Research/Income Publications/Faculty Cooking fuel/Mortality Interdisc./AI Steals/Blocks Biodiversity/Water
𝑑𝑖𝑠𝑡𝑝𝑜𝑠 4.314 0.936 4.539 3.769 4.352 3.609 0.921 4.401
𝐾0.5 47.716 4.942 56.388 45.751 40.080 29.289 4.051 52.841
Task 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 𝐾0.5 𝐹 0.5 Task 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 𝐾0.5 𝐹 0.5 QS26 4.313 0.905 1.464 CWUR 6.674 0.951 1.606 QS25 4.291 0.944 1.519 CSM 1.956 0.472 0.488 QS24 4.250 1.059 2.057 CSR 2.771 0.215 0.313 THE 9.114 1.872 2.486 NBA 3.450 0.662 1.075 Table 6: 𝐺𝑆𝐶𝑚𝑑 runtime in milliseconds on representative real-data tasks under three distance functions. CSM abbreviates CSMetrics and CSR abbreviates CSRankings.
receives zero credit. Conv-SC is better suited to this setting: it estimates the convex exact-stability region directly, as shown next.
7.6
Conv-SC is motivated by the gap between exact and approximate volume computation: exact high-dimensional polyhedral volume is #𝑃-hard [26], while convex-body volume can be approximated in polynomial time [25, 31]. When the stability region is convex, Conv-SC exploits this advantage directly. This experiment checks whether the polynomial-time convexvolume advantage of Conv-SC appears in runtime. We compare 𝐺𝑆𝐶𝑚𝑑 and Conv-SC under the 0/∞ distance, using generated data to observe the trend over multiple random instances and real data to check the same behavior on a natural high-dimensional dataset. For generated data, we randomly generate both the table values and the positive target weight vector that defines the target ranking; each point in Figure 3 is the median over five random trials. The final plot reports 𝑛 = 20, 30, 40 because 𝑛 = 25 lies between the two smaller curves and adds little visual information. For real data, we use MPI because it has ten numeric indicators and therefore gives a natural 𝑑 = 2, . . . , 10 column-prefix test; the other real datasets have fewer selected indicators in our processed tasks and do not provide the same ten-step dimension sequence. We report MPI top 30, 50, 100 to show how the same real dataset behaves as the ranked set grows. All runs use 𝜖 = 0.3 and 𝛼 = 0.1. Every Conv-SC point is a measured convex-volume runtime. For 𝐺𝑆𝐶𝑚𝑑 , we use measured runtimes whenever the fixed-error run is feasible; otherwise we report a pointwise runtime estimate. The estimate uses the Conv-SC stability estimate 𝑠, the fixed-error sample bound from Section 5, and measured per-sample throughput on the same task. This is reasonable because the bound gives the sample budget once 𝑠 is known, and the per-sample cost is directly measured. As a validation, across all 24 plotted points with measured 𝐺𝑆𝐶𝑚𝑑 runtimes, the measured-to-estimated ratios ranged from 0.47 to 2.17, with median 1.29 and mean 1.30; all were within a factor of 3. This agreement supports using the estimates to show the runtime scale for fixed-error runs that would be impractically long to execute directly. Figure 3 gives the clearest scaling evidence because generated inputs create a controlled, less correlated stress test for exact-stability computation. In this setting, Conv-SC grows smoothly with dimension, while 𝐺𝑆𝐶𝑚𝑑 quickly moves into the high-runtime regime. Figure 4 shows the corresponding real-data behavior on MPI. The MPI indicators are correlated, so the real-data curves are less uniform than the generated curves. Even in this more structured setting, Conv-SC remains feasible through all ten indicators, while 𝐺𝑆𝐶𝑚𝑑
𝐹 0.5 10.227 2.133 11.438 10.095 8.613 8.942 1.737 10.675
Table 5: Runtime in milliseconds for exact 𝐺𝑆𝐶 2𝑑 on real twodimensional cases. CSMetrics uses its reported two-score ranking; the other rows use one sampled two-attribute projection from each dataset.
7.5
Polynomial Efficiency of Conv-SC
Efficiency of 𝐺𝑆𝐶 2𝑑 and 𝐺𝑆𝐶𝑚𝑑
We measure the efficiency of 𝐺𝑆𝐶 2𝑑 and 𝐺𝑆𝐶𝑚𝑑 on representative ranking tasks. For 𝐺𝑆𝐶 2𝑑 , we report exact runtimes on two-attribute inputs. For 𝐺𝑆𝐶𝑚𝑑 , we report the sampling cost needed to meet a fixed user-specified error tolerance. Efficiency of 𝐺𝑆𝐶 2𝑑 . CSMetrics is the natural real-data case for this experiment because its reported ranking is defined by two publication-based scores. We therefore report CSMetrics first. To check that this behavior is not specific to this dataset, we also sample one two-attribute projection from each of the other real datasets and compute exact 2D general stability under 𝑑𝑖𝑠𝑡𝑝𝑜𝑠 , 𝐾0.5 , and 𝐹 0.5 . Table 5 shows that all these real 2D cases finish in milliseconds. Efficiency of 𝐺𝑆𝐶𝑚𝑑 . Following the fixed-error setting in Section 5, we use 𝜖 = 0.3 and 𝛼 = 0.1. Table 6 reports runtimes on representative real-data tasks with reported or naturally defined target rankings. The rows in Table 6 finish in at most 0.010 seconds. This shows that 𝐺𝑆𝐶𝑚𝑑 is practical for the distance-sensitive stability scores used in the real-data investigation. Exact stability can also be measured by 𝐺𝑆𝐶𝑚𝑑 , since it is the special case of general stability under the 0/∞ distance. However, exact-stability values are usually much smaller than the corresponding distance-sensitive scores because every non-identical ranking 11
acceptability indices measuring how often an alternative attains a given rank. In contrast, our object is a reported ranking as a whole. General stability evaluates the full ranking region and compares complete induced rankings through a user-defined ranking distance, distinguishing minor changes from changes that alter the substantive conclusion. Ranking is also central in data mining. Ranking items with multiple attributes for downstream applications has motivated work on ranking [1, 18, 29], top-k [27, 30], and skyline queries [6, 12, 41, 45]. Some work on ranking and top-k focuses on uncertainty, missing values, and noise in the dataset [8, 19, 36]. In contrast, ranking stability focuses on uncertainty in the scoring functions related to user preferences. Some recent studies also apply fairness and diversity constraints to rankings [4, 15, 44, 46, 52]. For example, given a ranking weight vector, [4] seeks a similar vector with fairer results. These investigations align with our goal of supporting more responsible rankings. As the motivation for stability originated from detecting cherrypicked models, data perturbations have also been used to identify cherry-picked trendlines [5, 7] and generalizations [37]. Our Conv-SC algorithm draws motivation from advances in computing convex-body volumes and from the hit-and-run method. Convex-body volume computation is an important problem in computational geometry; state-of-the-art works include [31, 40]. Hitand-run sampling is also widely studied, with applications in volume computation and other domains [2, 11, 20, 43]; [38, 39] provided key theoretical insights on its efficiency. For geometric concepts such as half-space, see [24].
Generated Random-Trial Median Runtime 1e+07s Conv-SC
GSC_md
Measured
Estimated
1e+06s 100000s
Runtime (log scale)
10000s 1000s 100s 10s 1s 0.1s 0.01s
Synthetic n=20
Synthetic n=30
2
Synthetic n=40
3
4
5
6
Dimension d
Figure 3: Generated-data runtime scaling under the 0/∞ distance. Each point is the median over five generated tables and random positive target weights for 𝑛 = 20, 30, 40. Conv-SC shows polynomial runtime scaling with dimension, while 𝐺𝑆𝐶𝑚𝑑 grows rapidly as 𝑑 increases. Real data: Conv-SC vs GSC_md 1e+13s Conv-SC
1e+12s
GSC_md
Measured
Estimated
1e+11s 1e+10s
Runtime (log scale)
1e+09s 1e+08s 1e+07s 1e+06s 100000s 10000s 1000s 100s 10s 1s 0.1s 0.01s 2
MPI top 30
3
4
MPI top 50
5
6 MPI top 100
7
8
9
10
Dimension d
9
Figure 4: Real-data column-prefix runtime scaling under the 0/∞ distance. We use the first 𝑑 MPI indicators for the top 30, 50, 100 items.
We introduced general stability, a distance-based extension of exact ranking stability that gives partial credit to rankings close to the target while recovering exact stability as a special case. We developed exact two-dimensional and sampling-based multidimensional algorithms, analyzed why fixed-error sampling can become expensive in rare-event regimes, and identified quasiconvex distance functions as a structured class where Conv-SC reduces stability computation to convex-volume approximation. Experiments on real and generated data show that distance-sensitive stability can avoid overreacting to minor ranking changes, while Conv-SC exploits convex structure to make stability computation feasible for quasiconvex distances in high dimensions. Overall, general stability offers a flexible framework for evaluating the robustness of reported rankings while letting users specify which ranking changes matter in their application.
increasingly depends on the runtime estimates justified above as the ranked set grows from top 30 to top 100.
8
CONCLUSION
RELATED WORKS
Our work can be viewed as an extension of [3], which investigates the stability of rankings defined by various acceptable scoring methods. More recently, [14] proposed a complementary notion of local stability for rankings. Their work studies how perturbing the data values of a single tuple can change that tuple’s position, and uses dense regions to tolerate swaps among items with similar quality. In contrast, our work keeps the dataset fixed and studies uncertainty in the scoring weights; general stability remains a global rankingregion measure, but uses ranking distances so that similar rankings can contribute differently from completely different rankings. Our setting is also related to multi-criteria decision making and multi-criteria decision analysis (MCDM/MCDA), where alternatives are evaluated using multiple criteria and criteria weights support choices, recommendations, or rankings [10, 28, 32]. Robustness methods such as stochastic multicriteria acceptability analysis (SMAA) explore the weight space under uncertain or incomplete preference information [34, 35, 47]. These methods are typically decision- or alternative-centered: for example, SMAA reports rank 12
REFERENCES
[28] José Figueira, Salvatore Greco, and Matthias Ehrgott (Eds.). 2005. Multiple Criteria Decision Analysis: State of the Art Surveys. Springer. [29] Floris Geerts, Heikki Mannila, and Evimaria Terzi. 2004. Relational link-based ranking. [30] Ihab F Ilyas, George Beskales, and Mohamed A Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Computing Surveys (CSUR) 40, 4 (2008), 1–58. [31] Ravi Kannan, László Lovász, and Miklós Simonovits. 1997. Random walks and an o*(n5) volume algorithm for convex bodies. Random Structures & Algorithms 11, 1 (1997), 1–50. [32] Ralph L. Keeney and Howard Raiffa. 1976. Decisions with Multiple Objectives: Preferences and Value Tradeoffs. Wiley. [33] Ravi Kumar and Sergei Vassilvitskii. 2010. Generalized distances between rankings. In Proceedings of the 19th international conference on World wide web. 571– 580. [34] Risto Lahdelma, Joonas Hokkanen, and Pekka Salminen. 1998. SMAA: Stochastic Multiobjective Acceptability Analysis. European Journal of Operational Research 106, 1 (1998), 137–143. [35] Risto Lahdelma and Pekka Salminen. 2001. SMAA-2: Stochastic Multicriteria Acceptability Analysis for Group Decision Making. Operations Research 49, 3 (2001), 444–454. [36] Jian Li and Amol Deshpande. 2010. Ranking continuous probabilistic datasets. Proceedings of the VLDB Endowment 3, 1-2 (2010), 638–649. [37] Yin Lin, Brit Youngmann, Yuval Moskovitch, HV Jagadish, and Tova Milo. 2021. On detecting cherry-picked generalizations. Proceedings of the VLDB Endowment 15, 1 (2021), 59–71. [38] László Lovász. 1999. Hit-and-run mixes fast. Mathematical programming 86 (1999), 443–461. [39] László Lovász and Santosh Vempala. 2004. Hit-and-run from a corner. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. 310–314. [40] László Lovász and Santosh Vempala. 2006. Simulated annealing in convex bodies and an O*(n4) volume algorithm. J. Comput. System Sci. 72, 2 (2006), 392–417. [41] Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J Lipton, and Jun Xu. 2010. Regret-minimizing representative databases. Proceedings of the VLDB Endowment 3, 1-2 (2010), 1114–1124. [42] Quacquarelli Symonds. [n.d.]. QS World University Rankings. https://www. topuniversities.com/world-university-rankings [43] Robert L Smith. 1996. The hit-and-run sampler: a globally reaching Markov chain sampler for generating arbitrary multivariate distributions. In Proceedings of the 28th conference on Winter simulation. 260–264. [44] Julia Stoyanovich, Bill Howe, and Hosagrahar Visvesvaraya Jagadish. 2020. Responsible data management. Proceedings of the VLDB Endowment 13, 12 (2020). [45] Julia Stoyanovich, William Mee, and Kenneth A Ross. 2010. Semantic ranking and result visualization for life sciences publications. In 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010). IEEE, 860–871. [46] Julia Stoyanovich, Ke Yang, and HV Jagadish. 2018. Online set selection with fairness and diversity constraints. In Proceedings of the EDBT Conference. [47] Tommi Tervonen and José Rui Figueira. 2008. A Survey on Stochastic Multicriteria Acceptability Analysis Methods. Journal of Multi-Criteria Decision Analysis 15, 1–2 (2008), 1–14. [48] Times Higher Education. [n.d.]. World University Rankings 2016. https://www. timeshighereducation.com/world-university-rankings/2016/world-ranking [49] United Nations Development Programme. [n.d.]. 2023 Global Multidimensional Poverty Index (MPI). https://hdr.undp.org/content/2023-globalmultidimensional-poverty-index-mpi#/indicies/MPI [50] Yale Center for Environmental Law and Policy. [n.d.]. 2024 Environmental Performance Index. https://epi.yale.edu/ [51] Zelda B. Zabinsky and Robert L. Smith. 2013. Hit-and-Run Methods. Springer US, Boston, MA, 721–729. https://doi.org/10.1007/978-1-4419-1153-7_1145 [52] Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yates. 2017. Fa* ir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 1569–1578.
[1] Rakesh Agrawal, Ralf Rantzau, and Evimaria Terzi. 2006. Context-sensitive ranking. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data. 383–394. [2] Hans C Andersen and Persi Diaconis. 2007. Hit and run as a unifying device. Journal de la societe francaise de statistique & revue de statistique appliquee 148, 4 (2007), 5–28. [3] Abolfazl Asudeh, HV Jagadish, Gerome Miklau, and Julia Stoyanovich. 2018. On obtaining stable rankings. Proceedings of the VLDB Endowment 12, 3 (2018), 237–250. [4] Abolfazl Asudeh, HV Jagadish, Julia Stoyanovich, and Gautam Das. 2019. Designing fair ranking schemes. In Proceedings of the 2019 international conference on management of data. 1259–1276. [5] Abolfazl Asudeh, Hosagrahar Visvesvaraya Jagadish, You Wu, and Cong Yu. 2020. On detecting cherry-picked trendlines. Proceedings of the VLDB Endowment 13, 6 (2020), 939–952. [6] Abolfazl Asudeh, Azade Nazi, Nan Zhang, and Gautam Das. 2017. Efficient computation of regret-ratio minimizing set: A compact maxima representative. In Proceedings of the 2017 ACM International Conference on Management of Data. 821–834. [7] Abolfazl Asudeh, You Will Wu, Cong Yu, and HV Jagadish. 2021. Perturbationbased Detection and Resolution of Cherry-picking. A Quarterly bulletin of the Computer Society of the IEEE Technical Committee on Data Engineering 45, 3 (2021). [8] Abolfazl Asudeh, Gensheng Zhang, Naeemul Hassan, Chengkai Li, and Gergely V Zaruba. 2015. Crowdsourcing pareto-optimal object finding by pairwise comparisons. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. 753–762. [9] Basketball Reference. [n.d.]. 2023–24 NBA Player Stats. https://www.basketballreference.com/leagues/NBA_2024_per_game.html [10] Valerie Belton and Theodor J. Stewart. 2002. Multiple Criteria Decision Analysis: An Integrated Approach. Springer. [11] Dimitris Bertsimas and Santosh Vempala. 2004. Solving convex programs by random walks. Journal of the ACM (JACM) 51, 4 (2004), 540–556. [12] Stephan Borzsony, Donald Kossmann, and Konrad Stocker. 2001. The skyline operator. In Proceedings 17th international conference on data engineering. IEEE, 421–430. [13] Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. [14] Felix S. Campbell and Yuval Moskovitch. 2026. Local Stability of Rankings. Proceedings of the ACM on Management of Data (2026). https://doi.org/10.1145/ 3802081 [15] L Elisa Celis, Damian Straszak, and Nisheeth K Vishnoi. 2018. Ranking with fairness constraints. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 107. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 28:1–28:15. https://doi.org/10.4230/LIPIcs.ICALP.2018.28 [16] Center for World University Rankings. [n.d.]. World University Rankings 2015. https://cwur.org/2015.php [17] Apostolos Chalkis, Vissarion Fisikopoulos, Marios Papachristou, and Elias Tsigaridas. 2025. volesti: A C++ library for sampling and volume computation on convex bodies. Journal of Open Source Software 10, 108 (2025), 7886. https://doi.org/10.21105/joss.07886 [18] Surajit Chaudhuri and Gautam Das. 2009. Keyword querying and ranking in databases. Proceedings of the VLDB Endowment 2, 2 (2009), 1658–1659. [19] Surajit Chaudhuri, Gautam Das, Vagelis Hristidis, and Gerhard Weikum. 2004. Probabilistic ranking of database query results. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30. 888–899. [20] Ming-Hui Chen and Bruce W Schmeiser. 1996. General hit-and-run Monte Carlo sampling for evaluating multidimensional integrals. Operations Research Letters 19, 4 (1996), 161–169. [21] Thomas M. Cover. 1967. The number of linearly inducible orderings of points in d-space. SIAM J. Appl. Math. 15, 2 (1967), 434–439. [22] CSMetrics. 2016. CSMetrics. CSMetrics. https://csmetrics.org [23] CSRankings. [n.d.]. CSRankings: Computer Science Rankings. https://csrankings. org/ [24] Mark De Berg. 2000. Computational geometry: algorithms and applications. Springer Science & Business Media. [25] Martin Dyer, Alan Frieze, and Ravi Kannan. 1991. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38, 1 (1991), 1–17. [26] Martin E. Dyer and Alan M. Frieze. 1988. On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17, 5 (1988), 967–974. [27] Ronald Fagin, Amnon Lotem, and Moni Naor. 2001. Optimal aggregation algorithms for middleware. In Proceedings of the twentieth ACM SIGMOD-SIGACTSIGART symposium on Principles of database systems. 102–113.
13