betaFeedback

WorksEconomics, Econometrics and Finance

Random Utility Models in the Consumption-Budget Setting: Vertex and Network-Flow Characterizations

Abstract

This note supplements our paper Alternative Computational Formulations for Testing Discrete-Choice Random Utility Models: Half-Space and Network-Flow Formulations and serves two purposes: 1. We clarify the conceptual distinctions between two classes of random utility models (RUM): those in the consumption-budget setting \citep{kitamura2019nonparametric} (hereafter KS) and those in the finite-alternative setting (e.g., Chapter~7 of \cite{chambers2016revealed}). In particular, we show (Theorem 1) that each rational type, as defined in KS, can be obtained as a coordinate projection of the deterministic choice vector induced by a strict preference ranking that satisfies what we call a patch-monotonicity condition. 2. We generalize the network-flow characterization for finite-alternative RUM in \cite{fiorini2004short} to the consumption-budget setting (Theorem 2). Specifically, we show that a vector of choice probabilities in the consumption-budget setting is rationalizable in the KS sense if and only if it is the image of a unit flow on a multi-arc powerset digraph under a fixed linear map. The key distinction is that our digraph allows multiple arcs between the same pair of nodes, whereas the digraph in Fiorini has at most one arc between any pair of nodes.

Introduction

This note supplements our paper Alternative Computational Formulations for Testing Discrete-Choice Random Utility Models: Half-Space and Network-Flow Formulations and serves two purposes:

  1. We clarify the conceptual distinctions between two classes of random utility models (RUM): those in the consumption-budget setting [3] (hereafter KS) and those in the finite-alternative setting (e.g., Chapter 7 of Chambers and Echenique [2016]).

    In particular, we show (Theorem 1) that each rational type, as defined in KS, can be obtained as a coordinate projection of the deterministic choice vector induced by a strict preference ranking that satisfies what we call a patch-monotonicity condition.

  1. We generalize the network-flow characterization for finite-alternative RUM in Fiorini [ [2] to the consumption-budget setting (Theorem 2). Specifically, we show that a vector of choice probabilities in the consumption-budget setting is rationalizable in the KS sense if and only if it is the image of a unit flow on a multi-arc powerset digraph under a fixed linear map. The key distinction is that our digraph allows multiple arcs between the same pair of nodes, whereas the digraph in Fiorini has at most one arc between any pair of nodes.

    This characterization allows us to adapt the Flow-CG algorithm developed in our paper to the consumption-budget setting.1

The remainder of this note is organized into four sections. Section 2 reviews the KS setup. For the finite-alternative RUM setup, we refer readers to our main paper. Section 3 presents the projection results, and Section 4 develops the network-flow characterization. Section 5 includes all the proofs. Throughout the note, we prioritize detailed explanations and illustrative examples over brevity.

Review of the Setup in KS

Budgets and Patches

The material in this section is adapted from Section 3 of KS. The primitive data in KS consist of choice frequencies observed on JJ linear budgets, each of the form

Bj={y∈R+K:pjTy=1},(1)B_j = \{y \in\mathbb{R}^{K}_{+}: p_j^{\mathsf{T}}y = 1\}, \tag*{(1)}

where KK denotes the number of commodities and pjp_j is the normalized price vector.3 It is assumed that the price vectors {pj}j=1J\{p_j\}_{j=1}^{J} are strictly positive and distinct so that they induce different budget sets.

KS partition the union of the budget sets into patches, defined as follows.

Definition 1 (Definition 3.2 in KS). Let X={x1,…,xI}\mathcal{X} = \{x_1,\ldots,x_I\} be the coarsest partition of ⋃j=1JBj\bigcup_{j=1}^{J} B_j such that, for every i∈{1,…,I}i \in\{1,\ldots,I\} and j∈{1,…,J}j \in\{1,\ldots,J\}, the patch xix_i lies entirely on, strictly above, or strictly below the budget plane BjB_j. Equivalently, two points y1,y2∈⋃j=1JBjy_1,y_2 \in\bigcup_{j=1}^{J} B_j belong to the same patch if and only if

sg⁡(pjTy1−1)=sg⁡(pjTy2−1)for all j=1,…,J,\operatorname{sg}(p_j^{\mathsf{T}}y_1-1)=\operatorname{sg}(p_j^{\mathsf{T}}y_2-1) \quad\text{for all } j=1,\ldots,J,

where sg⁡\operatorname{sg} denotes the sign function.

Intuitively, each budget is divided into patches according to whether its points lie on, strictly above, or strictly below each of the other budget planes. Each budget BjB_j is a disjoint union of IjI_j patches, which we enumerate as x1∣j,…,xIj∣jx_{1|j},\ldots,x_{I_j|j}.

The data relevant for rationalizability in the KS sense can be summarized by the probabilities of selecting each patch on each budget.

Definition 2 (Choice probability vector; Definition 3.4 in KS). The vector representation of a choice probability system is

ρ:=(ρ1∣1,…,ρI1∣1,…,ρ1∣J,…,ρIJ∣J)T,(2)\rho:= \left(\rho_{1|1},\ldots,\rho_{I_1|1},\ldots,\rho_{1|J},\ldots,\rho_{I_J|J}\right)^{\mathsf{T}}, \tag*{(2)}

where ρi∣j\rho_{i|j} is the probability that the bundle chosen from budget BjB_j belongs to patch xi∣jx_{i|j}.

Figure 1 below provides an example of the patch constructions for a 2-commodity-2-budget case.

Figure 1. The five distinct patches induced by two budgets with two commodities. The four colored segments exclude the intersection, which forms the shared singleton patch x3∣1=x3∣2x_{3|1}=x_{3|2}.

Rational Types

The KS approach tests whether the observed vector of choice probabilities π\pi can be expressed as a convex combination of the deterministic choice vectors induced by rational types. To define a rational type, we first define a choice type. A choice type selects one patch from each budget. We represent choice type tt by the binary vector

at=(d1∣1,…,dI1∣1,d1∣2,…,dI2∣2,…,d1∣J,…,dIJ∣J)T∈{0,1}∑j=1JIj,(3)a_t = \left(d_{1|1},\ldots,d_{I_1|1},d_{1|2},\ldots,d_{I_2|2},\ldots,d_{1|J},\ldots,d_{I_J|J}\right)^{\mathsf{T}} \in\{0,1\}^{\sum_{j=1}^{J} I_j}, \tag*{(3)}

where di∣j=1d_{i|j}=1 if type tt selects patch xi∣jx_{i|j} from budget BjB_j and di∣j=0d_{i|j}=0 otherwise. In particular,

∑i=1Ijdi∣j=1for all j∈{1,…,J}.\sum_{i=1}^{I_j} d_{i|j}=1 \quad\text{for all } j \in\{1,\ldots,J\}.

Rationality imposes additional restrictions on a choice type, which can be formulated using either SARP or GARP. Following the simplification discussed in § 3.2 of KS, we impose the following assumption.

Assumption 1 (Continuous demand). For each budget BjB_j, the distribution of demand is continuous.4

With pairwise distinct budget hyperplanes, intersection patches—those contained in at least two budgets—have lower dimension than the budget hyperplanes. Under Assumption 1, these patches have zero choice probability and can be omitted from the analysis. On the remaining patches, SARP and GARP impose the same restrictions on choice types.

From now on, all definitions involving patches exclude intersection patches, and we use SARP to define rationality. We retain the notation x1∣j,…,xIj∣jx_{1|j},\ldots,x_{I_j|j} for the remaining patches on budget BjB_j. Following Section 3.4.1 of KS, a rationality type is defined with respect to a directed graph on budgets.

Definition 3 (Induced Revealed Preference Relation on Budgets). Fix a choice type ata_t and the collection of budgets B={B1,…,BJ}\mathcal{B}=\{B_1,\ldots,B_J\}. For any pair j,k∈{1,…,J}j,k\in\{1,\ldots,J\}, we say that BkB_k is directly revealed preferred to BjB_j if there is an index i∈{1,…,Ij}i\in\{1,\ldots,I_j\} such that

di∣j=1andpkTy<1for all y∈xi∣j.(4)d_{i|j}=1 \quad\text{and}\quad p_k^{\mathsf{T}}y<1 \quad\text{for all }y\in x_{i|j}. \tag*{(4)}

Moreover, we define a directed revealed-preference graph with node set B={B1,…,BJ}\mathcal{B}=\{B_1,\ldots,B_J\}. For any distinct budgets BjB_j and BkB_k, include an arc Bk→BjB_k\to B_j if BkB_k is revealed preferred to BjB_j.

By construction, all points in a patch lie on the same side of each budget hyperplane, so the induced relation does not depend on the particular point chosen within a patch. A choice type satisfies SARP if and only if its induced graph is acyclic, yielding the following definition.

Definition 4 (Rational Type). A choice type ata_t is a rational type if its induced revealed preference graph on budgets is acyclic.

Given a collection of budgets, we can construct the collection of all distinct rational types {at}t=1T\{a_t\}_{t=1}^{T}, where TT is the number of such types. Recall that II denotes the number of patches, which is equivalent to the dimension of the choice probability vector. Let II denote the dimension of the choice probability vector. We stack the rational types columnwise to form a matrix A∈RI×TA \in\mathbb{R}^{I \times T}. By Theorem 3.1 of KS, a choice probability vector ρ\rho is rationalizable if and only if

∃v∈ΔT such that ρ=Av,\exists v \in\Delta^T \text{ such that } \rho= Av,

where ΔT\Delta^T is the unit simplex in RT\mathbb{R}^T, ΔT={x∈R+T:∑t=1Txt=1}\Delta^T = \{x \in\mathbb{R}_+^T : \sum_{t=1}^{T} x_t = 1\}. We denote the polytope generated by the KS rational types by PKS\mathcal{P}^{\mathrm{KS}}:

PKS:={ρ∈RI:ρ=Av for some v∈ΔT}.(5)\mathcal{P}^{\mathrm{KS}} := \{\rho\in\mathbb{R}^I : \rho= Av \text{ for some } v \in\Delta^T\}. \tag*{(5)}

Patch Monotonicity and a Vertex Characterization

Preliminary Discussion

KS’s approach employs discretization. In particular, KS partition the union of the budgets into finitely many mutually exclusive patches.

If we treat each patch as an individual alternative, we can consider a finite-alternative RUM that allows all I!I! strict rankings over the patches, where II is the number of patches. We expand the choice set associated with each budget to include all patches lying on or below the corresponding budget hyperplane. That is, for each Bj\mathcal{B}_j, we define the choice set

Dj={x∈X:x⊆{y∈R+K:pjTy≤1}}.(6)\mathcal{D}_j = \left\{x \in\mathcal{X} : x \subseteq\{y \in\mathbb{R}_+^K : p_j^{\mathsf{T}} y \le1\}\right\}. \tag*{(6)}

Here, X\mathcal{X} is the set of patches (alternatives) The JJ budgets index a choice probability system {{ρ(x,Dj)}x∈Dj}j=1J\{\{\rho(x,\mathcal{D}_j)\}_{x\in\mathcal{D}_j}\}_{j=1}^{J}, with one choice probability vector for each budget Bj\mathcal{B}_j.

A choice probability vector {ρ(x,Dj)}x∈Dj\{\rho(x,\mathcal{D}_j)\}_{x\in\mathcal{D}_j} induces a subprobability vector on the budget boundary Bj\mathcal{B}_j, given by {ρ(x,Dj)}x∈Dj:x⊆Bj\{\rho(x,\mathcal{D}_j)\}_{x\in\mathcal{D}_j:x\subseteq\mathcal{B}_j}. This need not be a valid choice probability vector in the KS setting because its entries may sum to less than one. More generally, some of the I!I! strict rankings do not induce rational types in the consumption-budget setting.5 Consider again the example with two budgets and two commodities.

For the budgets B1,B2\mathcal{B}_1,\mathcal{B}_2 in Figure 1, the expanded menus (excluding intersection patches) are

D1={x1∣1,x2∣1,x2∣2},D2={x1∣2,x2∣2,x1∣1}.\mathcal{D}_1 = \{x_{1|1}, x_{2|1}, x_{2|2}\}, \qquad\mathcal{D}_2 = \{x_{1|2}, x_{2|2}, x_{1|1}\}.

There are three rational types in the sense of KS, as shown in Table 1.

BudgetType 1Type 2Type 3
B1\mathcal{B}_1x1∣1x_{1|1}x2∣1x_{2|1}x2∣1x_{2|1}
B2\mathcal{B}_2x1∣2x_{1|2}x1∣2x_{1|2}x2∣2x_{2|2}

Table 1. The three rational types.

The remaining boundary-choice profile (x1∣1,x2∣2)(x_{1|1}, x_{2|2}) violates SARP: x2∣2x_{2|2} lies strictly below B1\mathcal{B}_1, and x1∣1x_{1|1} lies strictly below B2\mathcal{B}_2, so each chosen patch is directly revealed preferred to the other.

Table 2 lists all 24 strict rankings over the four patches and their induced choices from the expanded menus. Eight of these rankings (colored in gray) induce rational types in the KS setting: two generate Type 1, four generate Type 2, and two generate Type 3. The remaining rankings select a patch strictly below the corresponding budget hyperplane for at least one budget. The column denoted by monotonicity will be used in the next subsection.

RankingChoice from D1D_1Choice from D2D_2Monotone?
x1∣1≻x2∣1≻x1∣2≻x2∣2x_1|1 \succ x_2|1 \succ x_1|2 \succ x_2|2x1∣1x_1|1x1∣1x_1|1No
x1∣1≻x2∣1≻x2∣2≻x1∣2x_1|1 \succ x_2|1 \succ x_2|2 \succ x_1|2x1∣1x_1|1x1∣1x_1|1No
x1∣1≻x1∣2≻x2∣1≻x2∣2x_1|1 \succ x_1|2 \succ x_2|1 \succ x_2|2x1∣1x_1|1x1∣1x_1|1No
x1∣1≻x1∣2≻x2∣2≻x2∣1x_1|1 \succ x_1|2 \succ x_2|2 \succ x_2|1x1∣1x_1|1x1∣1x_1|1No
x1∣1≻x2∣2≻x2∣1≻x1∣2x_1|1 \succ x_2|2 \succ x_2|1 \succ x_1|2x1∣1x_1|1x1∣1x_1|1No
x1∣1≻x2∣2≻x1∣2≻x2∣1x_1|1 \succ x_2|2 \succ x_1|2 \succ x_2|1x1∣1x_1|1x1∣1x_1|1No
x2∣1≻x1∣1≻x1∣2≻x2∣2x_2|1 \succ x_1|1 \succ x_1|2 \succ x_2|2x2∣1x_2|1x1∣1x_1|1No
x2∣1≻x1∣1≻x2∣2≻x1∣2x_2|1 \succ x_1|1 \succ x_2|2 \succ x_1|2x2∣1x_2|1x1∣1x_1|1No
x2∣1≻x1∣2≻x1∣1≻x2∣2x_2|1 \succ x_1|2 \succ x_1|1 \succ x_2|2x2∣1x_2|1x1∣2x_1|2Yes
x2∣1≻x1∣2≻x2∣2≻x1∣1x_2|1 \succ x_1|2 \succ x_2|2 \succ x_1|1x2∣1x_2|1x1∣2x_1|2Yes
x2∣1≻x2∣2≻x1∣1≻x1∣2x_2|1 \succ x_2|2 \succ x_1|1 \succ x_1|2x2∣1x_2|1x2∣2x_2|2No
x2∣1≻x2∣2≻x1∣2≻x1∣1x_2|1 \succ x_2|2 \succ x_1|2 \succ x_1|1x2∣1x_2|1x2∣2x_2|2Yes
x1∣2≻x1∣1≻x2∣1≻x2∣2x_1|2 \succ x_1|1 \succ x_2|1 \succ x_2|2x1∣1x_1|1x1∣2x_1|2Yes
x1∣2≻x1∣1≻x2∣2≻x2∣1x_1|2 \succ x_1|1 \succ x_2|2 \succ x_2|1x1∣1x_1|1x1∣2x_1|2No
x1∣2≻x2∣1≻x1∣1≻x2∣2x_1|2 \succ x_2|1 \succ x_1|1 \succ x_2|2x2∣1x_2|1x1∣2x_1|2Yes
x1∣2≻x2∣1≻x2∣2≻x1∣1x_1|2 \succ x_2|1 \succ x_2|2 \succ x_1|1x2∣1x_2|1x1∣2x_1|2Yes
x1∣2≻x2∣2≻x1∣1≻x2∣1x_1|2 \succ x_2|2 \succ x_1|1 \succ x_2|1x2∣2x_2|2x1∣2x_1|2No
x1∣2≻x2∣2≻x2∣1≻x1∣1x_1|2 \succ x_2|2 \succ x_2|1 \succ x_1|1x2∣2x_2|2x1∣2x_1|2No
x2∣2≻x1∣1≻x2∣1≻x1∣2x_2|2 \succ x_1|1 \succ x_2|1 \succ x_1|2x2∣2x_2|2x2∣2x_2|2No
x2∣2≻x1∣1≻x1∣2≻x2∣1x_2|2 \succ x_1|1 \succ x_1|2 \succ x_2|1x2∣2x_2|2x2∣2x_2|2No
x2∣2≻x2∣1≻x1∣1≻x1∣2x_2|2 \succ x_2|1 \succ x_1|1 \succ x_1|2x2∣2x_2|2x2∣2x_2|2No
x2∣2≻x2∣1≻x1∣2≻x1∣1x_2|2 \succ x_2|1 \succ x_1|2 \succ x_1|1x2∣2x_2|2x2∣2x_2|2No
x2∣2≻x1∣2≻x1∣1≻x2∣1x_2|2 \succ x_1|2 \succ x_1|1 \succ x_2|1x2∣2x_2|2x2∣2x_2|2No
x2∣2≻x1∣2≻x2∣1≻x1∣1x_2|2 \succ x_1|2 \succ x_2|1 \succ x_1|1x2∣2x_2|2x2∣2x_2|2No

Table 2. All strict rankings and their induced choices from the expanded menus. Shaded rows induce rational types in the KS setting. The final column indicates whether the ranking satisfies patch monotonicity.

A question is therefore how we can restrict the strict preference rankings such that they induce a KS-stype rational types on the boundary patches. It turns out that one sufficient condition exists and we term it patch monotonicity.

Patch Monotonicity and the Projection Theorem

Definition 5 (Patch Monotonicity). For distinct patches x1,x2∈Xx_1, x_2 \in\mathcal{X}, we write x1≻dx2x_1 \succ^{d} x_2 if there exist y1∈x1y_1 \in x_1 and y2∈x2y_2 \in x_2 such that y1≥y2y_1 \ge y_2 componentwise.6 We say that a strict preference ranking ≻\succ satisfies patch monotonicity if x1≻dx2x_1 \succ^{d} x_2 implies x1≻x2x_1 \succ x_2 for all distinct x1,x2∈Xx_1,x_2 \in\mathcal{X}.7

Remark 1. Table 2 illustrates that satisfying patch monotonicity is sufficient, but not necessary, for a strict ranking to induce a rational type in the sense of KS. Nevertheless, each rational type in this example is induced by at least one strict ranking that satisfies patch monotonicity.

Remark 2. One may ask why Definition 5 uses an existential rather than a universal quantifier (i.e., every point in one patch is dominated by some point in the other patch). Consider the example with three budgets and two commodities in Figure 2. The budget B1B_1 lies strictly inside the feasible budget sets associated with B2B_2 and B3B_3. Each patch on these outer budgets contains a point that dominates some point of x1∣1x_{1|1}. However, neither left patch contains a point dominating (5/3,0)∈x1∣1(5/3,0) \in x_{1|1}, and neither right patch contains a point dominating (0,5/3)∈x1∣1(0,5/3) \in x_{1|1}. Thus, no single outer patch can provide a dominating point for every point of x1∣1x_{1|1}.

Three budgets and their patches

Figure 2. The inner budget B1B_1 is a single patch. Each outer budget has two patches. The intersection patch is excluded.

A version of patch monotonicity requiring such a universal comparison would allow the ranking

x1∣1≻x2∣2≻x1∣3≻x1∣2≻x2∣3.x_{1|1} \succ x_{2|2} \succ x_{1|3} \succ x_{1|2} \succ x_{2|3}.

This ranking selects x1∣1x_{1|1} from both expanded menus D2D_2 and D3D_3 and therefore does not induce a rational type in the sense of KS.

We now state our projection theorem. Recall the definition of PKS\mathcal{P}^{\mathrm{KS}} from (5).

Theorem 1. Given a collection of distinct budgets {Bj}j=1J\{B_j\}_{j=1}^{J}, let X={x1,…,xI}\mathcal{X} = \{x_1,\ldots,x_I\} denote the induced nonintersection patches. Let a1,…,aT∈{0,1}Ia_1,\ldots,a_T \in\{0,1\}^{I} denote the rational choice types as in Definition 4, and write A=[a1,…,aT]A = [a_1,\ldots,a_T]. Let Π\Pi denote the set of all strict preference rankings over X\mathcal{X}, and let Πr⊆Π\Pi_r \subseteq\Pi denote the rankings that satisfy patch monotonicity as defined in Definition 5. Let {Dj}j=1J\{D_j\}_{j=1}^{J} be the choice sets defined in (6). For each ≻∈Π\succ\in\Pi, let ρ≻\rho^\succ denote the deterministic choice probability vector obtained by selecting the highest-ranked patch from each DjD_j. Then the following statements hold:

  1. Every ranking in Πr\Pi_r induces a rational choice type in the sense of KS.

  1. Every rational choice type in the sense of KS is induced by at least one ranking in Πr\Pi_r.

  1. Define

Pr={∑≻∈Πrλ≻ρ≻:λ≻≥0 for all ≻∈Πr, ∑≻∈Πrλ≻=1}.\mathcal{P}^{r}=\left\{\sum_{\succ\in\Pi_{r}}\lambda_{\succ}\rho^{\succ}:\lambda_{\succ}\ge0\text{ for all }\succ\in\Pi_{r},\ \sum_{\succ\in\Pi_{r}}\lambda_{\succ}=1\right\}.

Let Proj denote the coordinate projection that retains only the coordinates ρ(x,Dj)\rho(x,\mathcal{D}_{j}) for which x⊆Bjx\subseteq B_{j}, ordered as in the rows of AA. Then

PKS=Proj⁡(Pr),(7)\mathcal{P}^{\mathrm{KS}}=\operatorname{Proj}(\mathcal{P}^{r}), \tag*{(7)}

In words, the set of rationalizable choice probability systems in the sense of KS is the projection of the choice probability polytope generated by rankings that satisfy patch monotonicity.

Multi-arc Network Flow Characterization

In the finite-alternative RUM setting, Fiorini [ [2] establishes a correspondence between strict preference rankings over nn alternatives and directed paths from the empty set to the full set of alternatives in the corresponding powerset digraph.

This section shows that an analogous characterization holds in the consumption-budget setting, with some modifications. In particular, we construct a powerset digraph whose nodes correspond to subsets of budgets. Since the individual choice alternatives are patches, a given ordering of the budgets may be consistent with multiple patch choices. To represent these possibilities, we use a multi-arc powerset digraph, in which multiple arcs between the same pair of nodes represent distinct admissible patch choices.

Examples

In this section, we demonstrate how to write multi-arc powerset digraphs with several examples.

Two Commodities and Three Budgets

We begin with an example involving two commodities and three budgets. Consider the following pairwise intersecting budgets in R+2\mathbb{R}_{+}^{2}:

B1={y∈R+2:29y1+19y2=1},\mathcal{B}_{1}=\left\{y\in\mathbb{R}_{+}^{2}:\frac{2}{9}y_{1}+\frac{1}{9}y_{2}=1\right\},
B2={y∈R+2:18y1+16y2=1},\mathcal{B}_{2}=\left\{y\in\mathbb{R}_{+}^{2}:\frac{1}{8}y_{1}+\frac{1}{6}y_{2}=1\right\},
B3={y∈R+2:112y1+13y2=1}.(8)\mathcal{B}_{3}=\left\{y\in\mathbb{R}_{+}^{2}:\frac{1}{12}y_{1}+\frac{1}{3}y_{2}=1\right\}. \tag*{(8)}

After excluding intersection patches, each budget Bj\mathcal{B}_{j} has three patches, which we enumerate as x1∣j,x2∣j,x3∣jx_{1|j},x_{2|j},x_{3|j} in increasing order of y1y_{1}. The pairwise intersection points are

P12=(125,215),P13=(247,157),P23=(6,32).P_{12}=\left(\frac{12}{5},\frac{21}{5}\right),\qquad P_{13}=\left(\frac{24}{7},\frac{15}{7}\right),\qquad P_{23}=\left(6,\frac{3}{2}\right).

Figure 3 illustrates the resulting nine nonintersection patches.

The nine nonintersection patches induced by three budgets with two commodities

Figure 3. The nine nonintersection patches induced by three budgets with two commodities. Patches on each budget are indexed in increasing order of y1y_1. Hollow circles mark the excluded intersection points.

Now consider an agent whose maximized utility is highest on B1\mathcal{B}_{1}, followed by B2\mathcal{B}_{2} and then B3\mathcal{B}_{3}. Thus, the agent must choose x1∣1x_{1|1} from B1\mathcal{B}_{1}, since x2∣1x_{2|1} and x3∣1x_{3|1} lie strictly below B2\mathcal{B}_{2}. We then remove B1\mathcal{B}_1 from the construction. On B2\mathcal{B}_2, both x1∣2x_{1|2} and x2∣2x_{2|2} lie above the remaining budget B3\mathcal{B}_3, whereas x3∣2x_{3|2} lies strictly below it. Either x1∣2x_{1|2} or x2∣2x_{2|2} may therefore be selected. After removing B2\mathcal{B}_2, any of the three original patches on B3\mathcal{B}_3 may be selected. Intuitively, the patch selected from the highest-ranked remaining budget must lie strictly above every other remaining budget. Figure 4 illustrates this sequence.

Sequential choices for the budget ordering $\mathcal{B}_1 \succ \mathcal{B}_2 \succ \mathcal{B}_3$

Figure 4. Sequential choices for the budget ordering B1≻B2≻B3\mathcal{B}_1 \succ\mathcal{B}_2 \succ\mathcal{B}_3. Thick colored segments indicate eligible patches on the current budget, dashed gray segments indicate ineligible patches, and thin lines show the other remaining budgets. Hollow circles mark the original excluded intersection points.

Figure 5 illustrates the subnetwork corresponding to the budget ordering B1≻B2≻B3\mathcal{B}_1 \succ\mathcal{B}_2 \succ\mathcal{B}_3. Each node SS records the indices of the budgets already removed. An arc from SS to S∪{Bj}S \cup\{B_j\} represents choosing its labeled patch from BjB_j and then removing BjB_j.

The subnetwork corresponding to $\mathcal{B}_1 \succ \mathcal{B}_2 \succ \mathcal{B}_3$

Figure 5. The subnetwork corresponding to B1≻B2≻B3\mathcal{B}_1 \succ\mathcal{B}_2 \succ\mathcal{B}_3. Nodes record the budgets already removed. Arc colors identify the budget being removed, and arc labels identify the chosen patch.

The first transition has a single arc, labeled x1∣1x_{1|1}. The second transition has two parallel arcs, labeled x1∣2x_{1|2} and x2∣2x_{2|2}, and the final transition has three parallel arcs, one for each patch on B3\mathcal{B}_3. Each path from ∅\varnothing to {B1,B2,B3}\{B_1, B_2, B_3\} selects one patch from each budget and induces a rational type consistent with the given ordering. The parallel arcs capture the fact that a budget ordering can be consistent with multiple patch choices. A deterministic rational type can thus be represented by sending one unit of flow along a single path.

We complete the network by repeating this construction for the remaining five strict rankings of the budgets. Figure 6 shows the complete multi-arc powerset digraph, which has eight nodes and 22 arcs. Each path from ∅\varnothing to {B1,B2,B3}\{\mathcal{B}_1,\mathcal{B}_2,\mathcal{B}_3\} specifies a budget ordering and one admissible patch choice on each budget, thereby inducing a rational type. Different paths may induce the same rational type.

The complete multi-arc powerset digraph for the three-budget example

Figure 6. The complete multi-arc powerset digraph for the three-budget example. Nodes record the budgets already removed. An arc’s color identifies the budget being removed, and its label identifies the chosen patch. Crossings of arcs are not additional nodes.

Mapping arc flows to choice probabilities is particularly simple. For example, the probability of choosing patch x1∣1x_{1|1} from budget B1\mathcal{B}_1 equals the sum of the flows on all arcs labeled x1∣1x_{1|1} in Figure 6.

Two Commodities and Three Budgets with a Dominated Budget

This example shows that some nodes of the powerset digraph can be omitted, depending on the geometry of the budgets. Recall the example in Figure 2, reproduced below. Here, every point of B1\mathcal{B}_1 lies strictly below the union of B2\mathcal{B}_2 and B3\mathcal{B}_3. Thus, any feasible strict budget ordering must place B1\mathcal{B}_1 last

Because each node records the budgets already removed, B1\mathcal{B}_1 can be removed only after both B2\mathcal{B}_2 and B3\mathcal{B}_3. Consequently, the nodes {B1}\{\mathcal{B}_1\}, {B1,B2}\{\mathcal{B}_1,\mathcal{B}_2\}, and {B1,B3}\{\mathcal{B}_1,\mathcal{B}_3\} are unreachable from ∅\varnothing and can be omitted. The reduced network, shown in Figure 8, has five nodes and seven arcs. If B2\mathcal{B}_2 is removed first, its chosen patch must be x2∣2x_{2|2}; if B3\mathcal{B}_3 is removed first, its chosen patch must be x1∣3x_{1|3}. Either patch on the second outer budget is then admissible, followed by the sole patch x1∣1x_{1|1} on B1\mathcal{B}_1.

Reduced multi-arc powerset digraph

Figure 8. The reduced multi-arc powerset digraph for Figure 7. The three unreachable nodes have been omitted. Arc colors identify the budget being removed, and arc labels identify the chosen patch.

Three budgets and their patches

Figure 7. The inner budget B1\mathcal{B}_1 consists of a single patch and lies strictly below both outer budgets. Each outer budget has two nonintersection patches. The hollow circle marks the excluded intersection.

We are now ready for formal definitions.

Formal Definitions

Let B:={B1,…,BJ}\mathcal{B} := \{\mathcal{B}_1, \ldots, \mathcal{B}_J\} denote the collection of budgets. We first introduce the notion of undominance, following Koida and Shirai [2024].

Definition 6 (Undominated patch). Let xi∣jx_{i|j} be a patch on budget Bj\mathcal{B}_j, and let B~⊆B∖{Bj}\widetilde{\mathcal{B}} \subseteq\mathcal{B} \setminus\{\mathcal{B}_j\} be a collection of budgets. We say that xi∣jx_{i|j} is undominated by B~\widetilde{\mathcal{B}} if it lies strictly above every budget

hyperplane in B~\widetilde{\mathcal B}, that is,

pℓTy>1for all y∈xi∣j and all Bℓ∈B~.(9)p_{\ell}^{\mathsf T}y>1 \qquad\text{for all }y\in x_{i|j}\text{ and all }\mathcal B_{\ell}\in\widetilde{\mathcal B}. \tag*{(9)}

Since intersection patches have been excluded, xi∣jx_{i|j} is undominated by B~\widetilde{\mathcal B} if and only if no patch on any budget in B~\widetilde{\mathcal B} dominates it in the sense of the relation ≻d\succ^{d} from Definition 5. By convention, every patch is undominated by the empty collection.

Definition 7 (Multi-arc powerset digraph). The initial node set is 2B2^{\mathcal B}, with source node ∅\varnothing and terminal node B\mathcal B. For each k=0,…,Jk=0,\ldots,J, define the layer

Lk:={S⊆B:∣S∣=k}.\mathcal L_k:=\{S\subseteq\mathcal B:|S|=k\}.

A node SS records the budgets already removed, so the remaining budgets are those in B∖S\mathcal B\setminus S. The initial layer is L0={∅}\mathcal L_0=\{\varnothing\}. We construct the graph iteratively, proceeding through the layers in increasing order of cardinality. For each k=0,…,J−1k=0,\ldots,J-1, each retained node S∈LkS\in\mathcal L_k, and each Bj∈B∖S\mathcal B_j\in\mathcal B\setminus S, add an arc

a=(S,S∪{Bj},i):S→xi∣jS∪{Bj}a=(S,S\cup\{\mathcal B_j\},i):\qquad S\xrightarrow{x_{i|j}}S\cup\{\mathcal B_j\}

for every i∈{1,…,Ij}i\in\{1,\ldots,I_j\} such that xi∣jx_{i|j} is undominated by the other remaining budgets B∖(S∪{Bj})\mathcal B\setminus(S\cup\{\mathcal B_j\}), that is, satisfies (9) with B~=B∖(S∪{Bj})\widetilde{\mathcal B}=\mathcal B\setminus(S\cup\{\mathcal B_j\}). After all candidate arcs from layer Lk\mathcal L_k to layer Lk+1\mathcal L_{k+1} have been considered, remove every node in Lk+1\mathcal L_{k+1} with no incoming arcs. Let G=(V,A)\mathcal G=(\mathcal V,\mathcal A) denote the resulting directed multigraph.

Now we define the unit-flow polytope.

Definition 8 (Unit-flow polytope). Let B:={B1,…,BJ}\mathcal B:=\{\mathcal B_1,\ldots,\mathcal B_J\} denote the collection of budgets, and let G=(V,A)\mathcal G=(\mathcal V,\mathcal A) be its associated multi-arc powerset digraph. For an arc a=(S,S′,i)∈Aa=(S,S',i)\in\mathcal A, write its flow as fa=fS,S′,if_a=f_{S,S',i}.

The unit-flow polytope FG\mathcal F_{\mathcal G} is the set of all nonnegative flow vectors f∈R+Af\in\mathbb R_{+}^{\mathcal A} satisfying, for every node S∈VS\in\mathcal V,

∑(S′,S,i)∈AfS′,S,i−∑(S,S′,i)∈AfS,S′,i={−1,S=∅,1,S=B,0,otherwise.(10)\sum_{(S',S,i)\in\mathcal A}f_{S',S,i}-\sum_{(S,S',i)\in\mathcal A}f_{S,S',i} = \begin{cases} -1, & S=\varnothing,\\ 1, & S=\mathcal B,\\ 0, & \text{otherwise}. \end{cases} \tag*{(10)}

The first sum is the total inflow into SS. The second sum is the total outflow from SS. A sum over an empty set of arcs is defined to be zero.

We write these constraints compactly as FG={f∈R+A:AGf=bG}\mathcal F_{\mathcal G}=\{f\in\mathbb R_{+}^{\mathcal A}:A_{\mathcal G}f=b_{\mathcal G}\}, where AGA_{\mathcal G} is the node–arc incidence matrix, and bGb_{\mathcal G} has entry −1-1 at the source, 11 at the terminal node, and 00 elsewhere.

The node–arc incidence matrix AGA_{\mathcal G} is totally unimodular, and bGb_{\mathcal G} is integral. Hence, the unit-flow polytope FG\mathcal F_{\mathcal G} is integral. Since G\mathcal G is acyclic, the vertices of FG\mathcal F_{\mathcal G} are precisely the incidence vectors of directed paths from ∅\varnothing to B\mathcal B.

We define the following linear mapping from the flow space to choice probability space.

Definition 9 (Mapping flows to choice probabilities). Let B:={B1,…,BJ}\mathcal B:=\{\mathcal B_1,\ldots,\mathcal B_J\} denote the collection of budgets, and let G=(V,A)\mathcal G=(\mathcal V,\mathcal A) be its associated multi-arc powerset digraph, with unit-flow polytope FG\mathcal F_{\mathcal G}. For a flow f∈FGf\in\mathcal F_{\mathcal G}, define the induced choice-probability vector ρf\rho_f by

(ρf)i∣j:=∑S⊆B(S,S∪{Bj},i)∈AfS,S∪{Bj},i.(11)(\rho_f)_{i|j}:=\sum_{\substack{S\subseteq\mathcal B\\(S,S\cup\{\mathcal B_j\},i)\in\mathcal A}}f_{S,S\cup\{\mathcal B_j\},i}. \tag*{(11)}

for j=1,…,Jj = 1, \ldots, J and i=1,…,Iji = 1, \ldots, I_j. Thus, each coordinate is the total flow on all arcs labeled xi∣jx_{i|j}. We denote the corresponding linear map by LGL_{\mathcal{G}}, so that ρf=LGf\rho_f = L_{\mathcal{G}}f.

In words, for each patch xi∣jx_{i|j} on budget set jj, (ρf)i∣j(\rho_f)_{i|j} equals the sum of the flows on all arcs associated with xi∣jx_{i|j}.

Now we are ready to state the network characterization theorem. Recall the definition of PKS\mathcal{P}^{\mathrm{KS}} from (5).

Theorem 2. Given a collection of budgets B={B1,…,BJ}\mathcal{B} = \{\mathcal{B}_1, \ldots, \mathcal{B}_J\}, let G=(V,A)\mathcal{G} = (\mathcal{V}, \mathcal{A}) be its associated multi-arc powerset digraph from Definition 7, FG\mathcal{F}_{\mathcal{G}} its associated unit-flow polytope from Definition 8, and LGL_{\mathcal{G}} the linear map from Definition 9. Then

PKS={LGf:f∈FG}.(12)\mathcal{P}^{\mathrm{KS}} = \{L_{\mathcal{G}}f : f \in\mathcal{F}_{\mathcal{G}}\}. \tag*{(12)}

Proofs

We first prove that the dominance relation ≻d\succ^{d} defined by Definition 5 is acyclic.

Lemma 1. ≻d\succ^{d} is acyclic.

Proof. Suppose, for contradiction, that there exists a cycle of distinct patches

x~1≻dx~2≻d⋯≻dx~m≻dx~1.(13)\widetilde{x}_1 \succ^{d} \widetilde{x}_2 \succ^{d} \cdots\succ^{d} \widetilde{x}_m \succ^{d} \widetilde{x}_1. \tag*{(13)}

Let Bb\mathcal{B}_b denote the budget containing x~1\widetilde{x}_1. Since x~1≻dx~2\widetilde{x}_1 \succ^{d} \widetilde{x}_2, there exist y1∈x~1y_1 \in\widetilde{x}_1 and y2∈x~2y_2 \in\widetilde{x}_2 such that y1≥y2y_1 \ge y_2 componentwise. Because the patches are disjoint and pbp_b is strictly positive,

pbTy2<pbTy1=1.p_b^{\mathsf{T}}y_2 < p_b^{\mathsf{T}}y_1 = 1.

By the definition of patches, x~2\widetilde{x}_2 therefore lies entirely strictly below Bb\mathcal{B}_b. Furthermore, whenever x≻dx′x \succ^{d} x' and xx lies strictly below Bb\mathcal{B}_b, the same argument implies that x′x' also lies strictly below Bb\mathcal{B}_b. Applying this implication successively around the cycle in (13) shows that x~1\widetilde{x}_1 lies strictly below Bb\mathcal{B}_b, contradicting x~1⊆Bb\widetilde{x}_1 \subseteq\mathcal{B}_b. Thus, ≻d\succ^{d} is acyclic. □\square

Proof of Theorem 1

The third result follows from the first two results and the linearity of coordinate projection. In particular, the first result implies that Proj⁡(Pr)⊆{Av:v∈ΔT}\operatorname{Proj}(\mathcal{P}^{r}) \subseteq\{Av : v \in\Delta^{T}\}, and the second result implies that {Av:v∈ΔT}⊆Proj⁡(Pr)\{Av : v \in\Delta^{T}\} \subseteq\operatorname{Proj}(\mathcal{P}^{r}), establishing the desired equality.

We now prove the first result. Let π∈Πr\pi\in\Pi_r be any strict ranking, and write ≻π\succ_{\pi} for the corresponding binary relation. For each Dj\mathcal{D}_j, let xjπx_j^{\pi} denote the selected patch. No patch lying strictly below Bj\mathcal{B}_j can be selected, because every such patch is dominated by at least one patch on Bj\mathcal{B}_j and π\pi satisfies patch monotonicity.8 Thus, xjπ⊆Bjx_j^{\pi} \subseteq\mathcal{B}_j for every jj. It remains to show that these choices induce a rational type in the sense of KS (i.e., Definition 4).

Consider the directed revealed-preference graph on the budgets {Bj}j=1J\{\mathcal{B}_j\}_{j=1}^{J} defined in Definition 3. Recall that the graph contains an edge Ba→Bb\mathcal{B}_a \to\mathcal{B}_b for a≠ba \ne b whenever the selected patch xbπx_b^{\pi} lies strictly below Ba\mathcal{B}_a. Suppose, for contradiction, that this graph contains a cycle

Ba1→Ba2→⋯→BaS=Ba1.(14)\mathcal{B}_{a_1} \to\mathcal{B}_{a_2} \to\cdots\to\mathcal{B}_{a_S} = \mathcal{B}_{a_1}. \tag*{(14)}

For any edge Ba→Bb\mathcal{B}_a \to\mathcal{B}_b, we have paTyb<1=paTyap_a^{\mathsf{T}}y_b < 1 = p_a^{\mathsf{T}}y_a for every ya∈xaπy_a \in x_a^{\pi} and yb∈xbπy_b \in x_b^{\pi}. Hence, xbπ∈Dax_b^{\pi} \in\mathcal{D}_a, where Da\mathcal{D}_a is the expanded choice set associated with Ba\mathcal{B}_a. Since π\pi selects xaπx_a^{\pi} from Da\mathcal{D}_a, we have

xaπ≻πxbπ.(15)x_a^{\pi} \succ_{\pi} x_b^{\pi}. \tag*{(15)}

Applying this argument along the cycle yields

xa1π≻πxa2π≻π⋯≻πxaSπ=xa1π,(16)x_{a_1}^{\pi} \succ_{\pi} x_{a_2}^{\pi} \succ_{\pi} \cdots\succ_{\pi} x_{a_S}^{\pi} = x_{a_1}^{\pi}, \tag*{(16)}

contradicting the acyclicity of the strict ranking π\pi. Therefore, the induced boundary choices satisfy SARP and form a rational type in the sense of KS.

We now prove the second result. We show that every rational type can be extended to a strict preference ranking over patches that satisfies patch monotonicity. Fix a rational type. Let xj⊆Bjx_j \subseteq\mathcal{B}_j denote the selected patch for j=1,…,Jj=1,\ldots,J. Since the type is rational, its revealed-preference graph on the budgets is acyclic. We can therefore choose a strict ordering consistent with this graph and, after relabeling the budgets, write

B1≻B2≻⋯≻BJ.(17)\mathcal{B}_1 \succ\mathcal{B}_2 \succ\cdots\succ\mathcal{B}_J. \tag*{(17)}

Define a binary relation ≻S\succ^{S} as follows: for each s=1,…,Js=1,\ldots,J, define

xs≻Sx⟺x≠xs and x⊆Bj for some j∈{s,…,J},x_s \succ^{S} x \quad\Longleftrightarrow\quad x \ne x_s \text{ and } x \subseteq\mathcal{B}_j \text{ for some } j \in\{s,\ldots,J\},

where xsx_s is the selected patch from Bs\mathcal{B}_s.

We will show that the union ≻S∪≻d\succ^{S} \cup\succ^{d} is acyclic, where ≻d\succ^{d} is defined in Definition 5. It can then be extended to a strict preference ranking over X\mathcal{X} by applying Theorem 1.4 of Chambers and Echenique [ [1] to its reflexive and transitive closure.

Suppose by way of contradiction that ≻S∪≻d\succ^{S} \cup\succ^{d} contains a cycle. Note that the relation ≻S\succ^{S} is acyclic. By Lemma 1, ≻d\succ^{d} is also acyclic. Consequently, the cycle in ≻S∪≻d\succ^{S} \cup\succ^{d} must contain edges from both relations. In particular, the cycle must contain at least one ≻S\succ^{S}-edge. Consider a segment between consecutive ≻S\succ^{S}-edges of the form

xsi≻Sx~s~i≻d⋯≻dxsk≻Sx~s~k,(18)x_{s_i} \succ^{S} \widetilde{x}_{\widetilde{s}_i} \succ^{d} \cdots\succ^{d} x_{s_k} \succ^{S} \widetilde{x}_{\widetilde{s}_k}, \tag*{(18)}

where x~s~i⊆Bs~i\widetilde{x}_{\widetilde{s}_i} \subseteq\mathcal{B}_{\widetilde{s}_i}. The two ≻S\succ^{S}-edges may be adjacent, with no ≻d\succ^{d}-edge in between.

We claim that si<sks_i < s_k. By the definition of ≻S\succ^{S} and (17), we have si≤s~is_i \le\widetilde{s}_i. If the ≻d\succ^{d}-chain is nonempty, the argument following (13) in Lemma 1 implies that xskx_{s_k} lies strictly below Bs~i\mathcal{B}_{\widetilde{s}_i}. Thus, s~i≠sk\widetilde{s}_i \ne s_k and Bs~i→Bsk\mathcal{B}_{\widetilde{s}_i} \to\mathcal{B}_{s_k} is a revealed-preference edge. By (17), we therefore have s~i<sk\widetilde{s}_i < s_k, and hence si≤s~i<sks_i \le\widetilde{s}_i < s_k. If the ≻d\succ^{d}-chain is empty, then x~s~i=xsk\widetilde{x}_{\widetilde{s}_i}=x_{s_k}, so xsi≻Sxskx_{s_i} \succ^{S} x_{s_k} directly implies si<sks_i < s_k.

Applying this argument to the successive ≻S\succ^{S}-edges around the cycle yields

s1<s2<⋯<sL<s1,s_1 < s_2 < \cdots< s_L < s_1,

where xs1,…,xsLx_{s_1},\ldots,x_{s_L} are the sources of ≻S\succ^{S} edges. This is a contradiction. Therefore, ≻S∪≻d\succ^{S} \cup\succ^{d} is acyclic.

The reflexive and transitive closure of ≻S∪≻d\succ^{S} \cup\succ^{d} is therefore a partial order. By Theorem 1.4 of Chambers and Echenique [ [1], it admits a linear-order extension. Let π\pi denote the strict preference ranking given by the strict part of this extension. By construction, π\pi satisfies patch monotonicity.

For every jj, the relation ≻S\succ^{S} places xjx_j above every other patch on Bj\mathcal{B}_j. The argument used in the first part shows that a ranking satisfying patch monotonicity must select a boundary patch from each expanded choice set Dj\mathcal{D}_j. Hence, π\pi selects xjx_j from Dj\mathcal{D}_j for every jj, proving the second result.

Proof of Theorem 2

As noted after Definition 8, the vertices of FGF_{\mathcal{G}} are the incidence vectors of directed paths from ∅\varnothing to B\mathcal{B}. We first show that each such path rr is mapped by LGL_{\mathcal{G}} to a rational type.

We first show that LGrL_{\mathcal{G}}r is a choice type. Along a path, each budget Bj\mathcal{B}_j is added exactly once, namely, at the unique transition

S⟶S∪{Bj}.S \longrightarrow S \cup\{\mathcal{B}_j\}.

The corresponding arc has exactly one patch label xijx_{ij} for some ii. Hence, exactly one patch is selected from each budget Bj\mathcal{B}_j. Therefore, LGrL_{\mathcal{G}}r is a choice type.

We next show that LGrL_{\mathcal{G}}r is a rational type. We verify that LGrL_{\mathcal{G}}r is rational by showing that the induced revealed-preference graph on budgets is acyclic according to Definition 3 and Definition 4. To construct such a graph, consider the patch xi∣jx_{i|j} selected when the path moves from SS to S∪{Bj}S \cup\{B_j\}. By the definition of the multi-arc powerset digraph, xi∣jx_{i|j} lies strictly above every budget

B∖(S∪{Bj}).\mathcal{B} \setminus(S \cup\{B_j\}).

Hence, if the selected patch xi∣jx_{i|j} lies strictly below some budget BℓB_\ell, then necessarily Bℓ∈SB_\ell\in S.

For each BjB_j and Bℓ∈SB_\ell\in S that appears before BjB_j along the path rr, we add an arc

Bℓ→Bj.B_\ell\to B_j.

Therefore, all arcs point from budgets that appear earlier on the path to budgets that appear later. The resulting graph contains every arc induced by the choice type LGrL_{\mathcal{G}r} under Definition 3. The order in which budgets are added along the path thus provides a topological ordering of the induced revealed-preference graph on budgets as in Definition 3. Consequently, the graph is acyclic, and LGrL_{\mathcal{G}r} is a rational type by Definition 4.

We now prove the reverse direction. Let aa be any rational type. We show that there exists a path rr in FG\mathcal{F}_{\mathcal{G}} such that LGr=aL_{\mathcal{G}r}=a.

Let xaj∣jx_{a_j|j} denote the patch selected by the rational type aa from budget BjB_j, for j=1,…,Jj=1,\ldots,J. By definition, aa induces an acyclic revealed-preference graph on the budgets B={B1,…,BJ}\mathcal{B}=\{B_1,\ldots,B_J\}. Hence, this graph admits a topological ordering. Without loss of generality, after relabeling the budgets, write this ordering as

B1≻B2≻⋯≻BJ,(19)B_1 \succ B_2 \succ\cdots\succ B_J, \tag*{(19)}

where every revealed-preference edge Bj→BkB_j \to B_k satisfies j<kj<k.

Let G\mathcal{G} be the multi-arc powerset digraph that is induced by B={B1,…,BJ}\mathcal{B}=\{B_1,\ldots,B_J\} according to Definition 7. We now show that there exists a path in G\mathcal{G} that follows the ordering in (19) and selects the patches specified by aa.

Let S1=∅S_1=\varnothing and, for k=1,…,Jk=1,\ldots,J, define

Sk:={B1,…,Bk−1}.S_k := \{B_1,\ldots,B_{k-1}\}.

We construct the path recursively by moving from SkS_k to Sk∪{Bk}S_k \cup\{B_k\}. Let xak∣kx_{a_k|k} denote the patch selected by aa from budget BkB_k. We claim that the arc

Sk→xak∣kSk∪{Bk}S_k \xrightarrow{x_{a_k|k}} S_k \cup\{B_k\}

is present in G\mathcal{G}.

Indeed, such an arc could be absent only if xak∣kx_{a_k|k} were dominated by the remaining budgets in the sense of Definition 6, that is, if it lay strictly below some remaining budget BℓB_\ell with ℓ>k\ell>k. But then the selected patch from BkB_k would lie strictly below BℓB_\ell, implying a revealed-preference edge

Bℓ→Bk.B_\ell\to B_k.

This contradicts the topological ordering in (19), according to which every revealed-preference edge points from an earlier budget to a later budget. Hence, the required arc is present at every step.

It follows that

∅→{B1}→{B1,B2}→⋯→B\varnothing\to\{B_1\} \to\{B_1,B_2\} \to\cdots\to\mathcal{B}

is a path in G\mathcal{G} whose arc labels are precisely xa1∣1,…,xaJ∣Jx_{a_1|1},\ldots,x_{a_J|J}. Therefore, if rr denotes the incidence vector of this path, then

LGr=a.L_{\mathcal{G}r}=a.

Combining the two directions, the vertices of FG\mathcal{F}_{\mathcal{G}} map exactly onto the rational types. Since FG\mathcal{F}_{\mathcal{G}} is the convex hull of its path vertices and linear maps commute with convex hulls, we obtain

PKS={LGf:f∈FG}.\mathcal{P}^{\mathrm{KS}}=\{L_{\mathcal{G}f}: f\in\mathcal{F}_{\mathcal{G}}\}.

References

  1. [1]Christopher P. Chambers and Federico Echenique. Revealed preference theory. Cambridge University Press, 2016.DOI
  2. [2]Samuel Fiorini. A short proof of a theorem of Falmagne. Journal of mathematical psychology, 48 (1):80–82, 2004.DOI
  3. [3]Yuichi Kitamura and Jörg Stoye. Nonparametric analysis of random utility models. Econometrica, 86(6):1883–1909, 2018. doi: 10.3982/ECTA14478.DOI

Paper details

vlnc:W_8jnb8wjx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Economics, Econometrics and Finance

Not recorded for this paper

View statement
Looking for related papers…
Contents