NONPARAMETRIC ANALYSIS OF RANDOM UTILITY MODELS
YUICHI KITAMURA∗ AND JÖRG STOYE∗∗

arXiv:1606.04819v2 [] 8 Dec 2017

Abstract. This paper develops and implements a nonparametric test of Random Utility Models. The
motivating application is to test the null hypothesis that a sample of cross-sectional demand distributions was generated by a population of rational consumers. We test a necessary and sufficient condition
for this that does not restrict unobserved heterogeneity or the number of goods. We also propose and
implement a control function approach to account for endogenous expenditure. An econometric result of independent interest is a test for linear inequality constraints when these are represented as
the vertices of a polyhedron rather than its faces. An empirical application to the U.K. Household
Expenditure Survey illustrates computational feasibility of the method in demand problems with 5
goods.

1. Introduction
This paper develops new tools for the nonparametric analysis of Random Utility Models (RUM).
We test the null hypothesis that a repeated cross-section of demand data might have been generated
by a population of rational consumers, without restricting either unobserved heterogeneity or the
number of goods. Equivalently, we empirically test McFadden and Richter’s (1991) Axiom of Revealed
Stochastic Preference.

Date: This Version: December 7, 2017.
Keywords: Stochastic Rationality.
JEL Classification Number: C14.
∗ ∗∗

Kitamura acknowledges financial support from the National Science Foundation via grants SES-0851759 and

SES-1156266. Stoye acknowledges support from the National Science Foundation under grant SES-1260980 and through
Cornell University’s Economics Computer Cluster Organization, which was partially funded through NSF Grant SES0922005. We thank Donald Andrews, Richard Blundell, Rahul Deb, Phil Haile, Chuck Manski, Daniel Martin, Rosa
Matzkin, Francesca Molinari, participants at various seminars, and in particular, Elie Tamer and the four referees for
helpful comments. We are grateful to Richard Blundell and Ian Crawford for their help with the FES data. We would
like to thank Whitney Newey in particular for suggesting the use of a control function to account for endogeneity in total
expenditure. All errors are our own. Ben Friedrich, Duk Gyoo Kim, Matthew Thirkettle, and Yang Zhang provided
excellent research assistance.
1

2

KITAMURA AND STOYE

Numerous other, recent papers nonparametrically test rationality, bound welfare, or bound
demand responses in repeated cross-sections. But all such papers that we are aware of have at least one
of the following features: (i) Unobserved heterogeneity is restricted; (ii) the approach is conceptually
limited to an environment with two goods or practically limited to a very small or low dimensional
choice universe; (iii) a necessary but not sufficient condition for rationalizability is tested. The present
paper avoids all of these. It is meant to be the beginning of a research program: Estimation of demand
distributions subject to rationalizability constraints, welfare analysis, and bounds on counterfactual
random demand are natural next steps.
Testing at this level of generality is computationally challenging. We provide various algorithms that can be implemented with reasonable computational resources. Also, we establish uniform
asymptotic validity of our test over a large range of parameter values in a setting related to moment
inequalities but where existing methods do not apply. The technique by which we ensure this is of
independent interest. Finally, we leverage recent results on control functions (Imbens and Newey
(2009); see also Blundell and Powell (2003)) to deal with endogeneity for unobserved heterogeneity
of unrestricted dimension. All these tools are illustrated with one of the work horse data sets of the
related literature. In that data, estimated demand distributions are not stochastically rationalizable,
but the rejection is not statistically significant. Our methods also can be (and recently have been)
applied to substantively different models that share certain core features with the benchmark model
that we now define.
Let

u : RK
+ →R
denote a utility function. Each consumer’s choice problem is characterized by some u, some expenditure level W , and a price vector p ∈ RK
+ . The consumer’s demand is determined as

(1.1)

y ∈ arg

max

0
y∈RK
+ :p y≤W

u(y),

with arbitrary tie-breaking if the utility maximizing y is not unique. For simplicity, we restrict utility
functions by monotonicity (“more is better”), but even this minimal restriction is not conceptually
necessary.

3

We initially assume that W and p are nonrandom, while the utility function u is randomly
drawn according to probability law Pu :1
u ∼ Pu .
Nonrandom W and p are the framework of McFadden and Richter (1991) and others but may
not be realistic in applications. In the econometric analysis in Section 5 as well as in our empirical
analysis in Section 7, we treat W as a random variable that may furthermore covary with u. For the
moment, our assumptions allow us to normalize W = 1 and drop it from notation. The demand y
in equation (1.1) is then indexed by the normalized price vector p. Denoting this by y(p), we have a
collection of distributions of demand
Pr(y(p) ∈ x), x ⊂ RK
+

(1.2)

indexed by p ∈ RK
++ . We initially assume that the distribution of utility functions Pu , i.e. the population being observed, is the same across price regimes. Once W (hence p, after income normalization)
is formulated as a random variable, this is essentially the same as imposing W ⊥
⊥u, an assumption we
maintain in initial analysis in Section 5.1 but drop in Section 5.2 and in our empirical application.
Throughout the analysis, we do not place substantive restrictions on Pu . Thus we allow for minimally
constrained, infinite dimensional unobserved heterogeneity across consumers.
We henceforth refer to (1.2) as a Random Utility Model (RUM).2 A RUM is completely parameterized by Pu , but it only partially identifies Pu because many distinct distributions will be
observationally equivalent in the sense of inducing the same distributions of demand.
Next, consider a finite list of budgets (p1 , ..., pJ ) and suppose observations of demand y from
repeated cross-sections over J periods are available to the econometrician. In particular, for each
1 ≤ j ≤ J, suppose Nj random draws of y distributed according to
Pj (x) := Pr(y(pj ) ∈ x), x ⊂ RK
+

(1.3)
are observed. Define N =

PJ

j=1 Nj

for later use. Then Pj can be estimated consistently as Nj ↑ ∞

for each j, 1 ≤ j ≤ J. The question is whether the estimated distributions may, up to sampling
1To keep the presentation simple, here and henceforth we are informal about probability spaces and measurability.

See McFadden (2005) for a formally rigorous setup.
2Thus, we interpret randomness of u as arising from unobserved heterogeneity across individuals. Random utility

models were originally developed in mathematical psychology, and in principle, our results also apply to stochastic choice
behavior by an individual. However, in these settings it would frequently be natural to impose much more structure
than we do.

4

KITAMURA AND STOYE

uncertainty, have arisen from a RUM. In the idealized setting in which there are truly J budgets,
we show how to test this with minimal further assumptions. Then, to bring the method from this
idealized setting to real data, we introduce some smoothness and also control function assumptions.
The main goals of our paper are as follows. We first show how to test stochastic rationalizability
of a given data set and demonstrate this using the UK Household Expenditure Survey. The adequacy
of the rationality assumption is undoubtedly a fundamental question. Even if we were to eventually
proceed to counterfactual analysis and policy evaluation that often assumes rationality at the basic
level, testing rationality without introducing ad hoc conditions would be a natural and important first
step. Second, once a practical procedure for rationality testing is developed, it can be further used to
obtain counterfactuals and carry out inference about them, once again under minimal assumptions.
Third, this paper offers a new statistical test with broad applicability. While motivated by the
application that we report, this test has already been used for other models as well, namely to a
nonparametric game theoretic model with strategic complementarity by Lazzati, Quah, and Shirai
(2017), to a novel model of “price preference” by Deb, Kitamura, Quah, and Stoye (2016), and
to a test of the collective household model by Hubner (2017). The method is extended to choice
extrapolation (using algorithms from an earlier version of this paper) in Manski (2014) and Adams
(2016); the former also demonstrates that a restriction to linear budgets is not necessary. Indeed,
the only way that the economics of a model affects our inference procedure is through the matrix
A defined later. The rest of the algorithm remains the same if model elements such the standard
revealed preference axiom or linear budget sets are replaced by other specifications, as long as the
overall set of budgets is finite.
The remainder of this paper is organized as follows. Section 2 discusses the related literature.
Section 3 develops a simple geometric characterization of the empirical content of a RUM and presents
algorithms that allow one to compute this characterization in practice. This is a “population level” (all
identifiable quantities are known) analysis whose first part builds on classic work by McFadden and
Richter (1991) and McFadden (2005). Section 4 explains our test and its implementation under the
assumption that one has an estimator of demand distributions and an approximation of the estimator’s
sampling distribution. Section 5 explains how to get the estimator, and a bootstrap approximation
to its distribution, by both smoothing over expenditure and adjusting for endogenous expenditure.
Section 6 contains a Monte Carlo investigation of the test’s finite sample performance, and Section 7
contains our empirical application. Section 8 concludes. All proofs are collected in Appendix A, and
pseudocode for some algorithms is in Appendix B, in the Supplemental Materials.

5

2. Related Literature
Our framework for testing Random Utility Models is built from scratch in the sense that it
only presupposes classic results on nonstochastic revealed preference, notably the characterization of
individual level rationalizability through the Weak (Samuelson 1938), Strong (Houthakker 1950), or
Generalized (Afriat 1967) Axiom of Revealed Preference (WARP, SARP, and GARP henceforth).3
At the population level, stochastic rationalizability was analyzed in classic work by McFadden and
Richter (1991) updated by McFadden (2005). This work was an important inspiration for ours, and
Section 3.1 clarifies and modestly extends it. Indeed, our test can be interpreted as statistical test of
their Axiom of Revealed Stochastic Preference (ARSP). They did not consider statistical testing nor
attempted to make the test operational, and could not have done so with computational constraints
even of 2005.
An influential related research project is embodied in a sequence of papers by Blundell, Browning, and Crawford (2003, 2007, 2008; BBC henceforth). They assume the same observables as we do
and apply their method to the same data. The core difference is that BBC analyze one individual
level demand system generated by nonparametric estimation of Engel curves. This could be loosely
characterized as revealed preference analysis of a representative consumer and in practice of average
demand, where the 2003 paper focuses on testing rationality and bounding welfare and later papers
focus on bounding counterfactual demand. Lewbel (2001) gives conditions on Random Utility Models
that ensure integrability of average demand, so BBC can be thought of as adding those assumptions
to ours. Also, the nonparametric estimation step in practice limits their approach to low dimensional
commodity spaces, whereas we present an application to 5 goods.4
Manski (2007) analyzes stochastic choice from subsets of an abstract, finite choice universe.
He states the testing and extrapolation problems in the abstract, solves them explicitly in simple
examples, and outlines an approach to non-asymptotic inference. (He also considers models with more
structure.) While we start from a continuous problem and build a (uniform) asymptotic theory, the
settings become similar after a crucial discretization step below. The core difference is that methods
in Manski (2007) will not be practical for a choice universe containing more than a few elements. In
a related paper, Manski (2014) uses our computational toolkit for choice extrapolation.

3See also especially Richter (1966) and Varian (1982).
4BBC’s implementation exploits only WARP and therefore a necessary but not sufficient condition for rationalizability.

This is remedied in Blundell, Browning, Cherchye, Crawford, De Rock, and Vermeulen (2015).

6

KITAMURA AND STOYE

Our setting much simplifies if there are only two goods, an interesting but obviously very specific
case. Blundell, Kristensen, and Matzkin (2014) bound counterfactual demand in this setting through
bounding quantile demands.5 They justify this through an invertibility assumption. Hoderlein and
Stoye (2015) show that with two goods, this assumption has no observational implications.6 Hence,
Blundell, Kristensen, and Matzkin (2014) use the same assumptions as we do; however, the restriction
to two goods is fundamental.
Hausman and Newey (2016) nonparametrically bound average welfare under assumptions resembling ours, though their approach additionally imposes smoothness restriction to facilitate nonparametric estimation and interpolation. Their approach is based on nonparametric smoothing, hence
the curse of dimensionality needs to be addressed in the presence of many goods, though conceptually
their main identification results apply to an arbitrary number of goods. Our method also applies to
any number of goods and is practically applicable to at least five goods.
With more than two goods, pairwise testing of a stochastic analog of WARP amounts to testing
a necessary but not sufficient condition for stochastic rationalizability. This is explored by Hoderlein
and Stoye (2014) in a setting that is otherwise ours and also on the same data. Kawaguchi (2017) tests
a logically intermediate condition, again on the same data. A different test of necessary conditions was
proposed by Hoderlein (2011), who shows that certain features of rationalizable individual demand,
like adding up and standard properties of the Slutsky matrix, are inherited by average demand under
weak conditions. The resulting test is passed by the same data that we use. Dette, Hoderlein, and
Neumeyer (2016) propose a similar test using quantiles.
In sum, every paper cited in this section has one of the features (i)-(iii) mentioned in the
introduction. We feel that removing aggregation or invertibility conditions is useful because these are
usually assumptions of convenience. Testing necessary and sufficient conditions is obviously (at least
in principle) sharper than testing necessary ones. And there are many empirical applications with
more than two or three goods.
Section 4 of this paper is (implicitly) about testing multiple inequalities, the subject of a large
literature in economics and statistics. See, in particular, Gourieroux, Holly, and Monfort (1982) and
Wolak (1991) and also Chernoff (1954), Kudo (1963), Perlman (1969), Shapiro (1988), Takemura
and Kuriki (1997), Andrews (1991), Bugni, Canay, and Shi (2015), and Guggenberger, Hahn, and
5The α-quantile demand induced by π is the nonstochastic demand system defined by the α-quantiles of π across j.
j

It is well defined only if K = 2.
6

A similar point is made, and exploited, by Hausman and Newey (2016).

7

Kim (2008). For the also related setting of inference on parameters defined by moment inequalities,
see furthermore Andrews and Soares (2010), Bugni (2010), Canay (2010), Chernozhukov, Hong, and
Tamer (2007), Imbens and Manski (2004), Romano and Shaikh (2010), Rosen (2008), and Stoye
(2009). The major difference to these literatures is that moment inequalities, if linear (which most
of the papers do not assume), define the faces of a polyhedron. The restrictions generated by our
model are more akin to defining the polyhedron’s vertices. One cannot in practice switch between
these representations in high dimensions, so that we have to develop a new approach. In contrast,
the inference theory in Hoderlein and Stoye (2014) only requires comparing two budgets at a time,
and Kawaguchi (2017) tests necessary conditions that are directly expressed as faces of a (larger)
polyhedron. Therefore, inference in both papers is much closer to the established literature on moment
inequalities.
3. Analysis of Population Level Problem
In this section, we show how to verify rationalizability of a known set of cross-sectional demand
distributions on J budgets. The main results are a tractable geometric characterization of stochastic
rationalizability and algorithms for its practical implementation.
3.1. A Geometric Characterization. Assume there is a finite sequence of J budget planes
0
Bj = {y ∈ RK
+ : pj y = 1}, j = 1, ..., J

and that the researcher observes the corresponding vector (P1 , ..., PJ ) of cross-sectional distributions
of demand Pj as defined in 1.3. We will henceforth call (P1 , ..., PJ ) a stochastic demand system. Using
a “more is better” assumption, we restrict choice to budget planes; this simplification is not essential
to the method. We do not restrict the number of goods K.
Definition 3.1. The stochastic demand system (P1 , ..., PJ ) is (stochastically) rationalizable if there
exists a distribution Pu over utility functions u so that
Z
(3.1)
Pj (x) = 1{arg
max
u(y) ∈ x}dPu ,
0
y∈RK
+ :pj y=1

x ⊂ Bj , j = 1, ..., J.

This model is extremely general. Uniqueness of nonstochastic demand has no observational
implications because a unique demand is observed for each data point. We already pointed out that
“more is better” is not essential either. The model is also extremely rich – a parameterization would involve an essentially unrestricted distribution over utility functions. Testing stochastic rationalizability
therefore seems formidable.

8

KITAMURA AND STOYE

