Approximating a RUM from Distributions on $k$-Slates

Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Alessandro Panconesi, Andrew Tomkins
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:4757-4767, 2023.

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 this Paper

BibTeX
@InProceedings{pmlr-v206-chierichetti23a, 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 = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {4757--4767}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/chierichetti23a/chierichetti23a.pdf}, url = {https://proceedings.mlr.press/v206/chierichetti23a.html}, 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.} }
Endnote
%0 Conference Paper %T Approximating a RUM from Distributions on $k$-Slates %A Flavio Chierichetti %A Mirko Giacchini %A Ravi Kumar %A Alessandro Panconesi %A Andrew Tomkins %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-chierichetti23a %I PMLR %P 4757--4767 %U https://proceedings.mlr.press/v206/chierichetti23a.html %V 206 %X 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.
APA
Chierichetti, F., Giacchini, M., Kumar, R., Panconesi, A. & Tomkins, A.. (2023). Approximating a RUM from Distributions on $k$-Slates. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:4757-4767 Available from https://proceedings.mlr.press/v206/chierichetti23a.html.

Related Material