Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity

Dear reviewer thanks for your time and effort for the review and suggestions, we address your concern below:

Q1: Line 104–105, $\Delta := | p_{i,j} - \frac12 |$. Something may be missing here, e.g., min or sum.
A1: thanks for spotting this, the correct definition should be $\Delta := \min_{(i,j) \in [N] \times [N]} | p_{i,j} - \frac12 |$

Q2: Line 247, “After N-1 rounds of finding the maximal item…” Why are there N−1 rounds here? Does U contain N items?
A2: This sentence “After N-1 rounds of finding the maximal item…” actually refers to Algorithm 1, where it finds the current maximal item and deletes it. After $N-1$ rounds, the remaining item will be the minimum item out of the N items. We will move it to the correct place. We apologize for the confusion.
As for Algorithm 2, the candidate set $U$ has at most $N$ items. Every time a new pairwise relation is revealed, one of the two items cannot be the maximum item, so we remove it from $U$. After at most $N$ rounds, the maximum item will be found.

Q3: Assumption 3.1 seems strong, as it requires all oracles to have consistent ratings for all pairs of items. This assumption may not hold in practice—for example, when evaluating two LLMs, some users may favor one model over the other, while others may not. Is it possible to relax this assumption?
A3: It is possible to consider more general cases. Without a strict consistency guarantee, we need to define a ground-truth ranking using numerical indicators like win rate. For example, one may use the Copeland/Borda score to determine a ground-truth ranking when there is inconsistency among oracles.
Additionally, these methods typically involve examining all oracles with the same accuracy and then concluding with a majority voting, which usually leads to a less efficient algorithm (introducing an additional factor of $M$).

Q4: What are the logarithmic factors hidden in Theorem 5.4?
A4: $\log^2 (M) \log(H_i)$ is the hidden factor.

Dear reviewer, thanks for your positive comment. We address your question raised below:

Q1: ``medium'' in Algorithm 4 should be defined in the text.
A1: medium follows the definition in conventional statistics, where it’s the number(item) that is ranked in the middle of all numbers in the set of interest. We will add an explanation to the main text.

Q2: Assumptions 3.2 and 3.3 can be named as definitions.
A2: Thanks for pointing it out. Indeed, we can define the two settings first. We will modify them in our revision.

Q3: Page 3, Lines 138 -139: ``Iterative-Insertion-Ranking (IIR) [Ren et al., 2019] proposes an algorithm ...'' requires rewording.
A3: That’s a great catch, we would revise it into: Ren et al. propose the Iterative-Insertion-Ranking (IIR) algorithm that uses preference interval trees to perform binary search to sequentially insert items into an already ranked list.

Q4: The notations $H_i$,$H_{i,j}$ cause confusion (especially in the table and main contributions) since it is not defined until page 4, and I had to refer to the reference papers to determine their precise definition. Also, in Table 1, $\Delta_i$ is not defined, even in text (I believe).
A4: To improve the readability of the paper, we consider moving the “Preliminaries” section right after the “Introduction”, where $H$ can be defined a bit earlier. For $H$ we used in the ‘’Abstract’’ and ‘’Introduction’’ section, we revised the wording so that understanding it as a Hardness Factor is enough to proceed with reading. $\Delta_i$ is defined on the right column of line 174, based on the definition of $\Delta$.

Q5: The authors assume there is no ‘best’ oracle for all pairs of comparisons. If there is a single best oracle, does the algorithm quickly detect that oracle and is able to reduce the complexity that closely matches the single oracle case?
A5: That is right, if there is indeed a single best oracle, the algorithm can be slightly modified to only keep those decent oracles found in previous rounds, and eventually only one best oracle will be left to perform all of the rest pairs.
Line 96, right column, mentions an algorithm that maintains two sets of estimates globally: one for items and one for oracles (Wu et al., 2022). This paper studies exactly the setting you mentioned under SST, which can be easily extended to the WST setting as well. We will revise the original text to incorporate this.

Dear reviewer thanks for your time and effort for the review and suggestions, we address your concern below:

