Discrete Choice, Permutations and Reconstruction
The 12 April 2019 at 2.30p.m.
Sala del Consiglio, VIII piano (vie Celoria 18)
Speaker: Flavio Chierichetti, Sapienza University
Reference people: Paolo Boldi
The family of Random Utility Models was developed over 50 years ago to codify rational user behavior in choosing one item from a finite set of options. In this setting each user draws i.i.d. from some distribution a utility function mapping each item in the universe to a real-valued utility. The user is then offered a subset of the items, and selects the one of maximum utility. A Max-Dist oracle for this choice model takes any subset of items and returns the probability (over the distribution of utility functions) that each will be selected. A discrete choice algorithm, given access to a Max-Dist oracle, must return a function that approximates the oracle. We will discuss a number of results in the most general RUM setting, and in the important special case of a Multinomial Logit mixture model.
(Joint work with Ravi Kumar and Andrew Tomkins.)