Active Ranking without Strong Stochastic Transitivity
Authors: Hao Lou
Tao Jin
Yue Wu
Pan Xu
Quanquan Gu
Farzad Farnoud
Venue: NeurIPS 2022 Accept (2022)
Keywords: ranking
noisy comparison
WST
SST
sample complexity

Abstract: Ranking from noisy comparisons is of great practical interest in machine learning. In this paper, we consider the problem of recovering the exact full ranking for a list of items under ranking models that do *not* assume the Strong Stochastic Transitivity property. We propose a $$\delta$$-correct algorithm, Probe-Rank, that actively learns the ranking of the items from noisy pairwise comparisons. We prove a sample complexity upper bound for Probe-Rank, which only depends on the preference probabilities between items that are adjacent in the true ranking. This improves upon existing sample complexity results that depend on the preference probabilities for all pairs of items. Probe-Rank thus outperforms existing methods over a large collection of instances that do not satisfy Strong Stochastic Transitivity. 
Thorough numerical experiments in various settings are conducted, demonstrating that Probe-Rank is significantly more sample-efficient than the state-of-the-art active ranking method.

Active Ranking without Strong Stochastic Transitivity
Hao Lou
Tao Jin
Dept. of Electrical Computer Engineering University of Virginia Charlottesvilll, VA 22903 haolou@virginia.cd
Department of Computer Science University of Virginia Charlottesville, VA 22903 taoj@virginia, edu
Yue Wu
Pan Xu
Department Computer Science University of California, Los Angeles Los Angeles, CA 90095 ywuêca www.ca.ucla.ce. ucla.
Dept. of Biostatistics & Bioinformatics
Duke University
Durham, NC 27705
pan. xu@dkuu edu
Quanquan Gu
Farzad Farnoud
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095 qguêcs ucla.edu
Dept. of Electrical & Computer Engineering
University of Virginia Charlottesville, VA 22903 farzad@virginia. edu
Abstract
Ranking from noisy comparisons is of great practical interest in machine learning. this paper, we consider the problem recovering the exact full ranking for list of items under ranking models that do not assume the Strong Stochastic Transitivity property. We propose d-correct algorithm, Probe-Rank, that actively learns the ranking from noisy pairwise comparisons. We prove sample complexity upper bound for Probe-Rank, which only depends on the preference probabilities between items that are adjacent in the true ranking. This improves upon existing sample complexity results that depend on preference probabilities for all pairs of items. Grobe-Rank thus outperforms existing methods that do not satisfy Strong Stochastic Transitivity. Thorough numerical experiments in various settings conducted, demonstrating that Moobe-Rank is significantly more sample-efficient than the state-of-the-an active ranking method.
large collection of instances
Introduction
Ranking from noisy comparisons has wide range of applications including voting 5 7 identifying winner/full ranking of teams in sport leagues, ranking players in online gaming systems (17),
crowdsourcing services (6), web search [ and recommendation systems 2
23
In practice,
comparisons usually contain certain levels of "noise". For example, duels a game are not always won by the more proficient player, and preferences between movies/restaurants different individuals. The presence of noise is commonly studied using probabilistic comparison model 222 25), where item has certain probability win the comparison over another group of items.
also vary among
We are interested in estimating the total ranking. To guarantee that the ranking is consistent with the preference probabilities, it is often assumed [12
25 that if ranks higher than j. then i wins
"Co-corresponding Authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

comparison against j with probability Pt, > 2- This assumption is referred to as Weak Stochastic Transitivity (WST). It is clear that the closer pi.j is to 1.2 the more difficult it becomes to compare i and j. A more strict assumption, Strong Stochastic Transitivity (SST), is also often made 10 24 26 SST requires items that have closer ranks to be more difficult to compare, i.e., if i
k, then
Pi.k 2 max (pt.j. Pj..)) > 2. Formal definitions of WST and SST are stated in Section 2
However, SST can be too strong in many scenarios. For instance, in sports, match outcomes are usually affected by team tactics. Team may play tactic that counters team i, resulting in a higher winning rate against team i compared with team j. Furthermore, items usually have multidimensional features and people may compare different pairs based on different features. close pair in the overall ranking is thus not necessarily harder to compare than pair that has a large gap. For example, when comparing cars, people might compare a given pair based on their interior design and another pair based performance. As another example, in experiment with games of chance with different probabilities of winning and payoffs (30), it was observed that "people chose between adjacent gambles according the payoff and between the more extreme gambles according probability, or expected value."
Motivated by such applications, in this paper, we study the problem of recovering the full ranking of n items under more general setting, where only WST holds, while SST is not assumed to hold. We focus on only pairwise queries as they are easier to obtain and less prone to error in practice. Furthermore, as many applications [6] [22 allow interactions between users/annotators, we consider comparisons collected in adaptive manner. Our goal is to use few comparisons possible and
achieve a high confidence.
Existing algorithms 121 25 cannot avoid comparing every item i with the item i" that is the most similar to i, i.e. |p...-
min { Pt., - }. Further, [25] pointed out that comparing item pairs that are adjacent in the true ranking are necessary. When SST holds, adjacent pairs are also the most difficult pairs distinguish, existing methods thus achieve sample-efficiency. For example, the Iterative- Snneiive-Ineettion--i -nnerttion-Rninngg (IIR) algorithm proposed in (25) maintains a preference tree and performs ranking by inserting items one after another. During the insertion process, every item possible to be compared with every other item (and thus the most similar one), depending on the relative order of insertion and the true ranking. Under SST, IIR was shown to enjoy the optimal sample complexity with mild conditions.
However, when SST does not hold, comparing nonadjacent items harms the performance. Consider an extreme scenario where the true ranking is 1 > 2 > 3 and P1.2 = P2.3 = 0.8, P1.3 = 2 2 If item 1 is directly compared to item 3, then it can take θ (2a0) queries] For instance, in IIR. this can happen during the insertion process of item when item happens to be the root of the preference tree. A simple fix exists as we can let the three pairs be compared simultaneously. The comparisons between items I and 2, items 2 and 3 will terminate much earlier and provide us with the accurate enough information 1 > 2, 2 3, which is sufficient recover the total ranking. Therefore, it is important to devise an algorithm whose sample complexity will not be harmed when SST fails to hold.
Contribution. In this paper, we propose an active algorithm, termed Probe-Rank, that ranks n items based on pairwise comparisons. Probe-Rank is maxing-based algorithm, i.e., it ranks items by performing n - steps of maxing. We show that as long as the WST condition satisfied, with probability least 1 ō, Probe-Rank returns the correct ranking after conducting at most
72
o
A
(log log (Ar*) log (n/6))
[P.j 1 Probe- Rank is the first algorithm whose sample complexity only depends on comparison probabilities of adjacent items instead of all pairs of items [21 25 29 B1). Theoretical analyses and numerical experiments under various settings are provided and show that Probe-Rank is more efficient than the state-of-the-art methods when comparing nonadjacent items is more difficult than comparing adjacent items. We also present preliminary analysis on the sample complexity lower bound in the worst case scenario when SST
comparisons, where A minjaj and i are adjacent
we need θ ((p.) - 122 comparisons to be confident enough about the order between any two items and j .i. [n].
'In fact, according to [3

---

does not hold. Further, we present a variant of Frobe-Rank, named Goobe-Rank-SDe in Appendix B Numerical experiments show that the variant is more sample-efficient under various settings.
2 Preliminaries
Notation Without loss of generality, let [n] = 11,2....,, denote the set of n items. We write p ~ Uni(a, b) to denote that p sampled uniformly at random from the interval (a. b). and use Ber(p) to denote a Bernoulli random variable which equals 1 with probability p. We use (i. to denote the unordered item pair, i.e. (i.j) = (j. Comparisons between items are probabilistic. Whenever two items i,j are compared, (respectively, j) is preferred with probability Pt.j (respectively, Pj.i). independent of any other quantities. For all + j. Pi.j + Pj. = 1. probabilistic comparison model over [ri] is thus defined by the set of probabilities P = [Pi.. (Pi.jhieee isijjsn
In this paper, asymptotic notation including (()), (-)) are defined in the standard sense, with O(),, (()), (.)) denoting corresponding weaker forms by allowing logarithmic factors.
Problem setup We assume that there exists a total ordering '>" over [m]] such that 01 > 02 > on for some permutation (........ Tn) of [n]. The permutation is referred to as the true ranking. Two items are called adjacent they are adjacent a, i.e., one ranks right next to the other. also assume that has higher
To ensure that the true ranking is consistent with comparisons, rank than j if and only if Pa.j > 3. In other words, if an item i is more preferred than j in a, then i has better chance win the comparison with j. This assumption is known as Weak Stochastic Transitivity (WST). more strict assumption, Strong Stochastic Transitivity (SST), is also frequently adopted. In addition to WST, SST assumes that whenever > j k: Pi,k 2 max (Pi.j- P5.x). In this paper, we assume only WST and our goal is to recover the true ranking with a given confidence level by taking pairwise comparisons and minimize the sample complexity. Problem instances are uniquely determined by the permutation a representing the true ranking and the comparison probabilities P.
Definition (6-correct algorithm). An algorithm is said be d-correct for any input instance, with probability at least - 6, it returns a correct result in finite time.
is clear that the closer Pt.j is to 2, the more difficult it becomes to obtain the ordering between i and j. Therefore, the probability gap Aijj defined as Aij P.. - | provides a charac- terization of the ranking task difficulty and will be used a parameter for measuring sample complexities of algorithms. For instance, (25] lemma 12] shows that for any d-correct algorithm A, Ta[A]
lim sup -- -0 2[Jog log & +log 15 0, where [A[ is the expected number of samples taken by A two items with probability gap A. Further, for each item i, we define
A
min A..i ププ
(2)
the minimum probability gap between item and any other item j, and define
joj and are adjacent in A.g.
min
(3)
the minimum probability gap between i and its adjacent items in the true ranking. Note that A, S A by definition and the equality holds when SST is satisfied.
3 Related work
The problem of ranking under coherent probabilistic comparisons dates back to 1994 14. Feige et al. [14] studied the comparison model assuming that i > j + Pi.j = 1 + A for some known A. It was shown that any 5-correct algorithm finds the true ranking with at least O(nA log (n/ (n/))) comparisons in the worst case. Later in (21). a 8-correct algorithm TOP was proposed to rank the top-k elements by assuming only the existence of total ranking (WST). The state-of-the-art IIR algorithm was proposed in 25), as discussed in Section comparison of related algorithms are presented in Table
3

---

Table I: d-correct algorithms for exact ranking with sample complexity guarantee. Definitions of
j. A, A can be found in Section 2
Algorithm
Assumptions P
Sample complexity
Single Elimination
WST
O
nellog n) (1/))
Tournament [21
mini giessn A7,
PLPAC-AMPR 29
The Plackett-Luce model
0
log m [ log 30, ))
Peraaive-Insertion Rankinn 25
WST
0
Σ
(loglog log a. + log
1=1 A?
Probe-Rank (this paper)
WST
0
Σ
(3,) (loglog b. log ;
1=1
Ranking maxing has also been widely studied under more strict assumptions, e.g. SST, RST and
ST and usually in the probably approximately correct (PAC) setting [10] II 12 24
26 27 29 32]
In particular, 124, 26, 27 [2] considered parametric comparison models such as the multinomial logit (MNL) model. Note that parametric models are often more restrictive and can imply SST/STI conditions. In the PAC setting, the goal is to find an e-ranking ri > T2 > >
In such that goes
Pri.s > 1
2 c for all i < Although e-rankings become closer to the true ranking to 0, pointed out by [25 that PAC ranking algorithms cannot be easily extended the case when e 0. Among all, 12 is the most relevant work to this paper. In [12], PAC ranking and maxing were studied for both SST and WST settings. For WST, an instance- -nneeeededdeeeeennt lower bound (n²²) was proved, and a brute-force algorithm which compares each pair to an accuracy of e and thus conducts ((n²² ) (n))) comparisons was proposed. Note that in this paper, we are aiming at recovering the exact ranking instead of an e-ranking. An exact ranking is preferred over an epsilon-ranking in competitive applications like voting and sport games, where people are not satisfied with approximate winner. Furthermore, suggested by (25), analyzing the exact ranking helps us to gain a better understanding about the instance-wise upper and lower bounds. A which
trivial extension of the frute-force algorithm can lead sample complexity Ö n² min; AT,/
is substantially worse than proposed algorithm.
Although we believe WST can be considered natural and reasonably weak assumption, there are situations that WST does not hold as a ranking over items may not exist or, if it does, all comparison probabilities are not necessarily consistent with that ranking. So another line of research is to allow comparison probabilities Pt.j take any values in (0, as long Pt.j + Pj. = 1. In such scenarios, rankings can be defined and derived based on various criteria including Borda score [16 19 28 and Copeland score [4. 33 The ranking problem has also been studied from a heterogeneous perspective [8 31,, where queries are made by multiple agents with different comparison probabilities. In 115 the problem of testing whether the WST condition holds was studied. More broadly, the problems of ranking, maxing or selection can be formulated in the context of ducling bandits. A comprehensive survey can be found in [3].
4 Proposed algorithm
In this section, we propose ò-correct algorithm for exact ranking of all problem instances that satisfy the WST condition. As mentioned previously, our algorithm is designed to outperform existing methods in situations where nonadjacent items can be more difficult to compare than adjacent items.
To avoid spending unnecessary samples on item pairs with small probability gaps, we propose a subroutine named Successive- Comparriso (SC) (see Subroutine [T]. SC uses parameter for controlling to what extent the comparison should last. Specifically, SC compares a given item pair for fixed number by (2/²²) (2) log(1/5-)) times with an accuracy level e, 2-T and confidence level 8, 66/( 2 If the empirical probability that (respectively, j) wins over 1/2 by more
3 Under relaxed stochastic transitivity (RST), it assumed that for all i > j > k. A.. 2 7 max (Di, A for some 0 < < < 1. Under stochastic triangle inequality (STI), is assumed that for all > > A: ALA S D., + AjK.

---

than 2,/ then SC returns (respectively. j) as the more preferred item. Otherwise, SC will return "unsure' inform us that more samples are needed.
For two items and j. SC (,, 7) will be called successively with r increasing by at a time. We show in Appendix A that after gets large enough such that 6, Ai,j the correct ordering between i and j will be returned with high probability.
Subroutine Successive- Conpessiiie-ommmiiioooooo (i 6, r) (SC)
1: Input: items j. confidence level 6, probing parameter
5 2: 0, 2-,,,, Ör c77, _ by = 2/2 log +.
3: For t= to b do
4: compare and j once; if i wins, wt 1;
5: p; p /0:/b;:
6: return [. if D. eer return [J, if 1 eer and return 'unsure' else;
Partial order preserving graph During the ranking process, we maintain directed graph T to store the partial orders we have obtained from SC instances so far. The graph I'' is initialized with n nodes vi...., Vn and no edge exists between any two nodes. Nodes Vi, V2,..., Vn represent items respectively. In our algorithm, T' is involved with three types of operations, edge update, node removal and maximal set selection. Every time an instance of SC returns a pairwise order, e.g.. i > j. we add a directed edge from V3 to V,, written as T = TU > j). Moreover, we also complete all edges in the transitive closure of the existing edges. In other words, the edge between V/2 and Vj induces a directed path from Vs, to Veg. then a directed edge from VE, to Ví, is also added to T. By completing the transitive closure, we can avoid comparing pairs whose ordering can be inferred from current knowledge and keep T acyclic. In the ranking process, we only run comparisons on item pairs that are not connected by edges and hence no contradictions in orderings will be returned by SC. By removing node Vi, we remove Vi and all edges of Vi from T. The maximal elements of are the nodes which do not have any incoming edges. Since edges represent comparison results returned by SC, maximal elements correspond to items that have not lost to any other items. Note that since is acyclic, maximal elements always exist.
1, 2.
Next, we establish our ranking algorithm Probe-Rank (see Algorithm 2) Probe-Rank finds the true ranking by performing maxing for n rounds. In every round I,, subroutine Probe-Max returns an item in St as the most preferred item (the maximum), where S, denotes the set of remaining unranked items right before round t. The strategy of Probe-Max
repeatedly apply SC on all item pairs. For every item pair (), we initialize global variable Ti.j as the probing parameter for SC instances that run over i.j. The graph 7 storing obtained partial orders is also viewed as a global variable. Parameters Tú, and graph 7 will be accessed and altered in Probe-Max.
Algorithm 2 Probe-Rank
Input: items [n]. confidence level ò
2: S [n]. Ans [0]". initialize T, Ti.j = 1 for all pairs of items + to n do
3: For
4: imas = Probe-Max(S 25/n²)
5: remove imaz from T; Ans(t 1] mani Se11 = Sz \ fmmat:
6: Ans(n 1] S, [0]: return Ans;
In Probe-Max(S, 5) (see Subroutine 3.. SC instances are performed only on items that are possible to be the actual maximum. Let U be the set of maximal elements in T. By definition, every item in U has not lost to any other item in S yet. Assuming all previous comparison results (obtained form SC) correct, to find the actual maximum, it suffices focus on items in U. We use S2 to denote the set of all unordered item pairs in S, i.e., 52 = {(a, b) a, b E S, a * b). All 'legitimate" pairs that can potentially provide with information about the maximum item in S are thus
P = {i.,)) (i E U or E U), (i.j) E S (i..) & T}.
(4)
where (i,j) & T means that nodes V; and V, are not connected in While U contains more than one items, Probe-Max keeps applying SC on item pairs in P. If item in V loses comparison, then
5

---

we remove it from U. In every iteration of the while loop, the pairs (i':j") in P with the smallest value are chosen and SC (i", jJ" 5", Tr+;"" 5-) are performed. Note that the T value increases by one after each call of SC. Starting with item pairs with small values guarantees that we do not miss any useful information that can obtained by paying only small amount of comparisons.
Subroutine Probe-Max(S,6)
1: Input: set unranked items S, SC confidence level 5
2: Let U be the set of maximal elements according to T;
3: While [0] > do
4: Let P = {(t,j)= (i E UUrrje j U), (1,5) E S², (1, TT;
5:
For (a, b) in argmin argmin (a.))EPT.. do
6: Ans = SC (a, b, 6, Ta,b); Ta,b Ta.b + 1;
7: If Ans is not 'unsure' then
8:
w. 1 = Ans; T = TU (w 1); If UU > 1 and I E U then U =U) (7}
9:
return O0;
We provide simple example demonstrating the ranking process.
Example 1. Consider items 2,3,3,4 4} with true ranking 1 > 2 3 > 4. Figure shows the status of T, U, Sy throughout the ranking process. particular, we assume the pairwise comparison results are all correct and returned in order > 2, > 4, 1 3, 2 > 3, 3 > 4.
2
4
3
making 2,,2,3,4) 4). 8t-
retumed.
returnad.
{1).
[1,3, 4).
[1,3].
2
3
(2).
(
returned.
[2,3, 3,4, (2,3).
8a
[3, 4),
(3).
43.
Figure 1: An illustration of the steps by Probe- Ranking, assuming true ranking as 1 > 2 > 3 4.
Upper bound on the sample complexity of Probe-Rank
In this section, provide sample complexity upper bound for the proposed algorithm Probe-Rank.
Theorem 2. Let 8 0 be an arbitrary constant. For all problem instances satisfying the Weak Stochastic Transitivity (WST) property, with probability at least 1 - 8, Probe-Ran returns the true ranking of items and conducts at most
0
(log log (A: + log ))))
A
(5)
1=1
comparisons, where A is defined as in 3
The proof of Theorem 2 deferred to Appendix A

---

By the preceding theorem, the sample complexity of Probe-Rant is upper bounded by the sum of terms 3 log A.) + (og(m))) with additional multiplicative factor of n. Recall from Section 2 that the term (A,)- "(og log(A,)
log(n/))) can be viewed as lower bound on the number of comparisons that is needed for obtaining the order between and its adjacent items with confidence level 8/n. Theorem thus suggests that in Probe-Rank, every item is compared until can be distinguished from its neighbors and no further. This matches with our intuition that only comparisons between adjacent items are necessary, and single nonadjacent pair being extremely hard to distinguish should not harm the overall sample complexity. In contrast, sample complexities of existing algorithms are determined by the smallest probability gap between items, which can lead to substantially large amount of unnecessary comparisons.
However, Probe-Rank achieves the dependence on A; instead of A; at the cost of an additional multiplicative factor of n. Intuitively, because we have zero prior information about which items are adjacent and which are not, Probe-Rank pays θ (n) attempts for each item i in order to 'identify" its neighbors and get the ordering feedback.
We compare Probe-Rank with the state-of-the-art IIR algorithm. Let C (Probe) and C (IIR) denote the sample complexities of two algorithms. From Table T and Theorem 2
(Probe) = Σ e (n((.))
C ( = Σ ((A.))
(6)
i=1
i=1
noting that from the proofs, the sample complexity upper bounds are both tight in the worst case.
Under WST with no other conditions assumed, A, S A. In particular, when Á. = ((yr) i, then C (Probe) and C (IR)) are of the same asymptotic order with respect to if A, A. w(V)) then Probe- Rank is asymptotically more sample-efficient than IIR. These phenomena are also reflected in our numerical experiments in Section (see Figure 3).
Remark. It is worth noting that IRR is optimal if the more strict assumption SST as well as some other conditions are made, as shown in (25). When SST holds, A A. Probe-Rank thus suffers from an additional factor of This case is also included in our numerical experiment (see Figure 2(a)p.
Experiments
In this section, we present numerical experiments demonstrating the practical performance of Probe- Rank. We compare Probe- Rank with the IIR algorithm, which was shown to outperform all the other baseline algorithms both theoretically and numerically [25). Our implementation can be found on Github 5
We study different settings where SST is satisfied, not guaranteed, or violated, but WST always holds, which is consistent with our theory. Specifically, we want rank n items with the true ranking 01 > 02 > ..... > on, where n varies over [10, 100). The probabilistic comparison model Psy is generated in different ways to satisfy different assumptions. Note that A and Aa are tuning parameters in all the following settings.
SST: SST is satisfied. Comparison probabilities Pij generated from the MNL model, where Po..ay = (exp(sa, $o,) 1)- and 801 "o.....,88 So,, decreasing sequence where so; 1004 (n+1-1)
WST: SST does not necessarily hold, Let Pt, Uni(} + Ad, 1) for all items i > j. NON-SST: SST does not hold. For adjacent items, we have Po..ti: Uni (1 Ad, 1). Otherwise, Aa
we have Po..,, Uné (2 + 10 2 Ad) for > i i+1 1.
ADJ-ASYM: SST does not hold. This setting is used to verify the asymptotic analysis in Section 5
For adjacent items, we set Po.,o111 = 1 + Ag- Otherwise, we set Po;.;;
= 1/ + A for j > i +
We consider cases where a equals 0.5 or
ADJ-CNST: SST does not hold. For adjacent items, we set Po,,0011 1 + A. Otherwise Po..;; =
3 + A for i 1. Here A A
7

---

Sample com complexity
10
Sample plexiity
Sample complexxity
10%:
10*
10%
100
104
IIR
10*
IIR
10
IIR
Rank
Probe-Ras
Prote Rank
25
50
75
100
25
50
75
100
25
50
75
100
Number
rank
Number of
Number of to rank
(a) SST: A. 0.3
(b) WST: Aa 0.3
NON-SST: Aa 0.3
Figure 2: Comparison of sample complexities of Probe-Rank and IIR under various settings. each subfigure. Aa is fixed while the number of items varies.
All experiments are averaged over 100 independent trials. For each trial, the ground truth ranking generated uni- formly random and the comparison probabilities are assigned accordingly. The confidence level ó is fixed to be 0.1. Throughout the experiment, every trial for every algorithm successfully recov- ered the correct ranking.
Sample complexity coiittyy
10P
Sample complexity
10"
10'
10a
10P
IIR
II
Probe Rank
Probe Rank
25
50
75
100
25
50
75
100
Number
Number of
(a) ADI-ASYM: A,
0.3, a
(b) ASYM: A, = 0.3, 0.5
We use internal clusters of intel "Sky- lake" generation CPUs. Each job con- tains a single model type for item num- bers ranging from 10 100 with step size of 10. Models are generated from a job unique random seed shared among the two algorithms. Most jobt with sample complexity smaller than 10" terminate in 3 minutes. For A. = 0.1 under the ADJ-ASYM model, hours are needed due to high sample complexity. Due to the space limit, more detailed experimental setups and thorough ablation studies can be found in Appendix(C
Figure 3: Relationship between n and gap Aa
Performance comparison Figure with y-axis in log- shows comparison of IIR and Probe- Ranking under the SST, WST and NON SST settings. The parameter As is set to be 0.3. It can seen that under the SST and WST settings (Figures ((a) 2(b),, Probe-Rank. consumes less samples than IIR for small n. As n gets larger, however, IIR becomes more sample-efficie
due to that Probe-Rese Rank has additional factor of in its sample complexity compared with IIR for instances satisfy SST. However, under the NON-SST setting where SST does not hold, Probe-Rank has a clear advantage
IIR, as shown in Figure 2(c)
Dependence on n and the probability gaps Following Theorem 2
we verify that the sample complexity of Probe-Rank lower than IIR when the number of items gets larger. We use the
ADJ-ASYM setting to simulate situations where nonadjacent items can be much more difficult to compare. In particu- lar, choose
10P
Sample complexity
IIR
Sample complexity
II Probe-Rank
(see Figure 3(a)
Probe-Rank
107
and a = 1/2 (see Figure 3(b)). It
107
can be the number of items n gets larger, the
from Figure 3(a) that
10
gap between the two curves also gets larger. This matches our analysis that when Á./,, = w(vn), then the sam- ple complexity of IR is of higher or- der than that of Probe-Rande
0.0
0.2
0.4
A4
A4
(a) NON-SST: n
ADI-CNST:
80,
When A, = (V)), Figure 3(b) shows that the gap between the two sample complexities varies little as n increases.
Figure 4: Ablation study the dependence of the sample complexity on the probability gap Ag.
Our analysis also suggests that sample complexities of two algorithms of the same order.

---

Furthermore, we show through the NON-SST and ADJ-CNSS settings that when the probability gaps of nonadjacent item pairs decrease, the advantage our algorithm will be more and more prominent.
In Figure 4 we fix n = 80 and let Ad vary. Clearly, Probe-Rank has an advantage over IR in both settings. In particular, Figure 4(b) shows the comparison of two algorithms in the ADJ-CNST setting with the probability gaps between adjacent items A fixed as 0.4. As the probability gap between nonadjacent items As varies from 0.01 0.4, it can be seen that the sample complexity of Probe-Rank does not vary much. However, the sample complexity of IIR has a positive correlation with 27 This numerical result matches our analysis that
is not affected by the comparison probability of nonadjacent items, which does not hold for IIR.
7 Discussion on the lower bound
In this section, we provide some insights about the lower bound for pairwise ranking by proposing a conjecture based particularly hard instance Sw that satisfies the WST condition.
Problem 1 (ZWST). The problem instance Iw ST is constructed as follows. Consider n items with an underlying ordering ">-" For all i j.
2 + A, if and j are adjacent,
P.j
2
+
10 A2 (og()/6), otherwise,
where and A are constants and n can be replaced by any other quantity that is smaller than n -2
By a reduction, any 8-correct algorithm that finds the maximum item for Iw can be constructed to find the maximum item for IyNa, described below in Problem 2
Therefore, lower bound on 2 will imply a lower bound of the same order for
the sample complexity for maxing Problem the maxing (and thus, ranking) problem for ST- ST- This lower bound is also worst-case lower bound for ranking under WST. In the following, we provide an analysis for Problem The reduction technique will be deferred to Appendix
Problem 2 (ISNG). Consider items with an underlying ordering ">'. One can make queries of the form 'if 1 > j" The feedback Y., binary random variable which takes value 1 the answer YES and takes value otherwise. The random variables Yi, are defined to follow distributions:
Ber( 1 - 2A), if j and i are adjacent, Ber ( otherwise.
Y1,5
Consider random vectors defined by P: = (Yr,1, Y. Yi,)) in Problem 2 The maximum element corresponds to the random vector p.-. where each entry is 1 1/2-Bernoull random variable. For every other non-maximum element i, P: will contain exactly one (1/2 2 random variable. Under such problem setting, finding the maximum item is equivalent to finding which vector has all its entries as 1/2- Berrnoollli random variables.
We conjecture that any 8-correct algorithm that can find the maximum item for IsNG has sample complexity at least
2(n² 2 A log(1/6)).
We start from viewing it as a hypothesis testing problem. Consider that an agent is asked to determine if t1 satisfies hypothesis Ho, defined
Ho Pı (PI.1.... .I,n), where PI,k Ber(1/2), Vk E [n].
or Hy. in which the j-th entry is biased:
Hj :p:p1- = (PI.I. PI.n), where Pı.j ~ Ber(1/2 -2/) PI, Ber(L/2), Vk $
Suppose the hypothesis testing algorithm A is 8-correct and stops within T rounds of interactions. We denote A(T) as the output the 7-th round, which is either (accept Ho) 1 (reject Ho). For any given j # 1, by the Bretagnolle-Hute inequality, we have
28 2 (o(((T) + 0) + (A(T) = 0) 2 KL(Fd1115))
(8)

---

where Po is the probability measure under Ho, and Po is the probability measure of the canonical bandit model under Ho. fact, we have the divergence decomposition lemma 20
Lemma 15.1]:
KI((P) (T Eo (T) Ber) (1/2 2A)), (9)
where Eg denotes the expectation under Ho: (T)) denotes under Ho. the expected number of queries for the entry Pı. within 7 rounds.; o. J. are the Bernoulli distributions specified by PI.A under Ho, Hj, respectively. The second equality is due to the fact that the only difference between Hn and Hj is that the j-th entry has different Bernoulli distributions.
Combining the two incquality above gives:
Berr Ber(1/2 1 22)) 2 log(1/40) (1/46).
(10)
Since (I.(Ber(11))) (1)) (
< (4x)² for all x < 2/9, we get Eg N, = 92A -2 log(1/6)).
Thus, the total expected number of queries under Ho will be M(n log(1/6)).
In Problem there are in total vectors. We reasonably conjecture that to identify which vector satisfies Hg requires at least ((n)) attempts, with each attempt costs Q(n -2 =llog( i.e any 8-correct algorithm requires (2(n2 log(1 //))/ queries.
Conclusion and future work
In this paper, studied the problem of exact ranking under the most general assumption WST. We proposed a d-correct algorithm Prohe-Rank, and derived an instance-wise upper bound on its sample complexity. The upper bound shows that the performance of Probe-Rank only depend the comparison probabilities of adjacent items and thus improves existing results when SST does not hold. Numerical results also suggest that ranking algorithm outperforms state-of-the-art. A discussion over the lower bound for pairwise ranking is also provided. We propose a conjecture that in the worst case, any algorithm has sample complexity times the number of comparisons needed for comparing all adjacent items. However, it remains an open problem whether our conjecture holds and will be left to future work.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. HL. TJ and FF are supported part by the NSF grant 19F-1908544. YW and QG are supported in part by the NSF grant CIF-1911 168. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
10

---

References
[1] Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference Machine Learning, pages 356.864. PMLR, 2014.
[2] Linas Baltrunas, Tadas Makeinskas, and Francesco Ricci. Group recommendations with rank aggregation and collaborative filtering. In Proceedings of the fourth ACM conference on Recommender systems, pages 119-126, 2010.
[3] Viktor Bengs, Róbert Busa-Feketee Adil EI Mesaoudi- Pauul,, and Byke Hüllermeier. Preference- based online learning with dueling bandits: A survey. J. Mach. Learn. Res., 22:7-1, 2021.
[4] Róbert Busa-Fekete, Balazs Szorenyi, Weiwei Cheng, Paul Weng, and Eyke Hüllermeier. Top-k selection based adaptive sampling of noisy preferences. In International Conference Machine Learning, pages 1094- 1102. PMLR, 2013.
[5] Andrew Caplin and Barry Nalebuff. Aggregation and social choice: A mean voter theorem. Econometrica: Journal of the Econometric Sociery, pages 1-23, 1991.
[6] Xi Chen, Paul N Bennett, Kevyn Collins-Thompseee Thompson, and Eric Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the sixth ACM international conference on Web search and data mining, pages 193-202, 2013.
[7] Vincent Conitzer and Tuomas Sandholm. Communication complexity of common voting rules. In Proceedings of the 6th ACM conference on Electronic commerce, pages 78-87, 2005.
[8] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pages 613-622, 2001.
[9] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[10] Moein Falahatgar, Yi Hao, Alon Orlitsky, Venkatadheerai Pichapati, and Vaishakh Ravindraku- mar. Maxing and ranking with few assumptions. Advances in Neural Information Processing Systems, 30, 2017.
[11] Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Maximum selection and ranking under noisy comparisons. International Conference on Machine Learning, pages (088-1096. PMLR, 2017.
[12] Moein Falahatgar, Ayush Jain, Alon Orlitsky, Venkatadheeraj Pichapati, and Vaishakh Ravin- drakumar, The limits of maxing, ranking, and preference learning. In International conference on machine learning, pages 1427-1436. PMLR, 2018.
[13] Roger H Farrell. Asymptotic behavior of expected sample size in certain one sided tests. The Annals of Mathematical Statistics, pages 36-72, 1964.
[14] Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy informa- tion. SIAM Journal on Computing, 23(5): 1001-1018 1994.
[15] Björ Haddenhorst, Viktor Bengs, and Eyke Hüllermeier. On testing transitivity in online preference learning. Machine Leurning, 11008)20033-208 2021.
[16] Reinhard Heckel, Nihar Shah, Kannan Ramchandran, and Martin J Wainwright. Active ranking from pairwise comparisons and when parametric assumptions do not help. The Annals of Statistics, 4766):309--3126, 2019.
[17] Ralf Herbrich, Tom Minka, and Thore Graepel. Trueskill bayesian skill rating system. Advances in neural information processing systems, 19, 2006.
[18] Tao Jin, Pan Xu, Quanquan Gu, and Farzad Farnoud. Rank aggregation via heterogeneous thurstone preference models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
11

---

[19] Sumeet Katariya, Lalit Jain, Nandana Sengupta, James Evans, and Robert Nowak. Adaptive sampling for coarse ranking. International Conference on Artificial Intelligence and Statistics, pages 1839-1848. PMLR, 2018.
[20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[21] Soheil Mohajer, Changho Suh, and Adel Elmahdy. Active learning for top-k rank aggregation from noisy comparisons. International Conference on Machine Learning, pages 2488-2497
PMLR, 2017.
[22] Thomas Pfeiffer, Xi Alice Gao, Yiling Chen, Andrew Mao, and David G Rand. Adaptive polling for information aggregation. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012.
[23] Chris Piech, Jonathan Huang, Zhenghao Chen, Chuong Do, Andrew Ng. and Daphne Koller. Tuned models of peer assessment in moocs. arXiv preprint arXiv: 1307.2579 2013.
[24] Wenbo Ren, Jia Liu, and Ness B Shroff. Pac ranking from pairwise and listwise queries: Lower bounds and upper bounds. arXiv preprint
2018.
[25] Wenbo Ren, Jia Kevin Liu, and Ness Shroff. On sample complexity upper and lower bounds for exact ranking from noisy comparisons. Advances in Neural Information Processing Systems, 32, 2019.
[26] Aadirupa Saha and Aditya Gopalan. Active ranking with subset-wise preferences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3312-3321. PMLR, 2019.
[27] Aadirupa Saha and Aditya Gopalan. From pac to instance-optimal sample complexity in the plackett-luce model. In International Conference on Machine Learning, pages 8367-8376. PMLR, 2020.
[28] Nihar B Shah and Martin Wainwright. Simple, robust and optimal ranking from pairwise comparisons. The Journal of Machine Learning Research, 18(1):7246-283, 2017.
[29] Balázs Szörényi, Róbert Busa-Fekete, Adil Paul, and Eyke Hüllermeier. Online rank elicitation for plackett-luce: A ducling bandits approach. Advances in Neural Information Processing Systems, 28, 2015.
[30] Amos Tversky. Intransitivity of preferences. Psychological review, 76(1):31, 1969.
[31] Yue Wu, Tao Jin, Hao Lou, Pan Xu, Farzad Farnoud, and Quanquan Gu. Adaptive sampling for heterogeneous rank aggregation from noisy pairwise comparisons. In International Conference on Artificial Intelligence and Statisties, pages 11014-11036. PMLR, 2022.
[32] Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proceedings of the 28th international conference on machine learning (ICML-II), pages 241-248. Citeseer, 2011.
[33] Masrour Zoghi, Zohar S Karnin, Shimon Whiteson, and Maarten De Rijke. Copeland ducling bandits. Advances in neural information processing systems, 28, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We mentioned that the pro- posed algorithm has additional factor of compared with state-of-the-art. We also illustrated that the proposed lower bound is a conjecture.
(c) Did you discuss any potential negative societal impacts of your work? [No] We believe that our work will cause any negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space limitation,
a part of the proofs is deferred in Appendices ^ aand
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] The code and dataset link is provided in 6eo they under GPLv3 license.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We do not use
any existing assets. For algorithms, we implement our version of algorithms in cited resources. For dataset, it is generated purely by code.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "fnBJWO_TyrG", "reviewer": "Reviewer_xP6H", "summary": "This work designs an active ranking algorithm for WST. Authors also analyze the sample complexity and correctness of the algorithm. They propose conjecture on lower bound which if true implies the near optimality of their algorithm. They also provide numerical experiments contrasting their algorithm against SOTA algorithms under more restrictive settings and show pros and cons. ", "questions": "I think it might be better to present some examples where this algorithm is necessary and epsilon-ranking isn't sufficient.", "limitations": "Authors have adequately addressed the limitations", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe sample complexity analysis is quite unique and clever. They divide the complexity analysis into two parts and bound each part using simple arguments. This makes following the proof quite easy.\n\n\nWeakness:\nEven though motivation for WST is justified well, the authors didn't mention why one needs an ordering stronger than epsilon-ranking. \nTheir algorithm has complexity of O(n^2) which is essentially same as that of the trivial epsilon-ranking. Having said that it is important to establish bounds for exact ranking and hence I lean towards accepting the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JS1Lo-hsXFc", "reviewer": "Reviewer_5wme", "summary": "This paper proposes the Probe-Rank algorithm for exact ranking under the Weak Stochastic Transitivity assumption. For true tranking recovery problem, the proposed algorithm guarantees instance-wise upper bound on its sample complexity. This instance-wise upper bound only depends on the preference probabilities between items that are adjacent in the true ranking. This is an improvement upon existing sample complexity results that depends on the preference probabilities for all pairs of items. Experimental results show that the proposed Probe-Rank algorithm outperforms the IIR algorithm, which is state-of-the-art in the area. In addition, a constructive example is made to illustrate the advantage of the instance-wise bound in the worst case.", "questions": "In Line 148, what would be the impact if the Partial order-preserving graph is not implemented? \nIf the proposed algorithm is implemented without Partial order-preserving graph to guarantee the acyclic/transitive property, would it become a competing method with a different line of research that does not assume coherent ranking, i.e., methods derived from Borda score and Copeland score? \n\nIn some other research, techniques to resolve the conflicts in non-coherent ranking is a practical problem. It is not in the scope of this research I believe but an interesting direction to look at if the proposed method is examined with noisy and non-coherent pairwise comparison data, which unfortunately is the case for many real-world datasets.", "limitations": "Given the theoretical focus, there is limited evidence of how the algorithm works on real-world data. This is acceptable but still a limitation given the presentation and length of the content.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- the writing is punchy with clear contributions and highlights\n- the operational details are noted with clarity; giving readers strong confidence to reproduce the numerical results\n\nWeakness:\n- given the theoretical nature of the major contribution; the experiment focuses only on the verification of theoretical findings and lacks practical guidance on real-world data practices", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4uQVvSiR0kH", "reviewer": "Reviewer_XjGa", "summary": "The paper analyzes the problem to identify the underlying ranking in dueling bandits under the assumption that the underlying preference probabilities fulfill weak stochastic transitivity. \nThe authors introduce a novel algorithm that is able to solve the problem in a $\\delta$-PAC manner and comes with an instance-wise sample complexity guarantee that depends only on the gaps of those arms, which are adjacent according to the underlying ranking, and not on the other gaps. ", "questions": "- Thm. 1 in [3] shows that maxing (and thus in particular ranking) in an $(\\epsilon,\\delta)$-PAC manner under WST requires in the worst-case $\\Omega(n^{2})$ samples.  As their worst-case instance is similar to yours, you could potentially adapt their proof for proofing your conjecture. Did you try this?\n- Thm 2: From looking at its proof, it appears that you could slightly strengthen Thm.2 and provide a more detailed bound without O-notation, i.e., you could explicitly provide the constant that is hidden in the O-term. Maybe you could state this constant for the sake of completeness in the appendix?\n- Under SST $\\Delta_i = \\widetilde{\\Delta}_i$  holds. You also mentioned RST in Sec. 3, and [3] e.g. discuss moderate stochastic transitivity. Could you say how $\\Delta_i$ and $\\tilde{\\Delta}_i$ can differ under such transitivity assumptions? I.e., would Probe-Rank still be better than IIR in special cases under such assumptions?\n\n[3] M. Falahatgar et al., The Limits of Maxing, Ranking, and Preference Learning, ICML 2018.", "limitations": "There do not seem to be any potential negative societal impacts of this work. The limitations of their theoretical results have adequately been addressed by the authors.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The problem of ranking in dueling bandits is relevant for practical purposes and has already been studied in the literature. The algorithmic solution of the authors appears novel and apparently outperforms the current state-of-the-art methods in special cases, both empirically and in theory.\n2. The authors prove an interesting upper bound on the sample complexity for Ranking under WST: In contrast to existing ones, theirs depends only on the gaps between adjacent arms (according to the ranking) and not on all gaps. \n3. The paper is well-written, the presentation of the algorithm is easily understandable and well illustrated with an example. The theoretical results appear reasonable. I did not check all the proofs in full detail, but at first sight they seem to be correct.\n\nWeaknesses:\n1. In the appendix, the authors present with Probe-Rank-SE an improved variant of their algorithm, which they do not mention in the main paper. In my opinion, the authors should either focus on this variant or at least mention it in the main part.\n2. The authors only conjecture (and not prove) a lower bound that would show (log-)optimality of their result. Even though the authors discuss where this conjecture comes from, the final step still needs to be made. And I have my doubts that this final step is possible, as one would have to add up expected sample complexity lower bounds that are valid w.r.t. different instances. However, this might suffice as motivation for the conjecture.\n\nMinor Weaknesses and Typos:\n- 29: It should be ''$p_{i,k} \\geq \\max (p_{i,j},p_{j,k}) > 1/2$''.\n- 42: You say you focus on pairwise comparisons, and before you have already said that you focus on WST. As far as I know, WST is only defined for pairwise comparisons. Maybe you could reformulate this.\n- 115: and [] usually\n- 118: In [the] PAC settings\n- 140: the comparison should last\n- 2 in Alg.1: $b_{\\tau} = \\lceil ... \\rceil$? Then, adapt (13) apparantly.\n- 196: The lower bound of order $\\tilde{\\Delta}^{-2} \\log(n/\\delta)$ is not stated in Sec. 2, but only in footnote 1. Maybe, you could also mention it next to (2).\n- 210: Theorem 2 does not show tightness of its bound, it does not contain a lower bound result.\n- 217: addition[al] factor\n- 225: Why $\\Delta_{d}$, what does $d$ stand for?\n- 318: under[r]\n- 466: $\\Delta_{i,j}>\\epsilon_{\\tau}$\n- 579: that [] at least\n- 3 in Alg.5: SE italic\n- 612: (Problem 3 in the main paper) = (Probl. 1 in the appendix)\n- 617: Sometimes in this section, WST etc. in the index is italic, sometimes not.\n\nAdditional Remark:\n\nIn Sec.1 you mention that SST may be too strong in some scenarios and motivate this way the usage of WST. This naturally raises the question how strong the WST assumption itself is. \nApart from [1], which detected violations of the Condorcet winner assumption (i.e., in particular of the WST assumption) in real-world examples and thus focused on identification of Copeland winners, [2] recently discussed testing whether the WST assumption is fulfilled or not. The authors showed that WST testing requires $\\Omega(n^2 \\Delta^{-2} \\log (1/\\delta))$ samples and, interestingly, they proved an instance-wise lower bound for corresponding solutions that depends on $\\Omega(n^2)$ of the gaps and in particular not only on adjacent ones as your upper bound.\n\n[1] $:=$ [30] in your main paper\n\n[2] B. Haddenhorst et al., On testing transitivity in online preference learning. Machine Learning, 2021", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept