Light RUMs

Flavio Chierichetti, Ravi Kumar, Andrew Tomkins
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:1888-1897, 2021.

Abstract

A Random Utility Model (RUM) is a distribution on permutations over a universe of items. For each subset of the universe, a RUM induces a natural distribution of the winner in the subset: choose a permutation according to the RUM distribution and pick the maximum item in the subset according to the chosen permutation. RUMs are widely used in the theory of discrete choice. In this paper we consider the question of the (lossy) compressibility of RUMs on a universe of size $n$, i.e., the minimum number of bits required to approximate the winning probabilities of each slate. Our main result is that RUMs can be approximated using $\tilde{O}(n^2)$ bits, an exponential improvement over the standard representation; furthermore, we show that this bound is optimal. En route, we sharpen the classical existential result of McFadden and Train (2000) by showing that the minimum size of a mixture of multinomial logits required to can approximate a general RUM is $\tilde{\Theta}(n)$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-chierichetti21a, title = {Light RUMs}, author = {Chierichetti, Flavio and Kumar, Ravi and Tomkins, Andrew}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {1888--1897}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/chierichetti21a/chierichetti21a.pdf}, url = {https://proceedings.mlr.press/v139/chierichetti21a.html}, abstract = {A Random Utility Model (RUM) is a distribution on permutations over a universe of items. For each subset of the universe, a RUM induces a natural distribution of the winner in the subset: choose a permutation according to the RUM distribution and pick the maximum item in the subset according to the chosen permutation. RUMs are widely used in the theory of discrete choice. In this paper we consider the question of the (lossy) compressibility of RUMs on a universe of size $n$, i.e., the minimum number of bits required to approximate the winning probabilities of each slate. Our main result is that RUMs can be approximated using $\tilde{O}(n^2)$ bits, an exponential improvement over the standard representation; furthermore, we show that this bound is optimal. En route, we sharpen the classical existential result of McFadden and Train (2000) by showing that the minimum size of a mixture of multinomial logits required to can approximate a general RUM is $\tilde{\Theta}(n)$.} }
Endnote
%0 Conference Paper %T Light RUMs %A Flavio Chierichetti %A Ravi Kumar %A Andrew Tomkins %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-chierichetti21a %I PMLR %P 1888--1897 %U https://proceedings.mlr.press/v139/chierichetti21a.html %V 139 %X A Random Utility Model (RUM) is a distribution on permutations over a universe of items. For each subset of the universe, a RUM induces a natural distribution of the winner in the subset: choose a permutation according to the RUM distribution and pick the maximum item in the subset according to the chosen permutation. RUMs are widely used in the theory of discrete choice. In this paper we consider the question of the (lossy) compressibility of RUMs on a universe of size $n$, i.e., the minimum number of bits required to approximate the winning probabilities of each slate. Our main result is that RUMs can be approximated using $\tilde{O}(n^2)$ bits, an exponential improvement over the standard representation; furthermore, we show that this bound is optimal. En route, we sharpen the classical existential result of McFadden and Train (2000) by showing that the minimum size of a mixture of multinomial logits required to can approximate a general RUM is $\tilde{\Theta}(n)$.
APA
Chierichetti, F., Kumar, R. & Tomkins, A.. (2021). Light RUMs. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:1888-1897 Available from https://proceedings.mlr.press/v139/chierichetti21a.html.

Related Material