English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Bradley-Terry-Luce (BTL) model is a popular statistical approach forestimating the global ranking of a collection of items using pairwisecomparisons. To ensure accurate ranking, it is essential to obtain preciseestimates of the model parameters in the $\ell_{\infty}$-loss. The difficultyof this task depends crucially on the topology of the pairwise comparison graphover the given items. However, beyond very few well-studied cases, such as thecomplete and Erd\"os-R\'enyi comparison graphs, little is known about theperformance of the maximum likelihood estimator MLE) of the BTL modelparameters in the $\ell_{\infty}$-loss under more general graph topologies. Inthis paper, we derive novel, general upper bounds on the $\ell_{\infty}$estimation error of the BTL MLE that depend explicitly on the algebraicconnectivity of the comparison graph, the maximal performance gap across itemsand the sample complexity. We demonstrate that the derived bounds perform welland in some cases are sharper compared to known results obtained usingdifferent loss functions and more restricted assumptions and graph topologies.We carefully compare our results to Yan et al. (2012), which is closest inspirit to our work. We further provide minimax lower bounds under$\ell_{\infty}$-error that nearly match the upper bounds over a class ofsufficiently regular graph topologies. Finally, we study the implications ofour $\ell_{\infty}$-bounds for efficient (offline) tournament design. Weillustrate and discuss our findings through various examples and simulations.

$\ell_{\infty}$-Bounds of the MLE in the BTL Model under General Comparison Graphs