Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
102,803 characters · 18 sections · 81 citation commands
Fundamental Limits of Testing the Independence of Irrelevant Alternatives in Discrete Choice
\newtheorem{defn}{Definition} \newtheorem{thm}{Theorem} \newtheorem{cor}{Corollary} \newtheorem{ass}{Assumption} \newtheorem{question}{Question}
A common goal for a wide variety of social-scientific pursuits is to infer preferences from the choices individuals make given a limited, discrete set of alternatives. Towards this goal, probabilistic discrete choice modelling is broadly applied in the study of transportation domencich1975urban, industrial organization berry1995automobile, marketing allenby1998marketing, network formation overgoor2019choosing, recommender systems resnick1997recommender, search engine ranking schapire1998learning, and other judgement or decision problems that are discrete in nature.
The study of discrete choice focuses on the following problem setting. A decision maker, either an individual or a representative of a population, chooses an alternative $x$ from a choice set $C$ of two or more alternatives. The set of alternatives is a subset of a broader universe $\mathcal{X}$ of $n$ alternatives. The choice set captures the restrictions faced by the chooser at the time the decision is made, either by design or due to constraints. The goal in modelling discrete choice is then to determine how choices are made by a decision maker (or a group of decision makers) across a specific collection $\mathcal{C}$ of unique subsets of $\mathcal{X}$. The collection $\mathcal{C}$ may be the collection of all subsets of $\mathcal{X}$, may be the collection of all pairs or of all triplets, or may be some empirically determined collection, and is generally treated as exogenous to the problem. The goal of probabilistic modelling is to model with what probability each item $x$ will be chosen from each set $C \in \mathcal{C}$. The corresponding challenge of inference is to recover a model given a dataset of subsets and choices from those subsets (and the identity of the decision makers, if heterogeneous).
Perhaps the most prevalent approach to modelling discrete choice is to assign a latent utility to all $n$ items of the universe, and then model decision making as a noisy maximization of the item utilities in a given choice set. The conditional Multinomial Logit (MNL) model mcfadden1977application, also known as the Bradley-Terry-Luce model bradley1952rank,luce1959individual, is the best known among these Random Utility Models falmagne1978representation that follow this utility-based approach. Indeed, the MNL model is the foundational workhorse of probabilistic discrete choice modelling for settings both small and large in scale.
The MNL model is widely described as modelling “rational” discrete choice, a position that can be motivated in several ways. A common motivation is a willingness to assume the axiom of the Independence of Irrelevant Alternatives (IIA) luce1959possible, also known as Luce's choice axiom. A motivating consequence of IIA is that under IIA, adding an item to a choice set does not change the relative probabilities of choosing the existing items in the original set. Alternative motivations for the MNL model include a willingness to assume a random utility model along with either independent Gumbel noise, which characterizes the MNL model manski1977structure or by assuming an independent random utility model that satisfies the axiom of uniform expansion yellott1977relationship. Regardless of the motivation, the MNL model is unique among all probabilistic models of discrete choice in satisfying IIA, so IIA can be thought of as a complete characterization of the model within the space of all discrete choice models.
The above idea that the MNL model is typically adopted as a result of careful deliberations about underlying assumptions is very generous towards practitioners: more often, the MNL model is adopted simply because it is easy to work with. It is easy to learn from data (the log-likelihood is convex, and the number of parameters scale linearly with $n$), it is easy to employ in prediction tasks (predicted choice probabilities have a simple functional form), and it is easy to interpret (the parameters of the model are interpretable as relative utilities of the items in the choice problem).
Given that IIA fully characterizes the MNL model, the widespread popularity of the model has directed a great deal of attention to varied evaluations of whether IIA holds in a given context or dataset. A large body of experimental evidence claims to document significant deviations from IIA across many domains. Examples of specific deviations that have received considerable attention include the compromise effect simonson1989choice, asymmetric dominance huber1982adding, and the similarity effect tversky1972elimination. As a result of these observations, which at least date back to Debreu's book review debreu1960review of Luce's original monograph, researchers have taken to developing models of discrete choice that eschew IIA; examples include the Elimination By Aspects (EBA) model tversky1972elimination, nested models mcfadden1978modeling, mixture models mcfadden1975aggregate,mcfadden2000mixed, Markov chain models blanchet2016markov, ragain2016pairwise, and contextual random utility models simonson1989choice,batsell1985new,chen2016modeling,seshadri2019raw.
The above evaluations and modelling efforts have in no way discouraged practitioners from using the MNL model, even at modest item sizes lurkin2017accounting,raval2019machine. One reason is that the models that eschew IIA have almost always been more complex than the MNL model, either in the number of parameters (sometimes scaling combinatorially in $n$ park2013theoretical) or in inferential difficulty keane1992note, chierichetti2018learning, benson2016relevance, and their use thus requires specific justification. Meanwhile, most empirical efforts to reject IIA do so in settings of, e.g., three items and two subsets (a pair and the full triplet) simonson1989choice, huber1982adding, tversky1972elimination. These demonstrations are highly illustrative, but not cleanly transferable to motivating problems with many more alternatives\footnote{While IIA violations in one setting could be an indicator of violations in another, different deviations studied often conflict with each other in direction and magnitude, making predictions difficult over a large number of unique subsets.}. This is to say, the small-scale demonstrations fall short of formally {\it testing} whether IIA holds for a general discrete choice problem. The demonstrations lack the objectivity, transparency, and interpretability that (properly used) testing procedures provide in practice johari2015always. While formal tests for IIA do exist, such as the early proposals of McFadden, Tye, and Train mcfadden1977application and of Hausman and McFadden hausman1984specification, these tests have been problematic in practice, as discussed further in the prior work discussion within this introduction. When IIA cannot be rejected with confidence for a given problem, it is natural to default to the MNL model. Should the deviations from IIA that have been documented in small problem instances indeed hold for larger instances, these deviations are being largely ignored by many of today's practitioners.
In this work we ask: given a dataset of choices from choice sets within a collection $\mathcal{C}$, how efficiently can IIA be tested in a general $n$ alternative setting? The main difficulty with such a test lies in the combinatorial nature of discrete choice problems. Whereas it is well known that the MNL model can be inferred with samples scaling only in $n$ under IIA negahban2012iterative, shah2016estimation, agarwal2018accelerated, a test of IIA is inherently a matter of model misspecification. For IIA to not hold, a sufficient condition is a departure from otherwise IIA-consistent choices by the choice probability of a single item on a single subset within the collection $\mathcal{C}$. A collection $\mathcal{C}$ with many subsets, notably subsets of large size, could then permit many distinct ways for departing from IIA and render all tests of IIA sample-intensive. This challenges follows what is sometimes called the Anna Karenina principle\footnote{The opening line of Tolstoy's {\it Anna Karenina} being: “Happy families are all alike; every unhappy family is unhappy in its own way.” Tolstoy} of high-dimensional hypothesis testing: all nulls are alike, but deviations from the null all deviate in their own way. In our context, the principle translates to say that while there are only a few ways to be “rational,” there are a many unique ways that people can be “irrational.”
As part of our work, we do not focus on any particular test of IIA, but rather, we interrogate the sample complexity inherent to the IIA testing problem by bounding from below the worst case error of any IIA testing procedure. Because we study the worst case error given a finite number of samples, our results are necessarily dependent on every set in $\mathcal{C}$ being allocated $\textit{some}$ of the samples. Were the structure of $\mathcal{C}$ ignored in this respect, with some sets receiving no samples, the worst case error of a test is always that of a random guess, since the "worst case" IIA deviation can be thought of as arising only in unsampled sets.
Our main contribution is to show that the sample complexity of testing IIA grows at least with the square root of the sum of all subset cardinalities in the collection $\mathcal{C}$. This scaling yields the pessimistic outcome that testing for IIA over a collection with many and large subsets can quickly require samples exponential in the number of items $n$. Our bounds also yield room for optimism. In many practical settings, $\mathcal{C}$ only consists of specific pairs and triplets, not, e.g., all subsets of size seventeen. For these settings, where the sum of all subset cardinalities in the collection $\mathcal{C}$ scales mildly with $n$, our bounds suggest the possible existence of surprisingly efficient procedures for testing IIA. This efficiency stands in contrast to the classical chi-squared approaches that require an accurate estimate of the distributions over the subsets in $\mathcal{C}$ and hence samples linear in the sum of subset cardinalities read2012goodness.
Although traditional theoretical analyses show that $\chi^2$ tests for discrete distributions are rate-optimal in the minimax sense, these analyses (see lehmann2005testing, pg. 593) treat the dimension as fixed and constant compared to a growing number of samples, and their resulting rates conceal the impact of problem size in relation to data. When dimensions are taken into account, estimation-based classical $\chi^2$ tests are no longer generally optimal, and tests are often feasible with far fewer samples than are required for estimation. This is shown in recent finite-sample analyses for a variety of basic testing problems over discrete distributions, including testing identity valiant2017automatic, testing amongst monotone distributions wei2016sharp, testing independence and many others properties daskalakis2018distribution. The possible existence of efficient procedures for testing IIA for practical $\mathcal{C}$ connects our work to this broader project in hypothesis testing properties of discrete distributions.
\paragraph*{\bf Prior work on hypothesis testing IIA} The problem of testing IIA was first posed in Luce's influential book luce1959individual introducing the MNL model. There, Luce considers a rudimentary test of whether the probability ratio of choosing two items from a two-item and three-item choice set are the same, as they should be under IIA. He performs an approximate calculation showing that estimating the two ratios with low variance in order to make an accurate claim about IIA seems to demand thousands of samples. The first formal hypothesis tests for IIA were proposed in 1977 by McFadden, Tye, and Train mcfadden1977application. These tests were later found to be asymptotically biased small1985multinomial and inspired several alternatives.
All of these alternative tests---by Hausman-McFadden hausman1984specification, Small-Hsiao small1985multinomial, and Horowitz horowitz1981identification---rely on the same mechanism to detect violations: they construct tests for differences in parameter estimates between estimation done in the presence or absence of an item in its associated choice sets. McFadden mcfadden1987regression has also proposed testing joint specifications in a regression framework. All these tests have been discovered to be problematic; Fry and Harris fry1996monte,fry1998testing first used simulations to show that the known tests have poor size properties, and that practical datasets were far too small to operate in their assumed asymptotic regime. Cheng and Long cheng2007testing later confirmed this finding through more rigorous simulation, but moreover demonstrated that data sampled from IIA models often reject the null hypothesis of this test even with extraordinarily large data sizes, and data sampled from other models often fail to reject. On the other hand, model based tests---tests that compare the MNL model to a more general model\footnote{Typical examples include the Generalized Extreme Value Model, Nested Logit, and the Mixed Multinomial Logit.} that nests the MNL model---are often unused because the models that eschew IIA suffer from computational intractability, or issues with identifiability cheng2007testing. These results have since influenced folklore long2005regression which advises researchers against using existing tests for IIA. While we do not propose any new tests in this work---only lower bounds on the sample complexity of the best possible tests---we hope that our lower bound results (and proof techniques) can open the door to new constructive tests that test IIA rigorously, if not also efficiently.
\paragraph*{\bf Prior graphical work on discrete choice} Our work's graphical treatment of discrete choice models is not unique in the literature. Namely, we are not the first to use graph properties to provide finite sample minimax lower bounds. In negahban2012iterative, random walks on pairwise comparison graphs form the basis for interpreting and analyzing the paper's main RankCentrality algorithm for inferring BTL model parameters. In shah2016estimation, eigenvalues of a comparison graph's Laplacian are used to prove the minimax optimality of the maximum likelihood estimator for the MNL model. The same problem is approached in hajek2014minimax, however with a greater emphasis on spectral gaps and graph degree distributions. Finally, Markov chains constructed from comparison graphs form the basis of multiple estimation algorithms, including maystre2015fast and agarwal2018accelerated. Every one of these works focuses on the estimation of MNL models, as opposed to testing their validity, the focus of our work. Novel about our work is the study of cycles in our comparison incidence graphs as the property crucial to departures from IIA. This property should not be confused with the cyclic monotonicity property of the MNL model used in shi2018estimating to construct a consistent estimator for the model, as cyclic monotonicity is a convex-analytic property that holds true for MNL regardless of the comparison graph.
\paragraph*{\bf The present work}
We provide the first formal lower bounds on the complexity of testing IIA. To do so, we leverage recent progress in the finite sample analysis of the complexity of testing discrete distributions over the last decade paninski2008coincidence,valiant2017automatic,wei2016sharp,acharya2015optimal across the statistics, information theory, and theoretical computer science literatures. The first step in our approach is a testing relaxation that studies a statistically and analytically simpler test than the IIA test, and requires a careful construction stemming from a desire to keep the sufficient statistics of the MNL model unchanged. The relaxed test is then connected to directing cycles of a particular {\it comparison incidence graph} $G_\mathcal{C}$ based on the collection $\mathcal{C}$, special properties of which always ensure a cycle decomposition. It is then shown, through a mixture of statistical and combinatorial analysis, that the cycles help guarantee (through their size properties) many orthogonal departures from IIA, furnishing a high lower bound for the IIA testing problem. Notable in our analysis is the key role of the structure of the collection of unique comparison sets $\mathcal{C}$ where the IIA property is being tested.
Our main result is then a minimax lower bound on testing IIA that, informally, lower bounds the error of the best possible test on the worst case problem instance for a given comparison setting and a given number of samples. The main consequence of our lower bound is that the worst-case sample complexity of the IIA testing problem is lower-bounded by a quantity proportional to $\sqrt{d}$, where $d$ is the sum of the sizes of the subsets in $\mathcal{C}$. In the case where a researcher considers all settings where IIA could be violated, that is, over all possible subsets of a universe set of $n$ items, size 2 or greater, $d$ is exponential in $n$. Thus, testing for IIA, in its most general form, has a worst case sample complexity that is at least exponential in the number of items.
A secondary consequence of our lower bound is one of optimism (or at least a lack of pessimism) when $d$ is small. Although the discrete choice literature treats IIA as one general property capturing the relationships within a set of items across all subsets, we develop our analysis in a way that makes it possible to discuss restricted notions of IIA, where we may only test IIA as it applied to a given collection of choice sets. As discussed earlier, if a discrete choice task only involves choices from, e.g., sets of size two and three, we are not really concerned with violations of IIA that may involve specific pathological sets of size seventeen. In developing minimax lower bounds that are collection-specific, we can ask what limitations may exist (what the sample complexity is) for testing these specific types of violations of IIA. In short, this framework lets us investigate limits on “problem-relevant irrationalities”, setting aside the overwhelming number of ways a person can be irrational without relevance for a given problem. For the specific case of pairwise comparisons, the lower bound furnished by our analysis is rather mild, scaling linearly in the number of items. We also study a particular cyclical comparison structure we dub the single big cycle, which results in lower bounds that are entirely “dimension-free”. Our lower bound can therefore be seen as optimistic in the cases of certain comparison structures: rationality is much easier to test if you restrict the number of irrationalities it is up against.
We organize the paper as follows. In Section (ref), we introduce the discrete choice problem setting by defining primitives that jointly capture the statistical and combinatorial aspects of the problem. Along the way, we formally describe the Independence of Irrelevant Alternatives (IIA), and characterize discrete choice settings that violate it. In Section (ref), we introduce the quantity central to the fundamental limits of testing IIA---the minimax risk---and state the paper's main result. In Sections 4 and 5, we develop the foundational lemmas that underlie this main result, constructing first a test that is statistically simpler than a test for IIA, and then proving a lower bound on the difficulty of the simpler test. We combine these lemmas in Section 6 to prove the paper's main result. Finally, in Section 7, we explore consequences of the result, taking advantage of the structure-dependent aspects to identify testing scenarios where the lower bounds furnish particularly pessimistic and optimistic perspectives.
To analyze the IIA testing problem, we require several new perspectives on how to encode the structure of a decision maker's behavior (IIA or not) as a mathematical object. The standard object of study for analyzing the discrete choices of an agent is the collection of probability distributions that describe an agent's choices over every subset of a universe of alternatives, together with the separate probability distribution that controls the frequencies of which sets are being queried. As a first step, in Section (ref) we introduce a new perspective on this union of objects as a single constrained high-dimensional discrete (i.e., categorical, multinomial) distribution. With this perspective, we are then able to define the property of satisfying IIA as a set of (non-linear) constraints on this high-dimensional object.
A second perspective that we introduce in Section (ref) is the idea of a comparison graph that captures the structural richness of $\mathcal{C}$, the collection of unique comparison sets in the dataset of interest. This comparison graph can capture the structure of arbitrary sets with arbitrary sizes, and differs from the standard study of “comparison graphs” from pairwise comparisons ford1957solution. We take this new perspective because properties native to this graph---chiefly, the average cycle length and a concept we term the {\it cycle dispersion index}---map directly to the fundamental limitations of testing IIA for a given collection $\mathcal{C}$.
Let $\mathcal{X}$ be a finite set of $n$ items with generic element $x \in \mathcal{X}$, and let $\mathcal{C} \subseteq 2^\mathcal{X}$ denote the observed space, a collection of $m \geq n$ unique unordered subsets $C \subseteq \mathcal{X}$ of size 2 or greater. A decision maker who is presented with a choice set $C \in \mathcal{C}$ chooses one item from the set. We let $P_{x,C}$ denote the probability that $x$ is chosen from $C$, $\forall x \in C$, and let $w(C)$ denote the probability of seeing choice set $C$, $\forall C \in \mathcal{C}$. The object $\mathcal{C}$ should be treated as a sample frame---the regime of sets of interest, or the regime of sets for which a notion of error is important---determined ahead of time (as opposed to being defined in terms of the sets so far observed in some dataset). That is, we are operating in a fixed-design setting, where $\mathcal{C}$ does not depend on, e.g., prior observations.
Our test is focused on a given dataset $\mathcal{D}_N = \lbrace (x_j, C_j) \rbrace_{j=1}^N$ that results from a decision maker making choices: a datapoint $j$ represents a decision scenario, and contains $C_j$, the choice set provided in that decision, and $x_j \in C_j$, the item chosen from that choice set. We assume each datapoint is an independent sample from the joint distribution over choices sets and choices:
That is, a datapoint is a sample from some discrete distribution over $d$ possible (choice, choice set) pairs, where $d = \sum_{C \in \mathcal{C}} |C|$. We refer to this $d$-dimensional discrete distribution as a choice system and denote it using $q$. Let $\mathcal{P}_\mathcal{C}$ denote the collection of all choice systems on the collection $\mathcal{C}$, i.e., the collection of all $d$-dimensional discrete distributions. The (choice, choice set) tuples $(x,C)$ can be used to intuitively index this distribution, so we will generally use $(x,C)$ in place of $1,\ldots,d$ when addressing a specific position in a specific choice system $q$.
Our definition of a choice system differs from Falmagne's falmagne1978representation,barbera1986falmagne related definition of a {\it system of choice probabilities} $\{P_{x,C}\}_{\forall C \subseteq \mathcal X, \forall x \in C}$. Our definition of a system explicitly includes the probability distribution over sets, $w(C)$, $\forall C \in \mathcal X$, which Falmagne's concept does not. Falmagne's definition can be thought of as studying choices separated from an exogenously defined collection of choice sets. Further, because our choice systems are built to span only observed $C \in \mathcal{C}$, under our definition all choice systems have a positive set probability $w(C)>0$ for all $C \in \mathcal{C}$. Without the assumption that $w(C)>0$ for all $C \in \mathcal{C}$, the worst case error of any test of IIA would be trivially large, since it has no chance of measuring a violation of IIA within a set $C$ that it can not observe.
The Independence of Irrelevant Alternatives (IIA) assumption constrains the probabilities $P_{x,C}$ to satisfy the following ratio for any $C \subset \mathcal{X}$:
As derived by Luce in luce1959individual, the IIA assumption consequently admits what Luce called a ratio representation,
for some $\gamma \in \mathbb{R}_+^n$. Clearly, $\gamma$ is scale invariant. Setting a scale such that $\sum_{z \in \mathcal{X}} \gamma_z = 1$ gives the interpretation that $\gamma_z = P_{z, \mathcal{X}}$. That is, this interpretation says that an IIA choice system can be described by just knowing $w(C)$, $\forall C \in \mathcal{C}$, and $P_{x,\mathcal{X}}$, $\forall x \in \mathcal X$.
We let $\mathcal{P}^{\text{IIA}}_\mathcal{C} \subset \mathcal{P}_\mathcal{C}$ denote the collection of all choice systems that satisfy IIA. Essentially, then, where $\mathcal{P}_\mathcal{C}$ is the space of all $d$-dimensional discrete distributions, $\mathcal{P}^{\text{IIA}}_\mathcal{C}$ is a family of (non-linearly) constrained $d$-dimensional discrete distributions. We emphasize that $\mathcal{P}^{\text{IIA}}_\mathcal{C}$ is non-convex, and that the convex hull of $\mathcal{P}^{\text{IIA}}_\mathcal{C}$ is dense in $\mathcal{P}_\mathcal{C}$; the latter fact we show in the appendix (Fact (ref)).
Let $\mathcal{M}_{\delta,\mathcal{C}} \subset \mathcal{P}_\mathcal{C}$ denote the set of non-IIA choice systems that are $\delta$-separated, in total variation distance, from the set of IIA choice systems $\mathcal{P}^{\text{IIA}}_\mathcal{C}$, for a given collection of choice sets $\mathcal C$:
Intuitively, $\delta$ describes the size of the indifference zone lehmann2005testing between the null and the alternative hypothesis, beyond which false acceptance becomes a serious error and ought to be limited. Since IIA and “not IIA” denote two contiguous sets, the separation makes the division of parameters sharp, and helps define the following testing problem, the central problem of this work:
Given the hypotheses in (ref), we define a test $\phi$ as a map, $\phi : \{ (x_1,C_1),...,(x_N,C_N) \} \mapsto \{0,1\}$ from the dataset to a decision to reject the null $H_0$. Our choice of total variation to define the separation of the testing problem is motivated by the distance metric's natural interpretation as describing the maximal gap in probability between two distributions over all possible events. Moreover, the choice is aligned with many other recent analyses of testing for discrete distributions paninski2008coincidence,wei2016sharp,valiant2017automatic and thus enables a direct comparison of the difficulty of testing IIA with the difficulty of testing other properties such as identity or monotonicity.
Several other measures of distance for the separation, e.g., Hellinger distance or Kullback-Liebler divergence, may also be reasonable acharya2015optimal,daskalakis2018distribution. The Hellinger distance metric is closely related to total variation distance and has been shown in certain testing scenarios to produce rates identical to those resulting from total variation distance daskalakis2018distribution. We conjecture this is also the case for the IIA testing problem, and leave such an exploration for future work. The Kullback-Liebler divergence is a weaker measure of separation; although it has been shown to lead to trivial (infinite) minimax risk when used in general problems of identity testing in discrete distributions, this concern does not arise for the case for IIA testing\footnote{Whereas in identity testing, two distributions can be arbitrarily close while having infinite KL divergence, the KL divergence to the closest point within IIA is always upper bounded by a finite quantity strictly decreasing with total variation distance.}. The measure is, however, unusual and difficult to interpret. As stated before, consider the $d$-dimensional uniform distribution and distributions $\epsilon$ far away in total variation distance; the KL divergence is $\mathcal{O}(d)$ larger than the TV distance when the distributional difference lies within a constant number of entries (as opposed to being spread evenly across all of the entries). For these reasons, we focus on total variation distance in this work.
To represent the comparison structure imposed by $\mathcal{C}$, we consider an undirected bipartite graph $G_\mathcal{C}$ with $n$ nodes for each item in $\mathcal{X}$ and $m$ nodes for each set in $\mathcal{C}$. Edges in this graph are drawn from the item nodes to the set nodes to indicate membership. That is, the nodes corresponding to each $C \in \mathcal{C}$ have edges extending to the items contained in $C$. This bipartite graph can also be thought of as representing a hypergraph with $n$ nodes, one for each item in $\mathcal{X}$, and $m$ hyperedges, one for each set in $\mathcal{C}$. The graph $G_\mathcal{C}$ is then the incidence graph of this hypergraph, and contain $d$ edges. As a result we call $G_\mathcal{C}$ the {\it comparison incidence graph}, to avoid confusion with other objects called comparison graphs in the study of pairwise comparisons ford1957solution,negahban2016rank.
Throughout this work, we will assume that $G_\mathcal{C}$ is connected, meaning that there is a path in the bipartite graph from every item $i$ to every item $j$.
This assumption corresponds to the necessary and sufficient condition for inference of an IIA choice system first established for pairs by Ford ford1957solution and later more generally by Hunter hunter2004mm. Moreover, we note that the requirement that $m \geq n$, stated earlier, is a sufficient condition on $\mathcal{C}$ to guarantee that there are cycles in $G_\mathcal{C}$\footnote{The necessary and sufficient condition to guarentee cycles in a connected $G_\mathcal{C}$ is $d \geq m + n$. Though our analysis still applies in this regime, we prefer the stronger condition $m \geq n$ to produce shorter analyses and cleaner expressions at the cost of sharpness when $m < n$.}. As we shall see, cycles are critically important: a $G_\mathcal{C}$ without cycles corresponds to a collection $\mathcal{C}$ for which all choice systems are IIA, rendering a test for IIA meaningless.
We call a decomposition of $G_\mathcal{C}$ into a set of $s$ simple cycles a {\it cycle decomposition}, and denote a cycle decomposition by $\sigma$. We define two functions of $\sigma$ that appear in the lower bound: $\mu(\sigma) = \frac{d}{|\sigma|}$, the average cycle length of cycles in the decomposition and $\alpha(\sigma) = \frac{1}{d}\sum_{\sigma_i \in \sigma} |\sigma_i|^2$, the cycle dispersion index\footnote{Although the index of dispersion traditionally refers to a ratio of variance and mean, we abuse the term slightly here to refer to a ratio of the cycle lengths' second moment and the cycle lengths' mean.} of cycles in the decomposition. We will elaborate on these terms further in Section (ref).
For simplicity of presentation of the results and proofs, for the remainder of this work we only consider the special case of collections $\mathcal{C}$ for which $|C|$ is even, $\forall C \in \mathcal{C}$, and where every item appears an even number of times across the subsets in $\mathcal{C}$. Under this restriction, we note that every node in $G_\mathcal{C}$ (on both sides of the bipartite graph) has even degree. As a consequence, $G_\mathcal{C}$ is Eulerian, which will be critical for our analysis. We note that a graph $G_\mathcal{C}$ with odd degrees can be made Eulerian by removing simple paths between odd-degree nodes. While we do not explicitly extend our lower bounds beyond $\mathcal C$ for which $G_\mathcal{C}$ is Eulerian, a modest exercise in bookkeeping relaxes the requirement of even set sizes and even item appearances.
Given a dataset $\mathcal D_N = \lbrace (x_j, C_j) \rbrace_{j=1}^N$ of choices, consider the testing problem, as stated in (ref), of the IIA property against the alternative of an arbitrary choice system that is $\delta$-separated from IIA. We seek to lower bound the minimax risk of this testing problem. The maximum risk of any test $\phi$ is a useful quantity that demonstrates how poor the test could be at finding IIA violations without further prior knowledge about the structure of the violations. Because tests can provide high power over certain types of violations while providing no power over others, it provides a level standard of comparison across tests by studying each test's worst case scenario balakrishnan2018hypothesis.
A minimax lower bound then bounds the error of the best possible test in its worst case, from below. The bound is given as a function of the number of samples $N$, the separation $\delta$ between the null and the alternative, and problem parameters. It is a statement about the fundamental possibility (or limitation) of effective tests for the testing problem. A lower bound on the minimax risk can also be restated as a lower bound on the sample complexity---the number of samples required to achieve a probability of error for a given separation---and equivalently, as a lower bound on the testing radius---the separation required to perform a test with a certain probability of error given a specific number of samples.
The minimax risk $R_{N,\delta}(\mathcal{P}^{\text{IIA}}_\mathcal{C})$ of the IIA testing problem, where risk is used in a uniform sense between the null and the alternative, is then
where the $\inf$ is taken over any test $\phi$. The testing radius $\delta_N(\mathcal{P}^{\text{IIA}}_\mathcal{C})$ is then be defined as
where $a$ is any constant less than $1/2$ (sometimes arbitrarily set to $a=1/3$). The testing radius describes the smallest size of indifference zone that allows hypotheses to be uniformly distinguishable with probability $1-a$. Finally, the sample complexity $N_\delta(\mathcal{P}^{\text{IIA}}_\mathcal{C})$ is defined similarly as
For both the sample complexity and testing radius quantities, we at times use $\smallrel\gtrsim$, followed by a expression, to denote that the quantities scale at at least a constant times that expression. As an alternative objective to lower bounding the minimax risk $R_{N,\delta}(\mathcal{P}^{\text{IIA}}_\mathcal{C})$, we provide in the appendix (Section (ref)) a reformulation of risk bounding as a problem centered around level-$\alpha$ tests, with the corresponding parallel statement to the risk-centered Theorem (ref) given below.
Given the preliminaries involved in defining our test and the concepts of minimax risk introduced above, we can now state our main result. We briefly interpret the result, but the proof of the theorem (given in Section (ref)) follows only after we go through two major steps: relaxing our test to a simpler test (Section (ref)) and introducing lower bounds on properties of the relaxed test (Section (ref)).
Examining the lower bound, it is clear that if the quantity $\frac{8\mu(\sigma)^4\alpha(\sigma)N^2 \delta^4}{d}$ is small, the minimax risk is bounded away from 0, and no uniformly consistent test exists. Keeping the quantity small then immediately determines a lower bound on the scaling, up to constants, of the testing radius and sample complexity.
The dependence of the lower bound on the comparison incidence graph properties $\mu(\sigma)$ and $\alpha(\sigma)$ is a feature unique to the IIA testing problem not found in previous general testing problems with discrete distributions. As we will illustrate more clearly in Section (ref), we find that for well-behaved, uniform, and dense comparison incidence graphs (e.g., for the collection of all pairwise comparisons), both $\mu(\sigma)$ and $\alpha(\sigma)$ can be set to constants independent of other problem parameters (and then incorporated into a constant $c$).
We will further show, through an extremal analysis, that $\mu(\sigma)$ and $\alpha(\sigma)$ are at most $2n$ for any comparison incidence graph, and approximately $c \log(n)$ for sufficiently dense comparison incidence graphs, where $n$ is the number of alternatives and $c$ a constant. This analysis yields a global lower bound on the minimax risk, one we state as a corollary to the main theorem in Section (ref), that replaces $\mu(\sigma)$ and $\alpha(\sigma)$ in the risk lower bounds with expressions only in terms of $n$ and $d$.
Although our main lower bound broadly addresses the question of testing IIA for a given collection $\mathcal{C}$, IIA is often defined in the discrete choice literature as a single property of the complete choice system of $n$ items. By this definition, any true test of IIA must encompass all subsets of an item universe, a setting where $d = n 2^{n-1}$. For this case, we obtain the following bound, derived in Section (ref): $$ R_{N,\delta}(\mathcal{P}^{\text{IIA}}_\mathcal{C}) \geq \frac{1}{2} - \frac{1}{4}\Big(\exp\Big(\frac{c \log(n)^5N^2 \delta^4}{n2^{n-1}} \Big) - 1\Big)^{\frac{1}{2}}, $$ with associated testing radius $\delta_N(\mathcal{P}^{\text{IIA}}_\mathcal{C})$ and sample complexity $N_\delta(\mathcal{P}^{\text{IIA}}_\mathcal{C})$ that scale as at least $$ \delta_N(\mathcal{P}^{\text{IIA}}_\mathcal{C}) \smallrel\gtrsim \frac{n^{\frac{1}{4}}2^{\frac{n}{4}}}{\log(n)^{\frac{5}{4}}\sqrt{N}}, \ \ \ \ N_\delta(\mathcal{P}^{\text{IIA}}_\mathcal{C}) \smallrel\gtrsim \frac{\sqrt{n}2^{\frac{n}{2}}}{\log(n)^{\frac{5}{2}}\delta^2}.$$ The sample complexity demonstrates that testing IIA, when treated as a general property of a choice system, requires at least samples exponential in the number of items $n$. We can thus conclude that testing IIA, when treated as a property of a complete choice system, is hopelessly intractable for large collections.
As stated earlier, the flexibility of our main lower bound allows for more refined analyses for specific collections $\mathcal{C}$, and yields room for optimism (that there may exist reasonably efficient tests) in a variety of special cases. Table (ref) shows the specific lower bound for the “all subsets” setting, in addition to highlighting these special cases where alternative arguments about $\mu(\sigma)^4\alpha(\sigma)$ can be applied to the general bound. Section (ref) gives a detailed derivation and discussion of these settings.
Rather than directly considering the IIA test stated in (ref), we will now take two concrete steps to introduce an analytically simpler test that is not statistically harder than the IIA test. By lower bounding the minimax risk of the simpler test, we obtain a lower bound on the harder IIA test. Two relaxation steps now follow, the first of which restricts $H_0$ to a single element of $\mathcal{P}^{\text{IIA}}_\mathcal{C}$, the uniform distribution $p_0$, and the second of which restricts $H_1$ from $\mathcal{M}_{\delta,\mathcal{C}}$ to a carefully constructed assortment of perturbations of $p_0$ that we can show all reside in $\mathcal{M}_{\delta,\mathcal{C}}$.
For the first simple step, consider the testing problem:
where $p_0$ is the uniform distribution, $p_{0,(x,C)} = 1/d, \forall (x,C)$ (recalling that each discete distribution is $d$-dimensional, where $d$ is the sum of the cardinalities of the choice sets in a given $\mathcal C$). Since $p_0 \in \mathcal{P}_0$, the problem is simpler than the original problem, and any lower bound on the performance of this problem carries over to the original problem of interest.
Now consider a discrete distribution $q_{b,\epsilon}$ that is a perturbation of the uniform distribution of the form:
That is, $b$ perturbs the uniform distribution such that there is no net translation over any set, or over all of the appearances of an item over sets. Our goal is to construct perturbations $q_{b,\epsilon}$, selecting $\epsilon$ and $b$ that land in $\mathcal{M}_{\delta,\mathcal{C}}$, meaning they are at least $\delta$ away (in TV distance) from $\mathcal{P}^{\text{IIA}}_\mathcal{C}$ but at the same time still correspond to valid probability distributions (i.e., within the $d$-simplex). We are starting our journey (in the direction of $b$) at the uniform distribution $p_0$, and we want to show that we always land at least $\delta$ away from {\it any} distribution in $\mathcal{P}^{\text{IIA}}_\mathcal{C}$.
Let $\mathcal{B}_\mathcal{C}$ be any collection of $M=|\mathcal{B}_\mathcal{C}|$ vectors $b$ satisfying the above conditions for the given collection $\mathcal C$. That is,
We define $\bar{q}_\epsilon = \frac{1}{M} \sum_{b \in \mathcal{B}_\mathcal{C}} q_{b,\epsilon}$ as the mixture distribution over the $M$ distributions in $\mathcal{B}_\mathcal{C}$. Samples from $\bar{q}_\epsilon$ would be drawn marginally, that is, some $q_{b,\epsilon}$ would be chosen uniformly from the $M$ possible distributions, and samples would then come from that $q_{b,\epsilon}$. Consider then the testing problem:
The difference between the original test in (ref) and the test in (ref) is illustrated in Figure (ref).
We now wish to identify a (large) set of $q_{b,\epsilon}$ where we can lower bound the distance from each $q_{b,\epsilon}$ back to $\mathcal{P}^{\text{IIA}}_\mathcal{C}$. Our strategy will involve considering $b$ where we can partition the indices into subsets and show that each subset has a lower bound on its contribution to the distance back to $\mathcal{P}^{\text{IIA}}_\mathcal{C}$. We then show that every partition will contribute at least a small distance to the total TV distance from IIA.
\paragraph*{\bf Perturbations and the comparison incidence graph} Consider the undirected bipartite graph $G_\mathcal{C}$ defined in Section (ref), and recall that by assumption every item appears an even number of times across sets in $\mathcal{C}$, and every set is of even size. We then have that every node in $G_\mathcal{C}$ is of even degree---hence, the graph is Eulerian.
Our key step in constructing favorable perturbations $b$ will be to treat the values in the vector $b$ as directing the edges in the undirected graph $G_\mathcal{C}$. Specifically, if $b_{(x,C)} = 1$, the edge is directed to be from the item-node for item $x$, to the set-node for set $C$, and if $b_{(x,C)} = -1$ the edge has the opposite direction. We now restate the sum constraints on a $b$ vector:
These constraints can be interpreted as requiring the in-degree of each node in $G_\mathcal{C}$ to equal its out-degree. We then observe that finding vectors $b$ that satisfy these constraints is equivalent to finding {\it Eulerian orientations} of the graph $G_\mathcal{C}$. Thus, $\mathcal{B}_\mathcal{C}$ is simply any collection of $M$ vectors that each correspond to a unique Eulerian orientation of $G_{\mathcal C}$. While there can be many Eulerian orientations of $G_\mathcal{C}$, our hope is to work with a specially structured collection $\mathcal{B}_\mathcal{C}$ such that the $q_{b,\epsilon}$ can be shown to land in $\mathcal{M}_{\delta,\mathcal{C}}$ for all $b \in \mathcal{B}_\mathcal{C}$.
\paragraph*{\bf Cycle decompositions and orientations of Eulerian bipartite graphs} To find a structured collection of Eulerian orientations of $G_\mathcal{C}$, we begin by examining the cycle decompositions of $G_\mathcal{C}$. We first raise the simple fact that every Eulerian graph can be decomposed into edge-disjoint simple undirected cycles. We remind the reader that we call a decomposition of $G_\mathcal{C}$ into a set of $s$ simple cycles a {\it cycle decomposition}. There are ostensibly many different ways to select edge-disjoint cycles of $G_\mathcal{C}$, and we denote the collection of all possible edge-disjoint cycle decompositions of $G_\mathcal{C}$ by $\Sigma_{\mathcal{C}}$.
A cycle decomposition $\sigma \in \Sigma_\mathcal{C}$ is a set of cycles forming a feasible edge-disjoint cycle decomposition of $G_\mathcal{C}$, and an element $\sigma_i \in \sigma$ denotes the $i$th cycle in $\sigma$. We use $|\sigma|$ to denote the number of cycles in the decomposition $\sigma$, and $|\sigma_i|$ to denote the length of each cycle. Since all cycles of bipartite graphs have even length, we will write $|\sigma_i|=2k_i$, where $k_i$ is the number of item-nodes in the cycle.
Lastly, observe that we can always find a cycle decomposition of $G_\mathcal{C}$ such that every cycle has size at most $2n$. This observation follows from a simple application of the pigeonhole principle: since $G_\mathcal{C}$ is bipartite, with $n$ item-nodes and $m$ set-nodes, any cycle of length greater than $2n$ must visit some item-node more than once; hence the cycle is not simple, and can be decomposed into two smaller edge-disjoint cycles.
\paragraph*{\bf From cycle decomposition to perturbations} We generate a structured collection of perturbation vectors $b$ by generating many distinct Eulerian orientations of a given cycle decomposition $\sigma$. We can independently direct the edges in each of the cycles in $\sigma$ in one of 2 directions (clockwise or counterclockwise), and all of these collections of directions correspond to valid $b$ vectors. Thus, we have found $M=2^{|\sigma|}$ different Eulerian orientation for $G_\mathcal{C}$, each with a one-to-one correspondence to a valid perturbation vector $b$.
We define $\mathcal{B}_\mathcal{C}(\sigma)$ as the {\it specific} collection of perturbation vectors $b$ that orient a cycle decomposition $\sigma$, refining our generic definition of such collections of perturbations $\mathcal{B}_\mathcal{C}$ in Equation (ref):
Here $(x,C)$ indexes the elements of the vector $b$ and we use $\ell$ to index sequential edges in a cycle $\sigma_i$. For each perturbation vector $b \in \mathcal{B}_\mathcal{C}(\sigma)$, we can construct a discrete distribution $q_{b,\epsilon}$ as described previously. We additionally define $\mu(\sigma) = \frac{d}{|\sigma|}$, the average cycle length.
\paragraph*{\bf Bounding separation} For any cycle decomposition $\sigma$ and its corresponding collection of vectors $b \in \mathcal{B}_\mathcal{C}(\sigma)$, with corresponding distributions $q_{b,\epsilon}$, we obtain the following result.
Now, we can focus on lower bounding the performance of the simplified hypothesis test of IIA given in (ref), using Le Cam's method yu1997assouad as a starting point. Using $\gamma(\mathbb{P}_0, \mathbb{P}_1)$ to denote the average of type I and type II errors of the best possible test for distinguishing between the binary hypotheses $\mathbb{P}_0$ and $\mathbb{P}_1$ defined in equation (ref), a testing inequality owed to Le Cam yu1997assouad states that
Thus, the minimax risk for the testing problem (ref) has a lower bound, and since that testing problem is simpler than the original problem, we have a minimax lower bound for the original problem. That is,
What remains is meaningfully upper bounding $||\mathbb{P}_0 - \mathbb{P}_1||_{\text{TV}}$, the total variational distance between the hypotheses, in terms of the parameters of interest.
Consider that
where
If we can upper bound the $\chi^2$ distance between the two hypotheses, we then have an upper bound on the total variational distance.
We obtain the following bound between the uniform distribution $p_0$ and our mixture of perturbations $q_{b,\epsilon}$, decomposed into two lemmas. The first lemma covers the aspects of the bounding exercise that are statistical, while the second lemma covers aspects that engage with the combinatorial structure of our set of perturbations derived from Eulerian orientations of the comparison incidence graph. In each case a low upper bound of the $\chi^2$ distance provides a high lower bound of the minimax risk of the IIA test.
Recall that $\mathcal{B}_\mathcal{C}$, defined in Equation (ref), is more general than $\mathcal{B}_\mathcal{C}(\sigma)$, defined in Equation (ref). The former set is not required to have any connection to a cycle decomposition and its orientations.
The remaining analysis applies only to sets of perturbations $\mathcal{B}_\mathcal{C}(\sigma)$ derived from an Eulerian orientation $\sigma$ of $G_\mathcal{C}$. With such a collection of perturbations, we can bound the role of $b^Tb'$ for each pair of perturbations. Recall that $\mathcal{B}_\mathcal{C}(\sigma)$ was defined in (ref) as the collection of $2^{|\sigma|}$ Eulerian orientations associated with a particular cycle decomposition $\sigma$. We now additionally define a set of vectors $\mathcal{A}_\mathcal{C}(\sigma)$, such that for every element $b \in \mathcal{B}_\mathcal{C}(\sigma)$, $\mathcal{A}_\mathcal{C}(\sigma)$ contains a vector $a \in \lbrace -1, 1\rbrace^{|\sigma|}$ to denote the directions of the $|\sigma|$ cycles that created $b$. Moreover, we introduce for every $\sigma$ a quantity $\alpha(\sigma) = \frac{1}{d} \sum_{\sigma_i \in \sigma}|\sigma_i|^2$ that serves as a normalized measure of the “dispersion” of the cycle decomposition $\sigma$. With this notation, we proceed to the following result.
We now use Lemma (ref) and (ref) to prove the main result in Theorem (ref).
We state the following risk bound for arbitrary $\mathcal C$ as a corollary, using our best arguments for bounding $\mu(\sigma)^4 \alpha(\sigma)$ for general $\mathcal C$ in terms of $d$ and $n$, though note that for specific $\mathcal C$ better bounds are possible, as discussed further in Section (ref).
It is worthwhile to briefly unpack the expressions for $\mu(\sigma)$ and $\alpha(\sigma)$ that result in the rather complex lower bound of Corollary (ref). Noteworthy is the $\min$ that appears in both expressions. The term results from the limitations of what can be said about cycle decompositions for general bipartite graphs. On one hand, the pigeonhole principle guarantees that for all comparison incidence graphs $G_\mathcal{C}$, cycles can be of size at most $2n$. Hence for Eulerian graphs we can ensure that the average cycle size $\mu(\sigma)$ and the cycle dispersion index $\alpha(\sigma)$ are each always at most $2n$.
A cycle size that is linear in $n$ is, however, unsatisfying for denser bipartite graphs, where we would expect cycles to be considerably smaller than $2n$. For the denser bipartite graphs, Lemma (ref) in the Appendix reveals that most cycles are indeed of order $\log(n)$, but a (often small) fraction of cycles will be of order $n$. This statement is tight for bipartite graphs. When $d$ is very large (generally, more than order $n^2$), such as the “all subsets” case we discuss in Section (ref), the fraction of order-$n$ cycles becomes negligible, and both $\alpha(\sigma)$ and $\mu(\sigma)$ can be upper bounded by some constant times $\log(n)$. However, when $d$ is very small, the graph is sparse and a majority of the cycles are order $n$, and the order $n$ terms dominate the expressions. The complex expressions of $\alpha(\sigma)$ and $\mu(\sigma)$ seek to precisely document how the transition from majority length-$n$ cycles to majority length-$log(n)$ cycles happens as the graph gets more dense, in terms of $d$ and $n$. The complexity then carries over to final risk bound, but also renders it useful for a wide range of scenarios.
As a closing remark, and a preview into the next section, we note that the above reduction to a global lower bound, though illustrative in a scenario where $d$ is exponential in the size of $n$, falls short for when $d$ is smaller. Consider instead the $\mathcal{C}$ that consists of all pairwise comparisons, for $n = 6x+1$ for any natural number $x$; following an elementary result of Kirkman kirkman1847problem,bollobas1986combinatorics, the graph $G_\mathcal{C}$ corresponding to such a $\mathcal{C}$ is Eulerian and can always be decomposed into cycles of size 6, making both $\alpha(\sigma)$ and $\mu(\sigma)$ constants. We elaborate on these different cases in greater detail in the following section.
We find it fruitful to leave both $\alpha(\sigma)$ and $\mu(\sigma)$ as a part of the lower bound; it renders the lower bound sharper, but also provides guidance for experimental design. Suppose $\mathcal{C}$ were chosen in a particular experiment, where the experimenter seeks to discover violations of IIA with a limited sample budget $N$. Our lower bound demonstrates the minimum worst case probability of error for any test for violations of IIA given a budget of samples $N$, but is clearly dependent on the choice of $\mathcal{C}$. The presence of a sample budget creates an essential trade off: while the experimenter would like to broaden the scope of her test, attempting to study more choice sets where IIA could be violated, adding sets to $\mathcal{C}$ would increase the minimum error of any tester---perhaps beyond an acceptable threshold. The minimum error can increase in two ways: due to the resulting increase in $d$ from the additional sets, but also due to the changes in $\alpha(\sigma)$ or $\mu(\sigma)$ from the changing structure of the comparison incidence graph $G_\mathcal{C}$. We use this setting---one of seeking to maximize coverage of choice sets given a fixed number of samples and risk threshold---to motivate a closer inspection of our lower bound.
Before we proceed, we note that while comparing our lower bounds across different $\mathcal{C}$, we omit a discussion of the mild differences in behavior of the separation $\delta$ across various $\mathcal{C}$. One difference, a consequence of Lemma $\ref{lemma:seperation}$, is that $\delta$ can be at most $(2\mu(\sigma))^{-1}$ and therefore loosely depends on both the support size $d$ and the cyclicality of $G_\mathcal{C}$. We omit this discussion, and more generally omit subscripting $\delta$ to not stray from the total variation distance metric's setting-independent property as the maximal gap in probability between any two distributions. Our omission is consistent with other analyses of testing paninski2008coincidence,wei2016sharp,valiant2017automatic, and consistent with the idea that $\delta$ is regarded as a small value kept as close to zero as allowable by the practical constraints of dimension and sample size.
IIA is defined as a property of the complete choice system of $n$ items, and hence, any true test of IIA must encompass all the subsets of an item universe. We thus focus first on the results of our lower bound on this problem instance. We again consider the slightly easier setting amenable to our analysis where we only study (all) subsets of even size. Over the unique even subsets of a choice system, a simple calculation reveals that every item then appears the following number of times,
which is always an even number. Hence, the resulting comparison graph is Eulerian, and our lower bound applies with $d=n2^{n-2}$. Given the sheer size of $d$, we do not lose much in the flavor of our statement by using the upper bounds for $\alpha(\sigma)$ and $\mu(\sigma)$ from Lemma (ref). In fact, since $d$ is exponentially large in $n$, the expressions for both $\alpha(\sigma)$ and $\mu(\sigma)$ can be upper bounded by $c \log(n)$ where $c$ is some constant\footnote{This argument is detailed in Corollary (ref), a corollary of Lemma (ref), in the Appendix.}. We then have the following lower bound for the setting of all subsets of even size, and consequently, a lower bound for the setting of all subsets\footnote{Conveniently, $d=n2^{n-1}$ for the case of all subsets (even or odd sizes), and we can use this value in our lower bound as it is within a constant factor of $d=n2^{n-2}$ for the all even subsets case.}:
That is, the best possible test for IIA has worst case error arbitrarily close to $1/2$---the error of a random guess---until the number of sample is exponentially large in $n$.
The result is insightful because it brings to light a special concept: although IIA is simple to represent, in order to test whether a choice system obeys IIA, the test must also consider every possible way a choice system can violate IIA in order to produce a meaningful certificate. Missing even one of those violations results in a test with arbitrarily large error in the worst case where the deviation is represented by that particular violation. Moreover, the number of deviations from IIA are not just numerous, but also close to IIA distributions in a statistical sense, thereby requiring an immensely large number of samples to guarantee a low probability of error.
Because IIA is a property about a combinatorial system, its conceptual simplicity does not aid in distinguishing it from the myriad of combinatorial alternatives. This point is our main takeaway: even the simplest, most storied theoretical concept in discrete choice is practically impossible to test for.
In light of this pessimistic result, we proceed to take a more defensive, practical viewpoint. In most practical settings, violations of IIA are not sought after in any choice set as much as choice sets of meaningful relevance. Often in practice, choice sets do not exceed a modest fixed size (e.g., pairs or triplets). Moreover, there may be sparsity even among the set of small choice sets, as practical constraints prevent the comparison of all items. In these settings, a practitioner does not ever care to test the combinatorially many different violations of IIA, but rather only cares about a restricted set of violations possible on the given choice sets. In other words, a choice system should only be regarded as deviating from IIA if it deviates within the sets of interest; else, a failure to reject is tantamount to the choice system obeying IIA.
Consider then the setting where $\mathcal{C}$ is restricted to only contain (all possible) pairs. This setting, sometimes called pairwise comparisons, is prevalent in discrete choice and most commonly found in match-up modelling in sports or games. In match-ups, for instance, the relevant violations of IIA are certainly restricted to pairs: sets of three do not have any meaning. Given a collection $\mathcal{C}$ of all possible pairs of a universe of $n$ items, we observe that an item appears $n-1$ times over all of the unique choice sets in the collection, and so $d=n(n-1)$. Hence, when $n$ is odd, $d$ is even, and then $G_\mathcal{C}$ is Eulerian (since all pairs are already of even size). We divide up the odd $n$ into three different cases, $n=6x+1$, $n=6x+3$, and $n=6x+5$ where $x$ is any natural number. As previewed earlier, by a result due to Kirkman kirkman1847problem, in the case of $n=6x+1$, $G_\mathcal{C}$ can always be decomposed into edge disjoint cycles of size $6$. The same argument applies to the $n=6x+3$ case. We come about this result by considering first a graph on $n$ nodes $H$ with undirected edges between two nodes compared in a choice set in $\mathcal{C}$. We note that every triangle in $H$ then maps uniquely to a cycle of size $6$ in the bipartite graph $G_\mathcal{C}$, containing both the items in the vertices of the triangle in $H$, as well as the vertices corresponding to the choice sets those comparisons were made in. Since $\mathcal{C}$ contains all pairwise comparisons, $H$ is the clique $K_n$, and Kirkman's result that $K_n$ cliques can be decomposed into edge-disjoint triangles when $n=6x+1$ and $n=6x+3$ is equivalent to $G_\mathcal{C}$ being decomposed into cycles of size 6. As a result, $\alpha(\sigma) = 6$, a term that can be swept into the constant $c$.
Then, for $n=6x+5$, separate prior work shows that $H$ can almost be decomposed into triangles, but $4$ edges remain feder2012packing. Since the nodes of $H$ have even degree, the removal of all the triangles still leaves all the nodes with even degree. Thus, the remaining edges form a cycle, and hence map to a cycle of size $8$ in $G_\mathcal{C}$. Thus, $\alpha(\sigma) = 6 + \frac{16}{d}$, which can again be upper bounded by a constant and swept into $c$. Thus, for the setting of all pairs with $n$ odd, we have the lower bound,
As we would expect, our lower bound is considerably more optimistic in this setting. Indeed, the number of samples $N$ only need to be on the same order as the number of items $n$ for our lower bound to fall away. This mild scaling demonstrates the value of restraining the sets of interest to just the pairs. While one cannot say anything about deviations from IIA beyond the pairs when looking only a pairwise data, such a restriction provides great advantages in sample efficiency.
We lastly consider a specialized $\mathcal{C}$ consists of only pair comparisons that form a simple “cycle” among the $n$ items: e.g. $\{i,j\}, \{j,k\}, \{k,l\}...\{z,i\}$. Here, $d = 2n$. We note that for this setting, the upper bound on $\alpha(\sigma)$ of $2n$ is sharp; that is, the only simple cycle decomposition of $G_\mathcal{C}$ is $G_\mathcal{C}$ itself, and hence $\alpha(\sigma)$ is no smaller than $2n$. We similarly have $\mu(\sigma)$ = $2n$. We then have, for this setting, a lower bound of:
That is to say, our lower bound falls away fast, regardless of $n$. Indeed, as written, the lower bound falls away faster for larger $n$; this errant behavior, however, we conclude comes largely from a likely lack of sharpness in characterizing the projection distance for a simple cycle in Lemma (ref), a possible area of improvement that we will leave for future work. Ignoring this added factor of $n^4$ contributed by $\mu(\sigma)$, we still see a rate falling off independent of $n$ or $d$.
This lack of a pessimistic lower bound translates to a cause for optimism, and a guideline for experimental design. In settings of highly limited samples, with an experimenter that can choose the $\mathcal{C}$ for which to allocate those samples, our lower bound “suggests” choosing a simple cycle for the allocation. In a choice system rife with deviations from IIA, most cycles would contain some of these violations. The benefit of allocating samples to only these cycles, as opposed to a greater number of sets such as all pairs, however, is a low rate of test error. That is, our lower bound guarantees that with a very small number of samples, the setting of “all pairs” will necessarily have high error for any test. In the setting of the “single big cycle”, however, our lower bound does not provide such a pessimistic result; should the test reject, an experimenter could be more confident of the accuracy of the rejection, and still achieve the overall goal of detecting deviations from IIA. Should it not, the experimenter would at least know to seek out different sets to test for violations. By restricting the test to a cycle in these low sample scenarios, a researcher trades a result guaranteed to be errant for a more conservative result likely to be veritable, and is therefore no worse off. This insight is one major deliverable from our structure-dependent finite sample analysis.
Unlike an observational study, where $\mathcal{C}$ and $w(C)$ are taken as given, it is not unrealistic in experimental design for both to be chosen. In this section, we have so far considered the benefit of carefully choosing $\mathcal{C}$. By potentially also choosing $w(C)$, however, an experimental can potentially allocate samples to every choice set in $\mathcal C$. At first glance, it may appear that our lower bounds do not apply for some well-chosen predetermined $w(C)$. Crucial to our bound is the reduction of the general IIA test (ref), which encompasses all IIA choice systems in the null (and hence, all $w(C)$), to the test of (ref), which considers only the uniform choice system in the null. For the uniform choice system, $w(C) = \frac{|C|}{d}$, a weight proportional to the size of each $C$. The testing reduction is valid because $\eqref{eq:iiatest}$ contains all $w(C)$ within its null. For a fixed $w(C)$, specifically, a $w(C) \neq \frac{|C|}{d}$, the validity of the reduction to test (ref) is no longer immediately obvious. The matter of a fixed $w(C)$ invokes a deeper question: are our lower bounds, and their associated pessimism, a result of $w(C)$ not being fixed?
Fortunately, our lower bounds apply regardless of whether $w(C)$ is chosen or not. Consider first that $w(C)$ has no bearing at all on whether a choice system is IIA. Next, observe that the lower bounds in this paper are “minimax”, studying only the worst case scenario for every tester $\phi$. Finally, note that all of the $\mathcal{C}$ studied so far form $G_\mathcal{C}$ that are Eulerian, which have exact cycle decompositions. A consequence of this property is that every entry within a choice system is part of some cycle, and hence can be part of some deviation from IIA. Because we only bound a test's worst case error, any potential direction of exit is a cause for concern as it may contribute to the worst case error. What is, then, the easiest $w(C)$ for testing IIA for the settings of this work? A $w(C)$ that prioritizes every entry of the choice system (and hence, every avenue of IIA departure) equally. This is a $w(C)$ proportional to size of each $C$, the $w(C)$ of (ref)'s uniform choice system. Were $w(C)$ not entry-wise proportional, then there would be some entry with less than uniform weight, and hence the worst case for that testing problem would now be strictly harder. Because $w(C) = \frac{|C|}{d}$ is the easiest $w(C)$, a problem with a fixed $w(C)$ could only be harder. Thus, our lower bounds carry over to those settings.
We develop a structure-dependent finite sample lower bound on the minimax risk of all hypothesis tests for IIA. A first consequence of this bound is rather grave: no general test for IIA can provide a meaningfully small worst case error without a number of samples exponential in the number of items. Our methods, however, provide more than just pessimism: by characterizing the lower bound for a wide range of $\mathcal{C}$, we demonstrate the value of “researcher priors”. Indeed, a prior that IIA violations lie only in the set of pairs vastly reduces the complexity of our lower bound. By incorporating the combinatorial structure of $\mathcal{C}$ into our testing problem, we gain further insight into the sample efficiency of specific structures. As a case study, we consider the optimism hinted by a rapidly diminishing “dimension-free” lower bound for the special case of a cycle, a feature reminiscent of the complexity of property testing for cyclicality.
While the IIA model is well specified, the complexity of a testing problem is dependent on both the complexity of the model class, as well as the complexity of possible departures. Research priors can limit the set of possible departures from IIA, and provide valuable performance improvements. With this perspective, we briefly assess the function of a widely used existing test for IIA, the Hausmann-McFadden test hausman1984specification. With this test, the proposal is to split a dataset and study two scenarios---the maximum likelihood IIA distribution with and without the presence of an item. Such a split may be viewed through the lens of two-sample hypothesis testing, where the question concerns whether the two scenarios produce the same distribution or whether they do not. The Hausmann-McFadden test is {\it not} a general test for IIA. Rather, it may be viewed as testing whether a single item $i$ (the item being removed) changes the IIA projection. Viewing the Hausmann-McFadden test in this lens demonstrates its potential merit---the implicit prior imposed by the test does not seem immediately unreasonable, but its value should be verified empirically. Such a view also defines the tests' limitations; there are many ways of violating IIA that preserve total orderings with and without a single item.
In contrast to the Hausmann-McFadden test, the universal logit test mcfadden1977application, a likelihood ratio test comparing the MNL model to an arbitrary choice system, is a general test for IIA that is asymptotically valid. However, the accuracy of the universal logit test depends on an accurate estimate of a choice system, which requires samples on the same order as $d$. As expected, this sample complexity exceeds the lower bound in this paper for general tests for IIA, which is (up to log factors for dense $\mathcal{C}$) samples on the same order as $\sqrt{d}$. The performance of the universal logit test and the requirement of our lower bound thus form a wide gap between sufficiency and necessity.
Akin to the Hausmann-McFadden test's implicit prior, yet another notion of a prior stems from a valid model for departures from IIA. Such “model-based” tests are scant in the field of discrete choice, for the main reason that the models themselves are often uninterpreble, inferentially intractable, or both. Hausman and McFadden originally proposed a model-based test centered around nested logit model in their early work on testing IIA hausman1984specification. A test against a nested logit model requires the specification of a candidate nesting, much as the Hausmann-McFadden test requires the specification of an item for removal. This high-dimensional specification requirement can be a tall order. Furthermore, inference for the nested logit model can be very difficult benson2016relevance. Recent work on model-based testing proposes the context-dependent utility model (CDM) seshadri2019raw, a model capable of modelling departures from IIA in terms of a “pairwise dependence on irrelevant alternatives” (and departures from the class of random utility models (RUMs) more generally), while still exhibiting ease of optimization (a convex likelihood), tractable finite-sample uniform convergence guarantees, and parametric efficiency. A good model can serve as an excellent platform for principled testing of departures from IIA, with the obvious limitation that departures in the blindspots of the model will remain untested.
We do not propose any new tests in this work---only lower bounds on the sample complexity of the best possible tests. We hope that our lower bound results, with proof techniques that harness the structure-dependent boundary between IIA and more general choice systems in the finite sample domain, can open the door to new constructive tests that test IIA rigorously and efficiently, perhaps even optimally (fully allowing for the possibility that our lower bounds may not be tight). Our sublinear sample complexity lower bound seems to place the IIA testing problem at the intersection of property testing and sublinear algorithms. Much progress has been made at this intersection very recently due to the considerable attention it has received from the statistics, information theory, and theoretical computer science communities. The wide availability of recent results and the immense practical importance thus makes the pursuit of a sublinear IIA testing procedure especially attractive.
Indeed, discrete choice has no shortage of important questions that are similarly ripe for study, especially with regards to testing properties (sometimes called axioms) of choice data. We briefly discuss the idea of testing regularity, RUM-representability, and strong stochastic transitivity. Regularity asks whether the probability of choosing an alternative from a choice set is non-decreasing if the choice set is strictly enlarged. Regularity is perhaps the most studied property of RUMs, and a test is akin to a test of monotonocity for a set function. Another example takes a step beyond regularity, a procedure which asks whether a choice system is {\it RUM-representable}\footnote{As shown by Falmagne, regularity conditions are the first set of conditions that form the larger set of Block-Marschak inequalities block1959random that fully characterize RUMs.}. Though first posed as a testing question by Falmagne falmagne1978representation, this question continues to elude researchers. Recent work jagabathula2018limit provides a complete structure-dependent characterization of the algorithmic difficulty of estimating RUMs, but does not discuss any statistical difficulties, or testing. Another important challenge would be to develop an efficient procedure for testing {\it strong stochastic transitivity (SST)}, which asks whether a choice system can be determined simply by a total ordering over the items. SST remains crucial to a lasting legacy of empirical work davidson1959experimental,mclaughlin1965stochastic, tversky1969substitutability; though estimating a model that satisfies SST is well characterized chatterjee2015matrix,shah2016stochastically, the testing question remains largely unexamined. We thus hope that our work invites not only a rigorous rethinking of the IIA testing question, but also opens the door more broadly to a rigorous rethinking of testing in discrete choice.