The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
58,391 characters
Tractable Estimation of the Money Pump Index: A Comment
\maketitle
\begin{abstract}
\noindent The Money Pump Index (MPI) of \citet{echenique2011money} measures the severity of consumer irrationality, but computing the exact mean and median MPI over all revealed preference cycles is NP-hard \citep{smeulders2013note}. Existing solutions rely on heuristic proxies, such as evaluating only shorter cycles or bounding the MPI. By framing revealed preferences as a directed graph, this paper projects choice violations onto fundamental cycle bases, which are minimal sets of linearly independent cycles that span the graph's entire cycle space. This yields computationally tractable estimators for the mean and median MPI that are asymptotically equivalent to the original MPI. Applying this methodology to the scanner dataset analyzed by \citet{echenique2011money} and \citet{smeulders2013note}, the proposed estimators compute quickly and with negligible small-sample bias.
\end{abstract}
\vspace{0.5em}
\noindent\textbf{Keywords:} Revealed Preference, Money Pump Index, Fundamental Cycle Basis, Consumer Rationality\\
\noindent\textbf{JEL Classification:} C60, C63, D11, D12.
\newpage
\section{Introduction}
Irrational behavior makes consumers vulnerable because it allows arbitrageurs to extract money from them. \citet{echenique2011money} operationalized this concept by proposing the Money Pump Index (MPI), which measures the fraction of a consumer's budget an arbitrageur could extract by exploiting violations of the generalized axiom of revealed preference (GARP). When a consumer's choices violate GARP, there are typically multiple overlapping choice cycles that generate money pumps. A natural way to summarize the severity of a consumer's overall irrationality is to take the mean or median value of the money pumps across all such cycles.
However, calculating this mean or median severity is computationally intractable for large datasets. For example, consider a dataset of prices and bundles $D = \{(\mathbf{p}^t, \mathbf{x}^t)\}_{t=1}^n$ with $n=25$ observations. The number of potential cycles of length $k$ is $\binom{n}{k}(k-1)!$. For instance, if we just look at cycles of length $k=10$, there are $\binom{25}{10} \times 9! \approx 1.18 \times 10^{12}$ potential cycles. Summing across all possible cycle lengths results in an inordinately large number of cycles. Indeed, \citet{smeulders2013note} formalize this computational challenge by proving that computing the exact mean MPI (OA-MPI) is an NP-hard problem. Consequently, researchers analyzing datasets with many observations often use approximations to the true mean and median MPI by considering only shorter cycles, or using instead extreme values like the maximum/minimum MPI \citep{smeulders2013note}.
I examine whether we can tractably measure the mean and median MPI without imposing arbitrary cycle length restrictions. I overcome the $n!$ scaling associated with evaluating all cycles (i.e., the $\mathcal{O}(n!)$ complexity) by leveraging graph theory. Specifically, a dataset $D$ can be reformulated as a directed graph where observations are nodes and revealed preference relations are directed edges, meaning finding cycles in the graph is exactly equivalent to finding cycles in preferences. Adopting this framework, I propose a new approach that projects choice violations onto the graph's \textit{fundamental cycle basis}---a minimal, linearly independent set of cycles that spans the entire cycle space of the graph.
I introduce the Basis Average MPI, an equivalent formulation of the true mean MPI that aggregates over the graph's fundamental cycle bases rather than enumerating all individual cycles. While the total number of possible cycle bases remains large, this reformulation gives rise to an efficient estimator. By randomly sampling over the space of fundamental cycle bases, the estimator approximates the true mean MPI in polynomial time ($\mathcal{O}(K n^2)$, where $K$ is the sample size and $n$ is the number of observations). I formally establish the consistency of this estimator and provide theoretical bounds on its finite-sample empirical bias, which proves negligible in practice. Analogously, I introduce the Basis Percentile MPI and a corresponding consistent estimator for the median MPI (and any arbitrary percentile). Finally, I apply this methodology to the Stanford Basket Dataset as in \citet{echenique2011money} and \citet{smeulders2013note}. Across all 396 GARP-violating households, the estimators compute in under 40 seconds, achieving near-zero empirical bias (mean bias $< 0.0001$). Furthermore, while the estimated mean MPI closely aligns with the short-cycle approximation of \citet{echenique2011money}, the basis median reveals that truncating at cycle length 4 slightly overestimates the true median severity of irrationality.
The remainder of the paper proceeds as follows. Section \ref{sec:garp_mpi} formally links the MPI to the directed graph representation. Section \ref{sec:ensemble} constructs the fundamental cycle bases and proves the consistency of the random-path estimators. Section \ref{sec:empirical} validates the estimators on the Stanford Basket Dataset, demonstrating near-zero empirical bias. All proofs are relegated to the appendix.
\section{GARP and the MPI} \label{sec:garp_mpi}
\textbf{GARP}: Suppose we have a dataset $D = \{(\mathbf{p}^t, \mathbf{x}^t)\}_{t=1}^n$ of $n$ observations, where $\mathbf{p}^t \in \mathbb{R}_{++}^L$ is a positive price vector and $\mathbf{x}^t \in \mathbb{R}_+^L$ is a non-negative bundle. For any two observations $i$ and $j$, if and only if $\mathbf{p}^i \cdot \mathbf{x}^i \ge \mathbf{p}^i \cdot \mathbf{x}^j$, we say that $\mathbf{x}^i$ is \textit{directly revealed preferred} to $\mathbf{x}^j$, denoted as $\mathbf{x}^i R_0 \mathbf{x}^j$. The indirect revealed preference relation, denoted by $R$, is the transitive closure of $R_0$. Furthermore, $\mathbf{x}^i$ is \textit{strictly directly revealed preferred} to $\mathbf{x}^j$ if and only if $\mathbf{p}^i \cdot \mathbf{x}^i > \mathbf{p}^i \cdot \mathbf{x}^j$, denoted as $\mathbf{x}^i P_0 \mathbf{x}^j$. A dataset $D$ satisfies the generalized axiom of revealed preference (GARP) if, for any sequence of observations $(k_1, k_2, \dots, k_m)$ such that $\mathbf{x}^{k_1} R_0 \mathbf{x}^{k_2}$, $\mathbf{x}^{k_2} R_0 \mathbf{x}^{k_3}$, $\dots$, $\mathbf{x}^{k_{m-1}} R_0 \mathbf{x}^{k_m}$, it is not the case that $\mathbf{x}^{k_m} P_0 \mathbf{x}^{k_1}$.
As GARP is a binary test, we frequently use indices to quantify the severity of irrationality. Alongside the MPI \citep{echenique2011money}, the literature has proposed numerous such measures, such as Afriat's Efficiency Index \citep{afriat1967construction}, Varian's Index \citep{varian1990goodness}, the Houtman-Maks Index \citep{houtman1985determining}, the Minimum Cost Index \citep{dean2016measuring}, and the Swaps Index \citep{apesteguia2015measure}.\footnote{Recently, \cite{demuynck2023computing} have introduced Mixed-Integer Linear Programming (MILP) formulations for the average Varian Index, the Houtman-Maks Index, and the Minimum Cost Index. MILP solvers are typically very fast, overcoming computational problems normally associated with those indices.}
\textbf{MPI}: The fundamental idea behind the MPI is one of ``exploiting the vulnerability'' of irrational consumers by measuring the amount of money an ``arbitrageur'' could extract from them. If a consumer (represented by their dataset) violates GARP, it is because they exhibit a revealed preference cycle from their choices. For example, suppose observations $1$ and $2$ form a 2-cycle (cycle of length 2) such that $\mathbf{p}^1 \cdot \mathbf{x}^1 \ge \mathbf{p}^1 \cdot \mathbf{x}^2$ and $\mathbf{p}^2 \cdot \mathbf{x}^2 > \mathbf{p}^2 \cdot \mathbf{x}^1$, i.e., they chose such that $\mathbf{x}^1 R_0 \mathbf{x}^2$, and $\mathbf{x}^2 P_0 \mathbf{x}^1$.
As the consumer chose $\mathbf{x}^1$ at prices $\mathbf{p}^1$ when $\mathbf{x}^2$ was affordable, they implicitly value ``upgrading'' from $\mathbf{x}^2$ to $\mathbf{x}^1$ at a minimum of $\mathbf{p}^1 \cdot (\mathbf{x}^1 - \mathbf{x}^2)$. Likewise, at prices $\mathbf{p}^2$, the minimum value of upgrading from $\mathbf{x}^1$ to $\mathbf{x}^2$ is $\mathbf{p}^2 \cdot (\mathbf{x}^2 - \mathbf{x}^1)$. As described, an arbitrageur makes a profit by providing this ``exploitative upgrade service'' to the consumer, with arbitrageur profit being $\mathbf{p}^1 \cdot (\mathbf{x}^1 - \mathbf{x}^2) + \mathbf{p}^2 \cdot (\mathbf{x}^2 - \mathbf{x}^1)$, while still leaving the consumer with their preferred bundles. If it were not the case that $\mathbf{x}^2 P_0 \mathbf{x}^1$, the arbitrageur is no longer guaranteed to make a profit (i.e., there is no irrationality to exploit).
Generalizing to an arbitrary preference cycle $C = (k_1, k_2, \ldots, k_m)$ of length $m$, we define $\text{MPI}_D(C)$ which measures the arbitrageur's total money pump profit relative to the consumer's total expenditure within that cycle:
\begin{equation*}
\text{MPI}_D(C) = \frac{\sum_{i=1}^m \mathbf{p}^{k_i} \cdot (\mathbf{x}^{k_i} - \mathbf{x}^{k_{i+1}})}{\sum_{i=1}^m \mathbf{p}^{k_i} \cdot \mathbf{x}^{k_i}} = 1 - \frac{\sum_{i=1}^m \mathbf{p}^{k_i} \cdot \mathbf{x}^{k_{i+1}}}{\sum_{i=1}^m \mathbf{p}^{k_i} \cdot \mathbf{x}^{k_i}},
\end{equation*}
where $k_{m+1} = k_1$. For a given cycle $C$, this captures the proportion of the total cycle expenditure an arbitrageur could extract. To measure the MPI for an entire dataset $D$, \citet{echenique2011money} recommend the mean (denoted $\text{OA-MPI}_D$) or median (denoted $\text{OP}_{50}\text{-MPI}_D$, or more generally any $\alpha$-percentile $\text{OP}_\alpha\text{-MPI}_D$) of $\text{MPI}_D(C)$ over all cycles within $D$, while \citet{smeulders2013note} provide an algorithm for computing the maximum/minimum of $\text{MPI}_D(C)$ over all cycles (providing informative bounds on the OA-MPI).
For tractability with the following graph-theoretic approach, we use a normalized dataset $\tilde{D} = \{(\tilde{\mathbf{p}}^t, \mathbf{x}^t)\}_{t=1}^n$, where per-period prices are adjusted to $\tilde{\mathbf{p}}^t = \mathbf{p}^t / (\mathbf{p}^t \cdot \mathbf{x}^t)$ so that expenditures are normalized to 1 ($\tilde{\mathbf{p}}^t \cdot \mathbf{x}^t = 1$). We define an $n\times n$ matrix $X$ such that for any two observations, $k_i$ and $k_j$, the $(k_i,k_j)$-th entry of $X$ is $X_{k_i,k_j} = 1 - \tilde{\mathbf{p}}^{k_i} \cdot \mathbf{x}^{k_j}$.\footnote{For any two observations with $k_i\neq k_j$ in $\tilde{D}$, $X_{k_i,k_j} > 0$ indicates a strict preference violation.} With this matrix $X$, we have now defined a directed graph $G_{\tilde{D}}$ where each node is an observation. The weight on each directed edge is given by $X_{k_i,k_j}$, which is referred to as the money pump cost associated with observations $(k_i, k_j)$. This represents the exact fraction of the consumer's period-$k_i$ budget that the arbitrageur extracts by swapping the consumer's bundle $\mathbf{x}^{k_j}$ for bundle $\mathbf{x}^{k_i}$ at prices $\mathbf{p}^{k_i}$. We reformulate $\text{MPI}_D(C)$ on the normalized dataset $\tilde{D}$ for any cycle $C = (k_1, \dots, k_m)$ as:\footnote{When expenditures in $D$ are constant across periods, $\text{MPI}_D(C)$ and $\text{MPI}_{\tilde{D}}(C)$ are identical. When expenditures fluctuate, normalization induces a small divergence. In Appendix \ref{sec:appendix_normalization}, Lemma \ref{lem:equivalence} formally proves that the maximum possible difference is strictly bounded by $X_{\max} \cdot \left( \frac{\sqrt{r} - 1}{\sqrt{r} + 1} \right)$, where $r$ is the ratio between the highest and lowest expenditure in cycle $C$, and $X_{\max}$ is the largest single violation in the cycle. Applying this to our empirical application (Section \ref{sec:empirical}) in the most conservative way possible, evaluating the worst-case cycle for each household exhibiting two-cycle violations, $r$ has a median of only $1.101$ (mean $1.133$), yielding a median theoretical bound of $0.0021$ (mean $0.0046$) and an actual worst-case difference $|\text{MPI}_D(C) - \text{MPI}_{\tilde{D}}(C)|$ of only $0.0013$ (mean $0.0032$; see Table \ref{tab:normalization_stats} in Appendix \ref{sec:appendix_normalization}). We therefore proceed with the normalized dataset $\tilde{D}$ for the remainder of the paper.}
\begin{equation*}
\text{MPI}_{\tilde{D}}(C) = \frac{1}{|C|} \sum_{i=1}^{|C|} X_{k_i, k_{i+1}}.
\end{equation*}
\noindent\textbf{Example:} To solidify understanding, consider a consumer with dataset $\mathcal{D}$ comprising three observations (over three distinct goods), with $\mathbf{x}^1 = (1, 0, 0)$, $\mathbf{x}^2 = (0, 1, 0)$, and $\mathbf{x}^3 = (0, 0, 1)$, at prices $\mathbf{p}^1 = (1, 0.8, 1.5)$, $\mathbf{p}^2 = (0.9, 1, 0.7)$, and $\mathbf{p}^3 = (0.9, 0.9, 1)$. This consumer exhibits exactly 3 GARP-violating preference cycles: i) $\mathbf{x}^1 P_0 \mathbf{x}^2$, yet $\mathbf{x}^2 P_0 \mathbf{x}^1$; ii) $\mathbf{x}^2 P_0 \mathbf{x}^3$, yet $\mathbf{x}^3 P_0 \mathbf{x}^2$; iii) $\mathbf{x}^1 P_0 \mathbf{x}^2$, $\mathbf{x}^2 P_0 \mathbf{x}^3$, yet $\mathbf{x}^3 P_0 \mathbf{x}^1$.
Calculating all the associated money pump costs, we have:
\begin{align*}
X_{1,2} &= 1 - 0.80 = 0.20, & X_{2,1} &= 1 - 0.90 = 0.10, \\[0.85em]
X_{2,3} &= 1 - 0.70 = 0.30, & X_{3,2} &= 1 - 0.90 = 0.10, \\[0.85em]
X_{1,3} &= 1 - 1.50 = -0.50, & X_{3,1} &= 1 - 0.90 = 0.10.
\end{align*}
Let $C_{k_1, k_2, \dots, k_j}$ denote the choice cycle associated with the sequence of observations $k_1, k_2, \dots, k_j,k_1$ (with a $j$-cycle referring to a generic cycle of length $j$). We can then calculate the associated MPI for each of the 5 potential structural cycles. As an arbitrageur will not trade a cycle with a negative payout, we enforce $\text{MPI}(C) = \max(0, \frac{1}{|C|}\sum X)$:
\begin{align*}
\text{MPI}_{\mathcal{D}}(C_{1,2}) &= \frac{1}{2}(0.2 + 0.1) = 0.15, \\[0.85em]
\text{MPI}_{\mathcal{D}}(C_{2,3}) &= \frac{1}{2}(0.3 + 0.1) = 0.20, \\[0.85em]
\text{MPI}_{\mathcal{D}}(C_{1,2,3}) &= \frac{1}{3}(0.2 + 0.3 + 0.1) = 0.20.
\end{align*}
The standard OA-MPI, as recommended by \citet{echenique2011money}, measures the global severity of irrationality by averaging the money pump costs exclusively over the valid GARP-violating cycles in the dataset. As exactly 3 of the 5 potential cycles are strict violations, the OA-MPI evaluates to:
\begin{align*}
\text{OA-MPI}_{\mathcal{D}} &= \frac{1}{3} (0.150 + 0.200 + 0.200) = 0.183.
\end{align*}
For a dataset with $n$ observations, the total number of distinct choice cycles is given by $\sum_{j=2}^{n} \binom{n}{j} (j-1)!$, which clearly explodes as $n$ increases (with $\mathcal{O}(n!)$ complexity). Consequently, evaluating the average across all possible cycles becomes practically impossible for larger datasets. As shown by \citet{smeulders2013note}, computing the true mean (or median) MPI is an NP-hard problem, meaning that there can only exist a polynomial time algorithm for computation if $\text{P}=\text{NP}$.
\section{Basis MPI} \label{sec:ensemble}
\noindent\textbf{Example (continued):} I show that we can select a specific subset of just four cycles---referred to as a \textit{fundamental cycle basis}---to construct all other cycles. To see this, we use a directed \textit{Hamiltonian path} (hereafter, \textit{H-path}), which is a directed path that visits every node in a graph precisely once. By ordering the vertices along this path, we can classify all other edges in the graph relative to this sequence to form a cycle basis.
Consider the path sequence $l_1: 1 \to 2 \to 3$. We extract its fundamental cycle basis, denoted $\mathcal{B}_{l_1}$, as follows:
\begin{enumerate}
\item \textbf{Contiguous Subsegments:} A subsegment is a contiguous sequence of edges directly along the H-path. We take all possible contiguous subsegments of the path and close each one using a single \textit{back-edge} (an edge that points backwards against the path sequence) to form a cycle. For example, the subsegment $(1 \to 2)$ is closed by the back-edge $2\to1$ yielding $C_{1,2}$; $(2 \to 3)$ is closed by $3\to2$ yielding $C_{2,3}$; and the full path $(1 \to 2 \to 3)$ is closed by $3\to1$ yielding $C_{1,2,3}$.
\item \textbf{Skip-Edge 2-Cycles:} A \textit{skip-edge} is an edge that skips ahead along the H-path, jumping over intermediate vertices. We take any skip-edges along the path and close them using a single back-edge to form a 2-cycle. In our path, the only forward skip-edge is $(1 \to 3)$, which we close with the back-edge $3\to1$ yielding $C_{1,3}$.
\end{enumerate}
This yields the fundamental cycle basis $\mathcal{B}_{l_1} = \{C_{1,2}, C_{2,3}, C_{1,2,3}, C_{1,3}\}$ as shown in Figure \ref{fig:permutation_basis}.
\begin{figure}[ht]
\centering
\resizebox{\textwidth}{!}{\begin{tikzpicture}[
vertex/.style={circle, draw, minimum size=8mm, font=\large},
treeedge/.style={->, ultra thick, >=latex},
inactiveedge/.style={->, thick, >=latex, dashed, gray!50},
cycleedge/.style={->, ultra thick, >=latex, dashed, color=blue},
skipedge/.style={->, ultra thick, >=latex, postaction={decorate, decoration={markings, mark=at position 0.33 with {\arrow{latex}}, mark=at position 0.67 with {\arrow{latex}}}}},
box/.style={gray, thick, rounded corners}
]
\begin{scope}[xshift=5.5cm, yshift=2.5cm]
\node[anchor=east] at (-0.5, 0) {H-Path Sequence:};
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v2) at (2.5, 0) {2};
\node[vertex] (v3) at (5, 0) {3};
\draw[treeedge] (v1) -- (v2);
\draw[treeedge] (v2) -- (v3);
\end{scope}
\begin{scope}[xshift=0cm, yshift=0cm]
\draw[box] (-0.75, 1.35) rectangle (5.75, -1.35);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v2) at (2.5, 0) {2};
\node[vertex] (v3) at (5, 0) {3};
\draw[treeedge] (v1) -- (v2);
\draw[inactiveedge] (v2) -- (v3);
\draw[cycleedge] (v2) to[bend left=40] (v1);
\node at (2.5, -1.8) {\textbf{1. $C_{12}$}};
\end{scope}
\begin{scope}[xshift=7cm, yshift=0cm]
\draw[box] (-0.75, 1.35) rectangle (5.75, -1.35);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v2) at (2.5, 0) {2};
\node[vertex] (v3) at (5, 0) {3};
\draw[inactiveedge] (v1) -- (v2);
\draw[treeedge] (v2) -- (v3);
\draw[cycleedge] (v3) to[bend left=40] (v2);
\node at (2.5, -1.8) {\textbf{2. $C_{23}$}};
\end{scope}
\begin{scope}[xshift=0cm, yshift=-3.5cm]
\draw[box] (-0.75, 1.35) rectangle (5.75, -1.35);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v2) at (2.5, 0) {2};
\node[vertex] (v3) at (5, 0) {3};
\draw[treeedge] (v1) -- (v2);
\draw[treeedge] (v2) -- (v3);
\draw[cycleedge] (v3) to[bend left=30] (v1);
\node at (2.5, -1.8) {\textbf{3. $C_{123}$}};
\end{scope}
\begin{scope}[xshift=7cm, yshift=-3.5cm]
\draw[box] (-0.75, 1.35) rectangle (5.75, -1.35);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v2) at (2.5, 0) {2};
\node[vertex] (v3) at (5, 0) {3};
\draw[inactiveedge] (v1) -- (v2);
\draw[inactiveedge] (v2) -- (v3);
\draw[skipedge] (v1) to[bend left=40] (v3);
\draw[cycleedge] (v3) to[bend left=40] (v1);
\node at (2.5, -1.8) {\textbf{4. $C_{13}$}};
\end{scope}
\begin{scope}[xshift=13.5cm, yshift=-1.75cm, scale=0.9, transform shape]
\draw[treeedge] (0.2, 1.2) -- (1.2, 1.2);
\node[anchor=west, font=\small] at (1.2, 1.2) {Path subsegment};
\draw[inactiveedge] (0.2, 0.4) -- (1.2, 0.4);
\node[anchor=west, font=\small, text=black] at (1.2, 0.4) {Inactive edge};
\draw[skipedge] (0.2, -0.4) -- (1.2, -0.4);
\node[anchor=west, font=\small] at (1.2, -0.4) {Skip-edge};
\draw[cycleedge] (0.2, -1.2) -- (1.2, -1.2);
\node[anchor=west, font=\small, text=black] at (1.2, -1.2) {Back-edge};
\end{scope}
\end{tikzpicture}
}
\caption{Extracting the cycle basis from the H-path $1 \to 2 \to 3$. Each fundamental cycle is formed by closing a forward path (or skip-edge) with exactly one back-edge.}
\label{fig:permutation_basis}
\end{figure}
As in our revealed preference setting with a complete directed graph, there are exactly $n!$ distinct H-paths, and thus $n!$ such cycle bases that can be generated. For our 3-observation example, there are $3! = 6$ paths, yielding 6 cycle bases as follows:
\begin{align*}
l_1 (1\to 2\to 3): \mathcal{B}_{l_1} &= \{C_{1,2}, C_{2,3}, C_{1,2,3}, C_{1,3}\}, \\[0.85em]
l_2 (1\to 3\to 2): \mathcal{B}_{l_2} &= \{C_{1,3}, C_{3,2}, C_{1,3,2}, C_{1,2}\}, \\[0.85em]
l_3 (2\to 1\to 3): \mathcal{B}_{l_3} &= \{C_{2,1}, C_{1,3}, C_{1,3,2}, C_{2,3}\}, \\[0.85em]
l_4 (2\to 3\to 1): \mathcal{B}_{l_4} &= \{C_{2,3}, C_{3,1}, C_{1,2,3}, C_{2,1}\}, \\[0.85em]
l_5 (3\to 1\to 2): \mathcal{B}_{l_5} &= \{C_{3,1}, C_{1,2}, C_{1,2,3}, C_{3,2}\}, \\[0.85em]
l_6 (3\to 2\to 1): \mathcal{B}_{l_6} &= \{C_{3,2}, C_{2,1}, C_{1,3,2}, C_{3,1}\}.
\end{align*}
As a cycle basis spans the entire cycle space, any cycle not in the basis can be constructed through a linear combination of basis cycles. For example, Figure \ref{fig:linear_combination} illustrates how $C_{1,3,2}$ can be constructed using cycles strictly from $\mathcal{B}_{l_1}$ via the cycle formed from the linear combination $C_{1,3,2} = C_{1,3} + C_{1,2} + C_{2,3} - C_{1,2,3}$.\footnote{For 2-cycles, their ordering is unique up to cyclic permutation (i.e., interchangeable) meaning $C_{1,2} \equiv C_{2,1}$, $C_{1,3} \equiv C_{3,1}$, $C_{2,3} \equiv C_{3,2}$, and thus their associated MPIs are identical.}
\begin{figure}[ht]
\centering
\resizebox{\textwidth}{!}{\begin{tikzpicture}[
vertex/.style={circle, draw, minimum size=6mm, font=\normalsize},
edge/.style={->, thick, >=latex},
box/.style={draw, rounded corners, thick, draw=black!70}
]
\begin{scope}[xshift=0cm, yshift=0cm]
\draw[box] (-0.5, 0.7) rectangle (2.3, -2.0);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v3) at (1.8, 0) {3};
\node[vertex] (v2) at (0.9, -1.5) {2};
\draw[edge] (v1) to[bend left=15] (v3);
\draw[edge] (v3) to[bend left=15] (v1);
\node at (0.9, -2.5) {$C_{13}$};
\end{scope}
\node at (2.7, -0.75) {\Large $+$};
\begin{scope}[xshift=3.6cm, yshift=0cm]
\draw[box] (-0.5, 0.7) rectangle (2.3, -2.0);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v3) at (1.8, 0) {3};
\node[vertex] (v2) at (0.9, -1.5) {2};
\draw[edge] (v1) to[bend left=15] (v2);
\draw[edge] (v2) to[bend left=15] (v1);
\node at (0.9, -2.5) {$C_{12}$};
\end{scope}
\node at (6.3, -0.75) {\Large $+$};
\begin{scope}[xshift=7.2cm, yshift=0cm]
\draw[box] (-0.5, 0.7) rectangle (2.3, -2.0);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v3) at (1.8, 0) {3};
\node[vertex] (v2) at (0.9, -1.5) {2};
\draw[edge] (v2) to[bend left=15] (v3);
\draw[edge] (v3) to[bend left=15] (v2);
\node at (0.9, -2.5) {$C_{23}$};
\end{scope}
\node at (9.9, -0.75) {\Large $-$};
\begin{scope}[xshift=10.8cm, yshift=0cm]
\draw[box] (-0.5, 0.7) rectangle (2.3, -2.0);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v3) at (1.8, 0) {3};
\node[vertex] (v2) at (0.9, -1.5) {2};
\draw[edge] (v1) -- (v2);
\draw[edge] (v2) -- (v3);
\draw[edge] (v3) -- (v1);
\node at (0.9, -2.5) {$C_{123}$};
\end{scope}
\node at (13.5, -0.75) {\Large $=$};
\begin{scope}[xshift=14.4cm, yshift=0cm]
\draw[box] (-0.5, 0.7) rectangle (2.3, -2.0);
\node[vertex] (v1) at (0, 0) {1};
\node[vertex] (v3) at (1.8, 0) {3};
\node[vertex] (v2) at (0.9, -1.5) {2};
\draw[edge] (v1) -- (v3);
\draw[edge] (v3) -- (v2);
\draw[edge] (v2) -- (v1);
\node at (0.9, -2.5) {$C_{132}$};
\end{scope}
\end{tikzpicture}
}
\caption{Construction of the non-basis cycle $C_{1,3,2}$ using a linear combination of cycles from $\mathcal{B}_{l_1}$.}
\label{fig:linear_combination}
\end{figure}
To evaluate the total money pump cost of a given cycle basis, we aggregate the MPIs of its constituent cycles, assigning an MPI of 0 to any cycle that does not violate GARP. For each cycle basis, it might seem intuitive to take the arithmetic mean of the MPIs of the cycles in that cycle basis, and then aggregating again by taking the mean across all six cycle bases to arrive at a global measure for the MPI over the dataset. However, this is not quite the right approach as cycles of different lengths are oversampled at different rates. By simply counting the cycles across $l_1$ to $l_6$, we can see that there are eighteen 2-cycles and six 3-cycles. Specifically, there are three unique 2-cycles ($C_{1,2}, C_{1,3}, C_{2,3}$) that appear 6 times each, whereas the two unique 3-cycles ($C_{1,2,3}, C_{1,3,2}$) appear only 3 times each. We need to account for these frequencies when aggregating.
To achieve this, we must instead compute a weighted average where the MPI of a given cycle is weighted inversely by its frequency. For our 3-observation dataset, we weight the MPIs of 2-cycles by $1/6$ and 3-cycles by $1/3$. Recall that we previously identified exactly three valid GARP-violating cycles in this dataset ($C_{1,2}, C_{2,3}, C_{1,2,3}$) with MPI values of 0.15, 0.2, and 0.2 respectively. For any given basis $l_i$, we compute its frequency-adjusted sum of violating cycle costs $M(l_i)$, alongside a frequency-adjusted topological weight $W(l_i)$ (where non-violating cycles similarly contribute a weight of 0):
\begin{align*}
l_1: \quad M(l_1) &= \frac{0.15}{6} + \frac{0.2}{6} + \frac{0.2}{3}, \quad & W(l_1) &= \frac{1}{6} + \frac{1}{6} + \frac{1}{3}, \\[0.5em]
l_2: \quad M(l_2) &= \frac{0.2}{6} + \frac{0.15}{6}, \quad & W(l_2) &= \frac{1}{6} + \frac{1}{6}, \\[0.5em]
l_3: \quad M(l_3) &= \frac{0.15}{6} + \frac{0.2}{6}, \quad & W(l_3) &= \frac{1}{6} + \frac{1}{6}, \\[0.5em]
l_4: \quad M(l_4) &= \frac{0.2}{6} + \frac{0.2}{3} + \frac{0.15}{6}, \quad & W(l_4) &= \frac{1}{6} + \frac{1}{3} + \frac{1}{6}, \\[0.5em]
l_5: \quad M(l_5) &= \frac{0.15}{6} + \frac{0.2}{3} + \frac{0.2}{6}, \quad & W(l_5) &= \frac{1}{6} + \frac{1}{3} + \frac{1}{6}, \\[0.5em]
l_6: \quad M(l_6) &= \frac{0.2}{6} + \frac{0.15}{6}, \quad & W(l_6) &= \frac{1}{6} + \frac{1}{6}.
\end{align*}
To calculate what we refer to as the \textit{Basis Average MPI} for the dataset $\mathcal{D}$ ($\text{BA-MPI}_\mathcal{D}$), we sum these adjusted costs across the entire ensemble of bases and normalize by the sum of their weights:
\begin{equation*}
\text{BA-MPI}_\mathcal{D} = \frac{\sum_{i=1}^{6} M(l_i)}{\sum_{i=1}^{6} W(l_i)} = \frac{0.55}{3.0} = 0.1833.
\end{equation*}
This evaluates \textit{exactly} to the previously calculated $\text{OA-MPI}_{\mathcal{D}}$. Filtering out cycles that do not violate GARP and weighting GARP-violating cycles from the fundamental cycle bases by their appropriate frequencies across all bases allows us to recover the original mean MPI suggested by \citet{echenique2011money}.
\subsection{Basis Average MPI}
The logic from the previous example extends completely to arbitrary datasets, from which we can provide a highly tractable method for calculating the exact OA-MPI for any dataset.
First, to obtain the fundamental cycle basis from a generic H-path, we divide the available edges in the complete directed graph into the same two categories of \textit{forward-edges}, which jump ahead along the path sequence, and \textit{back-edges}, which jump backwards. Every cycle in our basis is formed by closing a forward path with exactly one back-edge. Cycles from contiguous subsegments of the H-path, say $v_i \to v_{i+1} \to \dots \to v_j$, are simply formed by taking the subsegment and closing the loop using a single back-edge from $v_j \to v_i$. This set of cycles extracts $n(n-1)/2$ basis cycles. Similarly, for the skip-edge 2-cycles, we take every forward skip-edge (e.g., $v_i \to v_j$ where $j \ge i+2$) and close the loop using the single back-edge $v_j \to v_i$. This extracts an additional $(n-1)(n-2)/2$ basis cycles. Thus, for each H-path we have a unique cycle basis with exactly $(n-1)^2$ distinct cycles.\footnote{As each class of cycles uniquely introduces a distinct set of non-tree edges (skip-edges and back-edges), the extracted cycles are strictly linearly independent. To see this, consider a boolean matrix where each row represents an extracted cycle and each column represents a non-tree edge in the graph, with a $1$ indicating that the edge is used in the cycle. If we order the columns such that forward skip-edges come first, followed by back-edges, and order the rows such that the 2-cycles come first, followed by the contiguous cycles, we get a block upper-triangular matrix with identity matrices on the diagonal. This triangular structure guarantees that the matrix has full rank, implying strictly linearly independent cycles within each basis.}
Given the fundamental cycle basis construction, we saw in the previous example the need to weight by the inverse of the exact frequencies of $j$-cycles, as shorter cycles are essentially oversampled relative to longer ones across the ensemble of bases. To formally derive these frequencies, let $\mathbb{I}(C \in \mathcal{B}_p)$ be an indicator function equal to $1$ if cycle $C$ is generated by path $p$. The total number of times $C$ is extracted across all $n!$ possible bases is $\sum_{p \in \mathcal{P}} \mathbb{I}(C \in \mathcal{B}_p)$. Given the way we construct the fundamental cycle bases, we can derive an exact formula for $\sum_{p \in \mathcal{P}} \mathbb{I}(C \in \mathcal{B}_p)$ which will depend only on the length of the cycle, and naturally the total number of nodes (observations) $n$. Denoting this frequency by $f(n,j)$, this can be determined via a straightforward counting argument.
Consider 2-cycles ($j=2$). Since there are $n!$ possible bases in total and every possible 2-cycle is extracted in every basis (as we take every possible pair of nodes and close the loop using a back-edge), the frequency of any 2-cycle is simply $f(n, 2) = n!$.
For cycles of length $j \ge 3$, our construction algorithm extracts a cycle if and only if its $j$ vertices appear consecutively in the H-path, forming a forward segment that is closed by a single back-edge. A specific $j$-cycle can be formed by $j$ distinct rotations of its vertices (e.g., a 3-cycle $A \to B \to C \to A$ can be formed by the sequence $A \to B \to C$, or $B \to C \to A$, or $C \to A \to B$). For any one of these $j$ specific sequences, we can treat those $j$ vertices as a single indivisible block. When constructing a path of length $n$, we are essentially placing this 1 block alongside the remaining $n-j$ individual vertices. For example, if $n=5$ and we are placing the specific sequence $[A \to B \to C]$, we are ordering $1$ block and $2$ remaining vertices (say, $D$ and $E$). This gives us a total of $n-j+1$ discrete objects to order (the block $[A \to B \to C]$, $D$, and $E$). Since the remaining $n-j$ vertices can be arranged in $(n-j)!$ ways, exactly $(n-j+1) \times (n-j)! = (n-j+1)!$ paths will contain this specific sequence. Summing over all $j$ possible rotations yields $f(n, j) = j(n-j+1)! \text{ for } j \ge 3$.
Given these frequencies, for any generic basis $\mathcal{B}_p$ generated by an H-path $p \in \mathcal{P}$, let $V(\mathcal{B}_p)$ denote the set of strictly GARP-violating cycles within that basis. Generalizing from the example, we define the frequency-adjusted sum of the violating cycle costs $M(p)$, and the corresponding frequency-adjusted weight $W(p)$, as:
\begin{equation*}
M(p) = \sum_{C \in V(\mathcal{B}_p)} \frac{\text{MPI}(C)}{f(n, |C|)}, \quad W(p) = \sum_{C \in V(\mathcal{B}_p)} \frac{1}{f(n, |C|)}.
\end{equation*}
We can now define the BA-MPI for a generic dataset $D$ as:
\begin{equation*}
\text{BA-MPI}_D = \frac{ \sum_{p \in \mathcal{P}} M(p) }{ \sum_{p \in \mathcal{P}} W(p) }.
\end{equation*}
This allows us to state the following equivalence:
\begin{theorem} \label{thm:ba_equiv}
For any dataset $D$, $\text{BA-MPI}_{D} = \text{OA-MPI}_{D}$.
\end{theorem}
Theorem \ref{thm:ba_equiv} formally establishes that estimating the BA-MPI is identical to estimating the OA-MPI, using all possible H-paths, instead of requiring the enumeration of the entire cycle space.
Directly enumerating all cycles to compute the exact OA-MPI is extremely costly, requiring $\mathcal{O}(n!)$ time to evaluate with \citet{smeulders2013note} proving that calculating the OA-MPI is an NP-hard problem. As Theorem \ref{thm:ba_equiv} establishes that the exact BA-MPI and exact OA-MPI yield identical values for any input dataset, computing the exact BA-MPI is also NP-hard. In fact, directly evaluating the BA-MPI over all $n!$ paths is asymptotically worse, taking $\mathcal{O}(n^2 n!)$ operations, since we must extract and evaluate the cycle basis for each H-path. This leads us to a natural estimator of the BA-MPI.
\textbf{BA-MPI Estimator:} Despite Theorem 1 guaranteeing an exact equivalence between the BA-MPI and the OA-MPI, computing all $n!$ paths remains intractable (e.g., a 30-observation dataset yields $30! \approx 2.65 \times 10^{32}$ paths). However, the BA-MPI has essentially transformed a combinatorial graph problem into a statistical problem, allowing us to use a random sample from the $n!$ H-paths as an estimator for the true BA-MPI, and thus the OA-MPI.
I define the \textit{BA-MPI Estimator} ($\text{BA-MPI}_{D,K}$) as the sample ratio estimator. To compute this, we sample $K$ H-paths (sampled with replacement) to generate a random sample of $K$ cycle bases, denoted by $\mathcal{S}_K$. With weights $w(C) = 1/f(n, |C|)$, we use these bases in the summations for the numerator and denominator:
\begin{equation*}
\text{BA-MPI}_{D,K} = \frac{ \frac{1}{K} \sum_{\mathcal{B} \in \mathcal{S}_K} \sum_{C \in V(\mathcal{B})} w(C) \text{MPI}(C) }{ \frac{1}{K} \sum_{\mathcal{B} \in \mathcal{S}_K} \sum_{C \in V(\mathcal{B})} w(C) },
\end{equation*}
allowing us to state the following proposition:
\begin{proposition} \label{prop:mean_MPI}
The BA-MPI estimator ($\text{BA-MPI}_{D,K}$) is a consistent estimator of the OA-MPI ($\text{OA-MPI}_{D}$) as the number of sampled paths $K \to \infty$.
\end{proposition}
If we consider $\text{BA-MPI}_{D}$ as an estimand which is equivalent to $\text{OA-MPI}_{D}$ by Theorem \ref{thm:ba_equiv}, it is easy to see that Proposition \ref{prop:mean_MPI} holds using the Strong Law of Large Numbers and the Continuous Mapping Theorem.
Crucially, the BA-MPI estimator overcomes the $\mathcal{O}(n!)$ complexity by drawing a finite sample of $K$ H-paths. For each sampled path $v_1 \to v_2 \to \dots \to v_n$, we can pre-compute cumulative edge costs (prefix sums) along the path in $\mathcal{O}(n)$ time. The total cost of any contiguous subsegment $v_i \to \dots \to v_j$ is then obtained in $\mathcal{O}(1)$ time by differencing these cumulative sums, and adding the back-edge cost $X_{v_j, v_i}$ takes $\mathcal{O}(1)$. As each basis contains $(n-1)^2$ cycles, evaluating all cycles in the basis requires only $\mathcal{O}(n^2)$ operations. With complexity of drawing a random path permutation being only $\mathcal{O}(n)$, each sampled basis is processed in $\mathcal{O}(n^2)$ time. Thus, by choosing $K \ll n!$, the total computational complexity to evaluate $K$ randomly sampled bases is strictly polynomial at $\mathcal{O}(K n^2)$, providing an efficient, consistent estimator for the OA-MPI, whose direct computation is fundamentally NP-hard.
Before proceeding, we discuss why sampling H-paths to extract cycle bases is vastly superior to drawing individual cycles at random to compute a Monte Carlo estimator. In principle, one could estimate the mean MPI by uniformly sampling cycles directly from the graph. This, however, is typically intractable because it implicitly requires counting/enumerating the total number of cycles.\footnote{Specifically, counting or uniformly sampling simple cycles in a directed graph without enumerating the entire cycle space is a \#P-complete problem \citep[Section 4, Problem 14]{valiant1979complexity}.} Alternatively, sampling from the complete cycle space and applying rejection sampling is computationally unviable, as the proportion of violating cycles is typically tiny relative to the size of the cycle space. In contrast, drawing an H-path uniformly at random is computationally trivial. By sampling paths instead of individual cycles, we circumvent these sampling bottlenecks, rapidly generating structured batches of $(n-1)^2$ cycles with exactly known selection probabilities.
While Proposition \ref{prop:mean_MPI} establishes consistency, as a ratio estimator, clearly the BA-MPI estimator will exhibit some form of finite-sample bias.\footnote{In the sense that the expectation of a ratio is, in general, not equal to the ratio of the expectations.} In the following proposition, we establish an upper bound on this bias. Let $\mu_M = \mathbb{E}[M(p)]$ and $\mu_W = \mathbb{E}[W(p)]$ denote the true population expectations of the basis sum and basis weight, respectively, with $\sigma_M^2 = \text{Var}[M(p)]$ and $\sigma_W^2 = \text{Var}[W(p)]$ denoting their respective population variances.
\begin{proposition} \label{prop:mean_bias}
Let $W_{\min} = \min_{p \in \mathcal{P}} W(p) > 0$ denote the population minimum basis weight in dataset $D$.\footnote{A strictly positive minimum basis weight $W_{\min} > 0$ is guaranteed whenever the dataset contains at least one 2-cycle violation, as every 2-cycle is extracted in the basis of every H-path. In typical revealed preference datasets, 2-cycle violations are ubiquitous (holding for 100\% of the violating households in our empirical application). If a dataset were to contain only higher-order cycles ($j \ge 3$), one can alternatively condition sampling on bases with non-empty violating cycle sets.} The absolute finite-sample bias of the BA-MPI estimator is bounded such that:
\begin{equation*}
\left| \mathbb{E}[\text{BA-MPI}_{D,K}] - \frac{\mu_M}{\mu_W} \right| \le \min\left( 1, \; \frac{1}{K} \left[ \frac{\mu_W \sigma_M \sigma_W + \mu_M \sigma_W^2}{\mu_W^2 W_{\min}} \right] \right).
\end{equation*}
\end{proposition}
Naturally, this upper bound on the bias shrinks proportionally to the reciprocal of the number of draws, $K$. As an analytical upper bound without distributional assumptions, it is typicaly conservative; in practice, to compute this bound, we use the sample analogues of the population parameters to evaluate the finite-sample bias.
\subsection{Basis Percentile MPI}
Analogously, we can also compute the median MPI of a dataset, or indeed, any arbitrary $\alpha$-percentile. We refer to this as the \textit{Basis $\alpha$-Percentile MPI} ($\text{BP}_\alpha\text{-MPI}_D$). The $\alpha$-percentile MPI originally proposed by \citet{echenique2011money} is denoted by $\text{OP}_\alpha\text{-MPI}_D$ (Original $\alpha$-Percentile MPI).
Recall from our previous example of a 3-observation dataset $\mathcal{D}$, the global set of strictly violating cycles contained exactly three elements with MPIs of 0.15, 0.2, and 0.2. The $\text{OP}_{50}\text{-MPI}_\mathcal{D}$ is simply the median of 0.15, 0.2, and 0.2, which is $0.20$. Naturally, this extends to any arbitrary $\alpha$-percentile. For instance, the $\text{OP}_{25}\text{-MPI}_\mathcal{D}$ is $0.15$.\footnote{As the $\alpha$-percentile is formally defined as the smallest value where the CDF reaches or exceeds $\alpha$, the 25th percentile is $0.15$.}
Formally, for any global set of strictly violating cycles $V$, we define the `original' cumulative distribution function ($\text{O-CDF}_D$) as the exact proportion of all cycles with an MPI less than or equal to $x$:
\begin{equation*}
\text{O-CDF}_D(x) = \frac{1}{|V|} \sum_{C \in V} \mathbb{I}(\text{MPI}(C) \le x).
\end{equation*}
The $\text{OP}_\alpha\text{-MPI}_D$ is the smallest value $M_\alpha$ such that $\text{O-CDF}_D(M_\alpha) \ge \alpha$.
To find the equivalent CDF using the fundamental cycle bases, we use a weighted and renormalized CDF, denoted $\text{B-CDF}_D(x)$. For every path $p \in \mathcal{P}$, let $V(\mathcal{B}_p)$ denote the set of strictly violating cycles extracted from its corresponding fundamental cycle basis $\mathcal{B}_p$. With the same weights, $w(C) = 1/f(n, |C|)$, the $\text{B-CDF}_D(x)$ over all paths is given by:
\begin{equation*}
\text{B-CDF}_D(x) = \frac{ \sum_{p \in \mathcal{P}} \sum_{C \in V(\mathcal{B}_p)} w(C) \mathbb{I}(\text{MPI}(C) \le x) }{ \sum_{p \in \mathcal{P}} \sum_{C \in V(\mathcal{B}_p)} w(C) }.
\end{equation*}
The $\text{OP}_\alpha\text{-MPI}_D$ is then calculated from the $\text{O-CDF}_D$, and the $\text{BP}_\alpha\text{-MPI}_D$ is defined as the specific MPI value $M_\alpha$ where $\text{B-CDF}_D(M_\alpha) \ge \alpha$.
Continuing our three-observation example, the cycle weights are $w(C_{1,2}) = 1/6$, $w(C_{2,3}) = 1/6$, and $w(C_{1,2,3}) = 1/3$. As in the $\text{BA-MPI}_\mathcal{D}$ calculation, the denominator of $\text{B-CDF}_\mathcal{D}(x)$ is $3$. At $x = 0.15$, only $C_{1,2}$ contributes mass across all paths, yielding:
\begin{equation*}
\text{B-CDF}_\mathcal{D}(0.15) = \frac{6(1/6)}{3} = \frac{1}{3}.
\end{equation*}
At $x = 0.2$, the remaining two cycles contribute, causing the CDF to jump to:
\begin{equation*}
\text{B-CDF}_\mathcal{D}(0.2) = \frac{6(1/6) + 6(1/6) + 3(1/3)}{3} = \frac{3}{3} = 1.
\end{equation*}
Thus, to find the $\text{BP}_{50}\text{-MPI}_\mathcal{D}$, we see that the value where the $\text{B-CDF}_\mathcal{D}$ first reaches or exceeds $0.50$ is exactly $0.20$, matching the $\text{OP}_{50}\text{-MPI}_\mathcal{D}$ value. Similarly, for the 25th percentile, the $\text{B-CDF}_\mathcal{D}$ reaches or exceeds $0.25$ at the exact point $x = 0.15$, again mirroring $\text{OP}_{25}\text{-MPI}_\mathcal{D}$.
We can now state an equivalent to Theorem \ref{thm:ba_equiv} for the $\text{BP}_\alpha\text{-MPI}_D$.
\begin{theorem} \label{thm:bp_equiv}
For any dataset $D$ and any $\alpha \in (0, 1]$, $\text{BP}_\alpha\text{-MPI}_D = \text{OP}_\alpha\text{-MPI}_D$.
\end{theorem}
In practice, to compute this exact percentile without enumerating all $n!$ cycles, we use the same random sample of $K$ cycle bases, $\mathcal{S}_K$. The estimator for the $\text{B-CDF}_D(x)$ is given by:
\begin{equation*}
\text{B-CDF}_{D,K}(x) = \frac{\sum_{\mathcal{B} \in \mathcal{S}_K} \sum_{C \in V(\mathcal{B})} w(C) \mathbb{I}(\text{MPI}(C) \le x) }{ \sum_{\mathcal{B} \in \mathcal{S}_K} \sum_{C \in V(\mathcal{B})} w(C) }.
\end{equation*}
By explicitly tracking this percentile across the sampled cycle bases, we get precise approximations of the true percentiles. The following propositions make this explicit in terms of consistency, and the exponential decay of the bias.
\begin{proposition} \label{prop:percentile_MPI}
The Basis $\alpha$-Percentile estimator ($\text{BP}_\alpha\text{-MPI}_{D,K}$) is a consistent estimator of the Original $\alpha$-Percentile MPI ($\text{OP}_\alpha\text{-MPI}_{D}$) as the number of sampled paths $K \to \infty$.
\end{proposition}
As the set of possible cycle MPIs in any finite dataset is discrete, let $\delta > 0$ be the vertical margin isolating the true percentile $M_\alpha$ on the step-function CDF:
\begin{equation*}
\delta = \min \left( \alpha - \max_{x < M_\alpha} \text{B-CDF}_D(x), \; \text{B-CDF}_D(M_\alpha) - \alpha \right) > 0,
\end{equation*}
where the first term represents the lower margin bounding the CDF prior to $M_\alpha$, and the second term represents the upper margin ensuring the threshold has crossed $M_\alpha$ (illustrated in Figure \ref{fig:delta_gap}). Any estimation error strictly smaller than $\delta$ guarantees that the empirical step function intersects the horizontal threshold $\alpha$ exclusively at the true percentile $M_\alpha$.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=1.5,
cdf/.style={thick, blue},
emp/.style={thick, dashed, red},
guide/.style={dotted, gray},
point/.style={circle, fill=blue, inner sep=1.5pt},
hollow/.style={circle, draw=blue, fill=white, inner sep=1.5pt, thick}
]
\draw[->] (-0.5,0) -- (5.5,0) node[right] {$x$};
\draw[->] (0,-0.2) -- (0,2.8) node[above] {CDF};
\draw[thick, gray, dashed] (0, 1.6) -- (5.5, 1.6);
\node[left, font=\bfseries] at (0, 1.6) {$\alpha$};
\draw[cdf] (-0.5, 0) -- (1, 0);
\node[hollow] at (1, 0) {};
\draw[cdf] (1, 1.0) -- (2.5, 1.0);
\node[point] at (1, 1.0) {};
\node[hollow] at (2.5, 1.0) {};
\draw[cdf] (2.5, 2.0) -- (4, 2.0);
\node[point] at (2.5, 2.0) {};
\node[hollow] at (4, 2.0) {};
\draw[cdf] (4, 2.3) -- (5.3, 2.3);
\node[point] at (4, 2.3) {};
\draw[guide] (2.5, 0) -- (2.5, 2.0);
\node[below, font=\bfseries] at (2.5, 0) {$M_\alpha$};
\draw (-0.05, 1.0) -- (0.05, 1.0);
\node[left] at (0, 1.0) {$\max_{x < M_\alpha} \text{B-CDF}_D(x)$};
\draw (-0.05, 2.0) -- (0.05, 2.0);
\node[left] at (0, 2.0) {$\text{B-CDF}_D(M_\alpha)$};
\draw[<->, thick, purple] (2.7, 1.0) -- (2.7, 1.6) node[midway, right] {Gap 1};
\draw[<->, thick, purple] (2.7, 1.6) -- (2.7, 2.0) node[midway, right] {Gap 2};
\node[left, purple] at (5.3, 0.4) {$\delta = \min(\text{Gap 1}, \text{Gap 2})$};
\end{tikzpicture}
\caption{Visualization of $\delta$. Gap 1 represents $\alpha - \max_{x < M_\alpha} \text{B-CDF}_D(x)$, and Gap 2 represents $\text{B-CDF}_D(M_\alpha) - \alpha$.}
\label{fig:delta_gap}
\end{figure}
\begin{proposition} \label{prop:percentile_bias}
Let $M_\alpha$ be the true $\alpha$-percentile, and let $\delta > 0$ be the strictly positive gap isolating $M_\alpha$ defined above. The absolute finite-sample bias of the Basis $\alpha$-Percentile estimator is bounded such that:
\begin{equation*}
\left| \mathbb{E}[\text{BP}_\alpha\text{-MPI}_{D,K}] - M_\alpha \right| \le \min\left( 1, \; 4 \exp\left( - \frac{2 K \delta^2 W_{\min}^2}{W_{\max}^2} \right) \right),
\end{equation*}
where $W_{\max} = \max_{p \in \mathcal{P}} W(p)$ and $W_{\min} = \min_{p \in \mathcal{P}} W(p) > 0$.
\end{proposition}
As the true population of cycle MPIs is discrete, the strictly positive vertical gap $\delta$ isolates the true percentile $M_\alpha$. Bias in our estimate for the percentile arises when the empirical CDF deviates from the true CDF by $\delta$ or more at critical points, causing the approximated CDF to cross the $\alpha$ threshold at the wrong step. The theoretical bound in Proposition \ref{prop:percentile_bias} provides a distribution-free worst-case guarantee that decays exponentially as the sample size $K$ grows. As it is a distribution-free bound evaluated over the extreme weights $W_{\min}$ and $W_{\max}$, it is conservative in finite samples.
Like the exact OA-MPI, computing any $\text{OP}_\alpha\text{-MPI}_D$ directly is an NP-hard problem \citep{smeulders2013note}. We overcome this computational issue using the consistent estimator for the B-CDF, which allows us to construct the empirical CDF in polynomial time $\mathcal{O}(K n^2)$.
\section{Empirical Application} \label{sec:empirical}
To validate our estimators in practice, I replicate the empirical analysis of \citet{smeulders2013note} alongside estimates of the mean and median MPI using the Stanford Basket Dataset. The dataset tracks the grocery purchases of 494 households over 26 weeks across 375 distinct goods. 396 households strictly violate GARP. For each GARP-violating household, I compute: (i) the minimum and maximum MPI bounds of \citet{smeulders2013note}; (ii) the approximated average and median MPI (by focusing on cycles of lengths 2, 3, and 4) of \citet{echenique2011money}; and (iii) the basis average and median MPI estimators ($\text{BA-MPI}_{D,K}$ and $\text{BP}_{50}\text{-MPI}_{D,K}$). I also compute the upper bounds on the finite-sample bias of these estimators from Proposition \ref{prop:mean_bias} and Proposition \ref{prop:percentile_bias} replacing population parameters with sample analogues. Additionally, recognizing that these analytical bounds are conservative worst-case scenarios, I quantify finite-sample bias using non-parametric bootstrap by drawing 1,000 bootstrap resamples (with replacement) from the set of sampled H-paths.\footnote{The estimation halts once the running estimator stabilizes (i.e., changes by less than $10^{-3}$ over 200 consecutive evaluations). To prevent premature termination, I enforce a mandatory ``burn-in'' phase of 1,000 evaluations where the convergence criterion is disabled. The absolute maximum limit is set to 5,000 evaluations, but across the entire estimation exercise, convergence occurs much earlier, taking an average of only 1,227 iterations per household.}
Table \ref{tab:mpi_stats} reports the descriptive statistics of these indices across all 396 GARP-violating households. Typically, revealed preference violations are heavily concentrated in shorter cycles (predominantly 2-cycles and 3-cycles). As shorter cycles dominate the total count of violations, the approximated mean MPI of \citet{echenique2011money} (which truncates at $k \le 4$) aligns closely with the Basis Average MPI ($0.0610$ vs $0.0609$), as also shown in Figure \ref{fig:cdf_plots} (left). However, the median MPIs exhibit meaningful differences: the Basis Median MPI reports noticeably lower values than the approximated median ($0.0557$ vs $0.0592$ in Table \ref{tab:mpi_stats}; $0.0471$ vs $0.0497$ for the household-level median; see Figure \ref{fig:cdf_plots}, right). This indicates that the Basis MPI captures longer, higher-order cycles that have lower money pump intensities. While these larger cycles do not substantially shift the overall expenditure-weighted average, they shift the percentile distribution. Thus, the estimator avoids the upward distortion in median severity induced by heuristics that rely on shorter cycles. Visually, the basis mean MPI fits symmetrically between the minimum and maximum bounds, providing further support to the observation of \citet{smeulders2013note} that those bounds are informative for the mean MPI, although less so for the median MPI.
\begin{table}[ht]
\centering
\footnotesize
\setlength{\tabcolsep}{4.5pt}
\caption{Descriptive Statistics of Money Pump Indices across GARP-violating Households ($n=396$)}
\label{tab:mpi_stats}
\vspace{0.5em}
\begin{tabular}{l c c c c c c c}
\toprule
& \multicolumn{3}{c}{\textbf{Min/Max MPI}} & \multicolumn{2}{c}{\textbf{Approximate MPI}} & \multicolumn{2}{c}{\textbf{Basis MPI}} \\
\cmidrule(lr){2-4} \cmidrule(lr){5-6} \cmidrule(lr){7-8}
\textbf{Statistic} & Min & Max & Range & Average & Median & Average & Median \\
\midrule
Average & 0.0341 & 0.0936 & 0.0595 & 0.0610 & 0.0592 & 0.0611 & 0.0551 \\
Standard deviation & 0.0288 & 0.0616 & 0.0604 & 0.0358 & 0.0369 & 0.0363 & 0.0360 \\
Number of zeros & - & - & 75 & - & - & - & - \\
Minimum & 0.0002 & 0.0048 & 0.0000 & 0.0048 & 0.0048 & 0.0048 & 0.0002 \\
First quartile & 0.0154 & 0.0489 & 0.0116 & 0.0356 & 0.0326 & 0.0356 & 0.0301 \\
Median & 0.0268 & 0.0797 & 0.0443 & 0.0551 & 0.0497 & 0.0551 & 0.0457 \\
Third quartile & 0.0425 & 0.1274 & 0.0863 & 0.0809 & 0.0789 & 0.0805 & 0.0738 \\
Maximum & 0.2782 & 0.4010 & 0.3350 & 0.2782 & 0.2782 & 0.2782 & 0.2782 \\
\bottomrule
\end{tabular}
\vspace{0.4em}
\begin{minipage}{0.95\textwidth}
\scriptsize
\textbf{Notes:} This table reports descriptive statistics of the Money Pump Index (MPI) across all 396 households that violate GARP in the Stanford Basket Dataset ($T=26$). \textit{Min/Max MPI} bounds are computed using the polynomial-time algorithm of \citet{smeulders2013note}; \textit{Range} is the difference between Max and Min. \textit{Approximate MPI} follows \citet{echenique2011money} by enumerating all cycles up to length $k=4$. \textit{Basis MPI} reports the Basis Average ($\text{BA-MPI}_{D,K}$) and Basis Median ($\text{BP}_{50}\text{-MPI}_{D,K}$) estimators proposed in this paper, computed via randomly sampled H-path cycle bases ($K \approx 1,227$ iterations per household). For 75 households, the Min and Max bounds coincide (Range = 0), representing the exact true mean MPI.
\end{minipage}
\end{table}
\begin{figure}[ht]
\centering
\includegraphics[width=0.48\textwidth]{tables_figures/cdf_plot.pdf} \hfill
\includegraphics[width=0.48\textwidth]{tables_figures/cdf_plot_median.pdf}
\caption{Empirical Cumulative Distribution Functions of Mean (left) and Median (right) Money Pump Indices across GARP-violating Households ($n=396$). The left panel compares the Min/Max bounds of \citet{smeulders2013note}, the approximate mean MPI ($k \le 4$) of \citet{echenique2011money}, and the proposed Basis Mean MPI ($\text{BA-MPI}_{D,K}$). The right panel compares the approximate median MPI and Basis Median MPI ($\text{BP}_{50}\text{-MPI}_{D,K}$).}
\label{fig:cdf_plots}
\end{figure}
Table \ref{tab:bias_bounds} reports the finite-sample empirical bias and theoretical bounds of the basis estimators across all households. For the mean MPI, the theoretical upper bounds on bias are tight for the vast majority of households (median $0.0008$). In contrast, the theoretical upper bound on the median MPI bias is conservative (median $3.9983$, bounded by $1.0000$), reflecting that it is a distribution-free worst-case guarantee whose analytical bound becomes conservative when basis weights exhibit wide dispersion. From Figure \ref{fig:bias_bounds_hist}, the non-parametric bootstrap empirical bias provides the operational verification: both the average bias for the mean MPI ($0.0001$) and the median MPI ($0.0037$) are tightly clustered around zero. This demonstrates that in practice, the basis estimators achieve near-zero finite-sample bias with modest draws.\footnote{In terms of computational performance, the comparison was run on a computer with an Apple M5 processor and 32GB RAM. Calculating the Min/Max bounds, the approximated MPI, and the Basis MPI (excluding bootstrap) took 30.5 seconds, 48.1 seconds, and 208.8 seconds respectively in native R. Using the \texttt{Rcpp} package to integrate R and C++, the times dropped to 0.07 seconds, 0.64 seconds, and 37.6 seconds. The performance improvements in the C++ implementations over base R come from porting the core algorithms to an environment which is optimized for intensive looping and memory management.}
\begin{table}[ht]
\centering
\footnotesize
\setlength{\tabcolsep}{10pt}
\caption{Finite-Sample Bias and Theoretical Bounds of Basis MPI Estimators}
\label{tab:bias_bounds}
\vspace{0.5em}
\begin{tabular}{l c c c c}
\toprule
& \multicolumn{2}{c}{\textbf{Empirical Bias}} & \multicolumn{2}{c}{\textbf{Theoretical Bounds}} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-5}
\textbf{Statistic} & Average & Median & Average & Median \\
\midrule
Average & 0.0001 & 0.0039 & 0.0262 & 2.3844 \\
Standard deviation & 0.0005 & 0.0141 & 0.2542 & 1.9635 \\
Number of zeros & 250 & 204 & 161 & 74 \\
Minimum & -0.0023 & -0.0271 & 0.0000 & 0.0000 \\
First quartile & -0.0000 & -0.0000 & 0.0000 & 0.0005 \\
Median & 0.0000 & 0.0000 & 0.0008 & 3.9983 \\
Third quartile & 0.0001 & 0.0030 & 0.0033 & 3.9994 \\
Maximum & 0.0053 & 0.1571 & 4.7621 & 4.0000 \\
\bottomrule
\end{tabular}
\vspace{0.4em}
\begin{minipage}{0.92\textwidth}
\scriptsize
\textbf{Notes:} This table reports summary statistics of the finite-sample empirical bias and analytical theoretical bounds of the Basis Average and Basis Median MPI estimators across all 396 GARP-violating households. \textit{Empirical Bias} is evaluated via non-parametric bootstrap drawing 1,000 resamples (with replacement) from the sampled H-path cycle bases. \textit{Theoretical Bounds} report the analytical upper bounds from Proposition \ref{prop:mean_bias} (Average) and Proposition \ref{prop:percentile_bias} (Median), calculated using sample analogues of population moments.
\end{minipage}
\end{table}
\begin{figure}[ht]
\centering
\includegraphics[width=1\textwidth]{tables_figures/bias_bounds_hist.pdf}
\caption{Histograms of Finite-Sample Empirical Bias and Analytical Theoretical Bounds across all 396 GARP-violating Households. The top row displays the empirical bias evaluated via 1,000 bootstrap resamples for the Basis Average (left) and Basis Median (right) MPI estimators. The bottom row displays the corresponding analytical finite-sample upper bounds from Proposition \ref{prop:mean_bias} (left) and Proposition \ref{prop:percentile_bias} (right).}
\label{fig:bias_bounds_hist}
\end{figure}
For 75 households, the minimum and maximum MPI bounds coincide; hence, this bound is their exact $\text{OA-MPI}_D$ \citep{smeulders2013note}. When computing the basis estimators for these 75 households, the results are identical to the exact MPI to within $10^{-6}$, providing direct empirical validation of our estimator against the true MPI values.
\section{Conclusion} \label{sec:conclusion}
This paper proposes a computationally tractable approach to calculate the mean and median Money Pump Index (MPI) of \citet{echenique2011money}. Without relying on shorter cycle approximations or min-max bounds to avoid NP-hard complexity issues, this approach conceptualizes choice violations as a directed graph. The violations are then projected onto the graph's fundamental cycle bases through the random sampling of Hamiltonian paths from which the bases are derived. Theoretical results establish that these estimators are consistent and computable in polynomial time. When applied to the Stanford Basket Dataset, it is shown that any finite-sample bias is negligible. Additionally, the basis mean MPI is in strong agreement with the OA-MPI, confirming that longer cycles do not contribute as much as shorter cycles, although they do have some effect on the median MPI. Finally, where the minimum and maximum MPI bounds are the same, the basis estimators also coincide. By reducing the computational burden, this methodology allows us to accurately estimate the true MPI tractably.
\clearpage