CAM Colloquium: Johan Ugander (Stanford University) - Discrete choice with irrelevant alternatives: models and lower bounds on testing
Frank H. T. Rhodes Hall 655
Many applications in preference learning assume that decisions come from the maximization of a stable utility function. Yet a large experimental literature shows that individual choices and judgements can be affected by "irrelevant" aspects of the context in which they are made. An important class of such contexts is the composition of the choice set. In this talk, I will introduce an extension of the Multinomial Logit (MNL) model, called the context dependent random utility model (CDM), which allows for a particular class of choice set effects based in pairwise interactions between alternatives. We show that the CDM can be thought of as a second-order approximation to a general choice system, can be inferred optimally using maximum likelihood and, importantly, is readily interpretable.
Beyond the presentation of the CDM model of and its properties, I will also discuss separate work on the general problem of determining whether or not an agent's behavior satisfies the so-called Independence of Irrelevant Alternatives (IIA) that characterizes the MNL model. While IIA is widely assumed as a modeling assumption, the formal size properties of hypothesis testing IIA are not well understood. We will replace some of the ambiguity in this literature with rigorous pessimism, demonstrating that any general test for IIA with low worst-case error would require a number of samples exponential in the number of alternatives of the choice problem. Our finite-sample and structure-dependent analysis is unorthodox in being highly combinatorial, constructing a lower bound by counting Eulerian orientations of cycle decompositions of a particular bipartite graph constructed from a data set of choices.
This talk is based on joint work with Alex Peysakhovich, Stephen Ragain, and Arjun Seshadri.
Johan Ugander is an Assistant Professor at Stanford University in the Department of Management Science & Engineering, within the School of Engineering. His research develops algorithmic and statistical frameworks for analyzing social networks, social systems, and other large-scale social data. Prior to joining the Stanford faculty he was a post-doctoral researcher at Microsoft Research Redmond 2014-2015 and held an affiliation with the Facebook Data Science team 2010-2014. He obtained his Ph.D. in Applied Mathematics from Cornell University in 2014. His awards include a Young Investigator Award from the Army Research Office (ARO), two Best Paper Awards (2012 ACM WebSci Best Paper, 2013 ACM WSDM Best Student Paper), and the 2016 Eugene L. Grant Undergraduate Teaching Award from the Department of Management Science & Engineering.