The Bradley-Terry condition is L₁-testable
From MaRDI portal
Publication:1699573
DOI10.1016/J.DISC.2017.10.026zbMATH Open1380.05086arXiv1609.05194OpenAlexW2964247258MaRDI QIDQ1699573FDOQ1699573
Authors: Konstantinos Tyros, Agelos Georgakopoulos 
Publication date: 23 February 2018
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: We provide an algorithm with constant running time that given a weighted tournament , distinguishes with high probability of success between the cases that 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.
Full work available at URL: https://arxiv.org/abs/1609.05194
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
Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)
Cites Work
- Title not available (Why is that?)
- Property testing and its connection to learning and approximation
- Title not available (Why is that?)
- Property testing in bounded degree graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- \(L_p\)-testing
- Title not available (Why is that?)
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Graph removal lemmas
- Every Monotone Graph Property Is Testable
- Introduction to Property Testing
- Easily testable graph properties
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)
