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

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 (Gt')t' ∈ T on a regular grid T subset [0,1], we aim at recovering the latent strengths of the items wt^* ∈ ℝn at any time t ∈ [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 (Gt')t' ∈ T is a sequence of Erd"os-Renyi graphs, we provide non-asymptotic ℓ2 and ℓ∞ error bounds for estimating wt^* which in particular establishes the consistency of this method in terms of n, and the grid size lvertTrvert. We also complement our theoretical analysis with experiments on real and synthetic data.