Computing optimal Bayesian decisions for rank aggregation via MCMC sampling
David James Hughes, Kevin Hwang, Lirong Xia · 2015
We propose two efficient and general MCMC algorithms to compute optimal Bayesian deci-sions 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 Mal-lows ’ 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 il-lustrated by experiments on real-world datasets. 1