The Bradley-Terry condition is L₁-testable

DOI10.1016/J.DISC.2017.10.026MaRDI QIDQ1699573zbMATH OpenOpenAlexFDO

Authors Konstantinos Tyros, Agelos Georgakopoulos

Publication date 23 February 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05194

zbMATH Keywords

Bradley-Terry modelproperty testingreversible Markov chain\(L_1\)-testerstochastic tournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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.

Recommendations

• Random sampling of labeled tournaments
• EM algorithms for generalized Bradley-Terry models
• scientific article; zbMATH DE number 123309
• To stay discovered: on tournament mean score sequences and the Bradley-Terry model
• Ranking in the generalized Bradley-Terry models when the strong connection condition fails

Cites work

• scientific article; zbMATH DE number 41025 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 3073477 (Why is no real title available?)
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Easily testable graph properties
• Every Monotone Graph Property Is Testable
• Graph removal lemmas
• Introduction to Property Testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• \(L_p\)-testing

This page was built for publication: The Bradley-Terry condition is \(L_1\)-testable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699573)