However, we next provide a very tractable characterization of stochastic rationalizability. The
essential insight was stated in passing by McFadden (2005) and goes as follows: The revealed preference
information contained in a given nonstochastic demand system only depends on whether choice from
Bi is on, above, or below Bj for all different i, j. Thus, for any two demand systems that agree on all
of these comparisons, either both or none are rationalizable. This allows one to transform the testing
problem into one where the universal choice set consist of sets like “the bit of budget B1 that is above
B2 and below all other budgets.” This set is finite. We then show that, here and in all other settings
of this type, the set of stochastic choice functions that are mixtures of rationalizable nonstochastic
ones – hence, stochastically rationalizable – can be expressed as a finite cone.
Formalizing this insight requires a few ingredients.
Definition 3.2. Let X := {x1 , ..., xI } be the coarsest partition of ∪Jj=1 Bj such that for any i ∈
{1, ..., I} and j ∈ {1, ..., J}, xi is either completely on, completely strictly above, or completely strictly
below Bj .
Elements of X will be called patches. Elements of X that are part of more than one budget
will be called intersection patches. Each budget can be uniquely expressed as union of patches; the
P
number of patches that jointly comprise budget Bj will be called Ij . Note that Jj=1 Ij ≥ I, strictly
so (because of multiple counting of intersection patches) if any two budget planes intersect.
Remark 3.1. Ij ≤ I ≤ 3J , hence Ij and I are finite.
The partition X is the finite universal choice set alluded to above. The basic idea is that all
choices from budget B1 that are on the same patch induce the same directly revealed preferences, so are
equivalent for the purpose of our test. Conversely, stochastic rationalizability does not at all constrain
the distribution of demand on any patch. Therefore, stochastic rationalizability of (P1 , . . . , PJ ) can
be decided by only considering the probabilities assigned to patches on the respective budgets. We
formalize this as follows.
Definition 3.3. The vector representation of (B1 , ..., BJ ) is a

PJ

j=1 Ij -vector

(x1|1 , . . . , xI1 |1 , x1|2 , . . . , xIJ |J )
whose first I1 components are the patches comprising B1 , the next I2 components are the patches
comprising B2 , and so forth. The ordering of patches on budgets is arbitrary but henceforth fixed.
Note that intersection patches appear repeatedly.

9

Definition 3.4. The vector representation of (P1 , ..., PJ ) is the

PJ

j=1 Ij -vector

π := (π1|1 , . . . , πI1 |1 , π1|2 , . . . , πIJ |J ),
where πi|j := Pj (xi|j ).
Thus, the vector representation of a stochastic demand system lists the probability masses that
it assigns to patches.
Next, a stochastic demand system is (stochastically) rationalizable iff it is a mixture of rationalizable nonstochastic demand systems. To intuit this, one may literally think of the latter as
characterizing rational individuals. It follows that the vector representation of a rationalizable stochastic demand system must be the corresponding mixture of vector representations of rationalizable
nonstochastic demand systems. The latter vector representations are in {0, 1}I , so there are only
finitely many of them. Thus, define:
Definition 3.5. The rational demand matrix A is the (unique, up to ordering of columns) matrix
such that the vector representation of each rationalizable nonstochastic demand system is exactly one
column of A. The number of columns of A is denoted H.
Remark 3.2. H ≤

QJ

j=1 Ij .

We then have:
Theorem 3.1. The stochastic demand system (P1 , ..., PJ ) is rationalizable iff its vector representation
can be written as
(3.2)

π = Aν for some ν ∈ ∆H−1 ,

where ∆H−1 is the unit simplex in RH . Furthermore, this representation obtains iff
(3.3)

π = Aν for some ν ≥ 0.
We conclude this section with a number of remarks.
GARP vs SARP. Rationalizability of nonstochastic demand systems can be defined, and our

test can therefore be applied, using either GARP or SARP. SARP will define a somewhat smaller
matrix A, but nothing else changes. Note that weak revealed preference occurs if demand on some
budget Bi is also on some other budget plane Bj . Therefore, GARP and SARP can disagree only
for nonstochastic demand systems that select from at least three intersection patches. The result

10

KITAMURA AND STOYE

also applies to the ”random utility” or ”unobserved heterogeneity” extension of any other revealed
preference characterization that allows for discretization of choice space. Indeed, see Deb, Kitamura,
Quah, and Stoye (2016) for an application to a different model of individual rationality and Hubner
(2017) for an application to the collective household consumption model.
Simplification if demand is continuous. Intersection patches are of lower dimension than
budget planes. Thus, if the distribution of demand is known to be continuous, their probability is
known to be zero, and they can be eliminated from X . In large problems, this will considerably
P
simplify A. Also, each remaining patch is a subset of exactly one budget plane, so that Jj=1 Ij = I.
We impose this simplification henceforth and in our empirical application, but none of our results and
algorithms depend on it. Observe finally that SARP and GARP agree in this case.
Generality of our characterization. At its very heart, Theorem 3.1 only uses that choice
from finitely many budgets can reveal only finitely many distinct revealed preference relations. Thus,
it applies to any setting with finitely many budgets, irrespective of budgets’ (possibly nonlinear) shape.
For example, budget sets are kinked in Manski (2014).
3.2. Computing A. We next elaborate how to compute A from a vector of prices (p1 , ..., pJ ). For
ease of exposition, we assume that intersection patches can be dropped. We add remarks on generalization along the way. We split the problem into two subproblems, namely checking whether a binary
“candidate” vector a is the vector representation of a rationalizable nonstochastic demand system (a
is then called rationalizable below) and finding all such vectors.
Checking rationalizability of a.
Consider any binary I-vector a with at most one entry of 1 on each subvector corresponding
to one budget. This vector can be thought of as encoding choice behavior on all or some budgets.
It is complete if it has exactly J entries of 1, i.e. it specifies a choice from each budget. It is called
incomplete otherwise. It is called rationalizable if those choices that are specified jointly fulfill GARP.
The rationalizable demand matrix A collects all complete rationalizable vectors a.
To check rationalizability of a given a, we initially extract a directly revealed preference relation.
For example, if (an element of) xi|j is chosen from budget Bj , then it is revealed preferred to all xi|k
on or below Bj . This information can be extracted extremely quickly.7

7In a preliminary step of the implementation, we compute a (I × J)-matrix X where, for example, the i-th row of X,

i ≤ I1 , is (0, −1, 1, 1, 1) if xi|1 is on budget B1 , below budget B2 , and above the remaining budgets. Each row therefore
encodes the revealed preference information implied by the corresponding choice.

11

We next check whether the transitive completion of directly revealed preference is cyclical.
This is done by checking cyclicality of the directed graph in which nodes correspond to elements of X
and in which a directed link indicates directly revealed preference. Operationally, this check can use
either the Floyd-Warshall algorithm (Floyd 1962), a depth-first search of the graph, or a breadth-first
search. All methods compute quickly in our application. An important simplification is to notice that
revealed preference cycles can only pass through nodes that were in fact chosen. Hence, it suffices to
look for cycles on the subgraph with the (at most) J corresponding nodes. This dramatically simplifies
the problem as I increases rapidly with J. Indeed, increasing K does not increase the size of graphs
checked in this step, though it tends to lead to more intricate patterns of overlap between budgets
and, therefore, to richer revealed preference relations.
In this heuristic explanation, we interpreted all revealed preferences as strict. This is without
loss of generality absent intersection patches because GARP and SARP then agree. If intersection
patches are retained, we just described how to test SARP and not GARP. To test GARP, one would
have to check rejected vectors a for the possibility that all revealed preference cycles are weak and
accept them if this is the case.8
Collecting rationalizable vectors.
This step is a potential bottleneck whose cost escalates rapidly (in general more than polynomially) with J. We very briefly mention two approaches that we do not recommend. First, one could
J
Q
check rationalizability of each of the
Ij logically conceivable candidate vectors a. We implemented
j=1

this approach for debugging purposes, but computational cost escalates rapidly. Similarly, we do not
recommend to initially list all possible preference orderings over patches and then generate columns
of A from them.
Our benchmark algorithm is based on representing all conceivable vectors a as leaves (terminal
nodes) of a rooted tree that is recursively constructed as follows: The root has I1 children corresponding to (x1|1 , . . . , xI1 |1 ). Each of these children has I2 children that correspond to (x1|2 , . . . , xI2 |2 ),
and so on for J generations. The leaves of the tree correspond to complete vectors a that specify to
choose the leaf and all its ancestors from the respective budgets. Non-terminal nodes can be similarly
identified with incomplete vectors.
The algorithm attempts a depth-first search of the tree. At each node, rationalizability of the
corresponding vector is checked. If an inconsistency is detected, the node and its entire subtree are
8The matrix X from footnote 7 is designed to allow for this as entries of 0 and 1 differentiate between weak and strict

preference. The information is not exploited in our empirical application.

12

KITAMURA AND STOYE

deleted. If the node is a leaf and no inconsistency is detected, then a new column of A has been
discovered. The algorithm terminates when each node has been either visited or deleted. It discovers
each column of A exactly once. Elimination of subtrees means that the vast majority of complete
candidate vectors are never visited. Pseudocode for the algorithm is displayed in appendix B.
Finally, a modest amount of problem-specific adjustment can lead to further, dramatic improvement. The key to this is contained in the following result.

Theorem 3.2. Suppose that for some M ≥ 1, (B1 , ..., BM ) are either all below or all above BJ .
Suppose also that choices from (B1 , ..., BJ−1 ) are jointly rationalizable. Then choices from (B1 , ..., BJ )
are jointly rationalizable iff choices from (BM +1 , ..., BJ ) are.
If the geometry of budgets allows it – this is particularly likely if budgets move outward over
time and even guaranteed if some budget planes are parallel – this theorem can be used to construct
columns of A recursively from columns of A-matrices that correspond to a smaller J. The gain can be
tremendous because (worst-case) computational cost of finding A increases more than exponentially
with A. A caveat is that application of Theorem 3.2 may require to manually reorder budgets so that
it applies. Also, while the internal ordering of (B1 , . . . , BM ) and (BM +1 , . . . , BJ−1 ) does not matter,
the Theorem may apply to distinct partitions of the same set of budgets. In that case, any choice
of partition will accelerate computations, but we have no general advice on which is best. We tried
the refinement in our empirical application, and it improves computation time for some of the largest
matrices by orders of magnitude. However, the depth-first search proved so fast that, in order to keep
it transparent, our replication code omits this step.

3.3. Examples. We conclude this section with some examples. All examples presume continuous
demand and therefore disregard intersection patches.

Example 3.1. The simplest example where RUM is not vacuous consists of two intersecting budgets,
0
0
thus J = 2 and there exists y ∈ RK
++ with p1 y = p2 y.

In this example, there are I = 4 patches. WARP, SARP, and GARP all agree on which
nonstochastic demand system to exclude. Index vector representations as in Figure 1, then the only

13

B1

π2|1

y2
π1|2

π2|2
π1|1

B2

y1

Figure 1. Visualization of Example 3.1.
excluded behavior is (1, 0, 1, 0)0 , thus


1 0 0



x

 1|1


 0 1 1  x2|1

A=
,


 0 1 0  x1|2


1 0 1
x2|2
where the rightmost column in the display is a reminder of which row of A corresponds to which
patch. The column cone of A can be explicitly written as







ν1













 ν2 + ν3 


C= 
 : ν1 , ν2 , ν3 ≥ 0 .





ν2






1





 ν1 + ν3
The only restriction on π beyond adding-up constraints is that π1|1 + π1|2 ≤ 1 or equivalently π2|2 ≥
π1|1 . This is well known to be the exact implication of a RUM for this example (Matzkin 2006,
Hoderlein and Stoye 2015). All of this is illustrated in Figure 1.
Example 3.2. The following is the simplest example in which WARP does not imply SARP, so that
applying Example 3.1 to all pairs of budgets will only test a necessary condition. More subtly, it

14

KITAMURA AND STOYE

can be shown that the conditions in Kawaguchi (2017) are only necessary as well. Let K = J = 3
and assume a maximal pattern of intersection of budgets; for example, prices could be (p1 , p2 , p3 ) =
((1/2, 1/4, 1/4), (1/4, 1/2, 1/4), (1/4, 1/4, 1/2)). Each budget has 4 patches for a total of I = 12
patches, and one can compute
















A=















0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0



x1|1

0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0
































x2|1

0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0
1 0 1 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0
0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

x3|1
x4|1
x1|2
x2|2
x3|2

.

x4|2
x1|3
x2|3
x3|3
x4|3

Interpreting this matrix requires knowing the geometry of patches. For example, choice of
patches x3|1 , x2|2 , and x3|3 from their respective budgets would violate SARP, thus A does not contain
the column (0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0)0 . We revisit this example in our Monte Carlo study.

Example 3.3. Our empirical application has sequences of J = 7 budgets in RK for K = 3, 4, 5 and
sequences of J = 8 budgets in R3 . The largest A-matrices are of sizes 78 × 336467 and 79 × 313440.9

Figure 2 visualizes one budget in R3 from our empirical application and its intersection with 6 other
budgets. There are total of 10 patches (plus 15 intersection patches).
4. Statistical Testing
This section lays out our statistical testing procedure in the idealized situation where, for finite
J, repeated cross-sectional observations of demand over J periods are available to the econometrician,
and each cross-section of size Nj is observed over the deterministic (and hence exogenous) budget
9In exploratory work using more complex examples, we computed an A matrix with over 2 million columns in a few

hours on a standard desktop computer.

15

25

20

services

15

10

5

0

0
5

0
10

5
10

15
15

20

20

nondurables

food

25

25

30

30
35

35

Figure 2. Visualization of one budget set in the empirical application.
plane for period j. We define a test statistic and critical value and show that the resulting test is
uniformly asymptotically valid over an interesting range of d.g.p.’s.
4.1. Null Hypothesis and Test Statistic. Recall from (3.3) that we wish to test:

(HA ): There exist ν ≥ 0 such that Aν = π.
This hypothesis is equivalent to

16

KITAMURA AND STOYE

(HB ):

minη∈C [π − η]0 Ω[π − η] = 0,

where Ω is a positive definite matrix (restricted to be diagonal in our inference procedure) and C :=

{Aν|ν ≥ 0} is a convex cone in RI . The solution η0 of (HB ) is the projection of π ∈ RI+ onto C under
√
the weighted norm kxkΩ = x0 Ωx. The corresponding value of the objective function is the squared
length of the projection residual vector. The projection η0 is unique, but the corresponding ν is not.
Stochastic rationality holds if and only if the length of the residual vector is zero.
A natural sample counterpart of the objective function in (HB ) would be minη∈C [π̂−η]0 Ω[π̂−η],
where π̂ estimates π, for example by sample choice frequencies. The usual normalization by sample
size yields
JN

(4.1)

:= N min[π̂ − η]0 Ω[π̂ − η]
η∈C

=

N min [π̂ − Aν]0 Ω[π̂ − Aν].
ν∈RH
+

Once again, ν is not unique at the optimum, but η = Aν is. Call its optimal value η̂. Then η̂ = π̂,
and JN = 0, if the estimated choice probabilities π̂ are stochastically rationalizable; obviously, our
null hypothesis will be accepted in this case.
4.2. Simulating a Critical Value. We next explain how to get a valid critical value for JN under
the assumption that π̂ estimates the probabilities of patches by corresponding sample frequencies and
that one has R bootstrap replications π̂ ∗(r) , r = 1, ..., R. Thus, π̂ ∗(r) − π̂ is a natural bootstrap analog
of π̂ − π. We will make enough assumption to ensure that its distribution consistently estimates the
distribution of π̂ − π0 , where π0 is the true value of π. The main difficulty is that one cannot use π̂
as bootstrap analog of π0 .
Our bootstrap procedure relies on a tuning parameter τN chosen s.t. τN ↓ 0 and

√

N τN ↑ ∞.10

Also, we restrict Ω to be diagonal and positive definite and let 1H be a H-vector of ones.11. The
restriction on Ω is important: Together with a geometric feature of the column vectors of the matrix
10In this section’s simplified setting and if π̂ collects sample frequencies, a reasonable choice would be

