# Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues

arXiv: https://arxiv.org/abs/1510.05610 · HTML: https://mlsanity.com/paper/1510.05610/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2015.

## Built on by (most cited first, 30 of 32)

- [PAL: Pluralistic Alignment Framework for Learning from Heterogeneous Preferences](https://mlsanity.com/paper/2406.08469/) (2024)
- [Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment](https://mlsanity.com/paper/2410.16714/) (2024)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [Poisoning Attack against Estimating from Pairwise Comparisons](https://mlsanity.com/paper/2107.01854/) (2021)
- [Towards More Robust NLP System Evaluation: Handling Missing Scores in Benchmarks](https://mlsanity.com/paper/2305.10284/) (2023)
- [A Statistical Framework for Ranking LLM-Based Chatbots](https://mlsanity.com/paper/2412.18407/) (2024)
- [Problem Solving Through Human-AI Preference-Based Cooperation](https://mlsanity.com/paper/2408.07461/) (2024)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Active Ranking of Experts Based on their Performances in Many Tasks](https://mlsanity.com/paper/2306.02628/) (2023)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method](https://mlsanity.com/paper/2109.13743/) (2021)
- [Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applications](https://mlsanity.com/paper/2201.08105/) (2022)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms](https://mlsanity.com/paper/2201.06438/) (2022)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)
- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [On the Sample Complexity of Rank Regression from Pairwise Comparisons](https://mlsanity.com/paper/2105.01463/) (2021)
- [A Cross Validation Framework for Signal Denoising with Applications to Trend Filtering, Dyadic CART and Beyond](https://mlsanity.com/paper/2201.02654/) (2022)
- [Optimal Differentially Private Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2507.09388/) (2025)
- [Achievability and Impossibility of Exact Pairwise Ranking](https://mlsanity.com/paper/2111.10021/) (2021)
- [Modeling and Correcting Bias in Sequential Evaluation](https://mlsanity.com/paper/2205.01607/) (2022)
- [Spectral Clustering for Crowdsourcing with Inherently Distinct Task Types](https://mlsanity.com/paper/2302.07393/) (2023)
- [Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications](https://mlsanity.com/paper/2501.07437/) (2025)
- [Statistical and computational challenges in ranking](https://mlsanity.com/paper/2512.21111/) (2025)
- [Beyond Kemeny Medians: Consensus Ranking Distributions Definition, Properties and Statistical Learning](https://mlsanity.com/paper/2602.10640/) (2026)
- [Learning What Evaluators Value: A Reliable Approach to Modeling Evaluator Preferences](https://mlsanity.com/paper/2605.16615/) (2026)
- [Can LLMs Rank? A Tale of Triads and Triage](https://mlsanity.com/paper/2606.30412/) (2026)

## Abstract (arXiv)

There are various parametric models for analyzing pairwise comparison data, including the Bradley-Terry-Luce (BTL) and Thurstone models, but their reliance on strong parametric assumptions is limiting. In this work, we study a flexible model for pairwise comparisons, under which the probabilities of outcomes are required only to satisfy a natural form of stochastic transitivity. This class includes parametric models including the BTL and Thurstone models as special cases, but is considerably more general. We provide various examples of models in this broader stochastically transitive class for which classical parametric models provide poor fits. Despite this greater flexibility, we show that the matrix of probabilities can be estimated at the same rate as in standard parametric models. On the other hand, unlike in the BTL and Thurstone models, computing the minimax-optimal estimator in the stochastically transitive model is non-trivial, and we explore various computationally tractable alternatives. We show that a simple singular value thresholding algorithm is statistically consistent but does not achieve the minimax rate. We then propose and study algorithms that achieve the minimax rate over interesting sub-classes of the full stochastically transitive class. We complement our theoretical results with thorough numerical simulations.