  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 real-world 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 worst-case 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 finite-sample domain, a feature crucial to understanding the behavior of
tests in the common data-poor settings of discrete choice. Our lower bounds are
structure-dependent, 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 structure-dependent 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.