s
τN =

log N
N

where N = minj Nj and Nj is the number of observations on Budget Bj : see (4.8). This choice corresponds to the “BIC
choice” in Andrews and Soares (2010). We will later propose a different τN based on how π is in fact estimated.
11In principle, 1 could be any strictly positive H-vector, though a data based choice of such a vector is beyond the
H

scope of the paper.

17

A, it ensures that among constraints implied by (3.3), those which are fulfilled but with small slack
become binding through the Cone Tightening algorithm we are about to describe. A non-diagonal
weighting matrix can disrupt this property. For further details on this point and its proof, the reader
is referred to Appendix A. Our procedure is as follows:
(i) Obtain the τN -tightened restricted estimator η̂τn , which solves
JN =

min

[ν−τN 1H /H]∈RH
+

N [π̂ − Aν]0 Ω[π̂ − Aν]

(ii) Define the τN -tightened recentered bootstrap estimators
π̂τ∗(r)
:= π̂ ∗(r) − π̂ + η̂τN ,
N

r = 1, ..., R.

(iii) The bootstrap test statistic is
∗(r)

JN

=

min

[ν−τN 1H /H]∈RH
+

N [π̂τ∗(r)
− Aν]0 Ω[π̂τ∗(r)
− Aν],
N
N

for r = 1, ..., R.
∗(r)

(iv) Use the empirical distribution of JN , r = 1, ..., R to obtain the critical value for JN .
The object η̂τN is the true value of π in the bootstrap population, i.e. it is the bootstrap analog
of π0 . It differs from π̂ through a “double recentering.” To disentangle the two recenterings, suppose
first that τN = 0. Then inspection of step (i) of the algorithm shows that π̂ would be projected onto
the cone C. This is a relatively standard recentering “onto the null” that resembles recentering of the
J-statistic in overidentified GMM. However, with τN > 0, there is a second recentering because the
cone C itself has been tightened. We next discuss why this recentering is needed.
4.3. Discussion. Our testing problem is related to the large literature on inequality testing but adds
an important twist. Writing {a1 , a2 , ..., aH } for the column vectors of A, one has
C = cone(A) := {ν1 a1 + ... + νH aH : νh ≥ 0},
i.e. the set C is a finitely generated cone. The following result, known as the Weyl-Minkowski
Theorem, provides an alternative representation that is useful for theoretical developments of our
statistical testing procedure.12
12See Gruber (2007), Grünbaum, Kaibel, Klee, and Ziegler (2003), and Ziegler (1995), especially Theorem 1.3, for

these results and other materials concerning convex polytopes used in this paper.

18

KITAMURA AND STOYE

Theorem 4.1. (Weyl-Minkowski Theorem for Cones) A subset C of RI is a finitely generated cone
(4.2)

C = {ν1 a1 + ... + νH aH : νh ≥ 0} for some A = [a1 , ..., aH ] ∈ RI×H

if and only if it is a finite intersection of closed half spaces
(4.3)

C = {t ∈ RI |Bt ≤ 0} for some B ∈ Rm×I .

The expressions in (4.2) and (4.3) are called a V-representation (as in “vertices”) and a H-representation
(as in “half spaces”) of C, respectively.
The “only if” part of the theorem (which is Weyl’s Theorem) shows that our rationality
hypothesis π ∈ C, C = {Aν|ν ≥ 0} in terms of a V-representation can be re-formulated in an Hrepresentation using an appropriate matrix B, at least in theory. If such B were available, our testing
problem would resemble tests of
H0 : Bθ ≥ 0

B ∈ Rp×q is known

based on a quadratic form of the empirical discrepancy between Bθ and η minimized over η ∈ Rq+ .
This type of problem has been studied extensively; see references in Section 2. Its analysis is intricate
because the limiting distribution of such a statistic depends discontinuously on the true value of Bθ.
One common way to get a critical value is to consider the globally least favorable case, which is θ = 0.
A less conservative strategy widely followed in the econometric literature on moment inequalities is
Generalized Moment Selection (GMS; see Andrews and Soares (2010), Bugni (2010), Canay (2010)).
If we had the H-representation of C, we might conceivably use the same technique. However, the
duality between the two representations is purely theoretical: In practice, B cannot be computed
from A in high-dimensional cases like our empirical application.
We therefore propose a tightening of the cone C that is computationally feasible and will have
a similar effect as GMS. The idea is to tighten the constraint on ν in (4.1). In particular, define
CτN := {Aν|ν ≥ τN 1H /H} and define η̂τN as optimal argument in
(4.4)

JN

:=
=

min N [π̂ − η]0 Ω[π̂ − η]

η∈CτN

min

[ν−τN 1H /H]∈RH
+

N [π̂ − Aν]0 Ω[π̂ − Aν].

Our proof establishes that constraints in the H-representation that are almost binding at the original
problem’s solution (i.e., their slack is difficult to be distinguished from zero at the sample size) will be

19

binding with zero slack after tightening. Suppose that
estimate S. Let η̃τN := η̂τN +
(4.5)

J˜N

√1 N (0, Ŝ)
N

:=
=

√

N (π̂ − π) →d N (0, S) and let Ŝ consistently

or a bootstrap random variable and use the distribution of

min N [η̃τN − η]0 Ω[η̃τN − η]

η∈CτN

min

[ν−τN 1H /H]∈RH
+

N [η̃τN − Aν]0 Ω[η̃τN − Aν],

to approximate the distribution of JN . This has the same theoretical justification as the inequality
selection procedure. Unlike the latter, however, it avoids the use of an H-representation, thus offering
a computationally feasible testing procedure.
To further illustrate the duality between H- and V-representations, we revisit the first two
examples. It is not possible to compute B-matrices in our empirical application.
Example 3.1 continued. With two intersecting budget planes, the cone C is represented by
x1|1 x2|1 x1|2 x2|2


−1
0
0
0


 0

0
−1
0



.
B =
1
1
 −1 −1



 1
1 −1 −1 


1
0
0 −1

(4.6)

The first two rows of B are nonnegativity constraints (the other two such constraints are redundant),
the next two rows are an equality constraint forcing the sum of probabilities to be constant across
budgets, and only the last constraint is a substantive economic constraint. If the estimator π̂ fulfills the
first four constraints by construction, then the testing problem simplifies to a test of (1, 0, 0, −1)π ≤ 0.
Example 3.2 continued. Eliminating nonnegativity and adding-up constraints for brevity,
numerical evaluation reveals

(4.7)

x1|1 x2|1 x3|1 x4|1 x1|1 x1|2 x3|1 x4|1 x1|1 x2|1 x3|1 x4|1


1
1
0
0
0 −1
0 −1
0
0
0
0



 0 −1
0
−1
0
0
0
0
1
1
0
0


.

B =

0
0
0
0
1
1
0
0
0
−1
0
−1




 0 −1 −1 −1

1
0
0
0
1
0
0
0


1
1
1
0
0
0
0 −1
0
0
0 −1

20

KITAMURA AND STOYE

The first three rows are constraints on pairs of budgets that mirror the last row of 4.6. The
next two constraints are not implied by these, nor by the SARP-like constraints in Kawaguchi (2017),
but they imply the latter.
4.4. Theoretical Justification. We now provide a detailed justification. First, we formalize the
notion that choice probabilities are estimated by sample frequencies. Thus, for each budget set Bj ,
denote the choices of Nj individuals, indexed by n = 1, ..., Nj , by


 1 if individual n chooses xi|j
di|j,n =
n = 1, ..., NJ .

 0 otherwise
I

N

j
j
, j = 1, 2, ..., J. For later use, define
Assume that one observes J random samples {{di|j,n }i=1
}n=1


d
J
 1|j,n 
X
..


dj,n := 
,
N
=
NJ .

.


j=1
dIj |j,n

An obvious way to estimate the vector π is to use choice frequencies
(4.8)

π̂i|j =

Nj
X

di|j,n /Nj , i = 1, ..., Ij , j = 1, ..., J.

n=1

The next lemma, among other things, shows that our tightening of the V-representation of C is
equivalent to a tightening its H-representation but leaving B unchanged. For a matrix B, let col(B)
denote its column space.
Lemma 4.1. For A ∈ RI×H , let
C = {Aν|ν ≥ 0}.
Also let
C = {t : Bt ≤ 0}
be its H-representation for some B ∈ Rm×I

 
B≤
such that B =  , where the submatrices B ≤ ∈ Rm̄×I
B=

and B = ∈ R(m−m̄)×I correspond to inequality and equality constraints, respectively. For τ > 0 define
Cτ = {Aν|ν ≥ (τ /H)1H }.
Then one also has
Cτ = {t : Bt ≤ −τ φ}

21

for some φ = (φ1 , ..., φm )0 ∈ col(B) with the properties that (i) φ̄ := [φ1 , ..., φm̄ ]0 ∈ Rm̄
++ , and (ii)
φk = 0 for k > m̄.
Lemma 4.1 is not just a re-statement of the Minkowski-Weyl theorem for polyhedra, which
would simply say Cτ = {Aν|ν ≥ (τ /H)1H } is alternatively represented as an intersection of closed
halfspaces. The lemma instead shows that the inequalities in the H-representation becomes tighter by
τ φ after tightening the V-representation by τN 1H /H, with the same matrix of coefficients B appearing
both for C and Cτ . Note that for notational convenience, we rearrange rows of B so that the genuine

inequalities come first and pairs of inequalities that represent equality constraints come last.13 This
is w.l.o.g.; in particular, the researcher does not need to know which rows of B these are. Then as we
show in the proof, the elements in φ corresponding to the equality constraints are automatically zero
when we tighten the space for all the elements of ν in the V-representation. This is a useful feature
that makes our methodology work in the presence of equality constraints.
The following assumptions are used for our asymptotic theory.
Assumption 4.1. For all j = 1, ..., J,

Nj
N

→ ρj as N → ∞, where ρj > 0.

Assumption 4.2. J repeated cross-sections of random samples

n
oNj
Ij
{di|j,n(j) }i=1

n(j)=1

, j = 1, ..., J,

are observed.
The econometrician also observes the normalized price vector pj , which is fixed in this section, for
each 1 ≤ j ≤ J. Let P denote the set of all π’s that satisfy Condition S.1 in Appendix A for some
(common) value of (c1 , c2 ).
Theorem 4.2. Choose τN so that τN ↓ 0 and

√

N τN ↑ ∞. Also, let Ω be diagonal, where all the

diagonal elements are positive. Then under Assumptions 4.1 and 4.2
lim inf inf Pr{JN ≤ ĉ1−α } = 1 − α
N →∞ π∈P∩C

where ĉ1−α is the 1 − α quantile of J˜N , 0 ≤ α ≤ 21 .
While it is obvious that our tightening contracts the cone, the result depends on a more delicate
feature, namely that we (potentially) turn non-binding inequalities from the H-representation into
binding ones but not vice versa. This feature is not universal to cones as they get contracted. Our
proof establishes that it generally obtains if Ω is the identity matrix and all corners of the cone
13In the matrix displayed in (4.6), the third and fourth row would then come last.

22

KITAMURA AND STOYE

are acute. In this paper’s application, we can further exploit the cone’s geometry to extend the
result to any diagonal Ω. Our method immediately applies to other testing problems featuring Vrepresentations if analogous features can be verified.

5. Extending the Scope of the Test
The methodology outlined in Section 4 requires that (i) the observations available to the econometrician are drawn on a finite number of budgets and (ii) the budgets are given exogenously, that is,
unobserved heterogeneity and budgets are assumed to be independent. These conditions are naturally
satisfied in some applications. The empirical setting in Section 7, however, calls for modifications
because Condition (i) is certainly violated in it and imposing Condition (ii) would be very restrictive.
We propose to use a series estimator to estimate the conditional choice probability vector π for a
specific expenditure W when W is distributed continuously (Section 5.1). Furthermore, a method to
test stochastic rationalizability in the presence of possible endogeneity of income is developed using a
control function method (Section 5.2).
The setting in this section is as follows. Let p̃j ∈ RK
++ denote the unnormalized price vector,
fixed for each period j. Let (S, S, P ) denote the underlying probability space. Since we have repeated

cross-sections over J periods, write P = ⊗Jj=1 P (j) , a J-fold product measure. Let Pu denote the
marginal probability law of u, which we assume does not depend on j. We do not, however, assume
that the laws of other random elements, such as income, are time homogeneous. Let w = log(W )
denote log total expenditure, and suppose the researcher chooses a value wj for w for each period j.
Note that our algorithm and asymptotic theory remain valid if multiple values of w are chosen for
each period.
5.1. Test statistic with smoothing. This subsection proposes a smoothing procedure based on a
series estimator (see, for example, Newey (1997)) for π to deal with a situation where total expenditure
W is continuously distributed, yet exogenous. We need some notation and definitions to formally state
the asymptotic theory behind our procedure with smoothing.
Let wn(j) be the log total expenditure of consumer n(j), 1 ≤ n(j) ≤ Nj observed in period j.
Assumption 5.1. J repeated cross-sections of random samples

n
oNj
Ij
{di|j,n(j) }i=1
, wn(j)

n(j)=1

,j =

1, ..., J, are observed.
The econometrician also observes the unnormalized price vector p̃j , which is fixed, for each 1 ≤ j ≤ J.

23

This subsection assumes that the total expenditure is exogenous, in the sense that
w⊥
⊥u
holds under every P (j) , 1 ≤ j ≤ J. This will be relaxed in the next subsection. Let pi|j (w) :=
Pr{di|j,n(j) = 1|wn(j) = w} then we have
pi|j (wj ) = Pr{D(p̃j /wn(j) , u) ∈ xi|j |wn(j) = wj }
= Pr{D(p̃j /wj , u) ∈ xi|j , u ∼ Pu }
where the second equality follows from the exogeneity assumption. Letting
πi|j = pi|j (wj )
and writing πj := (π1|j , ..., πIj |j )0 and π := (π10 , ..., πJ0 )0 = (π1|1 , π2|1 , ..., πIJ |J )0 , the stochastic rationality condition is given by
π∈C
as before. Note that π can be estimated by standard nonparametric procedures. For concreteness,
we use a series estimator, as defined and analyzed in Appendix A. The smoothed version of JN (also
denoted JN for simplicity) is obtained using the series estimator for π̂ in (4.1). In Appendix A we
also present an algorithm for obtaining the bootstrapped version J˜N of the smoothed statistic.

In what follows, Fj signifies the joint distribution of (di|j,n(j) , wn(j) ). Let F be the set of all
(F1 , ..., FJ ) that satisfy Condition S.2 in Appendix A for some (c1 , c2 , δ, ζ(·)).
Theorem 5.1. Let Condition S.3 hold. Also let Ω be diagonal where all the diagonal elements are
positive. Then under Assumptions 4.1 and 5.1
lim inf

inf

N →∞ (F1 ,...,FJ )∈F

Pr{JN ≤ ĉ1−α } = 1 − α

where ĉ1−α is the 1 − α quantile of J˜N , 0 ≤ α ≤ 21 .
5.2. Endogeneity. We now relax the assumption that consumer’s utility functions are realized independently from W . Exogeneity of budget sets is a standard assumption in classical demand analysis
based on random utility models; for example, it is assumed, at least implicitly, in McFadden and
Richter (1991). Nonetheless, the assumption can be a concern in applying our testing procedure to a
data set such as ours. Recall that the budget sets {Bj }Jj=1 are based on prices and total expenditure.
The latter is likely to be endogenous, which should be a concern to the econometrician.

24

KITAMURA AND STOYE

