Robust Monotone Ratings: A Bayesian, Linear-Time Scheme for Massive Ranked Competitions

This paper introduces a computer science approach to large-scale skill estimation that unifies probabilistic modeling with algorithmic efficiency. We present a Bayesian rating framework that models skills, performances, and ranked evidence, deriving closed-form MAP updates and a pseudodiffusion mechanism for temporal skill evolution. The resulting algorithms exhibit monotonicity properties that support incentive-compatibility, robustness to outliers via heavy-tailed likelihoods, and parallelizable operation with a proven space complexity of O of n times the maximum of n and h times log log of 1 divided by epsilon per competition round, where n is the number of participants and h is the history length. The method achieves a time complexity of O of n divided by epsilon squared times log log of 1 divided by epsilon under practical approximations, including history truncation and opponent subsampling. Theoretical properties, including runtime bounds and robustness limits, are paired with empirical evaluations on multi-million-interaction datasets, demonstrating improved prediction accuracy and substantial speedups on large-scale datasets compared to widely used baselines.