Linear-Time Inference for Pairwise Comparisons with Gaussian-Process Dynamics

In many competitive sports and games (such as tennis, basketball, chess and electronic sports), the most useful definition of a competitor's skill is the propensity of that competitor to win against an opponent. It is often difficult to measure this skill explicitly: take basketball for example, a team's skill depends on the abilities of its players in terms of shooting accuracy, physical fitness, mental preparation, but also on the team's cohesion and coordination, on its strategy, on the enthusiasm of its fans, and a number of other intangible factors. However, it is easy to observe this skill implicitly through the outcomes of matches. In this setting, probabilistic models of pairwise-comparison outcomes provide an elegant and effective approach to quantifying skill and to predicting future match outcomes given past data. These models, pioneered by Zermelo [1928] in the context of chess (and by Thurstone [1927] in the context of psychophysics), have been studied for almost a century. They posit that each competitor i (i.e., a team or player) is characterized by a latent score s R and that the outcome probabilities of a match between i and j are a function of