Approximating a RUM from Distributions on $k$-Slates
Abstract
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 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 scales to real-world datasets.
Cite
Text
Chierichetti et al. "Approximating a RUM from Distributions on $k$-Slates." Artificial Intelligence and Statistics, 2023.Markdown
[Chierichetti et al. "Approximating a RUM from Distributions on $k$-Slates." Artificial Intelligence and Statistics, 2023.](https://mlanthology.org/aistats/2023/chierichetti2023aistats-approximating/)BibTeX
@inproceedings{chierichetti2023aistats-approximating,
title = {{Approximating a RUM from Distributions on $k$-Slates}},
author = {Chierichetti, Flavio and Giacchini, Mirko and Kumar, Ravi and Panconesi, Alessandro and Tomkins, Andrew},
booktitle = {Artificial Intelligence and Statistics},
year = {2023},
pages = {4757-4767},
volume = {206},
url = {https://mlanthology.org/aistats/2023/chierichetti2023aistats-approximating/}
}