Source-linked AI summary
Random Utility Theory for Social Choice
Hossein Azari Soufiani, David C. Parkes, Lirong Xia
TL;DR
General random utility models offer more flexible preference modeling than Plackett-Luce, but inference beyond Plackett-Luce has been limited. This paper develops exponential-family RUM theory and MC-EM inference, showing concavity and bounded optima under stated conditions and favorable model-fit results for normal RUMs on two real-world datasets.
Problem
Inference for general random utility models is limited beyond Plackett-Luce, especially for natural alternatives such as normally distributed utilities.
Method
The paper studies exponential-family RUMs and estimates latent utilities with MC-EM, establishing conditions for concave log-likelihoods and bounded global-maxima sets.
Results
95% confidence comparisons on two real-world datasets show normal RUMs outperform Plackett-Luce on log-likelihood, predictive log-likelihood, and AIC.
Takeaways & Limitations
The approach supports scalable inference and model selection among flexible RUMs, including Plackett-Luce.
Takeaways & Limitations
Allowing variances to be estimated improves log-likelihood fit but removes the theoretical convergence guarantees available when variances are fixed to 1.
Abstract
from arXiv · showhide
Random utility theory models an agent's preferences on alternatives by drawing a real-valued score on each alternative (typically independently) from a parameterized distribution, and then ranking the alternatives according to scores. A special case that has received significant attention is the Plackett-Luce model, for which fast inference methods for maximum likelihood estimators are available. This paper develops conditions on general random utility models that enable fast inference within a Bayesian framework through MC-EM, providing concave loglikelihood functions and bounded sets of global maxima solutions. Results on both real-world and simulated data provide support for the scalability of the approach and capability for model selection among general random utility models including Plackett-Luce.
1 Introduction
Social choice can be framed as inference from ordinal preferences, but classical models impose restrictive assumptions and general RUM inference has been limited. This paper develops exponential-family RUM theory and MC-EM methods, with experiments supporting scalability and flexible model comparison.
- Social choice aggregates users’ partial or total rankings by selecting a representative ranking from noisy preference reports.
- Condorcet’s model uses identical independent pairwise-comparison distributions, ignores preference strength, permits cyclic preferences, and leads to computationally hard Kemeny optimization.
- RUMs assign each alternative a parameterized random utility, independently sample utilities, and rank alternatives by their realized scores.
- RUMs exclude cyclic outcomes and capture preference strength by assigning separate parameters to alternatives.
- The paper studies exponential-family RUMs, extends Plackett-Luce, and proposes MC-EM with controllable Monte Carlo error plus parallelized and Rao-Blackwellized E-steps.
- 95% confidence results on two real-world datasets show normal RUMs outperform Plackett-Luce on log-likelihood, predictive log-likelihood, and AIC.
2 RUMs and Exponential Families
The paper formulates social-choice data as preference profiles and estimates latent parameters by maximizing their likelihood. It specializes RUM utilities to exponential-family distributions, with Plackett-Luce arising from Gumbel utilities.
- A preference profile is a collection of one strict preference order from each of n agents.
- A voting rule maps each preference profile to a nonempty set of winning rankings, while MLE selects rankings associated with likelihood-maximizing parameters.
- The likelihood of a preference profile is defined from the probability of each observed order under the ground-truth parameters and utility distributions.
- The model restricts each alternative’s utility distribution to the exponential family, whose density uses natural parameters, a log-partition function, base measure, and sufficient statistics.
- Plackett-Luce is recovered when alternatives’ utilities follow Gumbel distributions with the specified sufficient-statistic and partition-function components.
3 Global Optimality and Log-Concavity
The paper establishes conditions under which random-utility likelihoods are concave and their global maximizers bounded, supporting global optimization and order recovery. For location families, these properties follow from log-concave noise densities and data connectivity conditions.
- Optimization: The likelihood is computed by maximizing the log-likelihood over the location parameters θ.
- Log-Concavity: A log-concave density for every location-family noise variable ζ_j guarantees a concave log-likelihood.The result applies through a lemma for probabilities defined by concave inequality constraints under log-concave noise.
- Log-Concavity: Normal and Gumbel location families satisfy the condition under fixed variance or shape, so their log-likelihoods are concave.This includes Plackett-Luce as a special case.
- Bounded Solutions: With one parameter fixed, the global-maximizer set is bounded if and only if every partition of alternatives has observed cross-partition preference evidence.Without fixing a parameter, translation invariance makes the maximizer set unbounded.
- Bounded Solutions: The boundedness proof uses a directed preference graph: bounded pairwise parameter differences along paths imply a bounded global-maximizer set.Condition 1 supplies paths between every pair of alternatives, and telescoping the bounded differences yields the result.
- Order Recovery: All global maxima induce the same strict order exactly when no maximizing parameter vector contains a tie between alternatives.Under this condition, any vector in the maximizer set reveals the unique order.
4 Monte Carlo EM for Parameter Estimation
The paper develops an MC-EM procedure for maximum-likelihood inference in exponential-family random utility models, using Monte Carlo sampling to approximate an otherwise intractable E-step. Under suitable conditions, the resulting likelihood geometry supports convergence, while implementation choices control approximation error.
- Algorithm: MC-EM estimates parameters by alternating a Monte Carlo E-step with an M-step that maximizes the expected complete-data log-likelihood.The E-step conditions on observed rankings and current parameters; the M-step produces the next parameter iterate.
- Monte Carlo E-step: The E-step samples latent utilities with a Gibbs sampler because the required conditional expectation has no analytical solution.Each utility is sampled from a truncated exponential-family distribution determined by neighboring ranked utilities and the current parameters.
- Monte Carlo E-step: Rao-Blackwellization reduces estimator variance, while parallelization over agents and alternatives improves the E-step procedure.The Rao-Blackwellized quantity can be treated as constant during the M-step, leaving the relevant sufficient statistics to be computed in the E-step.
- M-step: For normal models with fixed variance, the M-step uses the exponential-family parameterization to update each location parameter from the estimated sufficient statistics.The normal case is illustrated as a specialized MC-EM algorithm.
- Convergence: Concavity and bounded global maxima support convergence, but MC-EM lacks uniform convergence and requires approximation errors smaller than the differences between parameter values.The method targets accurate relative ordering rather than exact parameter estimation, and increasing the Monte Carlo sample size can reduce update variance.
5 Experimental Results
Experiments evaluate MC-EM on synthetic, election, and sushi preference data, showing scalable inference, robustness to subsampling, and improved fit for normal RUMs over Plackett-Luce when datasets are sufficiently large.
- Synthetic Data: Kendall correlation improves as the number of synthetic-data agents increases, while larger variance slows performance gains.The experiments use normal utilities with θj = j and Var = 2 or 4.
- Synthetic Data: At most 3 EM iterations and MN = 4000 samples are sufficient for inference in most synthetic-data cases.
- Model Robustness: Using half of the 280-vote election dataset achieves an average Kendall correlation greater than 0.4 with the full-data ranking.The subsampling experiment repeats each sample-size condition 200 times.
- Model Fitness: With n = 50, normal RUMs outperform Plackett-Luce with 95% confidence for log-likelihood, predictive log-likelihood, and AIC in both datasets.For n = 10, high variance prevents statistically significant fitness comparisons.
- Scalability: MC-EM running time scales linearly with the number of agents on election data, at 13.3 seconds per agent for 100 EM iterations.The reported setting increases Gibbs samples with iteration steps as 2000 + 300 × iteration.