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.
43,989 characters · 14 sections · 13 citation commands
Column Generation Algorithms for Nonparametric Analysis of Random Utility Models
In a recent paper "Nonparameteric Analysis of Random Utility Models", kitamura2012 (henceforth KS) develop a test for nonparametric testing of Random Utility Models (RUM). They test the hypothesis that a repeated cross-section of demand data might have been generated by a population of rational consumers. A practical implementation of this test leads to a challenging computational problem. The linear program proposed by mcfadden1990 is extended with a quadratic objective function, minimizing the Euclidean distance. In effect, the minimum distance between a vector and a cone in a high-dimensional space is calculated. This quadratic program must be solved to compute the test statistic and for each bootstrap replication for the simulation of the critical value. This quadratic program is large, with one variable for each rational choice type. The number of such types rises exponentially with the number of choice situations, and even identifying all types is time consuming. In fact, this is the main limiting factor in KS's implementation. \\
The computational problems handled in this paper are similar to those encountered in the study of random utility models in binary choice settings where rational choice types are represented by strict linear orders over the choice alternatives block1960. Specifically, cavagnaro2014 calculates Bayes factors, a measure for model comparison, for the random utility model. Calculating these factors requires numerous checks to test whether a vector lies inside a polytope. In effect, they test whether the Euclidean distance is equal to zero. For small datasets, inequalities are known describing the polytope, but these descriptions grow quickly with the number of choice alternatives and no full description exists for eight or more choice alternatives Marti2011ch. smeulders2018COR propose algorithms capable of handling larger datasets, by making use of an adaptation of the linear program of mcfadden1990. As in the current paper, the large number of rational choice types, and thus variables in the linear program, makes solving the complete model inefficient. By transforming the problem into an optimization problem, through which the point in the polytope minimizing the Manhattan-distance to the vector is found, a column generation approach can be applied. Informally, a column generation approach makes use of the fact that optimal solutions to optimization problems with large numbers of variables, but relatively few constraints, have optimal solutions that only use a relatively small number of variables. A column generation approach starts with a limited number of variables, and identifies new ones as needed through a separate optimization problem, and thus circumvents the problem of having to identify all rational choice types.\\
In this paper, we will use some of the same ideas. We propose a column generation approach for the Euclidean distance calculation. Furthermore, we note that the tightening procedure in KS is incompatible with column generation, as it requires knowledge of all rational choice types. To overcome this obstacle, we show that a slight modification to the procedure is possible to remove this requirement. To show the practical benefit of the column generation algorithm, we re-analyze the empirical application of deb2017revealed(henceforth DKSQ). To increase computation speed, we develop heuristic algorithms to generate interesting rational choice types for this setting. We show the computational improvements make it possible to study much longer budget sequences.\\
The paper unfolds as follows. In section (ref), we briefly describe the Random Utility Model (RUM). Section (ref) lays out the test described in KS, with a focus on the computational problem of calculating the test statistic. Next, in section (ref) we describe a column generation algorithm, which we use to more efficiently compute the test statistic. Section (ref) describes how to handle the tightening of the cone in a manner that is consistent with column generation. An empirical application is contained in Section (ref). We first describe the particular model tested in DKSQ. Next, we show how to implement the general column algorithm for this setting. Finally, we show the computational benefits of our approach.
We briefly describe the RUM in a discrete choice setting. KS handle a continuous choice setting, as does the application by DKSQ, but both rely on discretization to make testing possible. Consider the set $\mathcal{X}$ of all discrete choice options, we denote individual choice options by $x_i$. Let $u: \mathcal{X} \rightarrow \mathbb{R}$ denote a utility function. For simplicity, we assume $u(x_i) \ne u(x_j)$ for all $i, j \in \mathcal{X}, i \ne j$. A choice situation $t$ is characterized by a subset of the discrete choice options, denoted $\mathcal{X}_t \subseteq \mathcal{X}$. A rational actor with a utility function $u$ then picks choice option $x$ satisfying
We furthermore denote the choice option $x$ chosen in situation $t$ by $x(t)$.\\
Given the discrete nature of the choice options, there is a finite number of ways an actor can choose over all situations. We characterize a choice type, indexed by $r$, by the choices she makes in each choice situation. Specifically, we encode a choice type $r$ as $\mathbf{a}_r = (a_{r,1,1}, \ldots, a_{r,T,|\mathcal{X}|})$, with $a_{r,t,i} = 1$ if choice option $x_{i}$ is chosen in situation $t$ by type $r$ and $a_{r,t,i} = 0$ otherwise. The set of rational choice types $\mathcal{R}$ is the set of all types $r$ for which there exists some utility function $u_r$ such that
Let $P_\mathcal{R}$ be a probability distribution over all rational choice types, and let $p_r$ be the probability of a given choice type. We define the sets $\mathcal{R}_{t,i}$ as the subsets of $\mathcal{R}$ such that $r \in \mathcal{R}_{t,i}$ if and only if $a_{r,t,i} = 1$, i.e. $\mathcal{R}_{t,i}$ is the set of rational choice types which choose $x_i$ in choice situation $t$. Now suppose we observe choices for the given choice situations, with $\pi_{t,i}$ the rate at which option $i$ is chosen in situation $t$.
Before continuing, we would like to highlight the geometric interpretation of Definition (ref). Consider a space, with the number of dimensions equal to the sum of the number of choice options available in each choice situation, over all choice situations. We can interpret $\pi$ as a vector in this space, with $\pi_{t,i}$ the coordinate in the dimension associated with $t$ and $i$. Likewise, the vectors $\mathbf{a}_r$ provide coordinates in each dimension for each rational choice pattern. These vectors describe a convex cone, which we denote by $ \mathcal{C}$
This representation of the cone is called the $V$-representation, as it is based on the vectors defining the cone. Choice probabilities are rationalizable if and only if $\pi \in \mathcal{C}$. \\
Equivalently, there exists a $H$-representation of the cone, based on hyperplanes. Consider the set of hyperplanes $\mathcal{H} = \mathcal{H}^\leq \cup \mathcal{H}^=$. Each $h \in \mathcal{H}^\leq$ divides the space into half-spaces, one of which is the feasible region (which includes the hyperplane), the other infeasible. For each $h \in \mathcal{H}^=$, only the hyperplane itself is the feasible region. The union of these feasible regions is the cone $\mathcal{C}$. Specifically, consider a set of hyperplanes $\mathcal{H}$. For each $h \in \mathcal{H}$, there exist parameters $b_{h,t,i}$ with $\sum_{t}^{T} \sum_{i}^{I_t} b_{h,t,i} c_{t,i} = 0$ describing the hyperplane. Then
In this section, we briefly lay out the test described by KS, focussing on the computational problems that arise when implementing the test. We refer to KS for a more thorough explanation of the test.\\
Let $\hat{\pi}$ be an estimator for $\pi$. KS propose to use the Euclidean distance between the vector $\hat{\pi}$ and the cone $C$ as the test statistic $J_N$. Formally, $J_N$ is the optimum objective value to the problem ((ref))-((ref)). In this problem, $p_r$ denotes the probability associated with type $r$. $s_{t,i}$ denotes the distance, in the dimension associated with patch $i$ on budget $t$, between the linear combination of the types and the estimated choice probabilities $\hat{\pi}_{t,i}$. $N$ is the number of observations over all time periods. Note that if, and only if, $J_N = 0$, $\hat{\pi}$ is stochastically rationalizable in the sense of Definition (ref).
The projection of $\hat{\pi}$ onto $C$ is denoted by $\hat{\eta} = \sum_{r \in \mathcal{R}} p_r \mathbf{a}_r$.
The critical value is computed through a bootstrap procedure, which relies on a tuning paramater $\tau_N$. Given $R$ bootstrap replications with sample frequencies $\hat{\pi}^{*(r)}$ for $r = 1, \ldots, R$, the critical value for $J_N$ is computed as follows.
To compute the tests statistic $J_N$ and to obtain a critical value for it, the problem ((ref))-((ref)) must be solved once, and the problem ((ref))-((ref)) solved $1 + M$ times (once to obtain the $\tau_N$-tightened estimator, and then once for each bootstrap replication). As mentioned by KS, solving these problems is computationally challenging. The straightforward approach implemented by KS requires that each rational choice type $r \in \mathcal{R}$ is first identified (though this must be done only once), and then a large quadratic program must be solved. The number of rational choice types can however rise exponentially with the number of periods considered. This makes the approach by KS computationally costly for moderately sized instances, and makes larger instances impossible. Table (ref) shows the approximate number of rational choice types for different size instances in the application of DKSQ.\footnote{The number of total choice types is calculated exactly, random sampling is used to estimate the ratio of rational choice types to total choice types.}
In the following sections, we describe how these problems can be solved without requiring the identification of all choice types, by making use of a column generation algorithm. In section (ref), we handle the problem ((ref))-((ref)). Problem ((ref))-((ref)) is subtly different, requiring a strictly positive lower bound on the variables $p_r$, associated with the choice types. Solving this problem without identifying all choice types is thus not possible. However, in section (ref) we propose minor changes to the KS-procedure for obtaining the critical value, so that these strictly positive lower bounds are no longer necessary.
We will tackle this problem by making use of a column generation algorithm. Instead of solving ((ref))-((ref)) directly, we will start with a limited version of this problem, using only a small set of its variables. We will call this problem the {\it restricted master}. Given a solution to this problem, we find a hyperplane, separating the vector $\pi$ from the restricted polytope. In a second problem, called the {\it pricing problem} we check whether there exists any point of the full polytope on the side of $\pi$ of the separating hyperplane. If no such point exists, we show the solution to the restricted master is also a solution to ((ref))-((ref)). If such a point does exist, we add the corresponding variable to the restricted master and (re-)solve this problem. Such an approach to computing the distance between a point and a polytope, by iteratively taking into account additional vertices of a polytope, is originally described by wolfe1976. Wolfe does make use of an exhaustive list of vertices of the polytope, which is impractical given the large number of vertices in our application. cadoux2010 extends this to a setting without an exhaustive list of vertices. \\
Let us look at the proposed algorithm step-by-step. First, we solve problem ((ref))-((ref)) with a restricted set $\bar{\mathcal{R}}$ of $k$ choice patterns. The {\it bar} notation signifies that the variables, sets or solution belongs to a restricted master problem. From the optimal solution to this restricted problem, $\bar{\mathbf{p}}^* = (\bar{p}^*_1, \ldots, \bar{p}^*_k)$ and $\bar{\mathbf{s}}^* = (\bar{s}^*_{1,1}, \ldots, \bar{s}^*_{T,I_T})$, we can construct the Euclidean projection of $\pi$ on the restricted cone $\bar {\mathcal{C}}$. This projection is the vector $\bar{\mathbf{v}}^* = (\bar{v}^*_{1,1}, \ldots, \bar{v}^*_{T,I_T})$ with $\bar{v}^*_{t,i} = \sum_{r \in \bar{\mathcal{R}}_{t,i}} \bar{p}^*_r$. Now consider the characterization of a Euclidean projection on a convex set (in this case the cone $\mathcal{C}$)
Since $\mathcal{C}$ is the set of linear combinations of vectors $\mathbf{a}_r, r \in \mathcal{R}$, we can also state the following result:
Note that $(\hat{\pi}- \mathbf{v}^*) = \mathbf{s}^*$, thus we can rewrite $(\hat{\pi}- \mathbf{v}^*) \cdot (\mathbf{a}_r - \mathbf{v}^*) \leq 0 $ as $\mathbf{s}^* \mathbf{a}_r \leq \mathbf{s}^* \mathbf{v}^*$. Given this result, we can check whether $\bar{\mathbf{v}}^*$ is the Euclidean projection of $\pi$ on $\mathcal{C}$ by solving the following problem:
To answer this question, we solve a different optimization problem, usually referred to as the {\it pricing} problem.
It is clear that if we find an optimal solution to ((ref)), we can easily check whether it satisfies the threshold value $(\bar{\mathbf{s}}^* \bar{\mathbf{v}}^*)$. If the threshold is met, the choice type is added to the set of choice patterns considered in the restricted problem, which is then re-solved. Otherwise, the solution $\bar{\mathbf{p}}^*, \bar{\mathbf{s}}^*$ to the restricted problem is also the optimal solution to the problem considering the full set of choice patterns. \\
Although an optimal solution to ((ref)) is preferable, it is important to note that any $r \in \mathcal{R}$ with $\bar{\mathbf{s}} \mathbf{a}_r \geq \bar{\mathbf{s}}^* \bar{\mathbf{v}}^*$ is sufficient to continue with the column generation. To speed up computation, it can thus be more interesting to quickly find any type $r \in \mathcal{R}$ meeting the threshold than to spend a longer time finding the solution to ((ref)). Algorithm (ref) summarizes the column generation algorithm.
This approach allows us to solve ((ref))-((ref)) with only a fraction of the rational choice types identified, as we will show in the application.
In problems of the form ((ref))-((ref)), there is the additional complication that there is a strictly positive lower bound on $p_r$ for all $r \in \mathcal{R}$. This is incompatible with the column generation algorithm described in the previous section, which only uses a subset of these variables. We work around this problem in two steps. First, we show that for every problem of the form ((ref))-((ref)), with strictly positive lower bounds, there exists an equivalent problem with zero lower bounds which can be solved using the column generation algorithm. If all rational choice types have a strictly positie lower bound, finding this equivalent problem still requires knowledge of all rational choice types. However, we also show that the tightening can be achieved by setting strictly positive lower bounds for only a subset of the rational choice types.
Stating the equivalent problem still requires knowledge of all rational choice types to adjust the right hand side of the constraints. We therefore propose a tightening based on only a subset of the rational choice types.\\
Consider a subset of the rational choice types $\mathcal{R}' \subset \mathcal{R}$, such that for each hyperplane $h \in \mathcal{H}^\leq$, there exists at least one $r \in \mathcal{R}'$ such that $\sum_{t=1}^{T}\sum_{i=1}^{I_t} b_{h,t,i} a_{r,t,i} < 0$. The proof of Lemma 4.1 in KS can be applied to prove the following Lemma.
This result follows immediately from the proof of Lemma 4.1 in KS.\\
Note that identifying the exact distribution of $J_N^{*(m)}(\tau_N)$ is unnecessary, as only the ratio of bootstrap test statistics larger and smaller than $J_N$ is necessary to check whether it falls above or below the critical value. This can be exploited by making use of bounds on the bootstrap test statistics $J_N^{*(m)}(\tau_N)$, to more quickly determine the $p$-value. Specifically, if at any point in the column generation algorithm we can determine, for a given bootstrap repetition, that $J_N^{*(m)}(\tau_N)$ is either strictly larger or smaller than $J_N$, we terminate the algorithm. In this case we save the lower, or respectively the upper bound. This approach saves time, since bootstrap test statistics must not be computed exactly, but the resulting p-values do not change. \\
Calculating a upper bound on the bootstrap test statistic is straightforward. The objective value of the restricted master problem is immediately a upper bound on the objective value of the complete master problem, as any solution to the restricted master is also feasible for the complete master. Since a restricted master is already solved in every iteration of the column generation algorithm, no additional work is required to obtain this upper bound.\\
Lower bounds on the bootstrap test statistic can be obtained based on (optimal) solutions to the pricing problem as follows. Consider a pricing problem ((ref))-((ref)) with objective function $\sum_{t = 1}^{T} \sum_{i = 1}^{I_t} s_{t,i}a_{t,i}$, and let the optimal solution value to this pricing problem be $z^*$. In this case, for each $r \in \mathcal{R}$, we have $\sum_{t = 1}^{T} \sum_{i = 1}^{I_t} s_{t,i}a_{r,t,i} \leq z^*$. Since the cone $\mathcal{C}$ is the set of linear combinations of the vectors $a_r$, this in turn implies that
By solving the following, relatively simple, quadratic optimization problem we thus obtain a lower bound on the bootstrap test statistic.
Note that obtaining this lower bound requires an optimal solution to the pricing problem. This leads to the following trade-off, where using heuristics leads to a more efficient column generation algorithm, with less time spent per iteration. On the other hand, solving the pricing problem to optimality allows us to obtain a lower bound on the test statistic, which may end the column generation algorithm outright. In our implementation, we will only compute the lower bound in iterations for which the pricing problem was solved exactly.
For our empirical application, we use our improved algorithms to replicate the tests performed by deb2017revealed. We first briefly summarize the model tested by these authors in Section (ref). We focus on those aspects that are important to the computational problem of calculating the test statistic and critical value. To apply the general column generation approach described in previous sections to the setting of the application, some customization is required. This is described in Section (ref). \\
Consider a dataset $\mathcal{D} = \{(\mathbf{p}_t,\mathbf{q}_t)\}_{t=1}^T$, with $\mathbf{q}_t \in \mathbb{R}^L_+$ a bundle of $L$ goods bought at price vector $\mathbf{p}^t \in \mathbb{R}^L_{++}$. We are interested in the preference of the consumer over prices. Suppose, that for observations $t$ and $t'$, we have $\mathbf{p}_{t'}\mathbf{q}_t < \mathbf{p}_{t}\mathbf{q}_t$. In this case, the consumer would prefer prices $\mathbf{p}_{t'}$ over prices $\mathbf{p}_t$, since the former allows the consumer to purchase the same bundle of goods, and have (more) money left over to spend in other ways. Formally, we denote $\mathbf{p}_{t'}\mathbf{q}_t <(\leq) \mathbf{p}_{t}\mathbf{q}_t$ by $\mathbf{p}_{t'} \succ_p(\succeq_p) \mathbf{p}_t$. Furthermore, we denote the relation $\mathbf{p}_{t'} \succeq_p^* \mathbf{p}_t$ if there exists a chain of price vector such that $\mathbf{p}_{t'} \succeq_p \ldots \succeq_p \mathbf{p}_t$, and $\mathbf{p}_{t'} \succ_p^* \mathbf{p}_t$ if such a chain exists with at least one $\succ_p$ relation included.
Now consider a augmented utility function $u(\mathbf{q},-\mathbf{pq})$. Note that the utility depends both on the bundle of goods, as well as on the amount of money expended. DKSQ prove the following theorem.
This model can be discretized, which is necessary to employ the algorithms discussed previously. For each period $t= 1,\ldots,T$, the set of possible choices $(\mathbb{R}^L_+)$ is partitioned into subspaces $x_{t,1}, \ldots, x_{t,I_t}$, we use the word “patch" to refer to these elements. This partitioning is such that (1) $\mathbb{R}^L_+ = \bigcup_{i=1}^{I_t} x_{t,i}$ and (2) for all bundles $\mathbf{q}, \mathbf{q}' \in x_{t,i}$ and each other period $t'$, $\mathbf{q}$ and $\mathbf{q}'$ induce the same revealed preference relations, (3) the partition is of minimal size. Analogous to KS and DKSQ, we only consider patches corresponding to strict price preference relations. $\mathcal{X}_t$ denotes the set of patches of periods $t$, while $\mathcal{X}$ is the set of all patches. Note that for each time periods, the number of patches, and thus possible choices we must account for, is now bounded from above by $2^T$.\\
Instead of all possible utility functions, we only consider rational choice types. We encode a choice type $r$ as $\mathbf{a}_r = (a_{r,1,1}, \ldots, a_{r,T,I_T})$, with $a_{r,t,i} = 1$ if the patch $x_{t,i}$ chosen at time $t$ by type $r$ and $a_{r,t,i} = 0$ otherwise. The set of rational choice types $\mathcal{R}$ is the set of all types $r$ for which the chosen patches induce price preference relations satisfying GAPP. We furthermore define the sets $\mathcal{R}_{t,i} := \{r \in\mathcal{R}| a_{r,t,i} = 1\}$. Given that there exists a finite number of patches, the number of rational choice types to be considered is also finite.
In the previous sections, we lay out how the column generation approach can be used to calculate the test statistic and how to handle the tightening procedure. This description is given in a general way, without any reference to a specific setting. In case of the master problem, this is not necessary. Formulation ((ref))-((ref)) can be used for any discrete choice setting. However, the set of rational choice types $\mathcal{R}$ is determined by the setting. The pricing problem ((ref)), must thus also be tailored to it. In this section, we formulate a pricing problem to test GAPP, and discuss ways to solve it efficiently.\\
The binary variable $\alpha_{t,i}$ indicates which patch is chosen on each budget. $\alpha_{t,i} = 1$ if patch $x_{t,i}$ is chosen from $\mathcal{X}_t$, and $\alpha_{t,i} = 0$ otherwise. The binary variables $\rho_{t,j}$ represent the preference relations between $\mathbf{p}_t$ and $\mathbf{p}_j$. If the patch chosen in $\mathcal{X}_t$ induces $\mathbf{p}_t \succ_p\mathbf{p}_j$, then $\rho_{t,j} = 1$, otherwise $\rho_{t,j} = 0$. $X_{t,i,j}$ is a parameter indicating the price preferences induced by the choice of patch $x_{t,i}$, with $X_{t,i,j} = 1$ if $x_{t,i}$ induces $\mathbf{p}_j \succ_p\mathbf{p}_t$ and $X_{t,i,j} = 0$ otherwise.
Constraint ((ref)) ensures exactly one patch is chosen on each budget. Constraints ((ref))-((ref)) ensure GAPP is satisfied for the chosen patches. First, Constraint ((ref)) ensures that if a chosen patch induces a price preference relation ($X_{t,i,j} = 1$), $\rho_{j,t}$ must also be set to one. Constraint ((ref)) makes sure that the $\rho$-variables also reflect the transitivity of the preference relations. Finally, Constraint ((ref)) enforces that the preference relation is acyclic. Together, these constraints enforce that the $a_{t,i}$ variables encode a valid choice pattern that is consistent with GAPP. An optimal solution to this integer program shows whether or not a rational choice type exists that can be added to the master problem, if so, the $a_{t,i}$ variables encode one such type.\\
As mentioned earlier, an optimal solution to the pricing problem is not necessary to advance the column generation algorithm. Any rational choice type for which $\bar{s} a_r \geq \bar{s}^* \bar{v}^*$ can be added to the restricted master problem to obtain a better solution. Since solving the pricing problem to optimality is often computationally costly, we propose to solve the pricing problem using heuristics, which are usually much faster. Only if we can not identify new choice types to add to the restricted master using the heuristic algorithms, will we use exact algorithms. Algorithm (ref) shows how the heuristic and exact approaches work together. In the implementation, we use a {\it best insertion algorithm} LOP adapted for this particular problem. A detailed description of the implemented heuristic can be found in Appendix B.\\
The tightening procedure requires a subset of the rational choice types to be identified a priori. This set $\mathcal{R}'$ can be generated by randomly drawing choice types, testing whether they are rational and then keeping only rational choice types so generated. If the probability that a randomly chosen choice type is rational is low, this approach can be time consuming. To speed up the process, we opted for a semi-random method. In this method, we first randomly generate choice types. Small changes are then made to these choice types to remove violations of rationality. In the application, we set the size of the subset to 1,000 rational choice types. A detailed description of the procedure can be found in Appendix C.
The column generation algorithm described in the previous sections is implemented in C++, and CPLEX 12.8 is used to solve both the quadratic master problem, as well as the exact pricing problems. Computational experiments were run on a computer with a quad-core 2.6 GHz processor and 16Gb RAM. For the first bootstrap iteration, we initialize the set $\bar{\mathcal{R}}$ as an empty set. At the end of each bootstrap iteration, the set $\bar{\mathcal{R}}$ is saved and used as the starting set for the next bootstrap iteration. This approach generally speeds up computation, as good solutions for different bootstrap iterations usually have rational choice types in common, which do not need to be re-generated using these starting sets.\footnote{The set $\bar{\mathcal{R}}$ can become large over time, slowing down computation. If this is the case, it can be beneficial to record how often variables are used in the optimal solution and to periodically remove rarely used variables.}\\
In this section, we discuss the speed-ups that are achieved through the use of various techniques discussed above. Specifically, we iteratively compare the following configurations:
These algorithms are applied to the U.K. Family Expenditure Survey. Table (ref) contains the minimum, maximum and average computation time for these configurations over the different instances for a given number of periods. Computation times were capped at 1 hour (3600 seconds) for each instance.
AS DSKQ report that their current techniques do not allow the testing of more than 8 periods, it is clear that even in the simplest configuration, the column generation algorithm allows the testing of much larger datasets than are possible using the approach by KS and DKSQ. Table (ref) furthermore show the large impact the use of heuristics for the pricing problem and the use of bounds has on total computation time. While the influence is limited for the smaller instances, the addition of heuristics lowers average computation time by almost 60% for the 10 periods instances. For 15 periods, this decrease is nearly 75% for the instances which finished in both configurations. Likewise, the use of bounds to terminate computation earlier speeds up computation considerably, with a decrease in computation time of 35% for 10 periods and nearly 60% for 15 periods. Most of this speed-up is due to the lower bound, though for the 15 periods instances the addition of upper bounds lowered computation times by an additional 12%. While no instances of 20 periods finished within 1 hour, 142 bootstrap iterations were finished for the hardest instance, suggesting all instances could be finished within about 7 hours. For the full 25 periods dataset, 4.25 hours were necessary to complete 100 bootstrap iterations. \\
In the instances we tested, increasing the number of goods generally increased the computational difficulty of the problem. A higher number of goods led to higher numbers of patches, which in turn increased the number of (rational) choice types. Table (ref) clearly shows this. The increased difficulty is also clearly noticeable in the computation times. Whereas the 10 period instances for 3 goods are solved in 27 seconds on average, this was a lower bound for the 4 good, 10 periods instances. For 4 goods, 1 out of 16 instances was not finished within 1 hour, the other 15 took less than 8 minutes on average. 5 Good instances have slightly higher, but comparable, computation times. Due to the higher difficulty of the 4 and 5 good instances, larger instances still take significant amounts of time. For 15 periods, only 6 bootstrap repetitions were complete for the hardest instance, implying about 6 days of total computation time for 1000 bootstraps.
In this paper, we have shown that while the approach to testing random utility models developed by KS and DKSQ is computationally challenging, advanced algorithms allow for tests of far larger datasets. A main ingredient is to avoid complete enumeration of rational choice types, but generate these as necessary. Applying these algorithms to a model of consumption developed by DKSQ and empirical data from the U.K., we show that the model is supported by the data even over longer periods of time.