Tractable Estimation of the Money Pump Index
Listen
Radio episode about this paper
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.
econ.EM, econ.TH
Submitted: 2026-09-14
Updated: 2026-11-12
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 86/100
The gist: The Money Pump Index (MPI) of Echenique et al.
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
Summary
The Money Pump Index (MPI) of Echenique et al. p. 0 Tractable Estimation of the Money Pump Index: A
Comment
Gavin Kader
September 16, 2026
Abstract
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. Tractable Estimation of the Money Pump Index: A
Comment
Gavin Kader
September 16, 2026
Abstract
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.Where the paper says it
Where the paper says it
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! p. 3 101 (mean 1. 133), yielding a median theoretical bound of 0.Where the paper says it
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
Conclusion of Tractability
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. N. (1967). The construction of utility functions from expenditure data. p. 2 Generalizing to an arbitrary preference cycle C = (k1, k2, . , km) of length m, we
define MPID(C) which measures the arbitrageur’s total money pump profit relative to
the consumer’s total expenditure within that cycle:
MPID(C) =
Pm
i=1 p
ki
· (x
ki − x
ki+1 )
Pm
i=1 pki · xki
= 1 −
Pm
i=1 p
ki
· x
ki+1
Pm
i=1 pki · xki
,
where km+1 = k1. Generalizing to an arbitrary preference cycle C = (k1, k2, . , km) of length m, we
define MPID(C) which measures the arbitrageur’s total money pump profit relative to
the consumer’s total expenditure within that cycle:
MPID(C) =
Pm
i=1 p
ki
· (x
ki − x
ki+1 )
Pm
i=1 pki · xki
= 1 −
Pm
i=1 p
ki
· x
ki+1
Pm
i=1 pki · xki
,
where km+1 = k1.Where the paper says it
Where the paper says it
Apesteguia, J. and Ballester, M. p. 2 Alongside the MPI (Echenique et al. , 2011), the literature has proposed
numerous such measures, such as Afriat’s Efficiency Index (Afriat, 1967), Varian’s Index
(Varian, 1990), the Houtman-Maks Index (Houtman and Maks, 1985), the Minimum Cost
Index (Dean and Martin, 2016), and the Swaps Index (Apesteguia and Ballester, 2015). Alongside the MPI (Echenique et al. , 2011), the literature has proposed
numerous such measures, such as Afriat’s Efficiency Index (Afriat, 1967), Varian’s Index
(Varian, 1990), the Houtman-Maks Index (Houtman and Maks, 1985), the Minimum Cost
Index (Dean and Martin, 2016), and the Swaps Index (Apesteguia and Ballester, 2015). (2013), the proposed
estimators compute quickly and with negligible small-sample bias. Keywords: Revealed Preference, Money Pump Index, Fundamental Cycle Basis, Consumer Rationality
JEL Classification: C60, C63, D11, D12. (2013), the proposed
estimators compute quickly and with negligible small-sample bias. Keywords: Revealed Preference, Money Pump Index, Fundamental Cycle Basis, Consumer Rationality
JEL Classification: C60, C63, D11, D12.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Dean, M. and Martin, D. p. 2 Alongside the MPI (Echenique et al. , 2011), the literature has proposed
numerous such measures, such as Afriat’s Efficiency Index (Afriat, 1967), Varian’s Index
(Varian, 1990), the Houtman-Maks Index (Houtman and Maks, 1985), the Minimum Cost
Index (Dean and Martin, 2016), and the Swaps Index (Apesteguia and Ballester, 2015). Alongside the MPI (Echenique et al. , 2011), the literature has proposed
numerous such measures, such as Afriat’s Efficiency Index (Afriat, 1967), Varian’s Index
(Varian, 1990), the Houtman-Maks Index (Houtman and Maks, 1985), the Minimum Cost
Index (Dean and Martin, 2016), and the Swaps Index (Apesteguia and Ballester, 2015). 8A strictly positive minimum basis weight Wmin > 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). 8A strictly positive minimum basis weight Wmin > 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Demuynck, T. and Rehbeck, J. p. 2 (2013) provide an algorithm for computing the
maximum/minimum of MPID(C) over all cycles (providing informative bounds on the
OA-MPI). 1Recently, Demuynck and Rehbeck (2023) have introduced Mixed-Integer Linear Programming
(MILP) formulations for the average Varian Index, the Houtman-Maks Index, and the Minimum Cost
Index. (2013) provide an algorithm for computing the
maximum/minimum of MPID(C) over all cycles (providing informative bounds on the
OA-MPI). 1Recently, Demuynck and Rehbeck (2023) have introduced Mixed-Integer Linear Programming
(MILP) formulations for the average Varian Index, the Houtman-Maks Index, and the Minimum Cost
Index. (2013) provide an algorithm for computing the
maximum/minimum of MPID(C) over all cycles (providing informative bounds on the
OA-MPI). 1Recently, Demuynck and Rehbeck (2023) have introduced Mixed-Integer Linear Programming
(MILP) formulations for the average Varian Index, the Houtman-Maks Index, and the Minimum Cost
Index. (2013) provide an algorithm for computing the
maximum/minimum of MPID(C) over all cycles (providing informative bounds on the
OA-MPI). 1Recently, Demuynck and Rehbeck (2023) have introduced Mixed-Integer Linear Programming
(MILP) formulations for the average Varian Index, the Houtman-Maks Index, and the Minimum Cost
Index.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Echenique, F., Lee, S., and Shum, M. (2011). The money pump as a measure of revealed preference violations. p. 1 Echenique et al. (2011) 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). Echenique et al. (2011) 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).Where the paper says it
Where the paper says it
Houtman, M. and Maks, J. p. 2 Alongside the MPI (Echenique et al. , 2011), the literature has proposed
numerous such measures, such as Afriat’s Efficiency Index (Afriat, 1967), Varian’s Index
(Varian, 1990), the Houtman-Maks Index (Houtman and Maks, 1985), the Minimum Cost
Index (Dean and Martin, 2016), and the Swaps Index (Apesteguia and Ballester, 2015). Alongside the MPI (Echenique et al. , 2011), the literature has proposed
numerous such measures, such as Afriat’s Efficiency Index (Afriat, 1967), Varian’s Index
(Varian, 1990), the Houtman-Maks Index (Houtman and Maks, 1985), the Minimum Cost
Index (Dean and Martin, 2016), and the Swaps Index (Apesteguia and Ballester, 2015). Tractable Estimation of the Money Pump Index: A
Comment
Gavin Kader
September 16, 2026
Abstract
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. Tractable Estimation of the Money Pump Index: A
Comment
Gavin Kader
September 16, 2026
Abstract
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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Smeulders, B., Cherchye, L., De Rock, B., and Spieksma, F. C. (2013). The money pump as a measure of revealed preference violations: A comment. p. 0 Tractable Estimation of the Money Pump Index: A
Comment
Gavin Kader
September 16, 2026
Abstract
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. Tractable Estimation of the Money Pump Index: A
Comment
Gavin Kader
September 16, 2026
Abstract
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.Where the paper says it
Where the paper says it
Valiant, L. G. (1979). The complexity of enumeration and reliability problems. p. 2 1Recently, Demuynck and Rehbeck (2023) 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. 1Recently, Demuynck and Rehbeck (2023) 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.Where the paper says it
Where the paper says it
Varian, H. R. (1990). Goodness-of-fit in optimizing models. Journal of Econometrics, 46(1-2):125–140
Pruning redundant reasoning tokens
The authors first establish the link between the MPI and a directed graph where observations are nodes and revealed preference relations are directed edges They define GARP, which is a binary test, to quantify the severity of irrationality The MPI is then defined as measuring the amount of money an arbitrageur could extract by exploiting violations of GARP Generalizing to an arbitrary preference cycle C, MPID(C) captures the proportion of the total cycle expenditure an arbitrageur could extract
How the training signal is built
The authors construct a normalized dataset D˜ where per-period prices are adjusted to p˜t = p t/(p t · x t) so that expenditures are normalized to 1 (p˜t · x t = 1) With this matrix X, the weight on each directed edge is given by Xki,kj = 1−p˜ki · xkj The normalized MPI for a cycle C is then defined as MPID˜ (C) = 1/C Sum i=1 Xki,ki+1
Where the gains come from
The core gain comes from the Basis Average MPI (BA-MPID), which is derived by summing frequency-adjusted cycle costs across all n! possible H-paths and normalizing by the sum of their weights This leads to a tractable estimator with complexity O(Kn2), overcoming the NP-hard problem of exact OA-MPI computation The consistency of this estimator is proven using the Strong Law of Large Numbers and the Continuous Mapping Theorem
Basis 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 is bounded such that E[BPα-MPID,K] − Mα ≤ min 1, 4 exp − 2Kδ2W2min/Wmax This provides a distribution-free worst-case guarantee that decays exponentially as the sample size K grows
The paper proposes a computationally tractable approach to calculate the mean and median Money Pump Index (MPI) of Echenique et al. (2011) The method 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
Afriat, S. N. (1967). The construction of utility functions from expenditure data. International economic review, 8(1):67–77
Apesteguia, J. and Ballester, M. A. (2015). A measure of rationality and welfare. Journal of Political Economy, 123(6):1278–1310
Dean, M. and Martin, D. (2016). Measuring rationality with the minimum cost of revealed preference violations. Review of Economics and Statistics, 98(3):524–534
Demuynck, T. and Rehbeck, J. (2023). Computing revealed preference goodness-of-fit measures with integer programming. Economic Theory, 76(3):821–845
Echenique, F., Lee, S., and Shum, M. (2011). The money pump as a measure of revealed preference violations. Journal of Political Economy, 119(6):1201–1223
Houtman, M. and Maks, J. (1985). Determining all maximal data subsets consistent with revealed preference. Kwantitatieve Methoden, 19:89–104
Smeulders, B., Cherchye, L., De Rock, B., and Spieksma, F. C. (2013). The money pump as a measure of revealed preference violations: A comment. Journal of Political Economy, 121(6):1248–1258
Valiant, L. G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421
Varian, H. R. (1990). Goodness-of-fit in optimizing models.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Tractable Estimation of Money Pump Index: The improved AI system can compute exact mean and median MPI over all revealed preference cycles using a method that projects choice violations onto fundamental cycle bases, yielding an estimator asymptotically equivalent to the original MPI.
-
Basis Average MPI Computation: The system can calculate the Basis Average MPI in polynomial time by randomly sampling over the space of fundamental cycle bases, achieving computational complexity of O(Kn2).
-
Basis Percentile Estimation: The system can compute any arbitrary alpha percentile MPI using a consistent estimator for the B-CDF that is derived from randomly sampled H-paths, which is shown to be equivalent to the Original Alpha-Percentile MPI.
Abstract
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.
Related papers
- Stationarity with Occasionally Binding Constraints
- Backtesting High-Dimensional Expected Shortfall
- Higher-Order Neyman Orthogonality in Moment-Condition Models
- Online Bayesian Inference for a Dirichlet Process Mixture of Binary Logit Models
- Debiased Conditional Independence Tests for Causal Effects
- Sharp Testable Implications of Encouragement Designs