A dual approach to nonparametric characterization for random utility models

A dual approach to nonparametric characterization for random utility models

\abstract{This paper develops a novel characterization for random utility models (RUM), which turns out to be a dual representation of the characterization by Kitamura and Stoye (2018, ECMA). For a given family of budgets and its “patch" representation \'{a} l{a} Kitamura and Stoye, we construct a matrix $\Xi$ of which each row vector indicates the structure of possible revealed preference relations in each subfamily of budgets. Then, it is shown that a stochastic demand system on the patches of budget lines, say $\pi$, is consistent with a RUM, if and only if $\Xi\pi\geq \mathbbm{1}$, where the RHS is the vector of $1$'s. In addition to providing a concise quantifier-free characterization, especially when $\pi$ is inconsistent with RUMs, the vector $\Xi\pi$ also contains information concerning (1) sub-families of budgets in which cyclical choices must occur with positive probabilities, and (2) the maximal possible weight on rational choice patterns in a population. The notion of Chv\'{a}tal rank of polytopes and the duality theorem in linear programming play key roles to obtain these results.}

{\bf JEL Classification.} C02, D11, D12\\ {\bf Keywords:} {\sc Random utility model}; {\sc Revealed preference}; {\sc Strong axiom of revealed preference}; {\sc Linear programming}; {\sc Duality theorem}; {\sc Chv\'{a}tal rank}

\onehalfspacing

Introduction

In the literature of random utility models (RUM), Kitamura and Stoye (2018) (henceforth, KS) has established a powerful and tractable analytical tool for nonparametric demand analysis. Based on several fundamental results in revealed preference theory by Afriat (1967), Varian (1982) and McFadden and Richter (1990), they provide an insightful characterization for stochastic demand systems consistent with a RUM, as well as a statistical procedure for testing it based on empirical data. Afterward, in the literature, their approach has been further developed and turned out to be useful in various models. For example, Smeulders, Cherchye and De Rock (2021) develops an efficient computation technique for implementing the analysis in KS, while the papers including Aguiar, Gautheir, Kashaev and Plavala (2023), Deb, Kitamura, Quah and Stoye (2023) and Lazzati, Quah and Shirai (2024) show the applicability of Kitamura and Stoye's approach beyond the classical consumer theory, with some methodological contributions being also made in each of them.\footnote{Aguiar et al. (2023) deals with a dynamic consumption model, while Deb et al. (2023) works on the model of price preferences. Lazzati et al. (2024) applies KS' approach to game theoretical setting. }

Subsequent to these works, in this paper, we evolve the approach of KS from a theoretical perspective, especially in the framework of consumer theory. To be specific, this paper provides a novel necessary and sufficient condition for a stochastic demand system to be consistent with RUMs. Our characterization turns out to be a dual representation of that by KS, which has several attractive features. In terms of a formal aspect, we obtain a concise and easy-to-interpret quantifier-free condition, rather than solvability/satisfiability type conditions.\footnote{In the framework of abstract choice theory, by Block and Marschack (1960), the famous (quantifier-free) characterization, so called Block-Marschack polynominals, is known. Their condition is an extension of the monotonicity of choice frequencies with respect to the set inclusion relation on choice sets, rather than the structure of revealed preference relation. See Kono, Saito and Sandroni (2023) and Turansick (2024) for recent development in Block-Marschack type argument.} As a benefit from our representation, when a given stochastic demand system is inconsistent with RUMs, it simultaneously detects “where" the consistency breaks down. Furthermore, using the duality with the characterization by KS, it is also shown that our condition identifies “to what extent" a given stochastic demand system is (in)consistent with RUMs.

From a technical viewpoint, KS characterizes the set of RUM-consistent stochastic demand systems as a polytope of which vertices are deterministic choice patterns obeying the {strong axiom of revealed preference (SARP)}. Since the polytope is described by using the set of vertices, the characterization in KS is called a ${\cal V}$-representation. On the other hand, in this paper, we characterize the same polytope in terms of the set of hyperplanes generating it, which is often referred to as an ${\cal H}$-representation. Once a ${\cal V}$-representation is obtained, by Minkowski-Weyl duality, it is theoretically straightforward that there exists an ${\cal H}$-representation. However, as KS pointed out, this connection is purely theoretical and it is quite nontrivial to explicitly obtain it from the ${\cal V}$-representation by KS, let alone its economic implication. Indeed, the potential benefits from having an ${\cal H}$-representation are recognized in the literature, but it has not obtained beyond some specific numerical examples (see, for example, Aguiar et al. (2023) as well as KS).

Instead of starting from the ${\cal V}$-representation by KS, we directly construct a set of hyperplanes that captures observable restrictions from utility maximizing behavior, and rediscover the polytope of RUM-consistent demand systems by using it. More precisely, a keystone of our approach is constructing a matrix that captures the structure of revealed preference relations across budgets. This matrix is formed so that it provides a quantifier-free characterization for a (deterministic) choice pattern to obey SARP; that is, a set of hyperplanes determining SARP-consistent consumption patterns is specified. Then, we show that the same set of hyperplanes in fact generates the polytope corresponding to the set of stochastic demand systems consistent with RUMs. This means that the set of vertices of that polytope coincides with the set of SARP-consistent choice patterns. Since deterministic choice patterns are represented as binary vectors in our setting, the above property in turn corresponds to the integrality of polytopes. To prove it, we employ the notion of {Chv\'{a}tal rank}, which is a well-known concept in integer programming for, loosely speaking, measuring the degree of non-integrality of a given polytope. We prove that Chv\'{a}tal rank of the above polytope is equal to $0$, which is equivalent to the integrality of that polytope.\footnote{To the best of the authors' knowledge, this is the first attempt to apply the notion of Chv\'{a}tal rank in the literature of revealed preference theory, despite many successful applications of integer programming there. }

It should be also noted that our approach can be interpreted as an extension of that in Hoderlein and Stoye (2014), which characterizes the set of stochastic demand systems consistent with the {weak axiom of revealed preference (WARP)}. Their characterization is also given as a quantifier-free linear condition, and in fact it can be captured as a subsystem of our necessary and sufficient condition for RUMs. In this aspect, the current paper bridges between the condition for WARP-consistent stochastic choices by Hoderlein and Stoye (2014) and that for SARP-consistent stochastic choices by KS. Despite characterizing closely related models, the connection between these conditions has not necessarily been clear.

The rest of this paper is arranged as follows. In Section 2, we introduce the basic setting in the paper, and briefly explain the characterization for RUMs by KS. Then, in Section 3.1, our alternative characterization is established. There, it is also shown that, when a given demand system is inconsistent with RUMs, our necessary and sufficient condition specifies subfamilies of budgets where cyclical choices are crucial. We raise several numerical examples in Section 3.2, and proceed to the proof of the characterization theorem in Section 3.3. In Section 4.1, we formally show the duality between our characterization and that by KS, which immediately uncovers the connection between our characterization and the identification of the maximal fraction of rational choices. Some numerical examples are given in Section 4.2, and the proofs for the results in Section 4.1 are contained in Section 4.3. Lastly, in Section 5, we conclude the paper, with referring to some possible directions of future researches.

Rationalizability of random consumption

Throughout this paper, we follow the framework of KS, which is based on the classical consumer model. Suppose that there are $n$ $(\geq 2)$ commodities for which nonnegative consumption levels are allowed under positive price vectors. An increasing utility function is denoted by $u:\mathbb{R}^n_+\rightarrow \mathbb{R}$, and a random utility model (RUM) is defined as a distribution of these utility functions, which is in turn denoted by $\Phi$.

Our first objective is to characterize the observable restrictions from RUMs on choice behavior on finitely many budgets. Suppose that there are $J<\infty$ fixed budgets $B_j=\{y\in \mathbb{R}^n_+: p_j\cdot y=1\}$, where $p_j=(p_{j1},...,p_{jn})\in \mathbb{R}^n_{++}$ is a positive price vector for $j=1,2,...,J$. We also assume that cross-sectional distribution of demand corresponding to these budgets are observed; that is, we work with a population distribution, rather than any kind of empirical data. Denoting a distribution of demand on each ${\cal B}_j$ by $P_j(S)$ for $S\subset {\cal B}_j$, we call a profile of them, say, $P=(P_1,P_2,...P_J)$ as a stochastic demand system. The consistency of it with RUMs is defined as follows.

KS established a simple, but insightful geometric approach for characterizing the above defined rationalizability. A key idea for that is making patches of budget lines, using a kind of equivalent classes with respect to the direct revealed preference relations. To be specific, each budget set $B_j$ is divided into patches $\left(B_{j1},B_{j2},...,B_{jI_j}\right)$ defined such that

As seen from the definition, consumption vectors obtained from the same set of patches would derive the same direct revealed preference relations. In what follows, we always assume that any intersection of budget lines is not chosen with any positive probability, which is ensured if distributions of demands are continuous. By this assumption, as argued in KS, it suffices to consider patches belonging to a single budget set. Figure (ref) visualizes the construction of patches on budgets, where each patch excludes the intersection of two budget lines. In what follows, let $I=\sum^J_{j=1}I_j$; that is, $I$ is the total number of patches.

Using the notion of patches, we obtain the vector representation of a stochastic demand system as

where each $\pi_j:=\left(\pi_{j1},\pi_{j2},...,\pi_{jI_j}\right)$ is a probability vector on $\left(B_{j1},B_{j2},...,B_{jI_j}\right)$, and hence, each $\pi_{ji}$ stands for a probability mass put on the patch $B_{ji}$. (Note that, in the right most side, the semicolons indicate the separations of budgets, and we use this notation throughout this paper.) In fact, the rationalizability of a stochastic demand system can be tested through the property of its vector representation. Specifically, a stochastic demand system $P$ is rationalizable, if and only if the corresponding $\pi$ is represented as a convex combination of rational non-stochastic choice patterns explained below. This fact is extensively used also in our approach.

A deterministic choice pattern, referred to as a behavioral types, is formally defined as

where each $a_j:=\left(a_{j1},a_{j2},...,a_{jI_j}\right)$ is a binary vector with $\sum^{I_j}_{i=1} a_{ji}=1$. That is, each $a_j$ specifies one and only one patch $B_{ji}$, which can be interpreted as a choice from $B_j$. Abusing notation, let $a(B_j)=\left\{B_{ji}:a_{ji}=1\right\}$ and define the direct revealed preference $\succ^R$ such that

Since we do not consider the intersections of budget lines, it suffices to consider the case of a strict inequality. When it holds that for some ${\cal J}:=\{j_1,j_2,...,j_l\}\subset \{1,2,...,J\}$,

we say that the behavioral type has a revealed preference cycle. A behavioral type is rationalizable, if it obeys the strong axiom of revealed preference (SARP) in the sense that it does not have any revealed preference cycle.\footnote{In general, the rationalizability of (deterministic) consumer choices is characterized as the generalized axiom of revealed preference (GARP), which is slightly weaker than SARP (see, Afriat (1967) and Varian (1982)). Nevertheless, these two notions coincide under our assumption excluding the demand at the intersection of budgets. }

Let ${\cal A}$ be the set of all behavioral types, and ${\cal A}^*\subset {\cal A}$ be the set of all rationalizable behavioral types. Similarly, let $A$ be the matrix of which the set of column vectors is equal to ${\cal A}$, and $A^*$ be the matrix of which the set of column vectors is equal to ${\cal A}^*$. Then, Kitamura and Stoye's characterization theorem is given as follows.

\setcounter{theorem}{-1}

Thus, the above theorem characterizes the rationalizability through the existence of a nonnegative vector that solves the system of linear equation $\pi=A^*\tau^*$. In fact, as shown by KS, $\tau^*$ automatically satisfies the adding-up condition, and hence $\pi$ is represented as a weighted sum of rationalizable behavioral types. Theorem (ref) also implies that the set of rationalizable stochastic demand systems is captured as a polytope, since it is characterized as a convex hull of rationalizable behavioral types. In general, the representation of a polytope in terms of its vertices (as in Theorem (ref)) is referred to as a ${\cal V}$-represetantion.

On the other hand, it is well known that a polytope can be also represented as an intersection of finitely many half spaces of hyperplanes, which is referred to as an ${\cal H}$-representation. Once one of these representations is obtained, Minkowski-Weyl duality immediately implies the existence of the other representation. However, the existence here is purely theoretical and, in general, it is quite non-trivial to explicitly construct it. (See, for example, Ziegler (2007) for the detail.) Despite that, some specific structure of consumer problem allows us to establish an explicit ${\cal H}$-representation of Theorem (ref), which turns out to have several attractive economic implications. Construction of an alternative characterization is the goal of Section 3, and the duality with Theorem (ref) is explored in Section 4.

An alternative characterization

Characterization by hyperplanes

For investigating the rationalizability of stochastic demand systems, by Theorem (ref), it suffices to look at its vector representation. Hence, in the rest of this paper, we always deal with a stochastic demand system by its vector representation $\pi$, and we simply say that $\pi$ is (not) rationalizable when the underlying $P$ is (not) rationalizable.

A key idea for constructing the alternative characterization for RUMs is capturing the structure of possible revealed preference relation across patches. In particular, the following notion plays crucial roles in our analysis. Let ${\mathscr J}=\{{\cal J}\subset \{1,2,...,J\}: |{\cal J}|\geq 2\}$. For each ${\cal J}\in {\mathscr J}$, we say that a patch $B_{ji}$ is undominated in ${\cal J}$, if;

That is, for each subfamily of budgets ${\cal J}\in \mathscr{J}$, a patch $B_{ji}$ is undominated, if it is not dominated by any other patches turning up in ${\cal J}$ with respect to the direct revealed preference relation defined in ((ref)).\footnote{Put otherwise, a patch is undominated, if it is maximal in ${\cal J}$ with respect to the direct revealed preference relation. However, we use the notion of maximality/minimality with respect to set inclusion in other parts of the paper, so we simply use the term “undominated" instead of “maximal.".} (Otherwise, a patch is said to be dominated in ${\cal J}$.) Thus, if $a(B_j)=B_{ji}$ and it is undominated in ${\cal J}$, then there is no budget $B_{j'}$ for which $a(B_{j'})\succ^R a(B_j)$ with $j'\in \cal J$. Note that, as a basic property of undominatedness of patches, if $j\in {\cal J}'\subset {\cal J}''$ and a patch $B_{ji}$ is undominated in ${\cal J}''$, then it is also undominated in ${\cal J}'$.

Using the notion of undominated patches, we define the vector that can “detect" the existence of cyclical choices in each subfamily of budgets. Let for each ${\cal J}\in \mathscr{J}$, define $\xi^{\cal J}=(\xi^{\cal J}_{11},...,\xi^{\cal J}_{1I_1};...;\xi^{\cal J}_{J1},...,\xi^{\cal J}_{JI_J})\in \{0,1\}^I$ such that

Once $\xi^{\cal J}$ are obtained as above for all ${\cal J}\in \mathscr{J}$, let $\Xi$ be the $(|{\mathscr J}|\times I)$-matrix such that each row vector corresponds to each $\xi^{\cal J}$. All our results are derived from the nature of the vector $\xi^{\cal J}$ and matrix $\Xi$. Hence, before checking the properties of them, we raise a simple example to clarify how they are constructed (as well as the notion of undominated patches).

To see the basic property concerning $\xi^{\cal J}$, notice that for $a\in {\cal A}$, $\xi^{\cal J}\cdot a=0$ implies that none of selected patch $a(B_j)$ is undominated in ${\cal J}$. This immediately implies that the direct revealed preference relation $\succ^R$ has to admit at least one cycle within ${\cal J}$, since there are only finitely many budgets. In this sense, each $\xi^{\cal J}$ can detect whether a behavioral type $a$ has revealed preference cycles within $\{B_j\}_{j\in {\cal J}}$, and hence, the matrix $\Xi$ provides an alternative representation of SARP. Given the importance of this claim in the paper, we summarize it as a lemma and provide a formal proof. See also Remark 1 below Lemma (ref) for a more precise argument on the connection between $\xi^{\cal J}$ and revealed preference cycles.

{\sc Remark 1.} Concerning the “test" for the existence of cycle using $\xi^{\cal J}$, it should be noted that $\xi^{\cal J}\cdot a\geq 1$ does not necessarily mean that $\succ^R$ is acyclic on $\{B_j\}_{j\in {\cal J}}$. For instance, in the situation of Example (ref), if $a=(0,1,0;1,0,0;0,0,1)$, then $\xi^{\{1,2,3\}}\cdot a=1$. However, as $\xi^{\{1,2\}}\cdot a=0$ suggests, it contains a cycle $a(B_1)\succ^R a(B_2)\succ^R a(B_1)$. On the other hand, if $\xi^{{\cal J}'}\cdot a\geq 1$ for any ${\cal J}'\subset {\cal J}$, then it implies that $\succ^R$ is acyclic on $\{B_j\}_{j\in {\cal J}}$. Relatedly, if $\xi^{\cal J}\cdot a=0$ and there is no ${\cal J}'\subset {\cal J}$ for which $\xi^{{\cal J}'}\cdot a=0$, then it implies the existence of a revealed preference cycle involving all elements of $\{a(B_j)\}_{j\in {\cal J}}$; that is, letting ${\cal J}=\{j_1,j_2,...,j_l\}$, there is a cycle such as $a(B_{j_1})\succ^R a(B_{j_2})\succ^R\dots \succ^R a(B_{j_l})\succ^R a(B_{j_1}),$ possibly by adjusting the indices.

While Lemma (ref) ensures that the rationalizability of behavioral types can be tested by the system of inequalities (or equivalently, by the set of hyperplanes) generated by $\Xi$ and $\mathbbm{1}$, perhaps strikingly, it extends to the rationalizability of a stochastic demand system.

This is an alternative representation of the “test" for rationalizability of a given stochastic demand system, and hence, it is logically equivalent to Theorem (ref). On the other hand, the condition in Theorem (ref) is a quantifier-free characterization of random utility models. In addition, it characterizes the set of rationalizable demand systems as the intersection of half spaces of hyperplanes $\{\pi: \xi^{\cal J}\cdot \pi=1\}$ for ${\cal J}\in \mathscr{J}$. Thus, our characterization is an ${\cal H}$-representation of the polytope of those demand systems, of which the duality between the ${\cal V}$-representation in Theorem (ref) is shown in the next section. Further mathematical argument concerning this theorem is postponed to Section 3.3, since it works as a good introduction to the formal proof stated there.

The condition $\Xi\pi\geq \mathbbm{1}$ itself requires that the sum of choice frequencies across undominated patches should not be smaller than $1$ for every subfamily of budgets. Intuitively, this implies that the total weight on cyclical choices is not too large, and hence, the choices in a population is explained by a distribution of rational choices. This intuition is reminiscent of a necessary and sufficient condition for the consistency with weak axiom of revealed preference (WARP), established by Hoderlein and Stoye (2014).\footnote{Note that WARP requires the asymmetry of the direct revealed preference relation, or the lack of choice reversal between any pair of budgets. In addition, to be precise, Hoderlein and Stoye (2014) derived the upper bound and the lower bound of WARP-consistent behavior in a population, as well as the statistical procedure for estimating them from real data.} Their condition essentially requires that for every pair of budgets, the sum of choice frequencies across WARP-violating combination of patches should not exceed $1$, which is clearly equivalent to requiring $\xi^{\cal J}\cdot \pi\geq {1}$ for every ${\cal J}$ consisting of two budgets. For example, using the budget lines in Example (ref), their condition requires that $(\pi_{12}+\pi_{13})+\pi_{21}\le 1$, $\pi_{23}+(\pi_{31}+\pi_{32})\le 1$, and $\pi_{13}+\pi_{31}\le 1$, which is equivalent to $\xi^{\{1,2\}}\cdot \pi\geq 1$, $\xi^{\{2,3\}}\cdot \pi\geq 1$ and $\xi^{\{1,3\}}\cdot \pi\geq 1$. Thus, our result can be interpreted as an extension of Hoderlein-Stoye approach to the case of RUMs, or stochastic choices consistent with SARP. Relatedly, since WARP and SARP are equivalent in the two-commodity model, for checking the rationalizability in such a case, it suffices to consider $\xi^{\cal J}$ for ${\cal J}$ with $|{\cal J}|=2$ (i.e. Hoderlein and Stoye's condition). However, as we will see in the next section, the value of $\xi^{\cal J}\cdot \pi$ for ${\cal J}\in \mathscr{J}$ with $|{\cal J}|\geq 3$ can have some substantial information even in the two-commodity setting.

As a benefit of having the characterization in Theorem (ref), when $\pi$ is not rationalizable, it allows us to obtain some information about “where" the rationality breaks down. If $\pi$ is not rationalizable, then there exists some ${\cal J}\in \mathscr{J}$ such that $\xi^{\cal J}\cdot \pi<1$. Hence, in order to represent $\pi$ as a convex combination of behavioral types, it is inevitable to put positive weights on some behavioral types obeying $\xi^{\cal J}\cdot a=0$. By Lemma (ref), this in turn implies that revealed preference cycles within the budget family $\{B_j\}_{j\in {\cal J}}$ is crucial to explain $\pi$. In particular, given the fact stated in Remark 1, if ${\cal J}=\{j_1,j_2,...,j_l\}$ is a minimal element of $\mathscr{J}$ obeying $\xi^{{\cal J}}\cdot \pi<1$, then we have to put positive weights on some behavioral types containing a revealed preference cycle involving all elements of ${\cal J}$ (the one like ((ref))). We summarize this as a proposition for future references.

Numerical examples

Below, we raise three examples which respectively correspond to (i) a two-commodity and three-budget example where the stochastic demand system is rationalizable, (ii) a two-commodity and three-budget example where the stochastic demand is not rationalizable, and (iii) a three-commodity and three-budget example where the stochastic demand system is not rationalizable. As explained above, the first two cases can also be dealt with by Hoderlein and Stoye's condition, but it would help how our characterization works in a simple setting. The third example satisfies the condition by Hoderlein and Stoye, but not the condition in Theorem (ref).

Integrality of polytopes and the proof of Theorem (ref)

From a mathematical viewpoint, as already referred to, Theorem (ref) says that the set of rationalizable stochastic demand systems is characterized as the intersection of finitely many half spaces in the form of $\{\pi:\xi^{\cal J}\cdot \pi\geq 1\}$. Put otherwise, the set of rationalizable demand systems is represented as

On the other hand, Lemma (ref) says that

and hence, the set of rationalizable behavioral types is captured as the set of integral points of ${\cal P}$. Thus, the essential claim in Theorem (ref) is that ${\cal P}$ is an integral polytope of which the set of vertices is equal to ${\cal A}^*$. (Strictly speaking, the hyperplanes corresponding to the nonnegativity and adding-up conditions should be also included, but they do not affect the following argument and are omitted.) Note that a polytope is said to be integral, if it is equal to the convex hull of its integer points. For example, the polytope in Figure (ref)(a) is not an integral polytope, while that in Figure (ref)(b) is an integral polytope. Note that, in Figure (ref), lines represent hyperplanes, while dot points are regarded as integer points. In these polytopes, the sets of integral points are the same with each other. Thus, even if two sets of hyperplanes specify the same set of integer points, they may generate different polytopes. Rephrasing it in terms of the consumer theory, even if we obtain some matrix representation of rationalizable behavioral types, it might not generate the set of rationalizable stochastic demand systems, which makes the claim of Theorem (ref) nontrivial.

To show that the hyperplanes generated by matrix $\Xi$ create a situation described as Figure (ref)(b) rather than that described as Figure (ref)(a), we use the notion of Chv\'{a}tal rank explained below. In general, letting ${\cal Q}=\{q\in \mathbb{R}^L: Wq\geq \theta\}$ and ${\cal Q}_{\cal I}=\mbox{conv.}\left({\cal Q}\cap \mathbb{Z}^L\right)$, ${\cal Q}$ is integral if ${\cal Q}={\cal Q}_{\cal I}$. The set ${\cal Q}_{\cal I}$ is referred to as the integral hull of ${\cal Q}$. While the equality is not necessarily the case, ${\cal Q}_{\cal I}\subset {\cal Q}$ always holds, and, when $W$ is an $(M\times L)$-rational matrix, it is known that, the set $${\cal Q}^{(1)}:=\{q\in {\cal Q}: zW\mbox{ is integral for some }z\in [0,1]^M\Longrightarrow (zW)q\geq \lceil z\theta\rceil\}$$ is in between ${\cal Q}_{\cal I}$ and ${\cal Q}$. (Note that $\lceil\cdot \rceil$ stands for the ceiling function.) That is, it holds that ${\cal Q}_{\cal I}\subset {\cal Q}^{(1)}\subset {\cal Q}$. This ${\cal Q}^{(1)}$ is referred to as Chv\'{a}tal closure of ${\cal Q}$. Intuitively, Chv\'{a}tal closure adds some constraints to the original polytope ${\cal Q}$ to remove some non-integer vertices, such as dotted lines in Figure (ref)(a). Thus, ${\cal Q}^{(1)}$ is also a polytope, and defining ${\cal Q}^{(2)}$ as Chv\'{a}tal closure of ${\cal Q}^{(1)}$, it holds that ${\cal Q}_{\cal I}\subset {\cal Q}^{(2)}\subset {\cal Q}^{(1)}\subset {\cal Q}$. It is known that, repeating this procedure, there exists some $r<\infty$ such that ${\cal Q}^{(r)}={\cal Q}_{\cal I}$, with ${\cal Q}^{(0)}:={\cal Q}$. The minimum integer $r$ for which ${\cal Q}^{(r)}={\cal Q}_{\cal I}$ is called Chv\'{a}tal rank, and hence, ${\cal Q}$ is integral if and only if its Chv\'{a}tal rank is equal to $0$. See, for example, Schrijver (1980) and Conforti, Cornu\'{e}jols, Zambelli (2014) for the detailed argument.\footnote{This means that for any polytope ${\cal Q}$, there is a finitely-many-step procedure to obtain its integral hull ${\cal Q}_{\cal I}$. In addition, since each step just adds finitely many linear inequalities, eventually one can obtain the matrix representation of ${\cal Q}_{\cal I}$. However, in general, this “existence" is purely theoretical level, and it is typically hard to explicitly obtain ${\cal Q}_{\cal I}$, partly because the convergence is very slow and Chv\'{a}tal rank tends to be very large. Schrijver (1980) and Conforti et al. (2014) contains a fuller discussion concerning the upper bounds of Chv\'{a}tal rank of a given polytope. }

{\sc Remark 2.} Another (and perhaps more prevalent) approach for ensuring the integrality of a polytope is to show that the matrix determining it is a totally unimodular matrix (TUM). A matrix is called a TUM, if the determinant of every square submatrix can only take value $0$ or $\pm 1$, which automatically implies that the matrix must consist of $0$ and $\pm 1$. While the matrices in our numerical examples are TUMs, it is not at all clear if it is generally the case. At least, a matrix $\Xi$ obtained in our procedure typically violates a well known sufficient condition for being a TUM, which prohibits a matrix from having more than two non-zero entries in each columns, in addition to another requirement concerning the property of row sums. (See Schrijver (1980) for the detail). Note also that, since we fix the RHS of the system of inequalities, the total unimodularity of $\Xi$ is a sufficient condition, while our condition concerning Chv\'{a}tal rank is a necessary and sufficient condition for ${\cal P}$ to be integral.

Proof of Theorem (ref)

Given the above argument, to prove Theorem (ref), it suffices to show that for every $\pi \in {\cal P}$ and $|{\mathscr J}|$-dimensional vector $u=(u_{\cal J})_{{\cal J}\in \mathscr{J}}$, it holds that

which implies that ${\cal P}={\cal P}^{(1)}$, and hence ${\cal P}={\cal P}_{\cal I}$. Since $\lceil u\mathbbm{1}\rceil=\lceil \sum_{{\cal J}\in {\mathscr J}}u_{\cal J}\rceil$ holds in ((ref)), it suffices to show that there exists a partition of $\mathscr J$ such that the sum of $u_{\cal J}$'s on each component is an integer. (Then the total sum of $u$ is the sum of finitely many integers.) For this purpose, we use a profile of patches $(B_{11}, B_{21},...,B_{J1})$ constructed by adjustments of indices such that for $k=1,2,...,J-1$, (i) $B_{k1}$ is taken from $B_k$, and (ii) $B_{k1}$ is undominated in ${\cal J}_k:=\{k,k+1,...,J\}$, while it is dominated in any ${\cal J}_{k'}$ with $k'<k$.

Such a profile always exists as long as $p_{j'}\neq p_{j''}$ for all $j'\neq j''$. For example, suppose that there is some commodity for which all $p_j$'s take different values from each other. With no loss of generality, we may consider it as commodity $1$ and sort price vectors so that $p_{11}<p_{21}<\dots <p_{J1}$. Then, the patch on $B_1$ containing the vector $(1/p_{11},0,...,0)$ is clearly undominated in ${\cal J}_1$, and hence it works as $B_{11}$. The patch on $B_2$ containing the vector $(1/p_{21},0,...,0)$ would work as $B_{21}$, since it is dominated by $B_{1}$ through $B_{11}$, but not by any other budgets. The rest of $B_{k1}$ could be defined in a similar vein. Even if there is no such commodity (as in Example (ref)), one can find some vector $d\in \mathbb{R}^n_{+}\setminus \{0\}$ on the unit sphere such that price vectors are sorted as $p_1\cdot d<p_2\cdot d<\dots <p_J\cdot d$ with suitable adjustment of indices, because $J<\infty$. Then, a profile of patches $(B_{11}, B_{21},...,B_{J1})$ can be constructed in a similar way to the preceding case. That is, $B_{k1}$ is defined as the patch on $B_k$ containing the consumption vector $d/(p_k\cdot d)$.\footnote{Thus, one can regard the preceding case as the special case where $d=(1,0,...,0)$ works.}

Once we have constructed a profile of patches $(B_{11}, B_{21},...,B_{J1})$ as above, letting ${\mathscr J}_1=\{{\cal J}\in \mathscr{J}: {\cal J}\ni 1\}$, $B_{11}$ is undominated in every ${\cal J}\in {\mathscr J}_1$. Recalling the definition of $\xi^{\cal J}_{11}={\bf 1}(B_{11}\mbox{ is undominated in } {\cal J})$, this in turn implies that

where the subscript in the LHS indicates the coordinate corresponding to the patch $B_{11}$. Since the vector $u\Xi$ itself is assumed to be integral, the above sum is also integral.

By the construction of the profile $(B_{11}, B_{21},...,B_{J1})$, $B_{21}$ is undominated in ${\cal J}$, if and only if ${\cal J}\in {\mathscr J}_2:=\{{\cal J}\in {\mathscr J}:{\cal J}\ni 2\mbox{ and }{\cal J}\not\ni 1\}$. Thus, it holds that

which is also integral. In addition, it holds that ${\mathscr J}_1\cap {\mathscr J}_2=\emptyset$. Similarly, also for $k\geq 3$, the patch $B_{k1}$ is undominated in ${\cal J}$ if and only if ${\cal J}\in {\mathscr J}_k:=\{{\cal J}\in \mathscr{J}: {\cal J}\ni k\mbox{ and } {\cal J}\not\ni j\mbox{ for }j\le k-1\}$. Then, it holds that

which is integral. Moreover, ${\mathscr J}_k\cap {\mathscr J}_{k-1}=\emptyset$ for all $k$, and hence ${\mathscr J}_1, {\mathscr J}_2,...,{\mathscr J}_k$ are mutually exclusive. Repeating this process up to $k=J-1$, we obtain ${\mathscr J}_1, {\mathscr J}_2,...,{\mathscr J}_{J-1}$ that are mutually exclusive and $\bigcup^{J-1}_{k=1}{\mathscr J}_k=\mathscr{J}$. (Recall that ${\mathscr J}$ is the family of budgets with at least two elements.) Thus, ${\mathscr J}_1, {\mathscr J}_2,...,{\mathscr J}_{J-1}$ forms a partition of $\mathscr{J}$, and the sum of $u_{\cal J}$'s is integral on each ${\mathscr J}_k$ as desired. \qed

Duality and its implication

The maximal weight on rational types

While Theorem (ref) tests the rationality of a given stochastic demand system through the condition $\Xi\pi\geq \mathbbm{1}$, in fact, the value of $\Xi\pi$ also contains some information concerning the “degree" of (ir)rationality. To be more specific, we claim that when $\pi$ is not rationalizable, $\min_{{\cal J}\in \mathscr{J}}\xi^{\cal J}\cdot \pi\in [0,1)$ is equal to the maximal possible weight on rational behavioral types to explain $\pi$. To include the case of rationalizable stochastic demand systems, we introduce $\xi^{\overline{\cal J}}=(1/J,...,1/J;...;1/J,...,1/J)\in [0,1]^I$ and $\overline{\mathscr{J}}=\mathscr{J}\cup \{\overline{\cal J}\}$. Note that $\xi^{\overline{\cal J}}\cdot \pi=1$ holds for any stochastic demand system $\pi$. Using this extended set of indices $\overline{\mathscr J}$, we have the following.

This theorem shows the duality between the characterization by Theorem (ref) and that by Theorem (ref). To see this, let $c\in \{0,1\}^{|\cal A|}$ such that $c_a={\bf 1}(a\in {\cal A}^*)$ for every $a\in \cal A$, and consider the linear programming

Then, it is obvious that $\pi$ is rationalizable, if and only if the value of the above problem, say, $P(\pi)$ is equal to $1$. The dual of the problem ((ref)) is formulated as

in which, every $\xi^{\cal J}$ with ${\cal J}\in {\mathscr{J}}$ is feasible by Lemma (ref), while the feasibility of $\xi^{\overline{\cal J}}$ is obvious. Letting $D(\pi)$ be the value of problem ((ref)), the duality theorem implies that $P(\pi)=D(\pi)$, but Theorem (ref) makes a much stronger claim that $D(\pi)$ can be in fact achieved by one of finitely many vectors $\{{\xi}^{\cal J}\}_{{\cal J}\in \overline{\mathscr J}}$.

It is obvious that for each $a\in {\cal A}$, $P(a)={\bf 1}(a\in {\cal A}^*)$, and hence, by the duality theorem, $D(a)={\bf 1}(a\in {\cal A}^*)$ holds as well. Thus, Theorem (ref) is obvious for behavioral types. For each ${\cal J}\in \overline{\mathscr J}$, let us consider a subset of ${\cal A}$ that shares $\xi^{\cal J}$ as a solution to the dual problem ((ref)):

Note that a single behavioral type may be contained in multiple ${\cal A}^{\cal J}$'s. In addition, since $\xi^{\overline{\cal J}}\cdot a=1$ for any $a\in {\cal A}^*$, it holds that ${\cal A}^*={\cal A}^{\overline{\cal J}}$. In fact, for a given stochastic demand system $\pi$, a representation $\pi=\sum_{a\in {\cal A}}\tau_aa$ achieves the maximal possible weight on rational types in the sense that $P(\pi)=\sum_{a\in {\cal A}}\tau_aP(a)=\sum_{a\in {\cal A}^*}\tau_a$, if and only if the support of $\tau=(\tau_a)_{a\in {\cal A}}$ is a subset of some ${\cal A}^{\cal J}$ (${\cal J}\in \overline{\mathscr{J}}$). This property (in particular, “if" part) plays a central role in the proof of Theorem (ref), while it seems also of independent interest.

Gathering together with Theorem (ref), if one wishes to represent $\pi$ putting weights on rational behavioral types as much as possible, then, it suffices to look at the set of types ${\cal A}^{\cal J}$ for which ${\cal J}$ achieving the LHS of ((ref)). On the other hand, if one has obtained a representation of $\pi$ only by using types in a certain ${\cal A}^{\cal J}$, then it already achieves the maximal possible weight on rational types, and hence, such a family of budget ${\cal J}$ achieves the LHS of ((ref)). That is, the set of stochastic demand systems is partitioned into subsimplices generated by $\{{\cal A}^{\cal J}\}_{{\cal J}\in \overline{\mathscr{J}}}$, each of which provides a representation of $\pi$ achieving $P(\pi)$, the maximal possible weight on rational behavioral types.

The preceding proposition also indicates what kind of mixture can “improve" the fit to a rational choice model. It is not surprising that, even if a (deterministic) demand pattern of each person is not rational, a mixture of them across a population is more or less consistent with a RUM. As the simplest case, consider a mixture of demand behavior of two people, where both of their behavioral types violate SARP. Applying Proposition (ref), however, if (and only if) those behavioral types do not have any $\xi^{\cal J}$ as a common solution to ((ref)), then any nontrivial mixture of their behavior can admit positive weights on some rational behavioral types. A generalization of this property is formally proved as Lemma (ref) in the proof of Proposition (ref). (See also Lemma (ref) in Appendix.)

Lastly, we refer to the logical relationship across results in this paper. It is not difficult to see that the statement of Theorem (ref) implies Theorem (ref). Indeed, $\pi\in \cal P$ holds if and only if the RHS of ((ref)) is equal to $1$, and $\min_{{\cal J}\in \overline{\mathscr{J}}}\xi^{\cal J}\cdot \pi=1$ immediately implies that $\Xi\pi\geq \mathbbm{1}$. Nevertheless, the proof of Theorem (ref) in fact depends on Proposition (ref)(a), and the proof of the latter in turn depends on Theorem (ref). (The dependence is found in the proofs of lemmas in Appendix.) Thus, in the sense that assuming one of them derives others, Theorem (ref), Proposition (ref)(a) and Theorem (ref) are logically equivalent.

Numerical examples

We raise three numerical examples to see how Theorem (ref) and Proposition (ref) actually work. First, we revisit Example (ref) in the preceding section, where $\pi$ is not rationalizable. In this example, $D(\pi)$ is attained by $\xi^{\cal J}$ corresponding to ${\cal J}$ containing three budgets, when there are only two commodities. That is, even in the two-commodity setting, choice patterns over more than two budgets may have a certain revealed preference implication. To be more specific, although they do not affect the result of “0-1" test like Theorem (ref), it could have some information in deriving (a specific type of) degree of rationality. Second, we reconsider Example (ref), where despite the consistency with WARP, one cannot put any positive weight on rationalizable behavioral types to explain $\pi$. Lastly, we consider the case where a mixture of irrational behavioral types can admit a positive weight on rational behavioral types, and even can be fully rationalizable.

\setcounter{example}{2}

\setcounter{example}{3}

The proofs of results in this section

Proof of Theorem (ref) (based on Proposition (ref))

Given that $P(\pi)=D(\pi)$ holds by the duality theorem, the statement is essentially equivalent to $D(\pi)=\min_{{\cal J}\in \overline{\mathscr{J}}}\xi^{\cal J}\cdot \pi$. Since every $\xi^{\cal J}$ is feasible in the problem ((ref)), it suffices to show the existence of some ${\cal J}'\in \overline{\mathscr{J}}$ for which $D(\pi)=\xi^{{\cal J}'}\cdot \pi$. This is trivial if $\pi$ is rationalizable, since $\pi\in \mbox{conv.}({\cal A}^{\overline{\cal J}})$ has to hold. Even if $\pi$ is not rationalizable, the claim can be easily proved, once we establish Proposition (ref)(a). To see this, suppose that $\pi$ is not rationalizable and that $P(\pi)=\sum_{a\in {\cal A}^*}\tau_a$ for some $\tau\in \Delta(\cal A)$. Applying Proposition (ref)(a), it holds that $\tau_a>0\Longrightarrow a\in {\cal A}^{{\cal J}'}$ for some ${\cal J}'\in \mathscr{J}$, which also implies that $\tau_a>0\Longrightarrow\xi^{{\cal J}'}\cdot a=D(a)$.\footnote{Note that ${\cal J}'$ must be found in ${\mathscr J}$, rather than $\overline{\mathscr{J}}$, since $\pi\notin {\cal P}$ (i.e. $\pi$ is not rationalizable) is assumed.} This leads to $$\xi^{{\cal J}'}\cdot \pi=\sum_{a\in {\cal A}^{{\cal J}'}}\tau_a D(a)=\sum_{a\in {\cal A}^{{\cal J}'}\cap {\cal A}^*}\tau_a=P(\pi)=D(\pi),$$ which is what we have to show. \qed

Proof of Proposition (ref)

We start from part (b) of the statement. Suppose that $\pi$ is represented as a convex combination $\pi=\sum_{a\in {\cal A}}\tau_aa$ for some $\tau\in \Delta({\cal A})$, with obeying $\tau_a>0\Longrightarrow a\in {\cal A}^{\cal J}$ for a common ${\cal J}\in \overline{\mathscr J}$. It holds that

Moreover, since $D(a)={\bf 1}(a\in {\cal A}^*)$, it also holds that $\sum_{a\in {\cal A}}\tau_aD(a)=\sum_{a\in {\cal A}^*}\tau_a$, and hence, $\xi^{\cal J}\cdot \pi=\sum_{a\in {\cal A}^*}\tau_a$. Thus, if $\xi^{\cal J}\cdot \pi>D(\pi)$ were to hold, by the duality theorem, we would have $\sum_{a\in {\cal A}^*}\tau_aa>P(\pi)$. However, since $\pi=\sum_{a\in {\cal A}}\tau_aa$ is assumed, this contradicts the definition of $P(\pi)$. Hence, it must hold that $\xi^{\cal J}\cdot \pi=D(\pi)$, and the duality theorem implies that $P(\pi)=\sum_{a\in {\cal A}^*}\tau_aa$ as desired.

To prove the other direction (part (a)), the following lemma plays a key role. This is a generalization of the phenomenon observed in Example (ref), but the formal proof, which is postponed to Appendix, is rather involved.

Admitting this lemma, the rest of the proof is as follows. Suppose that a given stochastic demand system $\pi$ is represented as a convex combination of $a_1,a_2,...,a_m$ for which there is no ${\cal J}\in \overline{\mathscr{J}}$ such that $a_1,a_2,...,a_m\in {\cal A}^{\cal J}$. Letting $\pi=\sum^m_{k=1}\tau_ka_k$ with $\tau_1\geq \tau_2\geq\dots \geq \tau_m\geq 0$ with $\sum^m_{k=1}\tau_k=1$, it holds that

where we let $\tau_{m+1}=0$. For each $l=1,2,...,m$, $\left(\frac{1}{m-l+1}\sum^{m-l+1}_{k=1}a_k\right)$ is a stochastic demand system, and nonnegative numbers $(m-l+1)(\tau_{m-l+1}-\tau_{m-l+2})$ for $l=1,2,...,m$, add up to $1$. Indeed, it holds that

Using this, we obtain that

where the first inequality follows from the concavity of $D(\cdot)$, while the latter holds by Lemma (ref).\footnote{The concavity of $D(\cdot)$ follows from the fact that $D(\cdot)=P(\cdot)$ by the duality theorem. The concavity of $P(\cdot)$ is rather obvious, given that it is the value of the maximization problem ((ref)).} This means that $P(\pi)$, which is equal to $D(\pi)$, is not achieved by $\tau\in \Delta({\cal A})$ whose support is not restricted to some ${\cal A}^{\cal J}$. This completes the proof of Proposition (ref)(a). \qed

Conclusion

In this paper, we have developed a new approach to nonparametric characterization for RUMs. A keystone of our analysis is the construction of a matrix capturing the structures of revealed preference relations across patches in each subfamily of budgets. Then, using this matrix, we provide a quantifier-free necessary and sufficient condition under which a given stochastic demand system is rationalizable by a RUM. In our characterization, the set of rationalizable demand systems is captured as an intersection of finitely many half spaces, which corresponds the dual of the “vertex-based" characterization by KS.

Our characterization is something beyond checking the consistency with RUMs in that, especially when a given demand system is not rationalizable, one can simultaneously obtain (i) subfamily of budgets in which cyclical choices occur with positive probabilities and (ii) the maximal possible weight on rational behavioral types in a population. The former could be potentially useful to explore causes of irrational choices by checking, for example, any common structure among families of budgets in which irrational choices are inevitable. On the other hand, the latter would suggest the possibility of constructing some “non-binary" test or rationality indices for RUMs. Such a work could be related to the index of rationality by Apesteguia and Ballester (2015), which is based on stochastic choices, as well as other rationality indices for deterministic models including those explained in the textbook by Chambers and Echenique (2018).

As in KS and other related papers, potentially, the results in this paper can also be applied to empirical analysis. To deal with samples of choices rather than a choice distribution in a population level, one needs to establish some procedure for the statistical implementation. In the framework of consumer theory, KS provides a statistical test using bootstrap, which in fact uses theoretical nature of the dual of their characterization without explicitly knowing it. Now, having an explicit formulation of it by Theorem (ref), one may further develop the statistical procedure for testing the consistency with RUMs. For example, as mentioned in KS, we may appeal to some technology developed in the literature of generalized moment selections (GMS) such as Andrews and Soares (2010), Bugni (2010) and Canay (2010).\footnote{Note that Hoderlein and Stoye (2014) has actually developed a statistical procedure for their WARP test based on techniques along this line.} Amongst others, a recent work by Cox and Shi (2023) provides a tractable procedure for testing for moment inequality models that does not depend on simulation and tuning parameter.

Lastly, the approach in this paper seems also applicable to other models along the line of KS, such as a price preference model by Deb et al. (2023) and even in a game theoretic framework dealt with in Lazzati et al. (2024). In these models, stochastic choices are captured as a mixture of model-consistent deterministic choices. As in the proof of Theorem (ref), the notion of Chv\'{a}tal closure is useful to check if a characterization for deterministic choices directly extends to that for mixtures of them. If it does, then one could obtain a dual representation, possibly with some economic implications from it. Even if not, then, the constraints newly added by taking Chv\'{a}tal closure could suggest additional behavioral restrictions to be considered.