Lower Bounds on the Bayes Risk of the Bayesian BTL Model With Applications to Comparison Graphs

We consider the problem of aggregating pairwise comparisons to obtain a consensus ranking order over a collection of objects. We use the popular Bradley-Terry-Luce (BTL) model, which allows us to probabilistically describe pairwise comparisons between objects. In particular, we employ the Bayesian B...

Full description

Saved in:
Bibliographic Details
Published in:IEEE journal of selected topics in signal processing 2018-10, Vol.12 (5), p.975-988
Main Authors: Alsan, Mine, Prasad, Ranjitha, Tan, Vincent Y. F.
Format: Article
Language:English
Subjects:
Analytical models
Bayes methods
Bayesian analysis
BTL model
Computer simulation
Cramer-Rao bounds
Distortion
Games
Graph theory
Graphical representations
Inference algorithms
Information theory
Information-theoretic lower bounds
Lower bounds
Production scheduling
random graphs
ranking
Risk
Signal processing algorithms
Tree graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of aggregating pairwise comparisons to obtain a consensus ranking order over a collection of objects. We use the popular Bradley-Terry-Luce (BTL) model, which allows us to probabilistically describe pairwise comparisons between objects. In particular, we employ the Bayesian BTL model, which allows for meaningful prior assumptions and to cope with situations where the number of objects is large and the number of comparisons between some objects is small or even zero. For the conventional Bayesian BTL model, we derive information-theoretic lower bounds on the Bayes risk of estimators for norm-based distortion functions. We compare the information-theoretic lower bound with the Bayesian Cramér-Rao lower bound we derive for the case when the Bayes risk is the mean squared error. We illustrate the utility of the bounds through simulations by comparing them with the error performance of an expectation-maximization-based inference algorithm proposed for the Bayesian BTL model. We draw parallels between pairwise comparisons in the BTL model and interplayer games represented as edges in an Erdös-Rényi graph and analyze the effect of various graph structures on the lower bounds. We also extend the information-theoretic and Bayesian Cramér-Rao lower bounds to the more general Bayesian BTL model, which takes into account home-field advantage.
ISSN:1932-4553
1941-0484
DOI:10.1109/JSTSP.2018.2827303