Tractable Estimation of the Money Pump Index

summary

The gist

The Money Pump Index (MPI) of Echenique et al.

In short

The Money Pump Index (MPI) measures consumer irrationality but calculating its exact mean and median across all possible preference cycles is NP-hard. This work proposes a tractable solution by framing choice violations as directed graphs and projecting them onto fundamental cycle bases. This yields polynomial-time estimators that are asymptotically equivalent to the original MPI.

Key concepts

Money Pump Index (MPI)
The MPI quantifies consumer irrationality by measuring the arbitrageur's total money pump profit relative to a consumer's total expenditure within a preference cycle. A high MPI suggests significant violations of rational choice behavior.
Directed Graph Formulation
Revealed preferences are modeled as a directed graph where observations are nodes and revealed preference relations are directed edges. This structure allows complex cycles of choices to be represented geometrically, making the problem amenable to graph-based analysis.
Fundamental Cycle Basis
This is a minimal, linearly independent set of cycles that spans the entire cycle space of the choice graph. Instead of checking every possible cycle (which is too many), this basis allows researchers to aggregate metrics over a representative, manageable set of cycles.
Basis Average MPI (BA-MPI)
This is an equivalent formulation for the true mean MPI calculated by aggregating frequency-adjusted costs across all fundamental cycle bases. It replaces the computationally impossible task of enumerating every cycle with a tractable sum over these basis sets.

Terminology used across episodes

This episode discusses

The paper

Tractable Estimation of the Money Pump Index · Read on arXiv

The Money Pump Index (MPI) of Echenique et al. (2011) measures the severity of consumer irrationality, but computing the exact mean and median MPI over all revealed preference cycles is NP-hard (Smeulders et al., 2013). 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 Echenique et al. (2011) and Smeulders et al., (2013), the proposed estimators compute quickly and with negligible small-sample bias.

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: We're looking at the paper: "Tractable Estimation of the Money Pump Index".

Warren: Here's the gist of the paper. The Money Pump Index (MPI) of Echenique et al.

Ruth: (2011) measures the severity of consumer irrationality, but computing the exact mean and median MPI over all revealed preference cycles is NP-hard The paper proposes a computationally tractable approach to calculate the mean and median Money Pump Index (MPI) of Echenique et al.

Warren: (2011) by framing choice violations as directed graphs and projecting them onto fundamental cycle bases This methodology yields polynomial-time estimators that are asymptotically equivalent to the original MPI Tractability through Graph Theory The authors overcome the NP-hard scaling associated with enumerating all cycles by reformulating revealed preferences as a directed graph where observations are nodes and revealed preference relations are directed edges They propose projecting choice violations onto the graph’s fundamental cycle basis—a minimal, linearly independent set of cycles that spans the entire cycle space of the graph This yields computationally tractable estimators for the mean and median MPI that are asymptotically equivalent to the original MPI The Basis Average MPI is introduced as an equivalent formulation of the true mean MPI that aggregates over the graph’s fundamental cycle bases rather than enumerating all individual cycles Derivation of Cycle Metrics The Money Pump Index (MPI) measures the arbitrageur’s total money pump profit relative to the consumer’s total expenditure within a preference cycle C, defined as MPID(C) = Pm i=1 pki · (xki − xki+1) / Pm i=1 pki · xki For the normalized dataset D˜, the money pump cost associated with observations is given by Xki,kj = 1−p˜ki · xkj The MPI for a cycle C on the normalized dataset is reformulated as MPID˜ (C) = 1/C Sum i=1 Xki,ki+1 Basis Construction and Aggregation The fundamental cycle basis is constructed using a directed Hamiltonian path (H-path), where cycles are formed by closing a forward path or skip-edge with exactly one back-edge The total number of distinct H-paths is n!, yielding n!

Ruth: such cycle bases that can be generated To aggregate the MPIs, a frequency-adjusted sum M(p) and weight W(p) are computed for each basis p, where M(p) = Sum X C∈V (Bp) MPI(C)/f(n, C) The Basis Average MPI is then calculated as BA-MPID = Sum p∈P M(p) / Sum p∈P W(p) Consistency and Empirical Validation The BA-MPI estimator (BA-MPID,K) is a consistent estimator of the OA-MPI as the number of sampled paths K → ∞ The absolute finite-sample bias is bounded such that E

BPα-MPID,K: − Mα ≤ min 1, 4 exp − 2Kδ2W2min/Wmax Empirical application on the Stanford Basket Dataset shows that the Basis Mean MPI is in strong agreement with the OA-MPI The empirical bias for both mean and median MPI estimators is tightly clustered around zero, demonstrating near-zero finite-sample bias Percentile Estimation The Basis Percentile MPI (BPα-MPID) is defined by comparing the weighted and renormalized cumulative distribution function B-CDFD(x) to the original O-CDFD(x) The estimator BPα-MPID,K is a consistent estimator of the Original α-Percentile MPI (OPα-MPID) as K → ∞ The absolute finite-sample bias of the Basis α-Percentile estimator is bounded such that E

BPα-MPID,K: − Mα ≤ min 1, 4 exp − 2Kδ2W2min/Wmax Lemma on Metric Distortion Lemma 1 states that the maximum absolute difference between the MPI(C) calculated on D versus D˜ never exceeds Xmax · √r−1/√r+1 This bound is empirically verified, showing that the actual empirical distortion MPID − MPID˜ is even smaller than the conservative theoretical bound This approach allows us to accurately estimate the true MPI tractably by reducing the computational burden from O(n!) to a polynomial time complexity of O(Kn2) The methodology successfully avoids imposing arbitrary cycle length restrictions and provides an efficient, consistent estimator for the OA-MPI It confirms that longer cycles do not contribute as much as shorter cycles to the overall expenditure-weighted average, although they do have some effect on the median MPI The method effectively transforms a combinatorial graph problem into a statistical problem using random sampling of H-paths References Afriat, S.

