TrueSkill™: A Bayesian Skill Rating System

The MIT Press eBooksPublished 7 September 2007

Ralf Herbrich, Tom Minka, Thore Graepel

DOI10.7551/mitpress/7503.003.0076

Citations625

TL;DR

A new Bayesian skill rating system which can be viewed as a generalisation of the Elo system used in Chess, which tracks the uncertainty about player skills, explicitly models draws, can deal with any number of competing entities and can infer individual skills from team results.

Abstract

We present a new Bayesian skill rating system which can be viewed as a generalisation of the Elo system used in Chess. The new system tracks the uncertainty about player skills, explicitly models draws, can deal with any number of competing entities and can infer individual skills from team results. Inference is performed by approximate message passing on a factor graph representation of the model. We present experimental evidence on the increased accuracy and convergence speed of the system compared to Elo and report on our experience with the new rating system running in a large-scale commercial online gaming service under the name of TrueSkill.

Keywords

Computer ScienceEconomics, Econometrics and Finance

IEEE Transactions on Information TheoryFactor graphs and the sum-product algorithm

6,481 Citations2001Frank R. Kschischang, Brendan J. Frey +1 more

A generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph, that computes-either exactly or approximately-various marginal functions derived from the global function.

DSpace@MIT (Massachusetts Institute of Technology)A family of algorithms for approximate bayesian inference

902 Citations2001Thomas P. Minka, Rosalind W. Picard

This thesis presents an approximation technique that can perform Bayesian inference faster and more accurately than previously possible, and is found to be convincingly better than rival approximation techniques: Monte Carlo, Laplace's method, and variational Bayes.

View PDF

Journal of the Royal Statistical Society Series C (Applied Statistics)Parameter Estimation in Large Dynamic Paired Comparison Experiments

366 Citations1999Mark E. Glickman

A computationally simple non‐iterative algorithm for fitting a particular dynamic paired comparison model that improves over the commonly used algorithm of Elo by incorporating the variability in parameter estimates, can be performed regularly even for large populations of competitors.

View PDF

Lecture notes in computer scienceConstraint Classification: A New Approach to Multiclass Classification

176 Citations2002Sariel Har-Peled, Dan Roth +1 more

A new view of multiclass classification is presented and the constraint classification problem is introduced, a generalization that captures many flavors of multiclass classification and provides the first optimal, distribution independent bounds for many multiclass learning algorithms, including winner-take-all (WTA).

Constraint Classification: A New Approach to Multiclass Classification and Ranking

67 Citations2002Sariel Har-Peled, Dan Roth +1 more

Constraint classification is introduced, a framework capturing many flavors of multiclass classification including multilabel classification and ranking, and a meta-algorithm for learning in this framework is presented.