As independence between utility and budgets is fundamental to McFadden-Richter theory,
addressing it in our testing procedure might seem difficult. Fortunately, recent advances in nonparametric identification and estimation of models with endogeneity inform a solution. To see this, it
is useful to rewrite the model so that we can cast it into a framework of nonseparable models with
endogenous covariates. Writing pj = p̃j /W , where p̃j is the unnormalized price vector, the essence
of the problem is as follows: Stochastic rationalizability imposes restrictions on the distributions of
y = D(p, u) for different p when u is distributed according to its population marginal distribution
Pu , but the observed conditional distribution of y given p does not estimate this when w and u are
interrelated. More formally, for each fixed value wj and the unnormalized price vector p̃j in period j,
1 ≤ j ≤ J, define the endogeneity corrected conditional probability14
π(p̃j /ewj , xi|j ) := Pr{D(p̃j /ewj , u) ∈ xi|j , u distributed according to Pu }
Z
=
1{Dj (wj , u) ∈ xi|j }dPu
where Dj (w, u) := D(p̃j /ew , u). Then Theorem 3.1 still applies to
πEC := [π(p1 , x1|1 ), ..., π(p1 , xI1 |1 ), π(p2 , x1|2 ), ..., π(p2 , xI2 |2 ), ..., π(pJ , x1|J ), ..., π(pJ , xIJ |J )]0 .
If we define JEC = minν∈Rh [πEC −Aν]0 Ω[πEC −Aν], then JEC = 0 iff stochastic rationalizability holds.
+

Note that this new definition πEC recovers the definition of π in Section 5.1 when w is exogenous.
Suppose w is endogenous but there exists a control variable ε such that
w⊥
⊥u|ε
holds under every P (j) , 1 ≤ j ≤ J. For example, given a reduced form w = hj (z, ε) with hj monotone in
(j)

(j)

ε and z is an instrument, one may use ε = Fw|z (w|z) where Fw|z denotes the conditional CDF of w given
z under P (j) when the random vector (w, z) obeys the probability law P (j) ; see Imbens and Newey
(2009) for this type of control variable in the context of cross-sectional data. Note that ε ∼ Uni(0, 1)
(j)

under every P (j) , 1 ≤ j ≤ J by construction. Let Py|w,ε denote the conditional probability measure

for y given (w, ε) corresponding to P (j) . Adapting the argument in Imbens and Newey (2009) and
Blundell and Powell (2003), under the assumption that supp(w) = supp(w|ε) under P (j) , 1 ≤ j ≤ J
14This is the conditional choice probability if p is (counterfactually) assumed to be exogenous. We call it “endogeneity

corrected” instead of “counterfactual” to avoid confusion with rationality constrained, counterfactual prediction.

25

we have
Z

1Z

π(pj , xi|j ) =
0

Z
=
0

u
1

(j)

1{Dj (wj , u) ∈ xi|j }dPu|ε dε

(j) 
Py|w,ε y ∈ xi|j |w = wj , ε dε,

1 ≤ j ≤ J.

This means that πEC can be estimated nonparametrically. We propose to use a fully nonparametric
two-step estimator, denoted by πd
EC , to define our endogeneity-corrected test statistic JECN ; see
Appendix A for details. For this, the bootstrap procedure needs to be adjusted appropriately to
obtain the bootstrapped statistic J˜ECN : once again, the reader is referred to Appendix A.
Let zn(j) be the n(j)-th observation of the instrumental variable z in period j.
Assumption 5.2. J repeated cross-sections of random samples

n
oNj
Ij
{di|j,n(j) }i=1
, xn(j) , zn(j)
,j =
n=1

1, ..., J, are observed.
The econometrician also observes the unnormalized price vector p̃j , which is fixed, for each 1 ≤ j ≤ J.
In what follows, Fj signifies the joint distribution of (di|j,n(j) , wn(j) , zn(j) ). Let FEC be the set of
all (F1 , ..., FJ ) that satisfy Condition S.4 in Appendix A for some (c1 , c2 , δ1 , δ, ζr (·), ζs (·), ζ1 (·)). Then
we have:
Theorem 5.2. Let Condition S.5 hold. Also let Ω be diagonal where all the diagonal elements are
positive. Then under Assumptions 4.1 and 5.2,

lim inf

inf

N →∞ (F1 ,...,FJ )∈FEC

Pr{JECN ≤ ĉ1−α } = 1 − α

where ĉ1−α is the 1 − α quantile of J˜ECN , 0 ≤ α ≤ 21 .
6. Monte Carlo Simulations
We next analyze the performance of Cone Tightening in a small Monte Carlo study. To keep
examples transparent and to focus on the core novelty, we model the idealized setting of Section 4, i.e.
sampling distributions are multinomial over patches. In addition, we focus on Example 3.2, for which
an H-representation in the sense of Weyl-Minkowski duality is available; indeed, see displays (3.2)

26

KITAMURA AND STOYE

π0

π1

x1|1 .181 .190

π2

π3 π4

π5

π6

.2 .240

.3 .167 .152

x2|1 .226 .238 .25 .213

.2 .167 .107

x3|1 .226 .238 .25 .213

.2 .333 .441

x4|1 .367 .333

.3 .333

.3 .333

x1|2 .181 .190

.2 .240

.3 .333 .486

x2|2 .226 .238 .25 .213

.2 .167 .107

x3|2 .226 .238 .25 .213

.2 .167 .107

x4|2 .367 .333

.3 .333

.3 .333

x1|3 .181 .190

.2 .240

.3 .333 .486

x2|3 .226 .238 .25 .213

.2 .167 .107

x3|3 .226 .238 .25 .213

.2 .167 .107

x4|3 .367 .333

.3 .333

.3 .333

.3

.3

.3

Table 1. The π-vectors used for the main simulations. Entries reported to three digits
are rounded.
and (4.7) for the relevant matrices.15 This allows us to alternatively test rationalizability through a
moment inequalities test that ensures uniform validity through GMS.16
Data were generated from a total of 31 d.g.p.’s described below and for sample sizes of Nj ∈
{100, 200, 500, 1000}; recall that these are per budget, i.e. each simulated data set is based on 3 such
samples. The d.g.p.’s are parameterized by the π-vectors reported in Table 1. They are related as
follows: π0 is in the interior of C; π2 , π4 , and π6 are outside it; and π2 , π3 , and π5 are on its boundary.
Furthermore, π1 = (π0 + π2 )/2, π3 = (π0 + π4 )/2, and π5 = (π0 + π6 )/2. Thus, the line segment
connecting π0 and π2 intersects the boundary of C precisely at π1 and similarly for the next two pairs
of vectors. We compute “power curves” along those 3 line segments at 11 equally spaced points, i.e.
changing mixture weights in increments of .1, for a total of 31 distinct d.g.p.’s. This is replicated 500
15This is also true of Example 3.1, but that example is too simple because the test reduces to a one-sided test about

the sum of two probabilities, and the issues that motivate Cone Tightening or GMS go away. We verified that all testing
methods successfully recover this and achieve excellent size control, including if tuning parameters are set to 0.
16
The implementation uses a “Modified Method of Moments” criterion function, i.e. S1 in the terminology of Andrews
and Soares (2010), and the hard thresholding GMS function, i.e. studentized intercepts above −κN were set to 0 and
p
all others to −∞. The tuning parameter is set to κN = ln(Nj ).

27

Method

Nj

Cone

100

π0

·

·

·

·

π1

·

·

·

·

π2

.002 .004 .008 .008 .018 .024 .060 .110 .178 .238 .334

Tightening 200

0

0 .004 .008 .012 .040 .088 .164 .286 .410 .544

500

0

0 .004 .004 .026 .066 .166 .310 .500 .690 .856

1000

0

0

0

100

0

0

0 .002 .004 .004 .010 .024 .032 .066 .100

200

0

0

0

500

0

0 .002 .002 .026 .050 .150 .266 .442 .640 .814

1000

0

0

0

0 .008 .050 .194 .460 .758 .924 .976

π0

·

·

·

GMS

Method

Nj

Cone

100

0 .010 .058 .206 .466 .764 .924 .984

0 .004 .010 .018 .048 .082 .174 .262

·

π3

·

·

·

·

π4

.002 .002 .008 .006 .012 .016 .036 .070 .098 .148 .200

Tightening 200

0

0 .004 .008 .010 .036 .068 .112 .194 .296 .404

500

0

0 .004 .004 .026 .064 .156 .296 .456 .664 .786

1000

0

0

0

100

0

0

0 .002 .004 .004 .006 .018 .028 .066 .120

200

0

0

0

0 .004 .004 .012 .024 .056 .110 .216

500

0

0 .002

0 .004 .012 .034 .084 .196 .348 .544

1000

0

0

0

0 .002 .028 .080 .180 .406 .694 .892

π0

·

·

·

GMS

Method

Nj

Cone

100

0 .010 .058 .200 .460 .756 .916 .974

·

π5

·

·

·

·

π6

.002 .002 .006 .004 .020 .052 .126 .326 .548 .766 .934

Tightening 200

0

0 .002 .004 .008 .044 .202 .490 .836 .962 .996

500

0

0 .002 .004 .012 .072 .374 .880 .992

1

1

1000

0

0

0

1

1

100

0

0

0 .004 .008 .022 .072 .170 .388 .604 .808

200

0

0

0

500

0

0

0 .002 .004 .072 .292 .716 .952

1

1

1000

0

0

0

1

1

GMS

0 .006 .052 .606 .992

1

0 .006 .020 .112 .300 .640 .880 .974

0

0 .042 .498 .956

1

Table 2. Monte Carlo results. See Table 1 for definition of π-vectors. Recall that
{π1 , π3 , π5 } are on the boundary of C and π0 is interior to it. All entries computed
from 500 simulations and 499 replications per bootstrap.

28

KITAMURA AND STOYE

times at a bootstrap size of R = 499. Nominal size of the test is α = .05 throughout. Ideally, it should
be exactly attained at the vectors {π1 , π3 , π5 }.
Results are displayed in Table 2. Noting that the vectors are not too different, we would argue
that the simulations indicate reasonable power. Adjustments that ensure uniform validity of tests do
tend to cause conservatism for both GMS and cone tightening, but size control markedly improves
with sample size.17 While Cone Tightening appears less conservative than GMS in these simulations,
we caution that the tuning parameters and the distance metrics underlying the test statistics are not
directly comparable.
The differential performance across the three families of d.g.p.’s is expected because the d.g.p.’s
were designed to pose different challenges. For both π1 and π3 , one constraint is binding and three
more are close enough to binding that, at the relevant sample sizes, they cannot be completely ignored.
This is more the case for π3 compared to π1 . It means that GMS or Cone Tightening will be necessary,
but also that they are expected to be conservative. The vector π5 has three constraints binding, with
two more somewhat close. This is a worst case for naive (not using Cone Tightening or GMS) inference,
which will rarely pick up all binding constraints. Indeed, we verified that inference with τN = 0 or
κN = 0 leads to overrejection. Finally, we note that π2 and π4 fulfill the necessary conditions identified
by Kawaguchi (2017), so that his test will have no asymptotic power at a parameter value in the first
two panels of Table 2.
7. Empirical Application
We apply our methods to data from the U.K. Family Expenditure Survey, the same data used
by BBC. Our testing of a RUM can, therefore, be compared with their revealed preference analysis of
a representative consumer. To facilitate this comparison, we use the same selection from these data,
namely the time periods from 1975 through 1999 and households with a car and at least one child.
The number of data points used varies from 715 (in 1997) to 1509 (in 1975), for a total of 26341.
For each year, we extract the budget corresponding to that year’s median expenditure and, following
Section 5.1, estimate the distribution of demand on that budget with polynomials of order 3. Like
BBC, we assume that all consumers in one year face the same prices, and we use the same price data.
While budgets have a tendency to move outward over time, there is substantial overlap of budgets
at median expenditure. To account for endogenous expenditure, we follow Section 5.2, using total
household income as instrument. This is also the same instrument used in BBC (2008).
17We attribute some very slight nonmonotonicities in the “power curves” to simulation noise.

29

We present results for blocks of eight consecutive periods and the same three composite goods
(food, nondurable consumption goods, and services) considered in BBC.18 For all blocks of seven
consecutive years, we analyze the same basket but also increase the dimensionality of commodity
space to 4 or even 5. This is done by first splitting nondurables into clothing and other nondurables
and then further into clothing, alcoholic beverages, and other nondurables. Thus, the separability
assumptions that we (and others) implicitly invoke are successively relaxed. We are able to go further
than much of the existing literature in this regard because, while computational expense increases
with K, our approach is not subject to a statistical curse of dimensionality.19
Regarding the test’s statistical power, increasing the dimensionality of commodity space can
in principle cut both ways. The number of rationality constraints increases, and this helps if some of
the new constraints are violated but adds noise otherwise. Also, the maintained assumptions become
weaker: In principle, a rejection of stochastic rationalizability at 3 but not 4 goods might just indicate
a failure of separability.
Tables 3 and 4 summarize our empirical findings. They display test statistics, p-values, and the
numbers I of patches and H of rationalizable demand vectors; thus, matrices A are of size (I × H).
All entries that show JN = 0 and a corresponding p-value of 1 were verified to be true zeros, i.e.
π̂EC is rationalizable. All in all, it turns out that estimated choice probabilities are typically not
stochastically rationalizable, but also that this rejection is not statistically significant.20
We identified a mechanism that may explain this phenomenon. Consider the 84-91 entry in
Table 4, where JN is especially low. It turns out that one patch on budget B5 is below B8 and two
patches on B8 are below B5 . By the reasoning of Example 3.1, probabilities of these patches must
18As a reminder, Figure 2 illustrates the application. The budget is the 1993 one as embedded in the 1986-1993 block

of periods, i.e. the figure corresponds to a row of Table 4.
19Tables 3 and 4 were computed in a few days on Cornell’s ECCO cluster (32 nodes). An individual cell of a table

can be computed in reasonable time on any desktop computer. Computation of a matrix A took up to one hour and
computation of one JN about five seconds on a laptop.
20In additional analyses not presented here, we replicated these tables using polynomials of degree 2, as well as setting

τN = 0. The qualitative finding of many positive but insignificant test statistics remains. In isolation, this finding may
raise questions about the test’s power. However, the test exhibits reasonable power in our Monte Carlo exercise and also
rejects rationalizability in an empirical application elsewhere (Hubner 2017).
We also checked whether small but positive test statistics are caused by adding-up constraints, i.e. by the fact that all
components of π that correspond to one budget must jointly be on some unit simplex. The estimator π̂ can slightly
violate this. Adding-up failures occur but are at least one order of magnitude smaller than the distance from a typical
π̂ to the corresponding projection η̂.

30

KITAMURA AND STOYE

3 goods

4 goods

I

H

JN

75-81 36

6409

3.67

76-82 39

4209

77-83 41

p

I

H

5 goods

JN

p

JN

I

H

.38 52

39957 5.43 .29 55

53816

4.75 .24

11.6

.14 65

82507 5.75 .39 65

82507

5.34 .31

7137

9.81

.17 65 100728 6.07 .39 68 133746

4.66 .38

78-84 32

3358

7.38

.24 62

85888 2.14 .70 67 116348

1.45 .71

79-85 35

5628

.114

.96 71 202686 .326 .92 79 313440

.219 .94

80-86 38

7104 .0055 .998 58

81-87 26

713 .0007 .998 42

68738 1.70 .81 66 123462

p

7.91 .21

9621 .640 .89 52

28089

6.33 .27

82-88 15

42

0

1 21

177 .298 .60 31

1283

9.38 .14

83-89 13

14

0

1 15

31 .263 .49 15

31

9.72 .13

84-90 15

42

0

1 15

42 .251 .74 15

42 10.25 .24

85-91 15

63

.062

.77 19

195 3.59 .45 21

331

3.59 .44

86-92 24

413

1.92

.71 33

1859 7.27 .35 35

3739

9.46 .28

87-93 45 17880

1.33

.74 57

52316 6.60 .44 70 153388

6.32 .38

88-94 39

4153

1.44

.70 67 136823 6.95 .38 77 313289

6.91 .38

89-95 26

840

.042

.97 69 134323 4.89 .35 78 336467

5.84 .31

