- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies how to actively select pairs for comparison to discover statistically supported nontransitive preference cycles with as few comparisons as possible. The paper first builds a statistical model for pairwise comparisons and defines which cycles can be reported. It then constructs an anytime-valid confidence sequence for each pair. By sharing existing comparison data across cycles, the paper provides a theoretical guarantee that controls the overall probability of reporting any false cycle. Finally, the paper estimates the remaining evidence cost for each pair and uses these estimates to select the most promising cycle and the next pair to compare.
Critical strengths
-
Traditional preference ranking methods usually rely on scalar scores, which cannot fully capture nontransitive preference relationships. This paper focuses on discovering such preference cycles with fewer pairwise comparisons, which is a relatively novel idea.
-
This paper reuses existing comparison data and constructs a confidence sequence for each pair. Under the corresponding independence and stationarity assumptions, the method controls the probability of reporting at least one false cycle throughout the adaptive discovery process. The paper also provides solid theoretical guarantees for this error control.
-
This paper performs well across various simulated datasets and significantly improves the sampling efficiency of discovering nontransitive preference cycles.
Critical weaknesses
-
This paper only evaluates the proposed method on simulated datasets, without testing it on real-world data. This makes it difficult to fully demonstrate the practical value of the method.
-
The proposed remaining evidence cost scoring strategy does not show a clear advantage over the simple greedy strategy, as the two strategies achieve very similar performance across the simulated datasets.
-
The statistical assumptions in this paper are relatively strong, which limits the applicability of the proposed method in real-world settings. Could you consider relaxing these assumptions to make the method more broadly applicable?
Questions for authors
-
Could you provide some valid theorems to prove the optimality of your method?
-
You need to compare your method in some real-world datasets.
-
Could you consider relaxing your assumptions to make the method more broadly applicable?
2 comments
Thank you for the detailed responses and revisions. I appreciate the authors' efforts to address my previous concerns. The new experiments on the SUSHI human preference dataset provide useful evidence of the method's practical value. The additional comparisons with Greedy-margin, especially on the misspecified matrices and the real dataset, also show a clearer advantage of the remaining evidence cost strategy. These results largely address my first two concerns. The new theoretical results are also useful. Theorem L.2 provides a lower bound on the information required to discover a positive cycle. However, this does not establish the optimality or near-optimality of the proposed targeting strategy, since there is no guarantee that its sample cost is close to this lower bound. The bounded-score extension in Proposition L.1 also relaxes the original independence and binary-outcome assumptions. However, the method still requires a stable conditional mean, which may limit its use when preferences change over time. Overall, the revisions have addressed most of my concerns and significantly improved the paper. Although some theoretical limitations remain, they do not change my overall assessment. I therefore maintain my recommendation for acceptance.
Thank you for your careful review. We appreciate your constructive comments.
We have uploaded a revised version: changed text is in blue, new appendix sections have blue titles, and red margin notes name the review point each change addresses.
W1, Q2
We added a real-data evaluation on the public SUSHI human preference records; the protocol and full table are in our comment to all reviewers (item 1). On the 100-item task, with the same pilot, bounds, outcome streams and 60000-label cap for every method, targeting needs 6302.5 labels on average to find its first cycle, against 40267.5 for Greedy-margin and 33175 for Uniform-unresolved. At the cap, its reported cycles cover 215.60 distinct pairs, against 9.90 and 13.25. On the ten-item population, which has no positive cycle, no method makes a false report in 100 replays. The revised version adds this replay as a real-data section of the experiments.
W2
Targeting gains substantially over greedy on the misspecified matrices and on real data; on the low-rank matrices the gain is small. Table 6 gives 52.7 additional triangles over greedy for Misspecified 1, but 2.4 for Low-rank 1, where both rules nearly exhaust the same structure. Under matched information on all eight matrices (comment to all reviewers, item 2), targeting adds 35.40–52.35 distinct pairs and 7.70–11.90 edge-disjoint cycles on the four misspecified cases, so the gain persists after accounting for overlap. On SUSHI the score also cuts the first-report cost to less than a sixth of greedy's.
Q1
For optimality, the revision adds a lower bound that every valid method must pay to find any cycle, proved by a change of measure on a set of pairs that meets all positive cycles (comment to all reviewers, item 3); matching this benchmark with the empirical score is the open question. Algorithm 1 itself has proved error control and a cost bound. The probability of ever reporting a false cycle stays at most alpha however the algorithm adapts (Theorem 4.1). Because Algorithm 1 samples only unresolved directions in unresolved candidates, Theorem 5.2 bounds its cost of completing a fixed finite family with nonzero gaps, and hence its first-discovery cost when a positive cycle exists; Theorem 5.1 sharpens this for initially fixed orders by charging failed prefixes. The revised version adds the lower bound as a theorem with its proof.
W3, Q3
We relaxed the binary-outcome assumption to bounded scores, including fractional ties, provided the queried pair's score has a stable mean conditional on the full history. The argument is item 4 of our comment to all reviewers; it covers score distributions that change with the history while that mean stays fixed. For noisy or inconsistent judges, the SUSHI replay with independent response reversals at rates 0.1 and 0.2 keeps targeting at 20/20 successes with mean first costs 6702.5 and 8577.5, while Greedy-margin succeeds in 11/20 and 1/20 runs and Uniform-unresolved in 0/20, with no false reports. The revised version states the bounded-score extension after the validity theorem.
Thank you for the positive assessment; we hope these clarifications strengthen your support for acceptance.