Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice The Multinomial Logit (MNL) model and the axiom it satisfies, the Independence of Irrelevant Alternatives (IIA), are together the most widely used tools of discrete choice. The MNL model serves as the workhorse model for a variety of fields, but is also widely criticized, with a large body of experimental literature claiming to document realworld settings where IIA fails to hold. Statistical tests of IIA as a modelling assumption have been the subject of many practical tests focusing on specific deviations from IIA over the past several decades, but the formal size properties of hypothesis testing IIA are still not well understood. In this work we replace some of the ambiguity in this literature with rigorous pessimism, demonstrating that any general test for IIA with low worstcase error would require a number of samples exponential in the number of alternatives of the choice problem. A major benefit of our analysis over previous work is that it lies entirely in the finitesample domain, a feature crucial to understanding the behavior of tests in the common datapoor settings of discrete choice. Our lower bounds are structuredependent, and as a potential cause for optimism, we find that if one restricts the test of IIA to violations that can occur in a specific collection of choice sets (e.g., pairs), one obtains structuredependent lower bounds that are much less pessimistic. Our analysis of this testing problem is unorthodox in being highly combinatorial, counting Eulerian orientations of cycle decompositions of a particular bipartite graph constructed from a data set of choices. By identifying fundamental relationships between the comparison structure of a given testing problem and its sample efficiency, we hope these relationships will help lay the groundwork for a rigorous rethinking of the IIA testing problem as well as other testing problems in discrete choice.

Generalized transitivity: A systematic comparison of concepts with an application to preferences in the Babington Smith model Abstract   Reciprocal relations are binary relations Q with entries    Q  (  i  ,  j  )  xe2x88x88    0  ,  1     , and such that    Q  (  i  ,  j  )    Q  (  j  ,  i  )    1   . Relations of this kind occur quite naturally in various domains, such as preference modeling and preference learning. For example,      q    i  ,  j      could be the fraction of voters in a population who prefer candidate i to candidate j. In the literature, various attempts have been made at generalizing the notion of transitivity to reciprocal relations. In this paper, we compare three important frameworks of generalized transitivity: gstochastic transitivity, Ttransitivity, and cycletransitivity. To this end, we introduce Etransitivity as an even more general notion. We also use this framework to extend an existing hierarchy of different types of transitivity. As an illustration, we study transitivity properties of probabilities of pairwise preferences, which are induced as marginals of an underlying probability distribution on rankings (strict total orders) of a set of alternatives. In particular, we analyze the interesting case of the socalled Babington Smith model, a parametric family of distributions of that kind.