The Bradley--Terry condition is $L_1$--testable

Abstract

We provide an algorithm with constant running time that given a weighted tournament $T$, distinguishes with high probability of success between the cases that $T$ can be represented by a Bradley--Terry model, or cannot even be approximated by one. The same algorithm tests whether the corresponding Markov chain is reversible.