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.
Approximating a RUM from distributions on k-slates / Chierichetti, Flavio; Giacchini, Mirko; Kumar, Ravi; Panconesi, Alessandro; Tomkins, Andrew. - 206:(2023), pp. 4757-4767. (Intervento presentato al convegno 26th International Conference on Artificial Intelligence and Statistics tenutosi a Valencia, Spain).
Approximating a RUM from distributions on k-slates
Chierichetti, Flavio;Giacchini, Mirko;Panconesi, Alessandro;
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