90-96 19

120

.040

.95 56

3.55 .25

91-97 17

84

.039

.93 40

7379 3.32 .26 50

19000

3.27 .24

92-98 13

21

.041

.97 26

897 .060 .93 26

897

.011 .99

9

3

.037

.66 15

93-99

52036 4.42 .19 76 272233

63

0

1 15

63

0

1

Table 3. Empirical results with 7 periods. I = number of patches, H = number of
rationalizable discrete demand vectors, JN = test statistic, p = p-value.

add to less than 1. The estimated sum equals 1.006, leading to a tiny and statistically insignificant
violation. This phenomenon occurs frequently and seems to cause the many positive but insignificant
values of JN . The frequency of its occurrence, in turn, has a simple cause that may also appear
in other data: If two budgets are slight rotations of each other and demand distributions change
continuously in response, then rationalizable population probabilities for the relevant patches of these
two budgets will sum to just less than 1. If these probabilities are estimated independently across
budgets, the estimates will frequently add to slightly more than 1. With 7 or 8 mutually intersecting

31

3 goods
JN

p

71853 11.4

.17

76-83 64 114550 9.66

.24

77-84 52

57666 9.85

.20

78-85 49

76746 7.52

.26

I
75-82 51

H

79-86 55 112449 .114 .998
80-87 41

13206 3.58

.58

81-88 27

713

0

1

82-89 16

42

0

1

83-90 16

42

0

1

84-91 20

294 .072

.89

85-92 27

1239 2.24

.68

86-93 46

17880 1.54

.75

87-94 48

39913 1.55

.75

88-95 42

12459 1.68

.70

89-96 27

840 .047

.97

90-96 24

441 .389

.83

91-98 22

258 1.27

.52

92-99 14

21 .047

.96

Table 4. Empirical results with 8 periods. I = number of patches, H = number of
rationalizable discrete demand vectors, JN = test statistic, p = p-value.

budgets, there are many opportunities for such reversals, and positive but insignificant test statistics
may become ubiquitous.
The phenomenon of estimated choice frequencies typically not being rationalizable means that
there is need for a statistical testing theory and also a theory of rationality constrained estimation.
The former is this paper’s main contribution. We leave the latter for future research.

32

KITAMURA AND STOYE

8. Conclusion
This paper presented asymptotic theory and computational tools for nonparametric testing of
Random Utility Models. Again, the null to be tested was that data was generated by a RUM, interpreted as describing a heterogeneous population, where the only restrictions imposed on individuals’
behavior were “more is better” and SARP. In particular, we allowed for unrestricted, unobserved
heterogeneity and stopped far short of assumptions that would recover invertibility of demand. We
showed that testing the model is nonetheless possible. The method is easily adapted to choice problems that are discrete to begin with, and one can easily impose more, or fewer, restrictions at the
individual level.
Possibilities for extensions and refinements abound, and some of these have already been explored. We close by mentioning further salient issues.
(1) We provide algorithms (and code) that work for reasonably sized problem, but it would be
extremely useful to make further improvements in this dimension.
(2) The extension to infinitely many budgets would be of obvious interest. Theoretically, it can be
handled by considering an appropriate discretization argument (McFadden 2005). For the proposed
projection-based econometric methodology, such an extension requires evaluating choice probabilities
locally over points in the space of p via nonparametric smoothing, then use the choice probability
estimators in the calculation of the JN -statistic. The asymptotic theory then needs to be modified.
Another approach that can mitigate the computational constraint is to consider a partition of the space
of p such that RK
+ = P1 ∪P2 · · ·∪PM . Suppose we calculate the JN -statistic for each of these partitions.
Given the resulting M -statistics, say JN1 , · · · , JNM , we can consider JNmax := max1≤m≤M JNm or a
weighted average of them. These extensions and their formal statistical analysis are of practical
interest.
(3) It might frequently be desirable to control for observable covariates to guarantee the homogeneity
of the distribution of unobserved heterogeneity. This requires incorporating nonparametric smoothing
in estimating choice probabilities as in Section 5.1, then averaging the corresponding JN -statistics over
the covariates. This extension will be pursued.
(4) Natural next steps after rationality testing are extrapolation to (bounds on) counterfactual demand
distributions and welfare analysis, i.e. along the lines of BBC (2008) or, closer to our own setting,
Adams (2016) and Deb, Kitamura, Quah, and Stoye (2016). This extension is being pursued.

33

(5) The econometric techniques outlined here can be potentially useful in much broader contexts. Existing proposals for testing in moment inequality models (Andrews and Guggenberger 2009, Andrews
and Soares 2010, Bugni, Canay, and Shi 2015, Romano and Shaikh 2010) use a similar test statistic but
work with H-representations. In settings in which theoretical restrictions inform a V-representation
of a cone or, more generally, a polyhedron, the H-representation will typically not be available in
practice. We expect that our method can be used in many such cases.
References
Adams, A. (2016): “Mutually consistent revealed preference bounds,” Manuscript, University of Oxford.
Afriat, S. N. (1967): “The Construction of Utility Functions from Expenditure Data,” International Economic Review,
8(1), 67–77.
Andrews, D. W. (1991): “Heteroskedasticity and autocorrelation consistent covariance matrix estimation,” Econometrica, 59, 817–858.
Andrews, D. W., and P. Guggenberger (2009): “Validity Of Subsampling And “Plug-In Asymptotic” Inference For
Parameters Defined By Moment Inequalities,” Econometric Theory, 25, 669–709.
(2010): “Asymptotic size and a problem with subsampling and with the m out of n bootstrap,” Econometric
Theory, 26(02), 426–468.
Andrews, D. W., and G. Soares (2010): “Inference for Parameters Defined by Moment Inequalities Using Generalized
Moment Selection,” Econometrica, 78, 119–157.
Blundell, R., M. Browning, L. Cherchye, I. Crawford, B. De Rock, and F. Vermeulen (2015): “Sharp
for SARP: Nonparametric Bounds on Counterfactual Demands,” American Economic Journal: Microeconomics, 7(1),
43–60.
Blundell, R., M. Browning, and I. Crawford (2003): “Nonparametric Engel Curves and Revealed Preference,”
Econometrica, 71(1), 205–240.
(2007): “Improving Revealed Preference Bounds On Demand Responses,” International Economic Review,
48(4), 1227–1244.
(2008): “Best Nonparametric Bounds on Demand Responses,” Econometrica, 76(6), 1227–1262.
Blundell, R., D. Kristensen, and R. Matzkin (2014): “Bounding quantile demand functions using revealed preference inequalities,” Journal of Econometrics, 179(2), 112 – 127.
Blundell, R., and J. L. Powell (2000): “Endogeneity in nonparametric and semiparametric regression models,”
Manuscript.
Blundell, R., and J. L. Powell (2003): “Endogeneity in nonparametric and semiparametric regression models,”
Econometric Society Monographs, 36, 312–357.
Bugni, F. A. (2010): “Bootstrap Inference in Partially Identified Models Defined by Moment Inequalities: Coverage of
the Identified Set,” Econometrica, 78(2), 735–753.
Bugni, F. A., I. A. Canay, and X. Shi (2015): “Specification tests for partially identified models defined by moment
inequalities,” Journal of Econometrics, 185(1), 259 – 282.

34

KITAMURA AND STOYE

Canay, I. A. (2010): “{EL} inference for partially identified models: Large deviations optimality and bootstrap validity,”
Journal of Econometrics, 156(2), 408 – 425.
Chernoff, H. (1954): “On the Distribution of the Likelihood Ratio,” Annals of Mathematical Statistics, 25, 573–578.
Chernozhukov, V., H. Hong, and E. Tamer (2007): “Estimation and Confidence Regions for Parameter Sets in
Econometric Model,” Econometrica, 75(5), 1243–1284.
Deb, R., Y. Kitamura, J. Quah, and J. Stoye (2016): “Revealed Price Preference: Theory and Stochastic Testing,”
Manuscript, University of Toronto.
Dette, H., S. Hoderlein, and N. Neumeyer (2016): “Testing multivariate economic restrictions using quantiles:
The example of Slutsky negative semidefiniteness,” Journal of Econometrics, 191(1), 129–144.
Floyd, R. W. (1962): “Algorithm 97: Shortest Path,” Commun. ACM, 5(6), 345–.
Gourieroux, C., A. Holly, and A. Monfort (1982): “Likelihood Ratio Test, Wald Test, and Kuhn-Tucker Test in
Linear Models with Inequality Constraints on the Regression Parameters,” Econometrica, 50(1), 63–80.
Gruber, P. (2007): Convex and Discrete Geometry, Grundlehren der mathematischen Wissenschaften. New York:
Springer.
Grünbaum, B., V. Kaibel, V. Klee, and G. M. Ziegler (2003): Convex polytopes. New York: Springer.
Guggenberger, P., J. Hahn, and K. Kim (2008): “Specification Testing under Moment Inequalities,” Econometrics
Letters, 99, 375–378.
Hansen, L. P. (1982): “Large Sample Properties of Generalized Method of Moments Estimators,” Econometrica, 50(4),
1029–54.
Hausman, J. A., and W. K. Newey (2016): “Individual Heterogeneity and Average Welfare,” Econometrica, 84(3),
1225–1248.
Hoderlein, S. (2011): “How many consumers are rational?,” Journal of Econometrics, 164(2), 294–309.
Hoderlein, S., and J. Stoye (2014): “Revealed Preferences in a Heterogeneous Population,” The Review of Economics
and Statistics, 96(2), 197–213.
(2015): “Testing stochastic rationality and predicting stochastic demand: the case of two goods,” Economic
Theory Bulletin, 3(2), 313–328.
Houthakker, H. S. (1950): “Revealed Preference and the Utility Function,” Economica, 17(66), 159–174.
Hubner, S. (2017): “Its complicated: A Nonparametric Test of Preference Stability between Singles and Couples,”
Preprint, University of Oxford.
Imbens, G. W., and C. Manski (2004): “Confidence Intervals for Partially Identified Parameters,” Econometrica, 72,
1845–1857.
Imbens, G. W., and W. K. Newey (2002): “Identification and Estimation of Triangular Simultaneous Equation Models
without Additivity,” NBER Technical Working Paper Series.
(2009): “Identification and estimation of triangular simultaneous equations models without additivity,” Econometrica, 77(5), 1481–1512.
Kawaguchi, K. (2017): “Testing rationality without restricting heterogeneity,” Journal of Econometrics, 197(1), 153 –
171.
Kudo, A. (1963): “A Multivariate Analogue of the One-Sided Test,” Biometrika, 50(3/4), 403–418.

35

Lazzati, N., J. Quah, and K. Shirai (2017): “A revealed preference theory of monotone choice and strategic complementarity,” Manuscript, University of California Santa Cruz.
Lewbel, A. (2001): “Demand Systems with and without Errors,” American Economic Review, 91(3), 611–618.
Manski, C. F. (2007): “Partial Identification Of Counterfactual Choice Probabilities,” International Economic Review,
48(4), 1393–1410.
(2014): “Identification of incomeleisure preferences and evaluation of income tax policy,” Quantitative Economics, 5(1), 145–174.
Matzkin, R. (2006): “Heterogeneous Choice,” in Advances in Econometrics: Proceedings of the 9th World Congress.
Budapest: Cambridge University Press.
McFadden, D., and K. Richter (1991): “Stochastic rationality and revealed stochastic preference,” in Preferences,
Uncertainty and Rationality, ed. by J. Chipman, D. McFadden, and K. Richter. Boulder: Westview Press, pp. 161–186.
McFadden, D. L. (2005): “Revealed Stochastic Preference: A Synthesis,” Economic Theory, 26(2), 245–264.
Newey, W. K. (1997): “Convergence rates and asymptotic normality for series estimators,” Journal of Econometrics,
79(1), 147–168.
Perlman, M. D. (1969): “One-sided Testing Problems in Multivariate Analysis,” Annals of Mathematical Statistics,
40, 549–567.
Richter, M. K. (1966): “Revealed Preference Theory,” Econometrica, 34(3), 635–645.
Romano, J., and A. Shaikh (2010): “Inference for the Identified Set in Partially Identified Econometric Models,”
Econometrica, 78(1), 169–211.
Rosen, A. M. (2008): “Confidence sets for partially identified parameters that satisfy a finite number of moment
inequalities,” Journal of Econometrics, 146(1), 107–117.
Samuelson, P. A. (1938): “A Note on the Pure Theory of Consumer’s Behaviour,” Economica, 5(17), 61–71.
Shapiro, A. (1988): “Towards a Unified Theory of Inequality Constrained Testing in Multivariate Analysis,” International Statistical Review, 56(1), 49–62.
Stoye, J. (2009): “More on Confidence Intervals for Partially Identified Parameters,” Econometrica, 77, 1299–1315.
Takemura, A., and S. Kuriki (1997): “Weights of χ2 distribution for smooth or piecewise smooth cone alternatives,”
The Annals of Statistics, 25(6), 2368–2387.
Varian, H. R. (1982): “The Nonparametric Approach to Demand Analysis,” Econometrica, 50(4), 945–973.
Wolak, F. A. (1991): “The Local Nature of Hypothesis Tests Involving Inequality Constraints in Nonlinear Models,”
Econometrica, 59, 981–995.
Ziegler, G. M. (1995): Lectures on polytopes, Graduate texts in mathematics. New York: Springer.

S1

SUPPLEMENTAL MATERIALS
Appendix A: Proofs and Further Details of Inferential Procedures
Proof of Theorem 3.1. The proof uses nonstochastic demand systems, which can be identified with
vectors (d1 , . . . , dJ ) ∈ B1 × · · · × BJ . Such a system is rationalizable if dj ∈ arg maxy∈Bj u(y), j =
1, . . . , J for some utility function u.
Rationalizability of nonstochastic demand systems is well understood. In particular, and irrespective of whether we define rationalizability by GARP or SARP, it is decidable from knowing
the preferences directly revealed by choices, hence from knowing patches containing (d1 , . . . , dJ ). It
follows that for all nonstochastic demand systems that select from the same patches, either all or none
are rationalizable.
Fix (P1 , ..., PJ ). Let the set Y ∗ collect one “representative” element (e.g., the geometric center

point) of each patch. Let (P1∗ , ..., PJ∗ ) be the unique stochastic demand system concentrated on Y ∗ and

having the same vector representation as (P1 , ..., PJ ). The previous paragraph established that demand
systems can be arbitrarily perturbed within patches, so (P1 , ..., PJ ) is rationalizable iff (P1∗ , ..., PJ∗ ) is.
It follows that rationalizability of (P1 , ..., PJ ) can be decided from its vector representation π, and
that it suffices to analyze stochastic demand systems supported on Y ∗ .
Now, any stochastic demand system is rationalizable iff it is a mixture of rationalizable nonstochastic ones. Since Y ∗ is finite, there are finitely many nonstochastic demand systems supported
on it; of these, a subset will be rationalizable. Noting that these demand systems are characterized
by binary vector representations corresponding to columns of A, the statement of the Theorem is
immediate for the restricted class of stochastic demand systems supported on Y ∗ .



Proof of Theorem 3.2. We begin with some preliminary observations. Throughout this proof, c(Bi )
denotes the object actually chosen from budget Bi .
(i) If there is a choice cycle of any finite length, then there is a cycle of length 2 or 3 (where
a cycle of length 2 is a WARP violation). To see this, assume there exists a length N choice cycle
c(Bi )  c(Bj )  c(Bk )  ...  c(Bi ). If c(Bk )  c(Bi ), then a length 3 cycle has been discovered. Else,
there exists a length N − 1 choice cycle c(Bi )  c(Bk )  ...  c(Bi ). The argument can be iterated
until N = 4.
(ii) Call a length 3 choice cycle irreducible if it does not contain a length 2 cycle. Then a choice
pattern is rationalizable iff it contains no length 2 cycles and also no irreducible length 3 cycles. (In
particular, one can ignore reducible length 3 cycles.) This follows trivially from (i).