Title and authors: Ruth: The title of this paper is "Tractable Estimation of the Money Pump Index," which immediately tells you the main point: they’ve found a way to make estimating that Money Pump Index computationally tractable.

Warren: It’s about overcoming that NP-hard challenge we just talked about, where you can't compute the exact mean or median across all revealed preference cycles because of the massive number of possibilities.

Iris: They explain this by using graph theory, turning the choice violations into a directed graph and then focusing only on the fundamental cycle basis to get an estimate.

Ruth: It’s not just about finding a shortcut; it’s about transforming a combinatorial problem—counting every possible cycle—into something that has polynomial time complexity, which is much better than what was previously possible.

Warren: So for someone running a quantitative strategy, this means they can get an estimate of consumer irrationality that is fast enough to run daily or even in real-time without waiting forever for the exact answer.

Iris: They show that by using this fundamental cycle basis approach, you can compute the Basis Average MPI in polynomial time of n squared, which is a huge improvement over enumerating everything.

Ruth: That’s what they mean; they’re not trying to find every single cycle; they are aggregating across these fundamental structures to get the result you need for the overall severity measure.

Warren: And if you look at how it scales, the complexity of this new method is O of n squared, which is totally manageable compared to exponential time problems.

Iris: They also introduce a concept called "Basis Average MPI," which they define as summing up the frequency-adjusted costs of cycles across all those fundamental bases and normalizing that by a weight sum.

Ruth: That weighting and aggregation step is key because it’s what allows them to get an estimator that stays consistent with the original Money Pump Index as you keep adding more observations to your dataset.

The paper's summary: Warren: So, summarizing the core idea of this paper, they take the intractable problem of finding the exact mean or median MPI across all cycles and solve it by using a directed graph model and projecting choice violations onto its fundamental cycle basis.

Ruth: It’s a way to avoid counting every single potential money pump cycle—which is computationally impossible for large datasets—by instead focusing on these minimal sets of cycles that define the entire structure.

Iris: Essentially, they are replacing the massive enumeration of all cycles with a more manageable aggregation over these fundamental bases to arrive at an estimator that is asymptotically equivalent to the original Money Pump Index.

Warren: So, for the listener who just wants to know what this means practically, it means they’ve found a way to calculate a measure of consumer irrationality that is fast and accurate enough for serious economic analysis.

Ruth: They confirm this by applying their methodology to datasets like the scanner dataset analyzed by Echenique et al. two hundred eleven and Smeulders et al. two thousand thirteen showing that the proposed estimators compute quickly and have negligible small-sample bias.

Iris: They also tackle percentile estimation, introducing something called the Basis Percentile MPI, which compares a weighted and renormalized cumulative distribution function derived from these fundamental paths to the original one.

Warren: So it’s not just about the mean anymore; they can estimate any arbitrary alpha percentile of that index using this same graph-based approach for the percentile calculation.

Ruth: They give you a consistent estimator for the Original Alpha Percentile MPI, which means as you collect more data, this new method will converge to your true target percentile measurement.

The paper's improvements: Iris: One of the main improvements they propose is moving away from trying to calculate the exact mean or median directly and instead focusing on using the fundamental cycle basis for aggregation.

Warren: This shift means they are trading exact enumeration for a tractable approximation that is proven to be very close to the true value, which is what we need when dealing with huge datasets.

Ruth: They also introduce a lemma about metric distortion, which states that the maximum difference between the Money Pump Index calculated on their normalized data and the original one never exceeds some bound involving X max and square root of r minus one over square root of r plus one.

Warren: That’s good because it gives us a concrete way to control how much error we should expect when we use this estimator compared to the true value, rather than just saying "it's close."

Iris: They empirically verified this bound, showing that the actual distortion in empirical testing is even smaller than that conservative theoretical bound suggests.

Ruth: And on the practical side, they show that longer cycles don’t contribute as much to the overall expenditure-weighted average compared to shorter cycles, although longer cycles still have some effect on the median MPI.

Warren: So it’s a trade-off; you get efficiency by focusing on shorter structures for the average, but you still need to be careful when estimating the median because those longer paths matter more there.

Iris: The method also provides bounds on the finite sample bias for both their mean and percentile estimators, showing that this error shrinks exponentially as your sampling interval K grows larger.

Conclusion: Ruth: So to wrap up on "Tractable Estimation of the Money Pump Index," this paper successfully transforms a combinatorial graph problem into a statistical one using random sampling of Hamiltonian paths.

Warren: The main achievement here is providing a method with polynomial time complexity, O of n squared, to estimate both the mean and median MPI, which was previously considered NP-hard.

Iris: They've shown that the Basis Average MPI is a consistent estimator of the Original OA-MPI as you increase your sample size K to infinity, and the Basis Percentile MPI is a consistent estimator for any alpha percentile.

Ruth: So what this means for us in markets or economics is that we can now use this index to measure consumer irrationality with high computational efficiency without having to wait for an impossibly long calculation.

Warren: It allows us to get a reliable, fast estimate of how much money arbitrageurs could extract from consumer behavior, and the consistency proof shows that this estimate gets better the more data we feed it.

Iris: They also noted that they didn't impose any arbitrary restrictions on cycle lengths, which is important because it means their estimator doesn't have to worry about restricting analysis to just short cycles.

Ruth: That’s the key implication: they provide an efficient, consistent way to estimate the original Money Pump Index without imposing arbitrary cycle length restrictions or making assumptions that limit what you can measure.

Warren: So, in summary, this paper gives us a way to compute the mean and median MPI tractably by using fundamental cycle bases as a statistical shortcut.

More episodes

← Home