Electrical and Computer Engineering
menu MENU

Communications and Signal Processing Seminar

Discrete choice with irrelevant alternatives: models and lower bounds on testing

Johan UganderAssistant ProfessorStanford University, Management Science & Engineering (MS&E) Institute for Computational & Mathematical Engineering (ICME) School of Engineering
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 is readily interpretable. Beyond the presentation of the CDM model of and its properties, I will also discuss 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 postdoctoral 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), three Best Paper Awards (2012 ACM WebSci Best Paper, 2013 ACM WSDM Best Student Paper, 2020 AAAI ICWSM Best Paper), and the 2016 Eugene L. Grant Undergraduate Teaching Award from the Department of Management Science & Engineering

Join Zoom Meeting https://umich.zoom.us/j/97598571292

Meeting ID: 975 9857 1292

Passcode: XXXXXX (Will be sent via email to attendees)