S2

KITAMURA AND STOYE

(iii) Let J = 3 and M = 1, i.e. assume there are three budgets but two of them fail to
intersect. Then any length 3 cycle is reducible. To see this, assume w.l.o.g. that B1 is below B3 ,
thus c(B3 )  c(B1 ) by monotonicity. If there is a choice cycle, we must have c(B1 )  c(B2 )  c(B3 ).
c(B1 )  c(B2 ) implies that c(B2 ) is below B1 , thus it is below B3 . c(B2 )  c(B3 ) implies that c(B3 ) is
below B2 . Thus, choice from (B2 , B3 ) violates WARP.
We are now ready to prove the main result. The nontrivial direction is “only if,” thus it suffices
to show the following: If choice from (B1 , ..., BJ−1 ) is rationalizable but choice from (B1 , ..., BJ ) is not,
then choice from (BM +1 , ..., BJ ) cannot be rationalizable. By observation (ii), if (B1 , ..., BJ ) is not
rationalizable, it contains either a 2-cycle or an irreducible 3-cycle. Because choice from all triplets
within (B1 , ..., BJ−1 ) is rationalizable by assumption, it is either the case that some (Bi , BJ ) constitutes
a 2-cycle or that some triplet (Bi , Bk , BJ ), where i < k w.l.o.g., reveals an irreducible choice cycle.
In the former case, Bi must intersect BJ , hence i > M , hence the conclusion. In the latter case, if
k ≤ M , the choice cycle must be a 2-cycle in (Bi , Bk ), contradicting rationalizability of (B1 , ..., BJ−1 ).
If i ≤ M , the choice cycle is reducible by (iii). Thus, i > M , hence the conclusion.
Proof of Lemma 4.1. Letting ντ = ν − (τ /H)1H in Cτ = {Aν|ν ≥ (τ /H)1H } we have

Cτ

= {A[ντ + (τ /H)1H ]|ντ ≥ 0}
= C ⊕ (τ /H)A1H
= {t : t − (τ /H)A1H ∈ C}

where ⊕ signifies Minkowski sum. Define

φ = −BA1H /H.

Using the H-representation of C,

Cτ

= {t : B(t − (τ /H)A1H ) ≤ 0}
= {t : Bt ≤ −τ φ}.



S3

Note that the above definition of φ implies φ ∈ col(B). Also define
Φ := −BA

b0
 1
 .
= −  ..

b0m
=




 [a1 , · · · , aH ]


{Φkh }

where Φkh = b0k ah , 1 ≤ k ≤ m, 1 ≤ h ≤ H and let eh be the h-th standard unit vector in RH . Since
eh ≥ 0, the V-representation of C implies that Aeh ∈ C, and thus
BAeh ≤ 0
by its H-representation. Therefore
Φkh = −e0k BAeh ≥ 0,

(S.1)

But if k ≤ m̄, it cannot be that

1 ≤ k ≤ m, 1 ≤ h ≤ H.

aj ∈ {x : b0k x = 0}

for all j

whereas
b0k ah = 0
holds for m̄ + 1 ≤ k ≤ m, 1 ≤ h ≤ H. Therefore if k ≤ m̄, Φkh = b0k ah is nonzero at least for one
h, 1 ≤ h ≤ H, whereas if k > m̄, Φkh = 0 for every h. Since (S.1) implies that all of {Φkh }H
h=1 are
non-negative, we conclude that
φk =

H
1 X
Φkh > 0
H
h=1

for every k ≤ m̄ and φk = 0 for every k > m̄. We now have
Cτ = {t : Bt ≤ −τ φ}
where φ satisfies the stated properties (i) and (ii).



Before we present the proof of Theorem 4.2, it is necessary to specify a class of distributions,
to which we impose a mild condition that guarantees stable behavior of the statistic JN . To this
end, we further specify the nature of each row of B. Recall that w.l.o.g. the first m̄ rows of B
correspond to inequality constraints, whereas the rest of the rows represent equalities. Note that
the m̄ inequalities include nonnegativity constraints πi|j ≥ 0, 1 ≤ i ≤ Ij , 1 ≤ j ≤ J, represented by
the row of B consisting of a negative constant for the corresponding element and zeros otherwise.

S4

KITAMURA AND STOYE

Likewise, the identities that

PIj

is constant across 1 ≤ j ≤ J are included in the set of equality

i=1 πi|j

constraints.21 We show in the proof that the presence of these “definitional” equalities/inequalities,
which always hold by construction of π̂, do not affect the asymptotic theory even when they are (close
to) be binding. Define K = {1, ..., m}, and let KD be the set of indices for the rows of B corresponding
to the above nonnegativity constraints and the constant-sum constraints. Let KR = K \ KD , so that

b0k π ≤ 0 represents an economic restriction if k ∈ KR .22 Recalling the choice vectors (dj|1 , ..., dj|Nj )
are IID-distributed within each time period j, 1 ≤ j ≤ J, let dj denote the choice vector of a consumer

facing budget j (therefore w.l.o.g we can let dj = dj|1 ). Define d = [d01 , ..., d0J ]0 , a random I-vector of
binary variables. Note E[d] = π. Let
g = Bd
= [g1 , ..., gm ]0 .
With these definitions, consider the following requirement:
p
Condition S.1. For each k ∈ KR , var(gk ) > 0 and E[|gk / var(gk )|2+c1 ] < c2 hold, where c1 and c2
are positive constants.
This type of condition is standard in the literature; see, for example, Andrews and Soares (2010).
Proof of Theorem 4.2. By applying the Minkowski-Weyl theorem and Lemma 4.1 to JN and

J˜N (τN ), we see that our procedure is equivalent to comparing
JN =

min

t∈RI :Bt≤0

N [π̂ − t]0 Ω[π̂ − t]

to the 1 − α quantile of the distribution of
J˜N =

min

t∈RI :Bt≤−τN φ

N [η̃τN − t]0 Ω[η̃τN − t]

with φ = [φ̄0 , (0, ..., 0)0 ]0 , φ̄ ∈ Rm̄
++ , where
1
η̃τN = η̂τN + √ N (0, Ŝ),
N
η̂τN =

argmin
t∈RI :Bt≤−τ

Nφ

N [π̂ − t]0 Ω[π̂ − t].

21If we impose the (redundant) restriction 10 ν = 1 in the definition of C, then the corresponding equality restrictions
H

would be

P Ij

i=1

πi|j = 1 for every j.

22In (4.6), KR contains only the last row of the matrix.

S5