Q1: Since the proposed method is a combination of high-level ranking algorithm and a low-level oracle selection algorithm, it is possible to consider benchmarks based on existing methods given in Table 1, even if they are for the single-oracle setting.
A1: Thanks for the suggestion. The main difficulty in including more benchmarks is that most such benchmarks are offline datasets. There are no widely acknowledged benchmarks for online, interactive algorithms. This is the main reason why we use a synthetic environment with multiple oracles. Ren et al. also used a synthetic environment for the single-oracle setting.

Q2: I believe it can be simplified by separately describing building blocks. In my understanding, the proposed method is a combination of ranking estimation and oracle selection, and both of them can be independently combined with other methods.
A2: Thanks for your suggestion. You are correct that the algorithms can be broken down into two major pieces. We will revise and restructure the text to make it easier to read.

Dear reviewer, thanks for your positive comment. We address your question raised below:

Q1: Some assumptions might not hold in practical real-world applications. For instance, different people might rank different LLMs differently.
A1: It is possible to consider more general cases. Without a strict consistency guarantee, we need to define a ground-truth ranking using numerical indicators like win rate. For example, one may use the Copeland/Borda score to determine a ground-truth ranking when there is inconsistency among oracles. Additionally, these methods typically involve examining all oracles with the same accuracy and then concluding with a majority voting, which usually leads to a less efficient algorithm (introducing an additional factor of $M$).

Q2: In the bounds, the confidence term $\delta$ is missing. I guess they are in the log term. It might be good to present it to the readers to see how that affects the bound.
A2: We might omit some of the terms in the main text to reduce clutter for ease of reading. In Table 1, we included the log dependence on $\delta$.

Dear reviewer, thanks for your positive and constructive comments. We address your questions below:

Q1: The consistency assumption (Assumption 3.1) seems quite strong in practical settings. Have you considered a relaxed version where oracles can disagree on some small fraction of pairs? How would this affect your theoretical guarantees?
A1: Great suggestion! It is possible to generalize to a broader, more flexible case where oracles can disagree on a small group of pairs. However, without a strict consistency guarantee, we can only define an objective ranking using numerical indicators like win rate. For example, one may use the Copeland/Borda score to determine a ground-truth ranking when there is inconsistency among oracles. Additionally, these methods typically involve examining all oracles with the same accuracy and then concluding with a majority voting, which usually leads to a less efficient algorithm (introducing an additional factor of $M$).

Q2: Your RMO-SST algorithm achieves a log(N) factor improvement over prior work. Is this improvement purely analytical, or does it correspond to a specific algorithmic innovation that wasn't present in previous approaches?
A2: The improvement comes from applying new algorithm design that wasn't present in Saad’s work. In the previous work by Saad, when inserting an item into the sorting tree, their algorithm simply divided the confidence budget into $\log N$ pairwise comparisons, leading to an additional $\log N$ factor. Our improvement comes from treating the insertion as a whole process and carefully assigning the budget when inserting an item into the tree.

Q3: For the WST setting, you provide matching upper and lower bounds. Do you believe similar tight bounds exist for the SST setting? If there's a gap, where might the improvement come from?
A3: For the SST case, the lower bound is order-wise tight given the proof presented in Ren et al. 2019, which is briefly mentioned in Remark 5.5, line 339. Ren’s lower bound is for a single oracle, but can be easily modified to multiple oracles.

Q4: The empirical evaluation focuses on synthetic data with a specific pattern. How would performance change with more complex accuracy distributions, such as when different oracles have expertise on different subsets of items?
A4: The algorithm and theoretical analysis cover this case where different oracles have expertise on different subsets of items. For each subset of the items (or a specific pair in the context of this paper), the best oracles are elected from scratch for that specific pair. In this regard, our proposed algorithm will continue to enjoy at least the efficiency that a non-RMO version of the algorithm (e.g. Probe-Max) has.

Q5: Your algorithms require the number of oracles M as an input parameter. In crowdsourcing scenarios, this number might grow over time. Is there a natural way to adapt your algorithms to an online setting where new oracles can join?
A5: That’s a great question. Our algorithm can be viewed as selecting the best oracles for different pairs. Thus, when new oracles (crowd-source labellers) come in, they can wait until the algorithm attempts to compare the next new item pair. In this way, the algorithm can work without any modification.