# Approximating a RUM from Distributions on k-Slates

arXiv: https://arxiv.org/abs/2305.13283 · HTML: https://mlsanity.com/paper/2305.13283/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 22 May 2023.

## Builds on (most cited first, 7 of 7)

- [Discovering Context Effects from Raw Choice Data](https://mlsanity.com/paper/1902.03266/) (2019)
- [Predicting Choice with Set-Dependent Aggregation](https://mlsanity.com/paper/1906.06365/) (2019)
- [Learning from Comparisons and Choices](https://mlsanity.com/paper/1704.07228/) (2017)
- [Pairwise Choice Markov Chains](https://mlsanity.com/paper/1603.02740/) (2016)
- [Learning Mixed Multinomial Logit Model from Ordinal Data](https://mlsanity.com/paper/1411.0073/) (2014)
- [Learning an arbitrary mixture of two multinomial logits](https://mlsanity.com/paper/2007.00204/) (2020)
- [Going for Speed: Sublinear Algorithms for Dense r-CSPs](https://mlsanity.com/paper/1407.7887/) (2014)

## Built on by (most cited first, 1 of 1)

- [DETONATE: A Benchmark for Text-to-Image Alignment and Kernelized Direct Preference Optimization](https://mlsanity.com/paper/2506.14903/) (2025)

## Abstract (arXiv)

In this work we consider the problem of fitting Random Utility Models (RUMs) to user choices. Given the winner distributions of the subsets of size k of a universe, we obtain a polynomial-time algorithm that finds the RUM that best approximates the given distribution on average. Our algorithm is based on a linear program that we solve using the ellipsoid method. Given that its corresponding separation oracle problem is NP-hard, we devise an approximate separation oracle that can be viewed as a generalization of the weighted feedback arc set problem to hypergraphs. Our theoretical result can also be made practical: we obtain a heuristic that is effective and scales to real-world datasets.