Suppose B has m rows and rank(B) = `. Define an ` × m matrix K such that KB is a matrix whose
rows consist of a basis of the row space row(B). Also let M be an (I − `) × I matrix whose rows form

an orthonormal basis of kerB = ker(KB), and define P = KB
M . Finally, let ĝ = B π̂ and ĥ = M π̂.
Then
JN



0



KB
KB
−1 0
−1
= min N
(π̂ − t) P ΩP
(π̂ − t)
Bt≤0
M
M




K[ĝ − Bt] 0 −1 0
−1 K[ĝ − Bt]
= min N
.
P ΩP
Bt≤0
ĥ − M t
ĥ − M t

Let

 
Kγ
≤
=
I
U1 =
: γ = Bt, h = M t, B t ≤ 0, B t = 0, t ∈ R
h
then writing α = KBt and h = M t,




K ĝ − α 0 −1 0
−1 K ĝ − α
JN = min N
P ΩP
.
ĥ − h
ĥ − h
(αh)∈U1
Also define
 
 ≤

Kγ
γ
≤
m̄ =
I−`
U2 =
:γ=
, γ ∈ R+ , γ = 0, γ ∈ col(B), h ∈ R
h
γ=
where col(B) denotes the column space of B. Obviously U1 ⊂ U2 . Moreover, U2 ⊂ U1 holds. To see
∗
this, let Kγ
be an arbitrary element of U2 . We can always find t∗ ∈ RI such that γ ∗ = Bt∗ . Define
∗
h
t∗∗ := t∗ + M 0 h∗ − M 0 M t∗
then Bt∗∗ = Bt∗ = γ ∗ , therefore B ≤ t∗∗ ≤ 0 and B = t∗∗ = 0. Also, M t∗∗ = M t∗ +M M 0 h∗ −M M 0 M t∗ =
∗
h∗ , therefore Kγ
is an element of U1 as well. Consequently,
h∗
U1 = U2 .
We now have



K ĝ − α 0 −1 0
−1 K ĝ − α
P ΩP
= min N
ĥ − h
ĥ − h
(αh)∈U2

0


K ĝ − α
−1 0
−1 K ĝ − α
= N min
P ΩP
.
y
y
(αy)∈U2


JN

Define

 0
 
x
−1 0
−1 x
T (x, y) =
P ΩP
,
y
y

x ∈ R` , y ∈ RI−` ,

and
t(x) := min T (x, y),
y∈RI−`

s(g) :=

0

min

γ=[γ ≤ ,γ =0 ]0 ,γ ≤ ≤0,γ = =0,γ∈col(B)

t(K[g − γ]).

S6

KITAMURA AND STOYE

It is easy to see that t : R` → R+ is a positive definite quadratic form. We can write
JN

= N

min

0

γ=[γ ≤ ,γ =0 ]0 ,γ ≤ ≤0,γ = =0,γ∈col(B)

t(K[ĝ − γ])

= N s(ĝ)
√
= s( N ĝ).
We now show that tightening can turn non-binding inequality constraints into binding ones but not
vice versa. Note that, as will be seen below, this observation uses diagonality of Ω and the specific
geometry of the cone C. Let γ̂τkN , ĝ k and φk denote the k-th elements of γ̂τN = B η̂τN , ĝ and φ.

Moreover, define γτ (g) = [γ 1 (g), ..., γ m (g)]0 = argminγ=[γ ≤ 0 ,γ =0 ]0 ,γ ≤ ≤−τ φ̄,γ = =0,γ∈col(B) t(K[g − γ]) for

g ∈ col(B), and let γτk (g) be its k-th element. Then γ̂τN = γτN (ĝ). Finally, define βτ (g) = γτ (g) + τ φ

for τ > 0 and let βτk (g) denote its k-th element. Note γτk (g) = φk = βτk (g) = 0 for every k > m̄ and g.
Now we show that for each k ≤ m̄ and for some δ > 0,
βτk (g) = 0
if |g k | ≤ τ δ and g j ≤ τ δ, 1 ≤ j ≤ m̄. In what follows we first show this for the case with Ω = II , where
II denotes the I-dimensional identity matrix, then generalize the result to the case where Ω can have
arbitrary positive diagonal elements.
For τ > 0 and δ > 0 define hyperplanes
Hkτ = {x : b0k x = −τ φk },
Hk = {x : b0k x = 0},
half spaces
τ
H∠k
(δ) = {x : b0k x ≤ τ δ},

and also
Sk (δ) = {x ∈ C : |b0k x| ≤ τ δ}
for 1 ≤ k ≤ m. Define
L = ∩m
k=m̄+1 Hk ,
a linear subspace of RI . In what follows we show that for small enough δ > 0, every element x∗ ∈ RI
such that
(S.2)

τ
τ
x∗ ∈ S1 (δ) ∩ · · · ∩ Sq (δ) ∩ H∠q+1
(δ) ∩ · · · H∠m
(δ) for some q ∈ {1, ..., m̄}

S7

satisfies
x∗ |Cτ ∈ H1τ ∩ · · · ∩ Hqτ ∩ L

(S.3)

where x∗ |Cτ denotes the orthogonal projection of x∗ on Cτ . Let g ∗ k = b0k x∗ , k = 1, ..., m. Note that an
element x∗ fulfills (S.2) iff |g ∗ k | ≤ τ δ, 1 ≤ k ≤ q and g ∗ j ≤ τ δ, q + 1 ≤ j ≤ m̄. Likewise, (S.3) holds

iff βkτ (g ∗ ) = 0, 1 ≤ k ≤ q (recall βkτ (g ∗ ) = 0 always holds for k > m̄). Thus in order to establish the

desired property of the function βτ (·), we show that (S.2) implies (S.3). Suppose it does not hold;
then without loss of generality, for an element x∗ that satisfies (S.2) for an arbitrary small δ > 0, we
have
(S.4)

x∗ |Cτ ∈ H1τ ∩ · · · ∩ Hrτ ∩ L

and

x∗ |Cτ ∈
/ Hjτ , r + 1 ≤ j ≤ q

for some 1 ≤ r ≤ q − 1. Define halfspaces
τ
H∠k
= {x : b0k x ≤ −τ φk },

H∠k = {x : b0k x ≤ 0}
for 1 ≤ k ≤ m, τ > 0 and also let
F = H1 ∩ · · · ∩ Hr ∩ C,
then for (S.4) to hold for some x∗ ∈ RI satisfying (S.2) for an arbitrary small δ > 0 we must have
τ
τ
F | (H1τ ∩ · · · ∩ Hrτ ∩ L) ⊂ int(H∠r+1
∩ · · · ∩ H∠q
)

(Recall the notation | signifies orthogonal projection. Also note that if dim(F ) = 1, then (S.4) does
not occur under (S.2).) Therefore if we let
∆(J) = {x ∈ RI : 10I x = J, x ≥ 0},
i.e. the simplex with vertices (J, 0, · · · , 0), · · · , (0, · · · , 0, J), we have
(S.5)

τ
τ
(F ∩ ∆(J)) | (H1τ ∩ · · · ∩ Hrτ ∩ L) ⊂ int(H∠r+1
∩ · · · ∩ H∠q
).

Let {a1 , ..., aH } = A denote the collection of the column vectors of A. Then {the vertices of F ∩
¯ ∈ F ∩ ∆(J). Let B(ε, x) denote the ε-(open) ball with center x ∈ RI . By (S.5),
∆(J)} ∈ A. Let ā, ā
B ε, ā| ∩rj=1 Hjτ ∩ L



τ
τ
⊂ int(H∠r+1
∩ · · · ∩ H∠q
) ∩ H∠1 ∩ · · · ∩ H∠r

S8

KITAMURA AND STOYE

holds for small enough ε > 0. Let āτ := ā +

τ
H A1H ,

¯τ := ā
¯+
ā


0
¯ − ā) =
ā|(∩rj=1 Hjτ ) ∩ L − ā (ā

τ
H A1H ,

then


0 τ
¯ − āτ )
ā|(∩rj=1 Hjτ ) ∩ L − ā (ā

= 0
 

¯τ ∈ (∩rj=1 Hjτ )∩L. We can then take z ∈ B ε, ā|(∩rj=1 Hjτ ) ∩ L such that (z−ā)0 (ā
¯ −ā) <
since āτ , ā

¯) of distinct elements in A
0. By construction z ∈ C, which implies the existence of a triplet (a, ā, ā

¯ − ā) < 0. In what follows we show that this cannot happen, then the desired
such that (a − ā)0 (ā

property of βτ is established.
So let us now show that
(S.6)

(a1 − a0 )0 (a2 − a0 ) ≥ 0 for every triplet (a0 , a1 , a2 ) of distinct elements in A.

Noting that a0i aj just counts the number of budgets on which i and j agree, define
φ(ai , aj ) = J − a0i aj ,
the number of disagreements. Importantly, note that φ(ai , aj ) = φ(aj , ai ) and that φ is a distance (it
is the taxicab distance between elements in A, which are all 0-1 vectors). Now
(a1 − a0 )0 (a2 − a0 )
= a01 a2 − a00 a2 − a01 a0 + a00 a0
= J − φ(a1 , a2 ) − (J − φ(a0 , a2 )) − (J − φ(a0 , a1 )) + J
= φ(a0 , a2 ) + φ(a0 , a1 ) − φ(a1 , a2 ) ≥ 0
by the triangle inequality.
Next we treat the case where Ω is not necessarily II . Write


ω12 0 . . . 0




 0 ω22 . . . 0 
.

Ω=

..


.


0 . . . 0 ωI2
The statistic JN in (4.1) can be rewritten, using the square-root matrix Ω1/2 ,
JN =

min

η ∗ =Ω1/2 η:η∈C

[π̂ ∗ − η ∗ ]0 [π̂ ∗ − η ∗ ]

or
JN = min
[π̂ ∗ − η ∗ ]0 [π̂ ∗ − η ∗ ]
∗
∗
η ∈C

S9

where
C ∗ = {Ω1/2 Aν|ν ≥ 0}
= {A∗ ν|ν ≥ 0}
with
A∗ = [a∗1 , ..., a∗H ], a∗h = Ω1/2 ah , 1 ≤ h ≤ H.
Then we can follow our previous argument replacing a’s with a∗ ’s, and using
∆∗ (J) = conv([0, ..., ωi , ....0]0 ∈ RI , i = 1, ..., I).
instead of the simplex ∆(J). Finally, we need to verify that the acuteness condition (S.6) holds for
A∗ = {a∗1 , ..., a∗H }.
For two I-vectors a and b, define a weighted taxicab metric
φΩ (a, b) :=

I
X
i=1

ωi |ai − bi |,

then the standard taxicab metric φ used above is φΩ with Ω = II . Moreover, letting a∗ = Ω1/2 a and
b∗ = Ω1/2 b, where each of a and b is an I-dimensional 0-1 vector, we have
a∗ 0 b∗ =

I
X
i=1

with ω̄ =

PI

i=1 ωi .

ωi [1 − |ai − bi |] = ω̄ − φΩ (a, b)

Then for every triplet (a∗0 , a∗1 , a∗2 ) of distinct elements in A∗

(a∗1 − a∗0 )0 (a∗2 − a∗0 ) = ω̄ − φΩ (a1 , a2 ) − ω̄ + φΩ (a0 , a2 ) − ω̄ + φΩ (a0 , a1 ) + ω̄ − φΩ (a0 , a0 )
= φΩ (a1 , a2 ) − φΩ (a0 , a2 ) − φΩ (a0 , a1 )
≥ 0,
which is the desired acuteness condition. Since JN can be written as the minimum of the quadratic

form with identity-matrix weighting subject to the cone generated by a∗ ’s, all the previous arguments
developed for the case with Ω = II remain valid.
Defining ξ ∼ N(0, Ŝ) and ζ = Bξ,


0



KB
KB
−1/2
−1 0
−1
−1/2
˜
JN ∼
min N
(η̂τN + N
ξ − t) P ΩP
(η̂τN + N
ξ − t)
Bt≤−τN φ
M
M
 h
i
−1/2
= N
min
t
K
γ̂
+
N
ζ
−
γ
τ
N
0
γ=[γ ≤ ,γ =0 ]0 ,γ ≤ ≤−τN φ̄,γ = =0,γ∈col(B)

S10

KITAMURA AND STOYE
I

N

j
j
conditional on data {{di|j,n }i=1
}n=1
, j = 1, 2, ..., J. Moreover, defining γ τ = γ + τN φ in the above,

and using the definitions of βτ (·) and s(·)
J˜N

∼ N
= N
= N

0

min

 h
i
t K γ̂τN + τN φ + N −1/2 ζ − γ τ

min

 h
i
t K γτN (ĝ) + τN φ + N −1/2 ζ − γ τ

min

 h
i
t K βτN (ĝ) + N −1/2 ζ − γ τ

γ τ =[γ τ ≤ ,γ τ =0 ]0 ,γ τ ≤ ≤0,γ τ = =0,γ τ ∈col(B)
0

γ τ =[γ τ ≤ ,γ τ =0 ]0 ,γ τ ≤ ≤0,γ τ = =0,γ τ ∈col(B)
0

γ τ =[γ τ ≤ ,γ τ =0 ]0 ,γ τ ≤ ≤0,γ τ = =0,γ τ ∈col(B)



= s N 1/2 βτN (ĝ) + ζ



Let ϕN (ξ) := N 1/2 βτN (τN ξ) for ξ = (ξ1 , ..., ξm )0 ∈ col(B), then from the property of βτ shown above,
its k-th element ϕkN for k ≤ m̄ satisfies

ϕkN (ξ) = 0
k (τ ξ) = 0 for k > m̄.
if |ξ k | ≤ δ and ξ j ≤ δ, 1 ≤ j ≤ m for large enough N . Note ϕkN (ξ) = N 1/2 βN
N

Define ξˆ := ĝ/τN and using the definition of ϕN , we write
(S.7)



ˆ +ζ .
J˜N ∼ s ϕN (ξ)

Now we invoke Theorem 1 of Andrews and Soares (2010, AS henceforth). As noted before, the
function t is a positive definite quadratic form on R` , and so is its restriction on col(B). Then
their Assumptions 1-3 hold for the function s defined above if signs are adjusted appropriately as
our formulae deal with negativity constraints, whereas AS work with positivity constraints. (Note
that Assumption 1(b) does not apply here since we use a fixed weighting matrix.) The function ϕN
in (S.7) satisfies the properties of ϕ in AS used in their proof of Theorem 1. AS imposes a set of
restrictions on the parameter space (see their Equation (2.2) on page 124). Their condition (2.2) (vii) is
a Lyapounov condition for a triangular array CLT. Following AS, consider a sequence of distributions
√
0 , ..., π 0 ]0 , N = 1, 2, ... in P ∩ C such that (1)
N BπN → h for a non-positive h as N → ∞
πN = [π1N
JN
√
and (2) CovπN ( N B π̂) → Σ as N → ∞ where Σ is positive semidefinite. The Lyapounov condition
holds for b0k π̂ under πN for k ∈ KR as Condition S.1 is imposed for πN ∈ P. We do not impose

Condition S.1 for k ∈ KD . Note, however, that: (i) The equality b0k π̂ ≤ 0 holds by construction for
every k ∈ KD and therefore its behavior does not affect JN ; (ii) If varπN (gk ) converges to zero for
√
some k ∈ KD , then N b0k [η̃τN − η̂τN ] = op (1) and therefore its contribution to J˜N is asymptotically

negligible in the size calculation. The other conditions in AS10, namely (2.2)(i)-(vi), hold trivially.
Finally, Assumptions GMS 2 and GMS 4 of AS10 are concerned with their thresholding parameter

S11

κN for the k-th moment inequality, and by letting κN = N 1/2 τN φk , the former holds by the condition
√
N τN ↑ ∞ and the latter by τN ↓ 0. Therefore we conclude
lim inf inf Pr{JN ≤ ĉ1−α } = 1 − α.
N →∞ π∈P∩C


Further details of the procedure in Section 5.1 Define q K (w) = (q1K (w), ..., qKK (w))0 , where
qjK (w), j = 1, ..., K are basis functions (e.g. power series or splines) of w. Instead of sample frequency
estimators, for each j, 1 ≤ j ≤ J we use
π̂i|j

= q

K(j)

0

b − (j)
(wj ) Q

Nj
X

q K(j) (wn(j) )di|j,n(j) /Nj ,

n(j)=1

b
Q(j)
=

Nj
X

q K(j) (wn(j) )q K(j) (wn(j) )0 /Nj

n(j)=1

π̂j

= (π̂1|j , ..., π̂Ij |j )0 ,

π̂ = (π̂10 , ..., π̂J0 )0 ,
to estimate πi|j , where A− denotes a symmetric generalized inverse of A and K(j) is the number of
basis functions applied to Budget Bj . The estimators π̂i|j ’s may not take their values in [0, 1]. This
does not seem to cause a problem asymptotically, though as in Imbens and Newey (2009), we may
(and do, in the application) instead use

b − (j)
π̂i|j = G q K(j) (wj )0 Q

Nj
X


q K(j) (wn(j) )di|j,n(j) /Nj  ,

n(j)=1

where G denotes the CDF of Unif(0, 1). Then an appropriate choice of τN is τN =

q

log n
n

with

(j)

n = min Nj Ij /trace(vN )
j

(j)

where vN is defined below. Strictly speaking, asymptotics with nonparametric smoothing involve
bias, and the bootstrap does not solve the problem. A standard procedure is to claim that one used
undersmoothing and can hence ignore the bias, and we follow this convention. The bootstrapped test
statistic J˜N (τN ) is obtained applying the same replacements to the formula (4.5), although generating
(j)

η̃τN requires a slight modification. Let η̂τN (j) be the j-th block of the vector η̂τN , and v̂N satisfy
(j) (j) −1

v̂N vN

→p IIj , where
(j)

(j)

K(j)
vN = [IIj ⊗ q K(j) (wj )0 QN (j)−1 ]ΛN [IIj ⊗ Q−1
(wj )]
N (j)q

S12

KITAMURA AND STOYE
0

0

(j)

with QN (j) := E[q K(j) (wn(j) )q K(j) (wn(j) ) ], ΛN := E[Σ(j) (wn(j) ) ⊗ q K(j) (wn(j) )q K(j) (wn(j) ) ], and

Σ(j) (w) := Cov[dj,n(j) |wn(j) = w]. Note that Σ(j) (w) = diag p(j) (w) −p(j) (w)p(j) (w)0 where p(j) (w) =
[p1|j (w), ..., pIj |j (w)]0 . For example, one may use

(j)
−
K(j)
b
(wj )]
v̂N = [IIj ⊗ q K(j) (wj )0 Q̂− (j)]Λ(j)[I
Ij ⊗ Q̂ (j)q
h
i
 (j)
PNj
b
b (j) (wn(j) ) ⊗ q K(j) (wn(j) )q K(j) (wn(j) )0 , Σ
b (j) (w) = diag pb(j) (w) −b
with Λ(j)
= N1j n(j)=1
Σ
p (w)b
p(j) (w)0 ,
K(j) (w
b − (j) PNj
pb(j) (w) = [b
p1|j (w), ..., pbIj |j (w)]0 and pbi|j (w) = q K(j) (w)0 Q
n(j) )di|j,n(j) /Nj . We
n(j)=1 q

use η̃τN = (η̃τN (1)0 , ..., η̃τN (J)0 )0 for the smoothed version of J˜N (τN ), where η̃τN (j) := η̂τN (j) +
(j)
√1 N (0, v̂N
), j = 1, ..., J.
Nj

I

N

j
j
Noting {{di|j,n(j) }i=1
, wn(j) }n(j)=1
are IID-distributed within each time period j, 1 ≤ j ≤ J, let

(dj , wj ) denote the choice-log-expenditure pair of a consumer facing budget j. Let d = [d01 , ..., d0J ]0 and
w = [w1 , ..., wJ ]0 , and define g = Bd = [g1 , ..., gm ]0 as before. Let Wj denote the support of wn(j) . For
a symmetric matrix A, λmin signifies its smallest eigenvalue.
Condition S.2. There exist positive constants c1 , c2 , δ, and ζ(K), K ∈ N such that the following
holds:
(i) π ∈ C;

(ii) For each k ∈ KR , var(gk |w = (w1 , ..., wJ )0 ) ≥ s2 (F1 , ..., FJ ) and E[(gk /s(F1 , ..., FJ ))4 |w =
(w1 , ..., wJ )0 ] < c1 hold for every (w1 , ..., wJ ) ∈ W1 × · · · WJ ;
(j)

(j)

(iii) supw∈Wj |pi|j (w) − q K (w)0 βK | ≤ c1 K −δ holds with some K-vector βK for every K ∈ N,
1 ≤ i ≤ Ij , 1 ≤ j ≤ J;

(iv) Letting qeK := CK,j q K , λmin E[e
q K (wn(j) )e
q K (wn(j) )0 ] ≥ c2 holds for every K and j, where
CK,j , K ∈ N, 1 ≤ j ≤ J are constant nonsingular matrices;

(v) maxj supw∈Wj ke
q K (w)k ≤ c2 ζ(K) for every K ∈ N.


Condition S.2(ii) is a version of Condition S.1 that accommodates the conditioning by w and series
estimation. Conditions S.2(iii)-(v) are standard regularity commonly used in the series regression
literature: (iii) imposes a uniform approximation error bound, (iv) avoids singular design (note the
existence of the matrices CK,j suffices) and (v) controls the lengths of the series terms used.
The next condition imposes restrictions on tuning parameters.
Condition S.3. τN and K(j), j = 1, ..., J satisfy
√
τN ↓ 0, and nτN ↑ ∞.

p

Nj K −δ (j) ↓ 0, ζ(K(j))2 K(j)/Nj ↓ 0, j = 1, ..., J,

S13

Proof of Theorem 5.1. We begin by introducing some notation.
Notation. Let bk,i , k = 1, ..., m, i = 1, ..., I denote the (k, i) element of B, then define
bk (j) = [bk,N1 +···Nj−1 +1 , bk,N1 +···Nj−1 +2 , ..., bk,N1 +···Nj ]0
for 1 ≤ j ≤ J and 1 ≤ k ≤ m. Let B (j) := [b1 (j), ..., bm (j)]0 ∈ Rm×Ij . For F ∈ F and 1 ≤ j ≤ J,
define
(j)

pF (w) := EF [dj,n(j) |wn(j) = w],

(j)

(1) 0

(j)

(J) 0

πF = [πF , ..., πF ]0

πF = pF (wj ),

and
(j)

ΣF (w) := CovF [dj,n(j) |wn(j) = w].


(j)
(j)
(j)
(j)
Note that ΣF (w) = diag pF (w) − pF (w)pF (w)0 .
The proof mimics the proof of Theorem 4.2, except for the treatment of π̂. Instead of the
sequence πN , N = 1, 2, ... in P ∩ C, consider a sequence of distributions FN = [F1N , ..., FJN ], N =
p
(j)
(j)
1, 2, ... in F such that Nj /K(j)B (j) πFN → hj , hj ≤ 0, 1 ≤ j ≤ J as N → ∞. Define QFN =
(j)

0

(j)

EFN [q K(j) (wn(j) )q K(j) (wn(j) )0 ] and ΞFN = EFN [B (j) ΣFN (wn(j) )B (j) ⊗ q K(j) (wn(j) )q K(j) (wn(j) )0 ], and
let
(j) −1

(j)

VFN := [Im ⊗ q K(j) (wj )0 QFN

(j)

(j) −1 K(j)

]ΞFN [Im ⊗ QFN

q

(wj )]

and
VFN :=

J
X

(j)

VFN .

j=1

Then by adapting the proof of Theorem 2 in Newey (1997) to the triangle array for the repeated
crosssection setting, we obtain
√

1

F

N
N VFN − 2 B[π̂ − πFN ] ;
N (0, Im ).

The rest is the same as the proof of Theorem 4.2.

Further details of the procedure in Section 5.2



To estimate πd
EC , we can proceed in two

steps as follows. The first step is to obtain control variable estimates b
n(j) , n(j) = 1, ..., Nj for each
(j)
j. For example, let Fbw|z be a nonparametric estimator for Fw|z for a given instrumental variable z

S14

KITAMURA AND STOYE

in period j. For concreteness, we consider a series estimator as in Imbens and Newey (2002). Let
rL (z) = (r1L (z), ..., rLL (z)), where r`L (z), ` = 1, ..., L are basis functions, then define
Nj
X

(j)
b− (j)
Fbw|z (w|z) = rL (z)0 R

n(j)=1

rL(j) (zn(j) )1{wn(j) ≤ w}/Nj

where
b
R(j)
=

Nj
X

rL(j) (zn(j) )rL(j) (zn(j) )0 /Nj

n(j)=1

Let
(j)
e
n(j) = Fbw|z (wn(j) |zn(j) ), n(j) = 1, ..., Nj .

Choose a sequence υN → 0, υN > 0 and define ιN (ε) = (ε + υN )2 /4υN , then let




1
if ε > 1 + υN







1 − ιN (1 − ε) if 1 − υN < ε ≤ 1 + υN



γN (ε) = ε
if υN ≤ ε ≤ 1 − υN






ιN (ε)
if − υN ≤ ε ≤ υN






0
if ε < −υN
then our control variable is εbn(j) = γN (e
εn(j) ), n(j) = 1, ..., Nj .
(j) 
bn(j) = (wn(j) , εbn(j) )0 ,
The second step is nonparametric estimation of Py|w,ε y ∈ xi|j |w = wj , ε . Let χ
n(j) = 1, ..., Nj for each j. Write sM (j) (χ) = (s1M (j) (χ), ..., sM (j)M (j) (χ))0 , where smM (j) (χ), χ ∈
(j) 
RK+1 , m = 1, ..., M (j) are basis functions, then our estimator for Py|w,ε y ∈ xi|j |w = ·, ε = · evaluated at χ = (w, ε) is
\
(j) 
Py|w,ε y ∈ xi|j |w, ε

M (j)

= s

0 b−

(χ) S (j)

Nj
X

sM (j) (b
χn(j) )di|j,n(j) /Nj

n(j)=1
M (j)

= sM (j) (χ)0 α
bi
where
b =
S(j)

Nj
X
n(j)=1

s

M (j)

M (j)

(b
χn(j) )s

0

(b
χn(j) ) /Nj ,

M (j)
α
bi

:= Sb− (j)

Nj
X
n(j)=1

sM (j) (b
χn(j) )di|j,n(j) /Nj .

S15
(j) 
Our endogeneity corrected conditional probability π(pj , xi|j ) is a linear functional of Py|w,ε y ∈ xi|j |w = wj , ε ,
\
(j) 
thus plugging in Py|w,ε y ∈ xi|j |w = wj , ε into the functional, we define

Z
\
π(p
j , xi|j ) :=
0

=

where

1

\
(j) 
Py|w,ε y ∈ xi|j |w = wj , ε dε
M (j)

D(j)0 α
bi

,
 
Z 1
wj
sM (j)   dε
D(j) :=
0
ε

i = 1, ..., Ij , j = 1, ..., J

and
0
\
\
\
\
\
\
πd
EC = [π(p1 , x1|1 ), ..., π(p1 , xI1 |1 ), π(p2 , x1|2 ), ..., π(p2 , xI2 |2 ), ..., π(pJ , x1|J ), ..., π(pJ , xIJ |J )] .

The final form of the test statistic is
0
d
JECN = N min [πd
EC − Aν] Λ[π
EC − Aν].
ν∈Rh
+

The calculation of critical values can be carried out in the same way as the testing procedure in Section
(j)

5.1, though the covariance matrix vN needs modification. With the nonparametric endogeneity
(j)

correction, the modified version of vN is
(j)

(j)

v̄N = [IIj ⊗ D(j)0 SN (j)−1 ]Λ̄N [IIj ⊗ SN (j)−1 D(j)]
where
0

SN (j) = E[sM (j) (χn(j) )sM (j) (χn(j) ) ],
(j)

(j)

(j)

(j)

Λ̄N = Λ̄1N + Λ̄2N ,

Λ̄1N = E[Σ̄(j) (χn(j) ) ⊗ sM (j) (χn(j) )sM (j) (χn(j) )0 ],

(j)

Λ̄2N = E[mn(j) m0n(j) ]

with
Σ̄(j) (χ) := Cov[dj,n(j) |χn(j) = χ],
mn(j) := [m01,n(j) , m02,n(j) , · · · , m0Ij ,n(j) ]0 ,
mi,n(j) :=

∂ (j) 
E γ̇N (εm(j) ) Py|w,ε y ∈ xi|j |wm(j) , εm(j) sM (j) (χm(j) )rL(j) (zm(j) )0 RN (j)−1 rL(j) (zn(j) )umn(j)
∂ε

di|j,n(j) , wn(j) , zn(j) ,
RN (j) := E[rL(j) (zn(j) )rL(j) (zn(j) )0 ],

(j)

umn(j) := 1{wn(j) ≤ wm(j) } − Fw|z (wm(j) |zn(j) ).

S16

KITAMURA AND STOYE

Define
(j)

then a possible choice for τN

nEC = min Nj Ij /trace(v̄N ),
j
q
(j)
log nEC
is τN =
. Proceed as in Section 5.1, replacing v̂N with a
n
EC

(j)
consistent estimator for v̄N for j = 1, ..., J, to define the bootstrap version J˜EC .

We impose some conditions to show the validity of the endogeneity-corrected test.
Let εn(j) be the value of the control variable ε for the n(j)-th consumer facing budget j.
I

N

j
j
Noting {{di|j,n(j) }i=1
, wn(j) , εn(j) }n(j)=1
are IID-distributed within each time period j, 1 ≤ j ≤ J, let

(dj , wj , εj ) denote the choice-log expenditure-control variable triplet of a consumer facing budget j.
Let d = [d01 , ..., d0J ]0 , w = [w1 , ..., wJ ]0 , e = [ε1 , ..., εJ ]0 and define g = Bd = [g1 , ..., gm ]0 as before. Let
Xj = supp(χn(j) ), Zj = supp(zn(j) ), and Ej = supp(εn(j) ), 1 ≤ j ≤ J. Following the above discussion,

define an RI -valued functional
(1)

(J)

(1)

(1)

(2)

(2)

(J)

(J)

π(Py|w,ε , ..., Py|w,ε ) = [π1|1 (Py|w,ε ), ..., πI1 |1 (Py|w,ε ), π1|2 (Py|w,ε ), ..., πI2 |2 (Py|w,ε ), ..., π1|J (Py|w,ε ), ..., πIJ |J (Py|w,ε )]0
where
(j)
πi|j (Py|w,ε )

and εn(j) :=

(j)
Fw|z (wn(j) |zn(j) )

Z

1

:=
0

(j) 
Py|w,ε y ∈ xi|j |w = wj , ε dε

for every j.

Condition S.4. There exist positive constants c1 , c2 , δ1 , δ, ζr (L), ζs (M ), and ζ1 (M ), L ∈ N, M ∈ N
such that the following holds:
(i) The distribution of wn(j) conditional on zn(j) = z is continuous for every z ∈ Zj , 1 ≤ j ≤ J;
(ii) supp(wn(j) |εn(j) = ε) = supp(wn(j) ) for every ε ∈ [0, 1], 1 ≤ j ≤ J;
(1)

(J)

(iii) π(Py|w,ε , ..., Py|w,ε ) ∈ C;

(iv) For each k ∈ KR , var(gk |w = (w1 , ..., wJ )0 , e = (ε1 , ..., εJ ))0 ≥ s2 (F1 , ..., FJ ) and E[(gk /s(F1 , ..., FJ ))4
|w = (w1 , ..., wJ )0 , e = (ε1 , ..., εJ )0 ] < c1 hold for every (w1 , ..., wJ , ε1 , ..., εJ ) ∈ W1 × · · · WJ ×
E1 × · · · E J ;

(v) Letting reL := CL,j rL , λmin E[e
rL (zn(j) )e
rL (zn(j) )] ≥ c2 holds for every L and j, where CL,j , L ∈
N, 1 ≤ j ≤ J, are constant nonsingular matrices;

(vi) maxj supz∈Zj ke
rL (z)k ≤ c1 ζr (L) for every L ∈ N.
(j)

(j)

(j)

(vii) supw∈Wj ,z∈Zj |Fw|z (w, z) − rL (z)0 αL (w)| ≤ c1 L−δ1 , 1 ≤ j ≤ J holds with some L-vector αL (·)
for every L ∈ N, 1 ≤ j ≤ J;

(viii) Letting seM := C̄M,j sM , λmin E[e
sM (χn(j) )e
sM (χn(j) )] ≥ c2 holds for every M and j, where
C̄M,j , M ∈ N, 1 ≤ j ≤ J, are constant nonsingular matrices;

S17

(ix) maxj supχ∈Xj ke
sM (χ)k ≤ Cζs (M ) and maxj supχ∈Xj k∂e
sM (χ)/∂εk ≤ c1 ζ1 (M ) and ζs (M ) ≤
Cζ1 (M ) for every M ∈ N;
(j)

(i,j)

(x) supχ∈Xj Py|w,ε {y ∈ xi|j |w, ε} − sM (χ)0 gM

(i,j)

≤ c1 M −δ , holds with some M -vector gM

for

every M ∈ N, 1 ≤ i ≤ Ij , 1 ≤ j ≤ J;
(j)

(xi) Py|w,ε {y ∈ xi|j |w, ε}, 1 ≤ i ≤ Ij , 1 ≤ j ≤ J, are twice continuously differentiable in χ = (w, ε).
(j) 
∂
Py|w,ε y ∈ xi|j |w, ε ≤ c1 and
Moreover, max1≤j≤J max1≤i≤Ij supχ∈χj ∂χ
(j) 
∂2
max1≤j≤J max1≤i≤Ij supχ∈χj ∂χ∂χ
≤ c1 .
0 Py|w,ε y ∈ xi|j |w, ε

Since we use the control function approach to deal with potential endogeneity in w (income), Conditions S.4(i)-(ii) are essential. See Blundell and Powell (2000) and Imbens and Newey (2009) for
further discussion on these types of restrictions. Just like Condition S.2(ii), Condition S.4(iv) is a
version of Condition S.1 that accommodates the two-step series estimation. Conditions S.4(iv)-(xi)
corresponds to standard regularity conditions stated in the context of the two-step approach adopted
in this section: (iv) and (x) imposes uniform approximation error bounds, (v) and (viii) avoid singular designs (note the existence of the matrices CL,j and C̄M,j suffices), and (vi) and (ix) control the
lengths of (the derivatives of) the series terms used. Condition S.4(xi) imposes reasonable smoothness
(j)

restrictions on the (observable) conditional probabilities Py|w,ε {y ∈ xi|j |w, ε}, 1 ≤ i ≤ Ij , 1 ≤ j ≤ J.
The next condition impose restrictions on tuning parameters.
Condition S.5. Let τN , M (j) and L(j), j = 1, ..., J satisfy τN ↓ 0,

√

nEC τN ↑ ∞, Nj L(j)1−2δ1 ↓ 0,

Nj M (j)−2δ ↓ 0, M (j)ζ1 (M (j))2 L2 (j)/Nj ↓ 0, ζs (M (j))6 L4 (j)/Nj ↓ 0, and ζ1 (M (j))4 ζr (L(j))4 /Nj ↓ 0

3 ≤ C(L(j)/N + L(j)1−2δ1 ), for some 0 < C < C.
and also C(L(j)/Nj + L(j)1−2δ1 ) ≤ υN
j

Proof of Theorem 5.2. The proof follows the same steps as those in the proof of Theorem 4.2,
except for the treatment of the estimator for π. Therefore, instead of the sequence πN , N = 1, 2, ...
in P ∩ C, consider a sequence of distributions FN = [F1N , ..., FJN ], N = 1, 2, ... in FEC and the
(j)

(j)

corresponding conditional distributions Py|w,ε;FN {y ∈ xi|j |w, ε} and Fw|z , 1 ≤ i ≤ Ij , 1 ≤ j ≤ J,
N
p
(j)
N = 1, 2, ... such that Nj /(M (j) ∨ L(j)))B (j) πFN → hj , hj ≤ 0, 1 ≤ j ≤ J as N → ∞, where
(1)

(j)

(J)

πFN = π(Py|w,ε , ..., Py|w,ε ) whereas the definitions of V FN , 1 ≤ j ≤ J are given shortly. Define
N

N

(j)

SFN = EFN [sM (j) (χn(j) )sM (j) (χn(j) )0 ] as well as
(j)

Ξ̄1F

N

(j)

0

= EFN [B (j) Σ̄FN (χn(j) )B (j) ⊗ sM (j) (χn(j) )sM (j) (χn(j) )0 ]

S18

KITAMURA AND STOYE

and
0

(j)

Ξ̄2F

N

= [B (j) ⊗ IM (j) ]EFN [mn(j);FN m0n(j);FN ][B (j) ⊗ IM (j) ]

where
(j)

ΣFN (χ) := CovFN [dj,n(j) |χn(j) = χ],
mn(j);FN := [m01,n(j);FN , m02,n(j);FN , · · · , m0Ij ,n(j);FN ]0 ,
mi,n(j);FN :=


∂ (j)
EFN γ̇N (εm(j) ) Py|w,ε;FN y ∈ xi|j |wm(j) , εm(j) sM (j) (χm(j) )rL(j) (zm(j) )0 RFN (j)−1 rL(j) (zn(j) )umn(j);FN
∂ε

di|j,n(j) , wn(j) , zn(j) ,
(j)

RFN (j) := EFN [rL(j) (zn(j) )rL(j) (zn(j) )0 ],

umn(j);FN := 1{wn(j) ≤ wm(j) } − Fw|z (wm(j) |zn(j) ).
N

With these definitions, let
V
(j)

(j)

(j)
FN


:= Im ⊗

(j) −1
D(j)0 SFN



(j)
Ξ̄FN





Im ⊗

(j) −1
SFN D(j)

(j)

with Ξ̄FN = Ξ̄1F + Ξ̄2F . Define
N

N

V FN :=

J
X

(j)

V FN .

j=1

Then by adapting the proof of Theorem 7 in Imbens and Newey (2002) to the triangular array for the
repeated cross-section setting, for the j’s that satisfy Condition (iv) we obtain
√

N V FN

− 12

F

N
N (0, Im ).
B[π̂ − πFN ] ;

The rest is the same as the proof of Theorem 4.2.



Appendix B: Algorithms for Computing A
This appendix details algorithms for computation of A. The first algorithm is the depth-first
algorithm for generic computation of A. The second algorithm is a refinement using Theorem 3.2.
All implementations are in MATLAB using CVX and are available from the authors. Algorithms use
notation introduced in the proof of Theorem 3.2.
Computing A as in Theorem 3.1.
1.

Initialize m1 = ... = mJ = 1.

2.

Initialize l = 2.

3.

Set c(B1 ) = xm1 |1 , . . . , c(Bl ) = xml |l .

Check for revealed preference cycles.

S19

4.

If a cycle is detected, move to step 7.

Else:

5.

If l < J, set l = l + 1, ml = 1, and return to step 3.

6.

Extend A by the column [m1 , ..., mJ ]0 .

Else:

7a.

If ml < Il , set ml = ml + 1 and return to step 3.

7b.

If ml = Il and ml−1 < Il−1 , set ml = 1, ml−1 = ml−1 + 1, l = l − 1, and return

to step 3.
7c.

If ml = Il , ml−1 = Il−1 , and ml−2 < Il−2 , set ml = ml−1 = 1, ml−2 = ml−2 + 1,

l = l − 2, and return to step 3.
(...)
7z.

Terminate.

Refinement using Theorem 3.2
Let budgets be arranged s.t. (B1 , ..., BM ) do not intersect BJ ; for exposition of the algorithm,
assume BJ is above these budgets.
1.

Use preceding algorithm to compute a matrix AM +1→J−1 corresponding to budgets

(BM +1 , ..., BJ ), though using the full X corresponding to budgets (B1 , ..., BJ ).23
2.

For each column aM +1→J−1 of AM +1→J−1 , go through the following steps:

2.1 Compute (using preceding algorithm) all vectors a1→M s.t.(a1→M , aM +1→J−1 ) is
rationalizable.
2.2 Compute (using preceding algorithm) all vectors aJ s.t.(aM +1→J−1 , aJ )
is rationalizable.
2.3 All stacked vectors (a01→M , a0M +1→J−1 , a0J )0 are valid columns of A.
Cowles Foundation for Research in Economics, Yale University, New Haven, CT 06520.
E-mail address: yuichi.kitamura@yale.edu
Departments of Economics, Cornell University, Ithaca, NY 14853, and University of Bonn, Germany; Hausdorff Center for Mathematics, Bonn, Germany.
E-mail address: stoye@cornell.edu

23This matrix has more rows than an A matrix that is only intended to apply to choice problems (B
M +1 , ..., BJ ).

