UAI Conference 2015 Conference Paper
Computing Optimal Bayesian Decisions for Rank Aggregation via MCMC Sampling
- David Hughes
- Kevin Hwang
- Lirong Xia
statistical decision-theoretic framework for social choice by Azari Soufiani et al. (2014). 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 ϕ−kmax, dmax, and the input size, where ϕ is the dispersion of the model, kmax measures agents’ largest total bias in bipartitions of alternatives, and dmax is the maximum ratio between prior probabilities. We also show that in some cases the mixing time is at least Θ(ϕ−kmax /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. A major challenge in previous research, especially in the Bayesian approaches, is the high computational complexity of decision making. For example, the maximum likelihood estimator (MLE) of a popular ranking model called Mallows’ model (Mallows, 1957) is NP-hard to compute (Bartholdi et al. , 1989). Computing optimal Bayesian decisions for rank aggregation is a hard combinatorial optimization problem because the parameter space is often discrete and its size is often exponential. Most previous work focused on designing efficient case-by-case algorithms for computing MLEs and MAPs of popular ranking models. However, the following question is left unanswered: