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:
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.
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 linear budgets, each of the form
where denotes the number of commodities and is the normalized price vector.3 It is assumed that the price vectors 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 be the coarsest partition of such that, for every and , the patch lies entirely on, strictly above, or strictly below the budget plane . Equivalently, two points belong to the same patch if and only if
where 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 is a disjoint union of patches, which we enumerate as .
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
where is the probability that the bundle chosen from budget belongs to patch .
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 .
Rational Types
The KS approach tests whether the observed vector of choice probabilities 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 by the binary vector
where if type selects patch from budget and otherwise. In particular,
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 , 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 for the remaining patches on budget . 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 and the collection of budgets . For any pair , we say that is directly revealed preferred to if there is an index such that
Moreover, we define a directed revealed-preference graph with node set . For any distinct budgets and , include an arc if is revealed preferred to .
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 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 , where is the number of such types. Recall that denotes the number of patches, which is equivalent to the dimension of the choice probability vector. Let denote the dimension of the choice probability vector. We stack the rational types columnwise to form a matrix . By Theorem 3.1 of KS, a choice probability vector is rationalizable if and only if
where is the unit simplex in , . We denote the polytope generated by the KS rational types by :
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 strict rankings over the patches, where 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 , we define the choice set
Here, is the set of patches (alternatives) The budgets index a choice probability system , with one choice probability vector for each budget .
A choice probability vector induces a subprobability vector on the budget boundary , given by . 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 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 in Figure 1, the expanded menus (excluding intersection patches) are
There are three rational types in the sense of KS, as shown in Table 1.
| Budget | Type 1 | Type 2 | Type 3 |
Table 1. The three rational types.
The remaining boundary-choice profile violates SARP: lies strictly below , and lies strictly below , 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.
| Ranking | Choice from | Choice from | Monotone? |
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| Yes | |||
| Yes | |||
| No | |||
| Yes | |||
| Yes | |||
| No | |||
| Yes | |||
| Yes | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No | |||
| No |
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 , we write if there exist and such that componentwise.6 We say that a strict preference ranking satisfies patch monotonicity if implies for all distinct .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 lies strictly inside the feasible budget sets associated with and . Each patch on these outer budgets contains a point that dominates some point of . However, neither left patch contains a point dominating , and neither right patch contains a point dominating . Thus, no single outer patch can provide a dominating point for every point of .

Figure 2. The inner budget 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
This ranking selects from both expanded menus and and therefore does not induce a rational type in the sense of KS.
We now state our projection theorem. Recall the definition of from (5).
Theorem 1. Given a collection of distinct budgets , let denote the induced nonintersection patches. Let denote the rational choice types as in Definition 4, and write . Let denote the set of all strict preference rankings over , and let denote the rankings that satisfy patch monotonicity as defined in Definition 5. Let be the choice sets defined in (6). For each , let denote the deterministic choice probability vector obtained by selecting the highest-ranked patch from each . Then the following statements hold:
Every ranking in induces a rational choice type in the sense of KS.
Every rational choice type in the sense of KS is induced by at least one ranking in .
Define
Let Proj denote the coordinate projection that retains only the coordinates for which , ordered as in the rows of . Then
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 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 :
After excluding intersection patches, each budget has three patches, which we enumerate as in increasing order of . The pairwise intersection points are
Figure 3 illustrates the resulting nine nonintersection patches.

Figure 3. The nine nonintersection patches induced by three budgets with two commodities. Patches on each budget are indexed in increasing order of . Hollow circles mark the excluded intersection points.
Now consider an agent whose maximized utility is highest on , followed by and then . Thus, the agent must choose from , since and lie strictly below . We then remove from the construction. On , both and lie above the remaining budget , whereas lies strictly below it. Either or may therefore be selected. After removing , any of the three original patches on 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.

Figure 4. Sequential choices for the budget ordering . 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 . Each node records the indices of the budgets already removed. An arc from to represents choosing its labeled patch from and then removing .

Figure 5. The subnetwork corresponding to . 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 . The second transition has two parallel arcs, labeled and , and the final transition has three parallel arcs, one for each patch on . Each path from to 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 to 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.

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 from budget equals the sum of the flows on all arcs labeled 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 lies strictly below the union of and . Thus, any feasible strict budget ordering must place last
Because each node records the budgets already removed, can be removed only after both and . Consequently, the nodes , , and are unreachable from and can be omitted. The reduced network, shown in Figure 8, has five nodes and seven arcs. If is removed first, its chosen patch must be ; if is removed first, its chosen patch must be . Either patch on the second outer budget is then admissible, followed by the sole patch on .

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.

Figure 7. The inner budget 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 denote the collection of budgets. We first introduce the notion of undominance, following Koida and Shirai [2024].
Definition 6 (Undominated patch). Let be a patch on budget , and let be a collection of budgets. We say that is undominated by if it lies strictly above every budget
hyperplane in , that is,
Since intersection patches have been excluded, is undominated by if and only if no patch on any budget in dominates it in the sense of the relation from Definition 5. By convention, every patch is undominated by the empty collection.
Definition 7 (Multi-arc powerset digraph). The initial node set is , with source node and terminal node . For each , define the layer
A node records the budgets already removed, so the remaining budgets are those in . The initial layer is . We construct the graph iteratively, proceeding through the layers in increasing order of cardinality. For each , each retained node , and each , add an arc
for every such that is undominated by the other remaining budgets , that is, satisfies (9) with . After all candidate arcs from layer to layer have been considered, remove every node in with no incoming arcs. Let denote the resulting directed multigraph.
Now we define the unit-flow polytope.
Definition 8 (Unit-flow polytope). Let denote the collection of budgets, and let be its associated multi-arc powerset digraph. For an arc , write its flow as .
The unit-flow polytope is the set of all nonnegative flow vectors satisfying, for every node ,
The first sum is the total inflow into . The second sum is the total outflow from . A sum over an empty set of arcs is defined to be zero.
We write these constraints compactly as , where is the node–arc incidence matrix, and has entry at the source, at the terminal node, and elsewhere.
The node–arc incidence matrix is totally unimodular, and is integral. Hence, the unit-flow polytope is integral. Since is acyclic, the vertices of are precisely the incidence vectors of directed paths from to .
We define the following linear mapping from the flow space to choice probability space.
Definition 9 (Mapping flows to choice probabilities). Let denote the collection of budgets, and let be its associated multi-arc powerset digraph, with unit-flow polytope . For a flow , define the induced choice-probability vector by
for and . Thus, each coordinate is the total flow on all arcs labeled . We denote the corresponding linear map by , so that .
In words, for each patch on budget set , equals the sum of the flows on all arcs associated with .
Now we are ready to state the network characterization theorem. Recall the definition of from (5).
Theorem 2. Given a collection of budgets , let be its associated multi-arc powerset digraph from Definition 7, its associated unit-flow polytope from Definition 8, and the linear map from Definition 9. Then
Proofs
We first prove that the dominance relation defined by Definition 5 is acyclic.
Lemma 1. is acyclic.
Proof. Suppose, for contradiction, that there exists a cycle of distinct patches
Let denote the budget containing . Since , there exist and such that componentwise. Because the patches are disjoint and is strictly positive,
By the definition of patches, therefore lies entirely strictly below . Furthermore, whenever and lies strictly below , the same argument implies that also lies strictly below . Applying this implication successively around the cycle in (13) shows that lies strictly below , contradicting . Thus, is acyclic.
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 , and the second result implies that , establishing the desired equality.
We now prove the first result. Let be any strict ranking, and write for the corresponding binary relation. For each , let denote the selected patch. No patch lying strictly below can be selected, because every such patch is dominated by at least one patch on and satisfies patch monotonicity.8 Thus, for every . 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 defined in Definition 3. Recall that the graph contains an edge for whenever the selected patch lies strictly below . Suppose, for contradiction, that this graph contains a cycle
For any edge , we have for every and . Hence, , where is the expanded choice set associated with . Since selects from , we have
Applying this argument along the cycle yields
contradicting the acyclicity of the strict ranking . 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 denote the selected patch for . 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
Define a binary relation as follows: for each , define
where is the selected patch from .
We will show that the union is acyclic, where is defined in Definition 5. It can then be extended to a strict preference ranking over by applying Theorem 1.4 of Chambers and Echenique [ [1] to its reflexive and transitive closure.
Suppose by way of contradiction that contains a cycle. Note that the relation is acyclic. By Lemma 1, is also acyclic. Consequently, the cycle in must contain edges from both relations. In particular, the cycle must contain at least one -edge. Consider a segment between consecutive -edges of the form
where . The two -edges may be adjacent, with no -edge in between.
We claim that . By the definition of and (17), we have . If the -chain is nonempty, the argument following (13) in Lemma 1 implies that lies strictly below . Thus, and is a revealed-preference edge. By (17), we therefore have , and hence . If the -chain is empty, then , so directly implies .
Applying this argument to the successive -edges around the cycle yields
where are the sources of edges. This is a contradiction. Therefore, is acyclic.
The reflexive and transitive closure of is therefore a partial order. By Theorem 1.4 of Chambers and Echenique [ [1], it admits a linear-order extension. Let denote the strict preference ranking given by the strict part of this extension. By construction, satisfies patch monotonicity.
For every , the relation places above every other patch on . The argument used in the first part shows that a ranking satisfying patch monotonicity must select a boundary patch from each expanded choice set . Hence, selects from for every , proving the second result.
Proof of Theorem 2
As noted after Definition 8, the vertices of are the incidence vectors of directed paths from to . We first show that each such path is mapped by to a rational type.
We first show that is a choice type. Along a path, each budget is added exactly once, namely, at the unique transition
The corresponding arc has exactly one patch label for some . Hence, exactly one patch is selected from each budget . Therefore, is a choice type.
We next show that is a rational type. We verify that 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 selected when the path moves from to . By the definition of the multi-arc powerset digraph, lies strictly above every budget
Hence, if the selected patch lies strictly below some budget , then necessarily .
For each and that appears before along the path , we add an arc
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 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 is a rational type by Definition 4.
We now prove the reverse direction. Let be any rational type. We show that there exists a path in such that .
Let denote the patch selected by the rational type from budget , for . By definition, induces an acyclic revealed-preference graph on the budgets . Hence, this graph admits a topological ordering. Without loss of generality, after relabeling the budgets, write this ordering as
where every revealed-preference edge satisfies .
Let be the multi-arc powerset digraph that is induced by according to Definition 7. We now show that there exists a path in that follows the ordering in (19) and selects the patches specified by .
Let and, for , define
We construct the path recursively by moving from to . Let denote the patch selected by from budget . We claim that the arc
is present in .
Indeed, such an arc could be absent only if were dominated by the remaining budgets in the sense of Definition 6, that is, if it lay strictly below some remaining budget with . But then the selected patch from would lie strictly below , implying a revealed-preference edge
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
is a path in whose arc labels are precisely . Therefore, if denotes the incidence vector of this path, then
Combining the two directions, the vertices of map exactly onto the rational types. Since is the convex hull of its path vertices and linear maps commute with convex hulls, we obtain
References
- [1]Christopher P. Chambers and Federico Echenique. Revealed preference theory. Cambridge University Press, 2016.DOI
- [2]Samuel Fiorini. A short proof of a theorem of Falmagne. Journal of mathematical psychology, 48 (1):80–82, 2004.DOI
- [3]Yuichi Kitamura and Jörg Stoye. Nonparametric analysis of random utility models. Econometrica, 86(6):1883–1909, 2018. doi: 10.3982/ECTA14478.DOI
