# Graph Resistance and Learning from Pairwise Comparisons

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2019.

## Built on by (most cited first, 5 of 5)

- [ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphs](https://mlsanity.com/paper/2110.10825/) (2021)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem](https://mlsanity.com/paper/2310.02016/) (2023)
- [Bradley-Terry model under general comparison graphs](https://mlsanity.com/paper/2610.06237/) (2026)

## Abstract (arXiv)

We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed "comparison graph" and every neighboring pair of items in this graph is compared k times according to the Bradley-Terry-Luce model (where the probability than an item wins a comparison is proportional the item quality). We are interested in how the relative error in quality estimation scales with the comparison graph in the regime where k is large. We prove that, after a known transition period, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm that is minimax optimal. The algorithm has a relative error decay that scales with the square root of the graph resistance, and provide a matching lower bound (up to log factors). The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, outperforms earlier results.