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.
89,519 characters · 17 sections · 69 citation commands
Approximating Choice Data by Discrete Choice Models
\abstract{ We obtain a necessary and sufficient condition under which random-coefficient discrete choice models, such as mixed-logit models, are rich enough to approximate any nonparametric random utility models arbitrarily well across choice sets. The condition turns out to be the affine-independence of the set of characteristic vectors. When the condition fails, resulting in some random utility models that cannot be closely approximated, we identify preferences and substitution patterns that are challenging to approximate accurately. We also propose algorithms to quantify the magnitude of approximation errors.
Keywords: Discrete choice, stochastic choice, mixed logit, random coefficients, finite mixture. }
Random-coefficient discrete choice models are workhorse models in many empirical applications. These models are commonly used to approximate various preferences and capture rich substitution patterns. However, the exact degree of flexibility and the limitations of the random-coefficient models have not been fully understood.\footnote{An important early work in this direction is mcfadden2000mixed. See the section on related literature for details.} In this paper, we obtain a necessary and sufficient condition under which random coefficient models can approximate the choice behavior generated by any nonparametric random utility model arbitrarily well. Our results suggest that some widely-used empirical models may not be flexible enough to capture important economic quantities, such as substitution patterns. In such instances, we introduce methods to pinpoint preferences that are particularly difficult to approximate with precision. Additionally, we propose algorithms designed to quantify the magnitude of these approximation errors. Our results help researchers assess if the models can capture choice behaviors relevant to the research problem at hand.
We consider the standard setup (e.g. in train2009discrete). Let $J$ be the set of all alternatives. For each alternative $j$, $x_j\in \mathbf{R}^K$ is the vector of characteristics of alternative $j$, where $K$ is the number of explanatory variables. With an {\it additive random utility model (ARUM)}, the choice probability of an alternative $j$ in a choice set $D \subset J$ is given by $\rho(D,j)= \mu(\{\varepsilon| \beta\cdot x_j+\eta_j+\varepsilon_j > \beta\cdot x_l+\eta_l+\varepsilon_l\ \forall l \in D\setminus \{j\}\})$, where $\beta$ is a deterministic vector capturing an agent's preferences, $\eta$ is a vector of {\it fixed effects}, which captures unobserved characteristics of alternatives, and $\varepsilon$ is a random utility shock that follows a probability measure $\mu$.\footnote{In this paper, we assume that $\mu$ is absolutely continuous with respect to the Lebesgue measure and the support is convex.} The class of the ARUMs is general and includes the probit, logit, and nested-logit models as special cases. The {\it random-coefficient} version of the ARUM is defined as follows. The choice probability is given by
where $m$ is a probability measure over $\beta$. In the standard interpretation, the distribution $m$ captures the heterogeneity of preferences among the population of agents.\footnote{Notice that the roles of $\beta$ and $\eta$ are different. The probability measure $m$ is only on $\beta$ but not on $\eta$.} When $\mu$ is an iid type-I extreme-value distribution, then $\rho$ reduces to a {\it mixed-logit model}, which is one of the widely used random-coefficient models.
Given the popularity of the random-coefficient ARAMs, it is important to understand its flexibility and limitations. For this purpose, we obtain a necessary and sufficient condition under which the random-coefficient ARUMs are rich enough to approximate any choice probabilities generated by nonparametric random utility models arbitrarily well across choice sets. For the approximation target, we choose the random utility models, which are defined as probability measures over strict preference rankings over alternatives. We choose this class of models because it is the most general and agnostic class of models assuming individuals' rational behavior. We study approximation {\it across choice sets} because many questions of interest (such as substitution patterns) rely on analyzing behaviors across choice sets. Moreover, choice data across choice sets are widespread, as in conjoint analysis allenby2019economic and demand analysis with multiple markets berry2021foundations.
In our main theorem (Theorem (ref)), we state that the necessary and sufficient condition is the affine-independence of the set $\{x_j \in \mathbf{R}^K| j \in J\}$.\footnote{A set $Y\equiv \{y_1,\dots, y_n\}$ is affinely independent if for any $y_i \in Y$, there exists no real number $\{\mu_j\}_{j \neq i}$ such that $y_i =\sum_{j \neq i} \mu_j y_j$ and $\sum_{j \neq i} \mu_j=1$. A set $Y\equiv \{y_1,\dots, y_n\}$ is affinely independent if and only if $\{y_2-y_1,\dots, y_n-y_1\}$ is linearly independent, where $y_1$ can be replaced by any $y_i$.} To interpret the condition, consider a typical setup, in which a researcher first fixes one probability measure $\mu$ over the shock $\varepsilon$; then the researcher estimates the distribution $m$ over coefficients $\beta$ and the fixed effects $\eta$ after observing a dataset. If the affine-independence condition is satisfied, then the researcher should be able to approximate any given dataset by using some random-coefficient ARUMs arbitrarily well across choice sets. On the other hand, if the affine-independence condition is violated, there exists a dataset generated by a random utility model that cannot be approximated arbitrarily well by any random-coefficient ARUM, no matter which random-coefficient distribution $m$ as well as fixed effects $\eta$ we use. The affine-independence condition is easy to test: the condition is generically equivalent to a further simpler condition: $K \ge |J|-1$, where $|J|$ is the number of alternatives and $K$ is the number of characteristics observed for each alternative.
In many empirical papers, researchers use the mixed-logit models that are linear in the original characteristics and do not contain additional terms such as polynomials. We call such models {\it linear mixed-logit models}. In these papers, we often observe a deviation from the condition $K\ge |J|-1$, resulting in the violation of the affine-independence condition. This means that the linear mixed-logit models may not be rich enough to approximate the true substitution pattern arbitrarily well across subsets of $J$, no matter how one chooses the distribution $m$ and the fixed effects $\eta$.
When the affine-independence condition is violated, our theorem shows that there exists random utility model that cannot be approximated arbitrarily well; moreover, our result implies that this happens because there are strict preference rankings that cannot be approximated arbitrarily well. Given this result, we introduce a tractable method to identify such strict preference rankings: this method can be efficiently implemented through straightforward linear programmings. To further quantify the flexibility of the random-coefficient ARUMs under researchers' consideration, we calculate the approximation error to degenerate stochastic choice funcition corresponding to the strict preference rankings that are challenging to approximate precisely. We also calculate the maximal substitution patterns allowed in the class of random-coefficient ARUMs. To calculate these quantities, we introduce two algorithms. One algorithm is a variant of the greedy algorithm proposed in barron2008approximation. The other algorithm is the EM (Expectation-Maximization) algorithm drawn from dempster1977maximum. The outputs of the algorithms can help researchers identify choice behaviors that are failed to be captured, and researchers can assess whether these behaviors are empirically relevant.
We apply our theorem and the two algorithms to a dataset of fishing-site choices thomson1991results. In the dataset, there are four alternatives (i.e., $|J|=4$) and two characteristic variables (i.e., $K=2$): price $p_j$ and a quality measure $q_j$ of each fishing site. We find that the affine-independence condition is violated with the original characteristics (i.e., $x_j=(p_j,q_j)$) because $K=2 \not \ge 3=|J|-1$. By using our methods, we find that half of the preferences cannot be approximated arbitrarily well. With our two algorithms, we measure the approximation errors to these preferences by the class of linear mixed-logit models. Regardless of the algorithm used, we find that the approximation errors are large. Specifically, the choice probabilities predicted by the closest linear mixed-logit model sometimes deviate from the true ones by over 70 percentage points. Moreover, we identify substitution patterns that cannot be captured well.\footnote{In this context, we define the substitution pattern as the largest increase of the choice probabilities of one alternative when another alternative becomes unavailable.} We find that the class of linear mixed-logit models limits the largest substitution pattern from one alternative to another to be at most $12$ percentage points, no matter how the parameters of the linear mixed-logit models are chosen.
The structure of the paper is as follows. In Section (ref), we introduce the models underpinning our analysis. Section (ref) presents the key theorems of the paper. A sketch of the proof is detailed in Section (ref). In Section (ref), we elaborate on the methodologies employed for measuring approximation errors. Finally, Section (ref) applies our theoretical framework to an empirical context, utilizing a real-world dataset for illustration.
The work most closely related to our paper are dagsvik1994discrete and especially mcfadden2000mixed, who show that any given (nonparametric) continuous random utility model can be approximated arbitrarily well by a mixed-logit model.\footnote{Our result is consistent with their result: heuristically speaking, the result by mcfadden2000mixed corresponds to the case when the researcher use arbitrarily higher order polynomials (i.e., $K \to \infty$), which satisfies our condition that $K \ge |J|-1$.} Nevertheless, there are important differences to note. In particular, our result holds for a much more general class of random-coefficient ARUMs, including but not confined to mixed-logit models. Second, our result is not only sufficient but also necessary. This is crucial given our purpose of clarifying the exact extent of flexibility and limitations of the random-coefficient ARUMs. Moreover, through our condition, our results provide a tight bound on how many parameters we need for an arbitrarily good approximation. Third, the setup of mcfadden2000mixed and our setup differ in that mcfadden2000mixed focus on the case where the set of characteristics is continuous. Hence, neither result implies the other. A recent paper by lu2021pure also studies the extent to which the approximation of a continuous random utility model (i.e., pure characteristics model) is possible by using mixed-logit models.
Another paper closely related to ours is norets2013surjectivity. They study whether ARUMs can represent any stochastic choice (i.e., market shares). However, their analysis focuses on a fixed choice set while our paper studies approximation across various choice sets. Other related papers also focus on a fixed choice set. In particular, berry1994estimating provides an earlier and classical inversion result useful for representing any stochastic choice on a given choice set. athey2007discrete investigate how a rich specification of the unobserved components is needed to represent any stochastic choice function in a fixed choice set.
Our analysis shares some of its spirit with the growing literature that identifies and estimates flexible discrete choice models under minimal assumptions. See, for example, berry2014identification, compiani2022market, and tebaldi2019nonparametric. Despite the similarity in the spirit, our problem is different from the standard econometric problems. We are not concerned with statistical estimation or identification problems, i.e. recovering model parameters in either sampled or population setting. In contrast, our primary goal is to explore the limitations of common modeling strategies within the discrete choice literature: our work focuses on a specification or approximation question rather than identification, estimation, or inference.
In the decision theory literature, there are two interpretations of stochastic choice. The first interpretation is based on the observation that even a single agent may make stochastic choices, as observed in recent experiments (see agranov2017stochastic). The second interpretation suggests that stochasticity arises from unobserved heterogeneity among a population of agents, as typically assumed in the empirical literature. Although our paper aligns with this latter perspective, we know of no research that directly relates to our papers.
Historically, logit models and random utility models have been analyzed extensively ever since Luce59 and block1960random. Recent studies, such as those by ApesteguiaBallester18 and FrickIijimaStrzalecki19, highlight the distinctions in choice behavior between random utility models and logit models.
Furthermore, a few recent studies examine the substitution property in discrete choice analysis. horan_substitution discusses the substitution patterns captured by random utility models. allen2020hicksian analyze aggregate complementarity in latent utility models used in discrete choice.
Set of alternatives: The set of all alternatives is denoted by $J$. $J$ is assumed to be finite.
\noindentChoice sets: Let $\mathcal{D}\subset 2^J\setminus \{\emptyset\}$ be the set of choice sets. Notice that $\mathcal{D}$ can be a proper subset of $2^J\setminus \emptyset$. Unless otherwise noted, throughout the paper we assume that $\mathcal{D}$ contains all binary and ternary choice sets: $\{j, l\} \in \mathcal{D}$ and $\{j,l,r\} \in \mathcal{D}$ for any $j, l ,r\in J$. In a part of the paper (i.e., Section (ref)), however, we drop this assumption and assume that $\mathcal{D}=\{J\}$ when we consider the case in which the researcher's purpose is fitting a model to the observed choice probabilities from the single choice set.
The set $\mathcal{D}$ may contain both observed choice sets as well as hypothetical choice sets the researcher is interested in. For example, even when the researcher observes consumers' choices only over $\{\text{train},\text{bus},\text{car}\}$, he may also be interested in choices over $\{\text{train},\text{bus}\}$, $\{\text{train},\text{car}\}$, and $\{\text{bus},\text{car}\}$ to learn the consumers' substitution pattern.
\noindentExplanatory variables: An alternative $j \in J$ is described by a real vector $x_j \in \mathbf{R}^K$ of explanatory variables, where $K$ is the number of the explanatory variables. For instance, if an alternative $j$ is a consumption good, the alternative may be described by its price $p_j$ and its quality index $q_j$; in that case $x_j=(p_j, q_j)$. Moreover, the researcher can include functions of original characteristics in $x_j$. Empirical applications often include higher order polynomials as well as splines or wavelets chen2007large. For example, with the original characteristics $(p_j,q_j)$ of alternative $j$, the researcher may include higher order polynomials such as $p_j^2,q_j^2, p_jq_j$ in the characteristic vector $x_j$ and can make the number $K$ of characteristic vectors larger. If the researcher includes all terms, then $x_j=(p_j,q_j,p_j^2,q_j^2,p_jq_j)$ and $K=5$.
\noindentStochastic choice function: A function $\rho: \mathcal{D} \times J \to [0,1]$ is called a {\em stochastic choice function} if $\sum_{j \in D}\rho(D,j)=1$ and $\rho(D,j)=0$ for any $j \not \in D$. The set of stochastic choice functions is denoted by $\mathcal{P}$. For each $(D,j) \in \mathcal{D} \times J$, the number $\rho(D,j)$ is interpreted as the probability that an alternative $j$ is chosen from a choice set $D$. In the context of discrete choice analysis, for example, $\rho(D,j)$ can be interpreted as the market share of product $j$ in a market in which the set of available products is $D$. In such cases, we interpret the stochastic choice function $\rho$ as aggregate choice probabilities across individuals.
\noindentRankings: Let $\Pi$ be the set of bijections between $J$ and $\{1,\dots, |J|\}$, where $|J|$ is the number of elements of $J$. For any element $\pi \in \Pi$, if $\pi(j)=i$, then we interpret alternative $j$ to be the $|J|+1-i$-th best element of $J$ with respect to $\pi$. If $\pi(j)>\pi(l)$, then $j$ is better than $l$ with respect to $\pi$. An element $\pi$ of $\Pi$ is called a {\it ranking} over $J$. A ranking describes an agent's strict preference relation.\footnote{Alternatively, a ranking can be defined as a binary relation that is complete, transitive and irreflexive. The relation is often called a linear order.}
For all $(D,j) \in \mathcal{D} \times J$ such that $j \in D$, if $\pi(j)> \pi(l)$ for all $l \in D \setminus \{j\}$, then we often write $\pi(j) \ge \pi(D)$. There are $|J|!$ elements in $\Pi$.
We denote the set of probability measures over $\Pi$ by $\Delta(\Pi)$. Since $\Pi$ is finite, $\Delta(\Pi) = \big\{(\nu_1,\dots, \nu_{|\Pi|}) \in \mathbf{R}_+^{|\Pi|}\big| \sum_{i=1}^{|\Pi|} \nu_i =1\big\}$, where $\mathbf{R}_+$ is the set of nonnegative real numbers.
We now introduce the definition of random utility models:
Notice that when $\mathcal{D}=\{J\}$, the restriction of random utility is vacuous: any stochastic choice function is a random utility model (i.e., $\mathcal{P}_r=\mathcal{P}$).\footnote{To see this, observe that $\mathcal{P}_r \subset \mathcal{P}$ by definition. We show the converse. For any $j \in J$, let $\pi_j \in \Pi$ such that $\pi_j(j) > \pi_j(l)$ for all $l \in D\setminus \{j\}$. Then $\rho^{\pi_j}(l)=1_j(l)$ for any $l \in J$, where $1_j(l)=1$ if $l=j$ and $1_j(l)=0$ if $l\neq j$. (For the definition of $\rho^{\pi}$, see definition ((ref)) in Section (ref).) For any $\rho \in \mathcal{P}$, define $\rho'=\sum_{j \in J}\rho(j)\rho^{\pi_j}$. Then, $\rho' \in \mathcal{P}_r$ and $\rho'(j)=\rho(j)$ for any $j \in J$, as desired. Hence, $\mathcal{P}\subset \mathcal{P}_r$. In general, we have $\mathcal{P}_r\subsetneq \mathcal{P}$ and the random utility models have some testable implication. For example, when $\mathcal{D}=2^J\setminus \emptyset$, random utility models are characterized by the non-negativity of the Block-Marschak polynomials.}
In certain scenarios, researchers might want to exclude rankings deemed unreasonable and restrict the set of rankings. We consider such a case in Section (ref) in the appendix.
In both theoretical and empirical literature, modeling assumptions are imposed to approximate the random utility models. Two important classes are defined as follows. First we introduce one definition.
In the following, we denote the inner product of two vectors $x$ and $y$ by $x \cdot y$.
The set of random-coefficient ARUMs is denoted by $\mathcal{P}_{ra}(\eta|\mu)$ and the set of ARUMs by $\mathcal{P}_{a}(\eta|\mu)$. When the context makes clear which standard probability measure $\mu$ we consider, we do not specify the standard probability measure $\mu$. \\
The term $\beta\cdot x_j$ is the {\it systematic part} of the utility of alternative $j$ captured by the observed characteristics $x_j$. The vector $\beta$ captures preferences of an agent and the distribution $m$ over coefficients $\beta$ describes the heterogeneity of preferences among the population of the agents. The constant $\eta_j$ is called a {\it fixed effect} that captures the utility of alternative $j$ from the unobserved characteristics; $\varepsilon_j$ is the shock to the utility of alternative $j$.
Almost all probability measures used in practice are standard. For a mixed-logit model, $\mu$ is an iid extreme-value type-I distribution; for a probit model, $\mu$ is the multivariate standard normal distribution. Note that in most empirical applications of these models, the mixing distribution $m$ is a parametric distribution like a multivariate normal distribution. In our case, the mixing distributions of the random coefficients do not come from a particular parametric family.
For the exposition later, we define the {\it mixed-logit models} formally as follows:
We give a few remarks on the models. First, we consider the models with fixed effects given their popularity in empirical applications. Fixed effects are used frequently to capture the unobserved characteristics of alternatives berry1995automobile. While there is a common presumption that utilizing fixed effects enables us to depict any behavior generated by the random utility model, we demonstrate that this may not hold when there are multiple choice sets. Each of our results is stated with and without fixed effects.
Second, in the models above, following mcfadden2000mixed as well as many other papers in discrete choice analysis, we write the systematic part of utility by $\beta\cdot x_j$. Although we have a linear structure in the explanatory variables $x_j$, it is important to remember that $x_j$ can be a function of original characteristics such as higher order polynomials of original characteristics as used in the proof of mcfadden2000mixed. Since any continuous function can be approximated by polynomials, our models are general enough to allow for flexible systematic parts of utility functions.
Finally, we review essential mathematical concepts. A {\it polytope} is a convex hull of finitely many points. The closure of a set $C$ is denoted by $\text{cl.} C$ with respect to the standard finite dimensional Euclidean topology. The {\it affine hull} of a set $C$ is the smallest affine set that contains $C$, and it is denoted by $\text{aff.} C$. The convex hull of a set $C$ is denoted by $\text{co.} C$. The {\it relative interior} of a convex set $C$ is the interior of $C$ in the relative topology with respect to $\text{aff.} C$. The relative interior of $C$ is denoted by $\text{rint.} C$.
To state the main result of the paper, we review a basic concept in geometry: A set $\{x_j \in \mathbf{R}^K| j\in J\}$ is {\it affinely independent} if no $x_j$ can be written as an affine combination of the other elements $\{x_l\}_{l \neq j}$. Formally, for any $j \in J$, there exists no real numbers $\{\alpha_l\}_{l \in J\setminus \{j\}}$ such that $x_j =\sum_{l \in J \setminus \{j\}} \alpha_l x_l$ and $\sum_{l \in J\setminus \{j\}} \alpha_l=1$.\footnote{It is easy to see that a set $\{x_j \in \mathbf{R}^K| j\in J\}$ is affinely independent if and only if $\{x_l-x_j\}_{l \in J \setminus \{j\}}$ is linearly independent for any $j$. }
We provide a sketch of the proof in Section (ref) and the formal proof in the appendix.
To interpret the main theorem, consider a typical practice where the shock distribution $\mu$ over $\varepsilon$ is fixed a priori by a researcher; then he or she estimates the distribution $m$ over coefficients $\beta$ as well as the fixed effects $\eta \in \mathbf{R}^{K}$ after seeing a dataset $\rho$ generated from a random utility model.
Statement (i) shows that if the set $\{x_j \in \mathbf{R}^K| j\in J\}$ is affinely independent, then the researcher should be able to approximate the given dataset $\rho$ arbitrarily well across choice sets $D \in \mathcal{D}$ by choosing an appropriate distribution $m$ over coefficients $\beta$. Statement (ii) shows that if the affine-independence condition fails, then there exists a random utility model that cannot be approximated arbitrarily well by any random-coefficient ARUM, no matter how the researcher changes the distribution $m$ over coefficients $\beta$ as well as the fixed effects $\eta$, given the arbitrary chosen standard probability measure $\mu$ over $\varepsilon$. For example, the approximation is impossible using any mixed-logit model nor any random-coefficient probit-model. In Propositions (ref) and (ref) in Section (ref), we will give examples of the random utility models that cannot be approximated arbitrarily well.
The affine-independence condition can be simplified further to a generically equivalent condition. To see this, remember the following basic facts: (i) if $|J|>K+1$, then $\{x_j \in \mathbf{R}^K| j \in J\}$ is not affinely independent; (ii) if $|J|\le K+1$, then the set is generically affinely independent.\footnote{This is a standard concept of genericity in the literature of discrete geometry. Even if the set is not affinely independent, as long as $|J|\le K+1$, for any $\varepsilon>0$, there exists an affinely independent set $X'$, obtained from $X$ by moving each point by a distance of at most $\varepsilon$ (see Section 3 of matousek2013lectures).} Given these observations, Theorem (ref) implies the following corollary:\footnote{One caveat of the result is that even though the generic condition holds, the original condition of the affine independence may not hold when explanatory variables include zeroes and ones. In that case, one should check the affine-independence of $\{x_j \in \mathbf{R}^K|j \in J\}$, rather than the generic condition.}
We now mention a few remarks on the results. First, to understand the results correctly, it is crucial to understand the space that we consider for the approximation. In Theorem 1, we study approximation across coordinates $(D,x)$ such that $x \in D \in \mathcal{D}$, which has very high dimensionality. On the other hand, in Proposition 1 of the following section, we consider a fixed choice set $\mathcal{D}=\{J\}$. Thus the underlying dimension is much smaller.
Second, as mentioned earlier, to increase the number $K$ of explanatory variables, researchers may include additional terms such as higher order polynomials (mcfadden2000mixed) as well as splines or wavelets chen2007large. In their proof, mcfadden2000mixed use higher order polynomials of arbitrarily high degrees to approximate continuous random utility model. In particular, in their construction, $x_j$ is a vector of monomials of any degree of original characteristics $(y_{j1},\cdots, y_{jn})$: \[ x_j=(\underbrace{y_{j1},\cdots, y_{jn}}_{\text{1st order terms}}, \underbrace{y_{j1}^2,\cdots, y_{jn}^2}_{\text{2nd order terms}},y_{j1}^3,\cdots, y_{jn}^3,.... )\in \mathbf{R}^{K}, \] where $K\to \infty$. Their result is thus consistent with the sufficiency part of our result: we proved that $K \ge |J|-1$ is sufficient in our setup.
Finally, in the theorem, following Mcfadden and Train (2000), we consider all possible random utility models (i.e., probability distributions over all rankings) as the prediction target mainly for simplicity. As mentioned after Definition 1, in some cases, the researchers may want to restrict the set of rankings by excluding those deemed unreasonable. In Section (ref) of the appendix, we provide a necessary and sufficient condition for the approximation of the restricted random utility model.
In the following, we provide a supplemental result for the case in which $\mathcal{D}=\{J\}$. Such a case corresponds to a situation in which the researcher is interested only in the observed choice probabilities (i.e., market shares) on a single set $J$ (but not on its subsets).
Note that the convex-independence condition is weaker than the affine-independence condition. This makes sense because the convex-independence condition guarantees the approximation only on the single choice set (i.e., $\{J\}$), while the affine-independence condition guarantees the approximation across all subsets $D \in \mathcal{D}$ of $J$ (including $J$ itself).
The implications of Theorem (ref) and Proposition (ref) are similar. One important difference arises when the conditions (i.e., the affine-independence condition in Theorem (ref) and the convex-independence condition in Proposition (ref)) are violated. In both cases, there exists a random utility model that cannot be approximated arbitrarily well {\it without} using fixed effects. However, as stated in Proposition (ref) (ii)(b), if fixed effects are used, any random utility model can be approximated arbitrarily well on one particular choice set $J$. (This result directly follows from norets2013surjectivity.) This is in contrast to Theorem (ref) (ii), which claims that there exists a random utility model that cannot be approximated arbitrarily well even using fixed effects across choice sets $\mathcal{D}$.\footnote{This difference originates from the fact that we require approximation on all $D \in \mathcal{D}$ in Theorem (ref), while in Proposition (ref), we require approximation only on $J$.}
Unlike the affine-independence, the convex-independence does not restrict the number of elements in a convex-independent set.\footnote{For example, in three-dimensional space $(x,y,z)$, consider a circumference of radius one whose origin is $(0,0,1)$ on a hyperplane of $z=1$. The number of points on the circumference is a continuum. However, the set of points on the circumference is convex-independent. } Thus, there exists no counterpart of Corollary (ref).
In this section, we mention the implications of the theorem and the proposition to the empirical literature. Many empirical papers use the mixed logit models that are linear in original characteristics and do not contain additional terms such as polynomials. We call such models {\it linear mixed-logit models}. In the papers, the convex-independence condition is usually satisfied. That is, it is often the case that any alternative $x_j$ lies outside the convex hull $\text{co.}(\{x_l | l \in J \setminus \{j\})$ of the other alternatives. In fact, we will see this is the case in a real dataset in Section (ref).
On the other hand, the condition that $K \ge |J|-1$ is frequently violated in various contexts, which in turn results in the breach of the affine-independence condition. Remember that $|J|$ is the number of alternatives and $K$ is the number of characteristics. There are many choice situations in which $|J|$ is very large such as choices of groceries, hospitals, cars, schools, or restaurants etc. In such a dataset, the condition is likely to be violated. This means that the class of linear mixed-logit models is rich enough to describe the choice data from a single choice set $J$; however, the class of the models may not be rich enough to approximate the true substitution pattern across choice sets, no matter how one chooses parameters and fixed effects.\footnote{By substitution patterns, in general, we mean how choice probabilities change in different choice sets. In Section (ref), we provide a more specific definition of substitution patterns.}
When the affine-independence condition is violated, there exist random utility models that cannot be approximated arbitrarily well. Our results in Section (ref) show hat this happens because the ARUMs cannot approximate some rankings arbitralily well. In the following, we propose a method to identify such rankings that are difficult to approximate precisely. The following definition is crucial:
The proposition below demonstrates that the failure of the affine-independence condition leads to the existence of unrepresentable rankings, which are exactly the rankings challenging to approximate accurately. To determine the representability of a specific ranking $\pi$, one can employ linear programming techniques.\footnote{The ranking $\pi(1)>\pi(2)>...>\pi(J)$ is representable if and only if the linear programming problem: $\max_{\beta\in \mathbf{R}^K,t\in \mathbf{R} } t$ subject to $\beta\cdot (x_j-x_{j+1})\geq t$ for each $j=1,...,J-1$ has the optimal value $\infty$. If the ranking is unrepresentable, the problem has the optimal value 0.} In Section (ref), utilizing a real dataset, we identify such unrepresentable rankings, as detailed in Table 1 of that section. The identification of these rankings enables researchers to evaluate which substitution patterns are challenging to capture within their models.
Notice that the requirement ((ref)) depends both on the specification of the characteristic vectors $\{x_j\}_{j \in J}$ as well as the set $\mathcal{D}$ of choice sets. The requirement ((ref)) becomes less restrictive as the characteristic vector $x_j$ becomes longer because it becomes easier to find the desired $\beta$ with additional characteristic variables; the requirement ((ref)) becomes more restrictive as the set $\mathcal{D}$ of choice sets becomes richer, simply because the number of inequalities to be satisfied becomes larger. As mentioned earlier, we usually consider the general choice sets $\mathcal{D}$, while in some places, we assume a simpler case in which $\mathcal{D} =\{J\}$. In the rest of this section, we consider the general $\mathcal{D}$. When there is no risk of confusion, we will simply say that a ranking $\pi \in \Pi$ is representable without specifying choice sets $\mathcal{D}$.
To show the proposition, for each ranking $\pi \in \Pi$, define
The function $\rho^{\pi}$ gives probability one to the best alternative $x$ in a choice set $D$ according to the strict ranking $\pi$.
Remember that so far we have assumed no fixed effects (i.e., $\eta=0$). In the following, we consider the case with fixed effects. As we explain in the next section, by using fixed effects, we can approximate any $\rho^{\pi}$. However, when the affine-independence condition fails, there still exist some random utility models that cannot be approximated well. The next proposition provides such random utility models:
Note that if a ranking $\pi$ is representable, then $\pi^{-}$ is also representable. The next proposition shows that when the affine-independence condition fails, approximating a mixture of $\rho^{\pi}$ and $\rho^{\pi^-}$ is impossible even using fixed effects when $\pi$ is not representable.
In this section, we provide a proof sketch. Readers who are not interested in the proofs may skip this section and go directly to the empirical sections (Sections (ref) and (ref)).
We prove Theorem (ref) and Proposition (ref) by using the five lemmas below. (As byproducts, we obtain Propositions (ref) and (ref).) Lemma 1 states a general condition for approximating random utility models with random coefficient ARUMs. Lemmas 2 and 3 translate the condition to a condition on the dimension of characteristics, which is easy to check in practice. Lemma 4 provides a class of random utility models that is hard to approximate even with the help of fixed effects. Lemma 5 states an important geometric insight that appears in the proof of Lemma 4.
We first consider models without fixed effects (i.e., $\eta=0$). The following fact is elementary but fundamental:
Observation: {\it The set $\mathcal{P}_r$ of random utility models is a polytope, that is, $\mathcal{P}_r=\text{co.} \{\rho^{\pi}| \pi \in \Pi\}$.}
The observation holds because for any random utility model $\rho \in \mathcal{P}_r$, we have $\rho = \sum_{\pi \in \Pi} \nu(\pi) \rho^{\pi}$, where $\nu$ is the probability measure on $\Pi$ rationalizing the random utility model. The hexagons in Figure (ref) below illustrate the polytope.\footnote{Although the geometric intuition is useful, it is important to notice that the figure oversimplifies the reality since the number (i.e., $|J|!$) of vertices and the dimension of a random utility model can be very large. To see why the dimension of a random utility model can be very large, remember that it assigns a number for each pair of $(D,j) \in \mathcal{D} \times J$. As mentioned, we calculate the dimension later in Proposition (ref) in Section (ref) of the appendix. }
Lemma (ref) gives a necessary and sufficient condition under which any random utility models can be approximated arbitrarily well by random coefficient ARUMs $(i.e., \mathcal{P}_{ra}(0| \mu))$ without fixed effects (i.e., $\eta=0$). The condition is that $\rho^{\pi} \in \text{cl.} \mathcal{P}_a(0| \mu)$ for any $\pi \in \Pi$, which means that $\rho^{\pi}$ can be approximated by a sequence of ARUMs without fixed effects (i.e., a sequence of elements of $\mathcal{P}_a(0| \mu)$).
The next lemma makes it easier for us to check the conditions of Lemma (ref).
Lemmas 1 and 2 imply the following:
Corollary (ref) offers a testable condition for determining if the random-coefficient ARUMs, without fixed effects, can adequately approximate any random utility model.\footnote{In Section (ref) of the appendix, we provide a generalization of Corollary (ref) for the case in which a researcher wishes to omit certain rankings from their analysis and restrict the set of possible rankings.}
As mentioned earlier, checking the representability of a particular ranking is easy. However, checking the representability of {\it all} rankings may be computationally demanding. This is because the number of rankings equals $|J|!$ and can be large. To overcome this problem, we obtain a simpler necessary and sufficient condition for any ranking $\pi \in \Pi$ to be representable:
To understand Lemma (ref) (1) geometrically, see Figure (ref). In the figure, we assume that there are two original characteristic variables, say $(p_j,q_j)$ for each alternative $j \in J$. In Figure (ref) (a) and (b), we consider the models with the original characteristics (i.e., $K=2$ and $x_j=(p_j,q_j)$ for each $j \in J$). In Figure (ref) (a), the set $\{x_1,x_2,x_3\}$ is affinely independent. Thus, by Lemma 3 (1) (the “if" part), any ranking is representable. For example, the ranking $\pi(1) > \pi(2)> \pi(3)$ is representable by $\beta \in \mathbf{R}^2$, which defines the parallel hyperplanes (indifference curves) in Figure (ref) (a). On the other hand, in Figure (ref) (b), the set $\{x_1,x_2,x_3,x_4\}$ is not affinely independent. The ranking $\pi(1)> \pi(4)> \pi(3)> \pi(2)$ is not representable. As the figure shows, no matter how one chooses $\beta \in \mathbf{R}^2$ and draws parallel hyperplanes as indifference curves, it does not hold that $\beta \cdot x_1 > \beta \cdot x_4 > \beta \cdot x_3> \beta \cdot x_2$. The existence of such an unrepresentable ranking is implied by the “only if" part of Lemma 3 (1).\footnote{The slope of the “indifference" line must be steeper than the slope of the line segment $(x_4,x_2)$ (because $\pi(4)> \pi(2)$) and less steep than the slope of the line segment $(x_4,x_1)$ (because $\pi(1)>\pi(4)$), which together imply that $\beta \cdot x_4>\beta \cdot x_3$.}
If we use ellipses as indifference curves, however, we can represent the ranking $\pi(1)> \pi(4)> \pi(3)> \pi(2)$ as in Figure (ref) (c).\footnote{As the radius of the ellipses becomes larger, the ranking becomes better.} The existence of such curves is again implied by the “if" part of Lemma 3 (1) since ellipses can be defined with the quadratic polynomials $\beta\cdot x_j$ with $x_j=(p_j, q_j, p_j^2, q_j^2, p_jq_j)$. Moreover the generic condition with quadratic polynomials is satisfied (i.e., $K=5\ge 3= |J|-1$ ) in this example.\footnote{In fact, we verified that the affine-independence condition is satisfied with quadratic polynomials.}
Lemma (ref) (2) is more straightforward. To see this, notice that when $\mathcal{D}=\{J\}$, any $\pi \in \Pi$ is representable in $\{J\}$ if and only if, for any $j\in J$, there exists $\beta$ such that $\beta \cdot x_j> \beta \cdot x_l$ for all $l \in J \setminus j$, which means that $J$ is convex-independent. By using Lemmas (ref), (ref), and (ref), we obtain statement (i) of Theorem (ref) and Proposition (ref).
Remember that so far we have assumed no fixed effects (i.e., $\eta=0$). In the following, we analyze the extent to which random utility models can be approximated arbitrarily well by using fixed effects. In particular, we show that if the affine independence condition fails then there exists a random utility model that cannot be approximated arbitrarily well even with using fixed effects.
First, we will see the usefulness of the fixed effects. It is easy to observe that when $\mathcal{D}=\{J\}$, any stochastic choice can be approximated arbitrarily well by using fixed effects.\footnote{This is intuitive since we can choose $|J|$ parameters (i.e., $(\eta_j)_{j \in J}$) to fit $|J|$ data points (i.e., $(\rho(J,j))_{j \in J}$).} Even for general $\mathcal{D}$, the following holds:
\noindentObservation: For any ranking $\pi$, there exists an ARUM with fixed effects that can approximate $\rho^{\pi}$ (i.e., vertices of polytope) arbitrarily well.\footnote{To see this, fix $\pi$ and choose $\eta \in \mathbf{R}^J$ such that $\eta_j>\eta_l$ if and only if $\pi(j) > \pi(l)$. Then, it can be shown that an ARUM $\rho_n$ defined by $\rho_n(D,j)= \mu(\{\varepsilon|n \eta_j+\varepsilon_j \ge n\eta_l +\varepsilon_l\text{ for all }l \in D \setminus \{j\}\})$ converges to $\rho^{\pi}(D,j)$ as $n \to \infty$.}
However, this is not enough to approximate any random utility model arbitrarily well across choice sets. As an illustration, consider two fixed effects, $\eta_1$ and $\eta_2$, and see Figure (ref) below. Remember that in the heuristic figure, the hexagon represents $\mathcal{P}_r=\text{co.}\{\rho^{\pi}| \pi \in \Pi\}$. The two convex sets in the hexagon correspond to $\mathcal{P}_{ra}(\eta_1|\mu)$ and $\mathcal{P}_{ra}(\eta_2|\mu)$ shaded pink and blue, respectively.\footnote{To see this remember that an element of $\mathcal{P}_{ra}(\eta|\mu)$ belongs to $\mathcal{P}_r$ and the set $\mathcal{P}_{ra}(\eta|\mu)$ is convex.} Notice that all vertices in the figure can be approximated arbitrarily well by elements of $\mathcal{P}_{ra}(\eta_1|\mu)$ or $\mathcal{P}_{ra}(\eta_2|\mu)$. However, some areas of the hexagon are not covered by either $\mathcal{P}_{ra}(\eta_1|\mu)$ or $\mathcal{P}_{ra}(\eta_2|\mu)$.
In reality, the problem is more complicated since we need to consider the union of all possible values of fixed effects, and thus the union of the continuum of convex sets $\mathcal{P}_{ra} ( \eta|\mu)$ across all values of $\eta \in \mathbf{R}^{|J|}$.\footnote{More formally, the difficulty arises because the set of all ARUMs with probability measure $\mu$ and with any fixed effects (i.e., $\bigcup_{\eta \in \mathbf{R}^J}\mathcal{P}_{ra}(\eta|\mu)$) may not be convex, although given $\eta$, each set $\mathcal{P}_{ra}(\eta|\mu)$ is convex. This is because mixtures can be taken only over $\beta$ but not over $\eta$. Thus approximating vertices is not enough for approximation over the polytope of random utility models.} Moreover, we need to consider all possible standard probability measure $\mu \in \mathcal{M}$. Nevertheless, Lemma (ref) provides a clear answer and states that if there exists a unrepresentable ranking, then there exists a class of random utility models that cannot be approximated arbitrarily well, no matter which fixed effects and probability distribution we use.
To prove the lemma, we need to prove the following two statements: (a) any strict convex combination between $\rho^{\pi}$ and $\rho^{\pi^{-}}$ cannot be approximated arbitrarily well by a {\it degenerate} ARUM with fixed effects; and (b) moreover it cannot be approximated arbitrarily well by a {\it nondegenerate} random-coefficient ARUM even with any fixed effects. We prove statement (a) in the appendix. To show statement (b), we introduce the following concept:
For example, in Figure (ref), $\rho^{\pi_1}$ and $\rho^{\pi_6}$ as well as $\rho^{\pi_i}$ and $\rho^{\pi_{i+1}}$ for each $i \le 5$ are adjacent and no other pairs are adjacent. Since $\pi$ and $\pi^{-}$ are reversed with each other, $\rho^{\pi}$ and $\rho^{\pi^{-}}$ seem very different. It turns out, however, that they are adjacent:\footnote{Our discussions with Jean-Paul Doignon and Haruki Kono were very helpful for obtaining this result.}
The characterization of adjacency of vertices for the case $\mathcal{D} =2^J \setminus \emptyset$ appears in doignion_adjacency. Lemma (ref) holds even for the case in which $\mathcal{D} \neq 2^J \setminus \emptyset$ as long as $\mathcal{D}$ contains all binary and trinary sets.\footnote{We are grateful to Haruki Kono for pointing out this fact.} The lemma allows us to complete the proof of Lemma (ref) as follows. If $\pi$ is not representable, then $\pi^-$ is also not representable. Although fixed effects are powerful enough to approximate each vertex $\rho^{\pi}$, we will prove that it is not powerful enough to approximate both $\rho^{\pi}$ and $\rho^{\pi^{-}}$ by using the same fixed effects, intuitively because $\rho^{\pi}$ and $\rho^{\pi^{-}}$ are reversed. Thus, no strict convex combination of $\rho^{\pi}$ and $\rho^{\pi^{-}}$ can be approximated arbitrarily well by the random-coefficient ARUMs with standard probability measure $\mu$, no matter which fixed effects we use. Notice that this conclusion does {\it not} follow if $\rho^{\pi}$ and $\rho^{\pi^{-}}$ are not adjacent since a strict convex combination of $\rho^{\pi}$ and $\rho^{\pi^{-}}$ may be represented in a different way. This proves statement (b) and thus, Lemma (ref). Lemmas (ref), (ref), (ref), and (ref) prove statement (ii) of Theorem (ref), as the proof in the appendix formalizes.
Proposition (ref) and (ref) in Section (ref) show that the approximation errors to some random utility models may not be negligible when the affine-independence condition fails. In this section, we provide a way to quantify the approximation errors. We first define the distance function as follows: For any $\hat{\rho},\rho \in \mathcal{P}_r$, define \[ d(\hat{\rho},\rho) \equiv\sqrt{\frac{\sum_{D\in \mathcal{D}} \sum_{j\in D} \left( \rho(D,j)-\hat{\rho}(D,j) \right)^2 }{|\mathcal{D}|}}. \] In our analysis, $\hat{\rho}$ is a given random utility model; $\rho$ is a random-coefficient ARUM by which we approximate $\hat{\rho}$. We divide the norm by $\sqrt{|\mathcal{D}|}$ to make the distance independent from the number of choice sets.\footnote{$d(\hat{\rho},\rho)$ can be written as $\|\rho-\hat{\rho}\|/\sqrt{|\mathcal{D}|}$, where $\|\cdot \|$ is the Euclidean norm (i.e., $l$2 norm). One can consider an alternative distance function based on $l_1$ norm as follows: $d_1(\hat{\rho},\rho)\equiv (\sum_{(j,D) \in J \times \mathcal{D} } |\hat{\rho}(D,j)-\rho(D,j)|)/|\mathcal{D}|$. Since $\sqrt{\sum_{(j,D)\in J \times \mathcal{D}} (\hat{\rho}(D,j)-\rho(D,j))^2} \le \sum_{(j,D)\in J \times \mathcal{D}} |\hat{\rho}(D,j)-\rho(D,j)|$, we can show that $d(\hat{\rho},\rho)/\sqrt{|\mathcal{D}|} \le d_1(\hat{\rho},\rho)$ for any $\rho$ and $\hat{\rho}$. So our approximation error divided by $\sqrt{|\mathcal{D}|}$ will provide a lower bound of an alternative approximation error measured by $d_1$. We use our distance function $d$ rather than $d_1$ because of the convexity of $d$ is useful for constructing an algorithm.} Notice that the maximal distance is $2$. For example, $d(\rho^{\pi},\rho^{\pi^-})= 2$ for any ranking $\pi$.
Given an approximation target $\hat{\rho} \in \mathcal{P}_r$ and a standard probability measure $\mu$, when researchers use random-coefficient ARUMs with fixed effects $\eta$, the approximation error is defined as:
We call ((ref)) the {\it approximation error to $\hat{\rho}$} by random-coefficient ARUMs with fixed effects $\eta$. Proposition (ref) shows that the approximation error to $\rho^{\pi}$ may not be negligible if $\pi$ is not representable. In Section (ref), we find that the approximation error can be large for some unrepresentable rankings in a real dataset.
Given $\hat{\rho}$, we propose two algorithms to solve ((ref)) and compute the approximation errors. The first is the standard EM (Expectation-Maximization) algorithm dempster1977maximum to estimate the best possible finite-mixture logit model. It is known, however, that the EM algorithm may not converge to the global optimum. To alleviate this concern, we propose a second greedy algorithm inspired by barron2008approximation. This algorithm solves a sequence of optimization problems and can be shown to converge to the global optimal solution. The structure of the random-coefficient RUMs is important for the proof. We provide explanations of these algorithms in Section (ref) of the online appendix.
In this section, we measure approximation errors with and without fixed effects by using a dataset on fishing-site choices from thomson1991results.\footnote{The dataset is taken directly from the R package `mlogit' by croissant2020package.} The dataset has been used by herriges1999nonlinear and cameron2005microeconometrics (p.464).
In the dataset, 1182 individuals choose among $4$ fishing modes, namely, $J=\{{\text{beach}}, {\text{boat}},$ ${\text{charter}}, {\text{pier}}\}$, which denote fishing from the beach, a private boat, a charter boat or a pier, respectively. Each alternative $j \in J$ is described by a vector of two characteristics $(p_j,q_j)$. The first characteristic $p_j$ is the fishing mode $j$'s price. The other characteristic $q_j$ is the {\it catch rate}, defined as a per-hour-fished basis for major species by fishing mode $j$.\footnote{In the original study, the values of $p_j$ and $q_j$ depend on each individual. For our analysis, we aggregate them by taking the average over individuals.}
Our empirical analysis concentrates primarily on mixed-logit models. This focus is motivated by the widespread application and acceptance of these models in contemporary research. In particular, we consider two specifications of mixed-logit models. The first one is the linear mixed-logit models, the mixed logit models that are linear in the original characteristics (i.e., $x_j=(p_j,q_j)$ for each $j \in J$). The second one is the mixed-logit model defined with quadratic polynomials (i.e., $x_j=(p_j,q_j, p_j^2, q_j^2, p_jq_j)$ for each $j \in J$). We call the model {\it quadratic mixed-logit model.}
We assume that $\mathcal{D}=2^J \setminus \emptyset$. Propositions (ref) and (ref) in Section (ref) of the online appendix imply that in order to obtain the best approximating random-coefficient model to the observed choice probabilities, it is sufficient to consider finite mixture models with at most $(\dim \mathcal{P}_r)+1=1+\sum_{D \in \mathcal{D}}(|D|-1)=18$ mixtures. See Section (ref) of the online appendix for the details.
The dataset contains four alternatives (i.e., $|J|=4$). If we use original characteristics as explanatory variables (i.e., $x_j=(p_j,q_j)$), then $K=2$ and the condition in Corollary (ref) is violated (i.e., $K=2 \not \ge 3= |J|-1$); thus the set $\{(p_j,q_j)\in \mathbf{R}^2 | j \in J\}$ is not affinely independent. Thus, by Theorem (ref), the linear mixed-logit models with fixed effects is not flexible enough to approximate some random utility models. This observation motivates us to compute approximation errors of the linear logit models without fixed effects (in Section (ref)) and the errors with fixed effects (in Section (ref)).
On the other hand, with quadratic polynomials, the generic condition for representability in Corollary (ref) is satisfied, since $K=5\ge 3=|J|-1$.\footnote{Given the increasing number of characteristic variables, a natural concern is the overfitting problem. We investigate this concern in Section (ref) of the online appendix.} In fact, we verified that $\{(p_j,q_j,p^2_j,q^2_j, p_jq_j) \in \mathbf{R}^5 |j \in J\}$ is affinely independent. Thus, by Theorem (ref), the quadratic mixed-logit models are flexible enough to approximate any random utility model. This theoretical implication is also numerically verified below.
In this section, we detail approximation errors without fixed effects. We say that a ranking $\pi$ is {\it linearly representable} if $\pi$ is representable in $\mathcal{D}$ with $x_j=(p_j,q_j)$; $\pi$ is {\it linearly unrepresentable} if $\pi$ is not linearly representable.
Since the affine-independence condition fails in the dataset with $x_j=(p_j,q_j)$, it follows from Proposition (ref) that there exists a ranking $\pi$ that is linearly unrepresentable. Thus the corresponding deterministic choice functions $\rho^{\pi}$ cannot be approximated by any linear mixed-logit model without fixed effects. Since there are four alternatives, there are twenty four rankings. Among them, we find that twelve rankings are not representable, and thus cannot be approximated arbitrarily well by linear mixed-logit models, as shown in Table (ref).
The table shows the approximation errors of the linear or quadratic mixed-logit models. We calculated the errors by the greedy algorithm and the EM algorithm. In both algorithms, approximation errors for representable rankings $\pi$ shown in the bottom row of the table are always zero, as the theorem predicts. On the other hand, the approximation errors for unrepresentable rankings $\pi$ are almost always larger than $0.4$, which means that even the best possible linear mixed-logit model deviates from the corresponding choice probabilities $\rho^{\pi}$ by $40$ percentage points or more on average. Some errors are much larger. For example, the approximation errors of the two rankings $\pi(1)>\pi(2)>\pi(3)> \pi(4)$ and $\pi(1)>\pi(2)>\pi(4)> \pi(3)$ by the linear models are more than $0.67$. This suggests that the substitution from alternative 1 to 2 would be difficult to capture. To see this notice that these two rankings are the only rankings in which alternative $1$ is the best and alternative $2$ is the second-best. See the next subsection for more detail.
Note that the approximation errors by quadratic mixed-logit models are zero, as shown in columns (4) and (5) in the table. This finding is also consistent with the theorem.
Our attention now turns to substitution patterns. We quantify how flexible the linear mixed-logit models are, by measuring the maximal substitution patterns that can be generated by the models. Specifically, for two alternatives $j$ and $l$, we calculate the following quantity:
Since $\rho$ is a random utility model, we have $\rho(J\setminus\{j\},l) \ge \rho(J,l)$.\footnote{The property is called monotonicity or regularity.} Thus the quantity in ((ref)) can be any nonnegative number that is less than or equal to one. The quantity $\rho(J\setminus\{j\},l)-\rho(J,l)$ describes how consumers would substitute to alternative $l$ if alternative $j$ becomes unavailable. The supremum of such quantities captures the {\it maximal substitution pattern} that can be generated by mixed-logit models without fixed effects.\footnote{The quantity in ((ref)) is always 1 when we can choose fixed effects freely. This is because we can always choose fixed effects large enough to approximate degenerate preferences.} We use the greedy algorithm to solve ((ref)), as detailed in section (ref) of the online appendix.\footnote{We do not use the EM algorithm as it cannot be easily transformed to solve the problem in ((ref)). We note that we can replace the $\sup$ in ((ref)) with $\inf$, for which we calculate the minimal substitution pattern. This problem can also be solved by the greedy algorithm. We omit the detail since the dataset satisfies the convex independence, so the minimal substitution pattern is 0. } conlon2021empirical analyze similar concepts called {\it diversion ratios}, which measure the fraction of consumers who switch their choices from alternative $j$ to $l$ after the price of alternative $j$ increases marginally. Our measure ((ref)) corresponds to the limit of {\it diversion ratios} in which the price of alternative $j$ increases to the infinity.\footnote{Precisely speaking, our measure corresponds to the limit of the numerator of the diversion ratio. Some recent papers study the substitution and complementarity property in the discrete choice analysis. See horan_substitution and allen2020hicksian.}
Table (ref) shows the values of maximal substitution between the two alternatives $j$ and $l$. Some numbers in the table are close to one, which implies that the linear mixed-logit models are rich enough to capture flexible substitution from $j$ to $l$. Some other numbers are smaller. In particular, the maximal substitution between alternative $1$ (i.e., beach) and $2$ (i.e., private boat) as well as the substitution between alternative $3$ (i.e., charter) and $4$ (i.e., pier) are at most $0.3$. In fact, the maximal substitution from $1$ to $2$ is $0.12$. This means that no matter how the parameters of a linear mixed-logit model are chosen, the maximal substitution from alternative 1 to alternative 2 is very limited.
This finding aligns with the result presented in Table (ref), where we observe substantial approximation errors for the two specific rankings: $\pi(1)>\pi(2)>\pi(3)> \pi(4)$ and $\pi(1)>\pi(2)>\pi(4)> \pi(3)$ are very large. In this way, identifying preferences that are hard to approximate with precision helps researchers in evaluating whether their models successfully capture relevant economic behaviors such as substitution patterns.
What remains to be explored is the approximation errors with fixed effects. By using fixed effects, we can approximate $\rho^{\pi}$ for any ranking $\pi$. By Proposition (ref), however, for each unrepresentable ranking $\pi$ and each $\alpha \in (0,1)$, any random utility model in a neighborhood of $\alpha \rho^{\pi}+(1-\alpha)\rho^{\pi^-}$ cannot be approximated arbitrarily well by the linear mixed-logit models with fixed effects. In Table (ref), we show the approximation error to $\frac{1}{2}\rho^{\pi}+ \frac{1}{2} \rho^{\pi^-}$ for each unrepresentable ranking.
In both algorithms, the approximation errors to $\frac{1}{2}\rho^{\pi}+\frac{1}{2}\rho^{\pi^-}$ are always around $0.2$ if $\pi$ is not representable. This means that even the best possible linear mixed-logit model deviates from $\frac{1}{2}\rho^{\pi}+\frac{1}{2}\rho^{\pi^-}$ by $20$ percentage points or more on average.
On the other hand, the approximation errors to $\frac{1}{2}\rho^{\pi}+\frac{1}{2}\rho^{\pi^-}$ are almost zero if $\pi$ is representable, as the theorem predicts. Also, the approximation errors by quadratic mixed-logit models are also almost zero, as the theorem again predicts.
In Section (ref), we applied our theorem and algorithms to a real dataset. The results summarized in Tables 1-3 demonstrate how the affine-independence condition and its generic condition $K \ge |J|-1$ serve as straightforward indicators for evaluating the efficacy of random-coefficient models in approximating random utility models.
When the affine condition is not met, as observed in our dataset utilizing the linear mixed-logit model, our methodology enables the quantification of approximation errors. This quantification is detailed in Tables 1 and 3, where errors are often significant. Furthermore, our analysis extends to assessing the limitations in the substitution patterns generated by random coefficient models, as described in Table 2. Additionally, consistent with the predictions of our theorem, we confirm that all approximation errors are zero (up to rounding errors) when employing quadratic models. We believe that these results provide researchers with useful tools for determining the extent to which a given model accurately reflects choice behaviors.