Timezone: »

Light RUMs
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins

Tue Jul 20 06:35 PM -- 06:40 PM (PDT) @ None
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)$.

Author Information

Flavio Chierichetti (Sapienza University)
Ravi Kumar (Google)
Andrew Tomkins (Google)

Related Events (a corresponding poster, oral, or spotlight)

  • 2021 Poster: Light RUMs »
    Wed Jul 21st 04:00 -- 06:00 AM Room None

More from the Same Authors