Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method

arXiv2109.13743MaRDI QIDQ6378804

Author name not available (Why is that?)

Publication date: 28 September 2021

Abstract: Many applications such as recommendation systems or sports tournaments involve pairwise comparisons within a collection of $n$ items, the goal being to aggregate the binary outcomes of the comparisons in order to recover the latent strength and/or global ranking of the items. In recent years, this problem has received significant interest from a theoretical perspective with a number of methods being proposed, along with associated statistical guarantees under the assumption of a suitable generative model. While these results typically collect the pairwise comparisons as one comparison graph $G$, however in many applications - such as the outcomes of soccer matches during a tournament - the nature of pairwise outcomes can evolve with time. Theoretical results for such a dynamic setting are relatively limited compared to the aforementioned static setting. We study in this paper an extension of the classic BTL (Bradley-Terry-Luce) model for the static setting to our dynamic setup under the assumption that the probabilities of the pairwise outcomes evolve smoothly over the time domain $[0,1]$. Given a sequence of comparison graphs $(G_{t^{\prime }}{)}_{t^{\prime }inmathcalT}$ on a regular grid $mathcalTsubset[0,1]$, we aim at recovering the latent strengths of the items $w_t^{\ast }inmathbb{R}^n$ at any time $tin[0,1]$. To this end, we adapt the Rank Centrality method - a popular spectral approach for ranking in the static case - by locally averaging the available data on a suitable neighborhood of $t$. When $(G_{t^{\prime }}{)}_{t^{\prime }inmathcalT}$ is a sequence of Erd"os-Renyi graphs, we provide non-asymptotic $el{l}_2$ and $el{l}_{infty}$ error bounds for estimating $w_t^{\ast }$ which in particular establishes the consistency of this method in terms of $n$, and the grid size $lvertmathcalTvert$. We also complement our theoretical analysis with experiments on real and synthetic data.

Has companion code repository: https://github.com/karle-eglantine/Dynamic_Rank_Centrality

This page was built for publication: Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method

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