Computing Optimal Bayesian Decisions for Rank Aggregation via MCMC Sampling

David Hughes RPI, Kevin Hwang RPI, Lirong Xia Rensselaer Polytechnic Institute
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:129-138, 2015.

Abstract

We propose two efficient and general MCMC algorithms to compute optimal Bayesian decisions for Mallows’ model and Condorcet’s model w.r.t. any loss function and prior. We show that the mixing time of our Markov chain for Mallows’ model is polynomial in $\varphi^{-k_{max}}$, $d_{max}$, and the input size, where $\varphi$ is the dispersion of the model, $k_{max}$ measures agents’ largest total bias in bipartitions of alternatives, and $d_{max}$ is the maximum ratio between prior probabilities. We also show that in some cases the mixing time is at least $\Theta(\varphi^{-k_{max}/2})$. For Condorcet’s model, our Markov chain is rapid mixing for moderate prior distributions. Efficiency of our algorithms are illustrated by experiments on real-world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-rpi15a, title = {Computing Optimal {B}ayesian Decisions for Rank Aggregation via {MCMC} Sampling}, author = {RPI, David Hughes and RPI, Kevin Hwang and Institute, Lirong Xia Rensselaer Polytechnic}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {129--138}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/rpi15a/rpi15a.pdf}, url = {https://proceedings.mlr.press/r13/rpi15a.html}, abstract = {We propose two efficient and general MCMC algorithms to compute optimal Bayesian decisions for Mallows’ model and Condorcet’s model w.r.t. any loss function and prior. We show that the mixing time of our Markov chain for Mallows’ model is polynomial in $\varphi^{-k_{max}}$, $d_{max}$, and the input size, where $\varphi$ is the dispersion of the model, $k_{max}$ measures agents’ largest total bias in bipartitions of alternatives, and $d_{max}$ is the maximum ratio between prior probabilities. We also show that in some cases the mixing time is at least $\Theta(\varphi^{-k_{max}/2})$. For Condorcet’s model, our Markov chain is rapid mixing for moderate prior distributions. Efficiency of our algorithms are illustrated by experiments on real-world datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Computing Optimal Bayesian Decisions for Rank Aggregation via MCMC Sampling %A David Hughes RPI %A Kevin Hwang RPI %A Lirong Xia Rensselaer Polytechnic Institute %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-rpi15a %I PMLR %P 129--138 %U https://proceedings.mlr.press/r13/rpi15a.html %V R13 %X We propose two efficient and general MCMC algorithms to compute optimal Bayesian decisions for Mallows’ model and Condorcet’s model w.r.t. any loss function and prior. We show that the mixing time of our Markov chain for Mallows’ model is polynomial in $\varphi^{-k_{max}}$, $d_{max}$, and the input size, where $\varphi$ is the dispersion of the model, $k_{max}$ measures agents’ largest total bias in bipartitions of alternatives, and $d_{max}$ is the maximum ratio between prior probabilities. We also show that in some cases the mixing time is at least $\Theta(\varphi^{-k_{max}/2})$. For Condorcet’s model, our Markov chain is rapid mixing for moderate prior distributions. Efficiency of our algorithms are illustrated by experiments on real-world datasets. %Z Reissued by PMLR on 04 October 2026.
APA
RPI, D.H., RPI, K.H. & Institute, L.X.R.P.. (2015). Computing Optimal Bayesian Decisions for Rank Aggregation via MCMC Sampling. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:129-138 Available from https://proceedings.mlr.press/r13/rpi15a.html. Reissued by PMLR on 04 October 2026.

Related Material