Discussion Papers In Economics
And Business

Note on the goodness-of-fit measure for GARP;
NP-hardness of minimum cost index
Kohei Shiozawa

Discussion Paper 15-18

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANNote on the goodness-of-fit measure for GARP;
NP-hardness of minimum cost index
Kohei Shiozawa

Discussion Paper 15-18

June 2015

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANNote on the goodness-of-fit measure for GARP; NP-hardness ofminimum cost index
Kohei Shiozawa∗

Abstract
The purpose of this paper is to show that the problem of computing minimum cost index (MCI),
which is proposed by Dean and Martin (2010, 2015) as a goodness-of-fit measure of GARP, is NPhard. We show the result by using a reduction from maximum acyclic subgraph problem (MASP)
which is a traditional decision problem known to be NP-complete.
Keywords: Revealed Preference; GARP; Goodness of Fit Measure; Minimum Cost Index; Computational Complexity
JEL classification: C60; D11∗ Graduate

School of Economics, Osaka University, Machikaneyama, Toyonaka, Osaka 560-0043, Japan.
nge013sk@student.econ.osaka-u.ac.jp

E-mail:1 IntroductionℓℓGiven a finite data set {(pk , xk )}nk=1 where pk ∈ R++, xk ∈ R +(k = 1, . . . , n), the data can be supported

by some non-satiated utility function u : Re ll+ → R as solutions of utility maximization problem if andonly if the data is consistent with the generalized axiom of revealed preference (GARP). This is a classicalresult of Afriat (Afriat, 1962; Diewert, 1973; Varian, 1982). Based on this result, we can test an arbitrary
data set {(pk , xk )}nk=1 whether there is a utility function that rationalize the data or not. This test has
a form of a choice between two alternatives and hence, if we have some data with GARP violation, we
have no information about the violation severity.
There are several severity-measure proposed in the literature and sometimes these are called goodnessof-fit measures. For example, Afriat (1972), Houtman and Maks (1985), Varian (1990), Echenique et al.
(2011), and Sumeulders et al. (2013) proposed some indices which are defined using the data and these
indices express, in various ways, how severely the data violate GARP. On the other hand, Smeulders
et al. (2013, 2014) shows that for many of those indices, computation is not so easy; the problem ofcomputing some indices are NP-hard.1 They show that the induces of Houtman and Maks (1985), Varian(1990), and Echenique et al. (2011) are NP-hard. On the other hand, they propose an polynomial-timealgorithm for Afriat (1972)’s index and two new indexes which have polynomial-time algorithms andbehave in a compatible way with Echenique et al. (2011)’s index.
Recently, Dean and Martin (2010, 2015) also proposed a new index called minimum cost index (MCI).
They suggest that the computation of MCI is not so easy. In this paper, we show that the computation problem of MCI is actually in the class NP-hard and hence. Our argument is very simple usinga polynomial-time reduction from the maximum acyclic subgraph problem (MASP), a classical NPcomplete problem.
We conclude this paper by proposing a new index. The definition of the new index is similar to
MCI and Echenique et al. (2011)’s indices, but it has a polynomial-time exact algorithm and a naturalinterpretation as a goodness-of-fit measure for GARP in view of the structure of GARP test.

2 Minimum Cost Index; Definition, Validity, and Complexity
The minimum cost index (MCI) is a goodness-of-fit measure for GARP which is proposed by Dean andMartin (2010, 2015). MCI expresses the minimum cost of information we must ignore from the data sothat the data satisfies an equivalent condition of GARP. We first formalize “an equivalent condition of
GARP” using some graph theoretic apparatus.
ℓℓ, xk ∈ R+(k = 1, . . . , n), we define theDefinition 1. For any data {(pk , xk )}nk=1 where pk ∈ R++
1 A problem in the class of NP-hard is not so easy in the sense that if we have a polynomial-time algorithm for the

problem then every problem in the class of NP can be solved in polynomial-time through the problem. In otherwards, the problem is as hard to solve as every NP problems. Moreover, at the present time, no NP problem hasa polynomial-time exact algorithm and hence, we conclude that, probably, there is no polynomial-time algorithm
for the problem. For more detailed discussions, see, Karp (1972), Garey and Johnson (1979), and Korte and Vygen(2008).

1

following directed graph: G := (V, Enp ) whereV := {x1 , x2 , . . . , xn }

(1)
′

′

Enp := {(xk , xk′ ) | k, k = 1, . . . , n, k ̸= k , and pk · (xk′ − pk ) ≦ 0}.

(2)

We call the graph G := (V, Enp ) the associated graph.
As shown in Piaw and Vohra (2003), Fujishige and Yang (2012), and Talla Nobibon et al. (2014), we
can translate GARP condition into graph theoretic conditions as stated in the following proposition.2
Proposition 1. Given the data {(pk , xk )}nk=1 , the following three conditions are equivalent.
(i) Cycrical consistency (GARP)：pk0 ·(xk1 −xk0 ) ≦ 0, pk1 ·(xk2 −xk1 ) ≦ 0, . . . , pkm ·(xkm+1 −xkm ) ≦ 0
implies pki · (xk(i+1) − xki ) = 0 for all i = 0, . . . , m (where m + 1 = 0).
(ii) The associated graph Gnp = (V, Enp ) has no strongly connected component (SCC) which has anegative edge.
(iii) The associated graph Gnp = (V, Enp ) has no cycle which has a negative edge.
The first condition is the Cyclical consistency condition defined by Afriat (1967) and equivalent withGARP (Varian, 1987). The second condition is proposed by Talla Nobibon et al. (2014) which is alsomentioned in Fujishige and Yang (2012). The third condition is a graph theoretic condition which isrelated to the definition of MCI as we will see below. Now, we introduce the formal definition of the
MCI.
ℓDefinition 2. (Dean and Martin, 2010; 2015) For any data {(pk , xk )}nk=1 where pk ∈ R++, xk ∈ℓ
R+(k = 1, . . . , n), we define the minimum cost index (MCI) as follows:

MCI := min{∑(xk ,xk

pk · (xk − xk′ ) | E ′ ⊂ Enp and G′ = (V, Enp \ E ′ ) contains no directed cycle} (3)′ )∈E ′

where Gnp = (V, Enp ) is the graph associated with the data {(pk , xk )}nk=1 defined in definition 1.3
While the original definition of MCI we introduced above is based on the idea that “the minimum costof information we must ignore from the data so that the data satisfies an equivalent condition of GARP”,
it is defined by a slightly deferent condition from the equivalent condition of GARP (the condition (iii)of Proposition 1). However, the equation
MCI := min{∑(xk ,xk= min{∑

pk · (xk − xk′ ) | E ′ ⊂ Enp and G′ = (V, Enp \ E ′ ) contains no directed cycle}′ )∈E ′

pk · (xk − xk′ ) | E ′ ⊂ Enp and G′ = (V, Enp \ E ′ ) contains no directed cycle with a negative edge}(xk ,xk′ )∈E ′(4)holds and we can see the definition of MCI actually grasps the above mentioned idea. Therefore, we
2 Fujishige and Yang (2012) essntiallly shows this result in a indivisible goods setting (discrete setting).
3 Dean and Martin (2010, 2015) define the MCI normalizing by the total wealth level of the data. That is, they define

MCI dividing the value (3) by the value sumn
k=1 pk ẋk > 0. Here, we omit this normalization since our goal is to see
the computational complexity of MCI and this (omission of) normalization obviously does not change the argument.

2

can also say, from Proposition 1, that the MCI has some validity as a goodness-of-fit measure. On theother hand, the MCI is not so easy to compute. Actually, as we will see below, the problem to calculate
MCI for an arbitrarily given data {(pk , xk )}nk=1 is NP-hard, hence we say that, probably, there is no
polynomial-time algorithm for MCI.
We formally state the problem to compute MCI.
MCI Computation Problem

ℓℓInstance: A data {(pk , xk )}nk=1 where pk ∈ R++, xk ∈ R+(k = 1, . . . , n).

Task: Compute MCI defined by the equation (3).
Theorem 1. MCI computation problem is NP-hard.
Proof. We first note that the following equations hold:∑pk · (xk − xk′ ) − MCI(xk ,xk′ )∈Enp= max{∑(xk ,xk′ )∈Enp= max{∑

pk · (xk − xk′ ) −∑(xk ,xk

pk · (xk − xk′ ) | E ′ ⊂ Enp and G′ := (V, Enp \ E ′ ) contains no cycle}′ )∈E ′′

pk · (xk − xk′ ) | E ⊂ Enp and G′ := (V, E ′ ) contains no cycle}.

(5)(xk ,xk′ )∈E ′We can observe the right hand side of this equation is a problem which asks the value of the maximum
weight acyclic subgraph. This problem is called the maximum acyclic subgraph problem (MASP) andknown to be NP-complete (Garey and Johnson, 1979). Formally, MASP is formalized as follows:

MASP



Instance: A simple directed graph G = (U, E) and an integer k ≧ 0.
Question: Is there any subset A′ ⊂ E such that subgraph G′ = (U, A′ ) is acyclic and |A′ | ≥ k.


We use a polynomial-time reduction from MASP. Given an arbitrary instance for MASP; a simple
directed graph G = (U, E) and an integer k ≧ 0, we construct an instance for MCI computation probnn, x k ∈ R+
(k = 1, . . . , n) and n := |V |.4 First, we definelem; a data {(pk , xk )}nk=1 where pk ∈ R++nconsumptions xk ∈ R+
(k = 1, . . . , n) as

xk := (xk1 , . . . , xk(k−1) , xkk , xk(k+1) , . . . , xkn ) := (0, . . . , 0, 1, 0, . . . , 0).

(6)

4 The idea for this construction is the same with Smeulders et al. (2014)’s one which they used to show NP-hardnessof Houtman-Maks index (Houtman and Maks, 1985) and Varian’s index (Varian, 1990).

3

nNext, we define prices pk ∈ R++(k = 1, . . . , n)
1 if (uk , uk′ ) ∈ E′
pkk := 2 if k = k ′
3 if (uk , uk′ ) ∈
/E

(7)

n
where pkk′ is the k ′ -th coordinate of price pk ∈ R++
and uk , uk′ ∈ U . Then, we have{
−1 < 0 if (uk , uk′ ) ∈ E
pk · (xk′ − xk ) = pkk′ − pkk =
1>0
if (uk , uk′ ) ∈/E(8)for all k, k ′ = 1, . . . , n where k ̸= k ′ . Therefore, if we construct the associated graph Gnp for this data{(pk , xk )}nk=1 then it is evident from equation (8) and the definition of associated graph Gnp that there
is a one-to-one correspondence between the edges in E and edges in Enp . Moreover, from equation (8),the equation (5) becomes∑

pk · (xk − xk′ ) − MCI(xk ,xk′ )∈Enp= max{∑

pk · (xk − xk′ ) | E ′ ⊂ Enp and G′ := (V, E ′ ) contains no cycle}(xk ,xk′ )∈E ′= max{∑

1 | E ′ ⊂ E and G′ := (U, E ′ ) contains no cycle}(uk ,uk′ )∈E ′= max{∑(uk ,uk

1 | E ′ ⊂ E and G′ := (U, E ′ ) contains no cycle}.

(9)′ )∈E ′

Therefore, the following equation also holds:|E| − MCI
= max{|E ′ | | E ′ ⊂ E and G′ := (U, E ′ ) contains no cycle}.

(10)

Summing up, we can have a polynomial-time algorithm for MASP using MCI computation problem asa subroutine. Step 1: Constitute the instance for MCI computation from the given instance of MASP
instance by (6) and (7). Step 2: Constitute the associated graph Gnp for the data constructed in step
1. Step 3: Compute the the MCI which is defined by (3). Step 4: Compute the LHS of (10) andcompare that value with the given integer k. If LHS of (10) ≧ k then the answer for the MASP is yes,and otherwise, the answer is no.
The computational time for these steps can obviously be bounded by polynomial time and hence, MCI
computation problem is NP-hard.

3 Concluding Remark
As we show, the problem of computing MCI is NP-hard and as shown by Smeulders et al. (2013, 2014)
many of indices proposed are also NP-hard problems. On the other hand, Smeulders et al. (2014) showthat Afriat (1973)’s index has a polynomial-time algorithm and Smeulders et al. (2013) proposed an4index which has a polynomial-time algorithm and behave nicely with money-pump measure of Echeniqueet al. (2011). (Smeulders et al. (2013) also show that the problem of computing the money-pumpmeasure is also NP-hard.) We propose a new index which has a polynomial-time algorithm and anatural interpretation as a goodness-of-fit measure for GARP.
All indices proposed by Echenique et al. (2011)’s money pump measure, Smeulders et al. (2013)’s
measure, and MCI of Dean and Martin (2015), are defined focusing on negative cycles in Gnp . From
proposition 1, we know that each negative cycle in Gnp creates a violation of GARP. However, also
shown in proposition 1, if there is a data with a violation of GARP, the associated graph Gnp has anegative cycle and these cycles are in a SCC of Gnp . In other words, all the relevant informations of thedata which are related to GARP violations is in SCCs of Gnp . This observation lead us another natural
goodness-of-fit measure for GARP.
∑mSCCI :=

h=1 (

∑

∑

(xk ,xk′ )∈Ch pk · (pk − pk ))′(xk ,xk′ )∈Enp pk · (pk − pk )
′

,

(11)

where Ch (h = 1, . . . , m) are subgraphs of Gnp which are induced by SCC of Gnp and (xk , xk′ ) ∈ Ch
expresses that the edge (xk , xk′ ) in contained the edge of Ch .5 Note that SCCI ∈ [0, 1] for any data.
This index has a natural interpretation: the ratio of the weight of GARP violation part of the data overthe entire weight of revealed preference relation. Moreover, it has a polynomial-time algorithm: Step 1:
Construct the related graph Gnp . Step 2: Compute all of the SCC by the SCCD algorithm. Step 3:
Compute the SCCI.
Theorem 1. The SCCI has an O(n2 ) algorithm.
The computational complexity of this algorithm actually can be bounded by polynomial-time. Hence,
we can compute SCCI in a reasonable time for an arbitrary data {(pk , xk )}nk=1 .

References[1] Afriat, S.N., 1967. The construction of utility functions from expenditure data. International
Economic Review 8, 1, 67–77.
[2] Afriat, S.N., 1973. On a system of inequalities in demand analysis: An extension of the classicalmethod. International Economic Review 14, 2, 460–472.
[3] Dean, M., Martin, D., 2010. How rational are your choice data? In Proceedings of the Conference
on Revealed Preference and Partial Identification.
[4] Dean, M., Martin, D., 2015. Measuring rationality with the minimum cost of revealed preference
violations. Review of Economics and Statistics, forthcoming.
[5] Diewert, W.E.,1973. Afriat and revealed preference theory. The Review of Economic Studies 40,
3, 419–425.
[6] Echenique, F., Lee, S., Shum, M., 2011. The money pump as a measure of revealed preference
5 Note that if the denominator∑(xk ,xk′ )∈Enp pk · (pk − pk′ ) is zero, then the data is rationalizable (Proposition 1).

Hence, in such cases, we define SCCI := 0.

5violations. Journal of Political Economy 119, 6, 1201–1223.
[7] Fujishige, S., Yang, Z., 2012. On revealed preference and indivisibilities. Modern Economy, 3,752–758.
[8] Garey, M.R., Johnson, D.S., 1979. Computers and intractability: A guide to the theory of NPcompleteness. W. H. Freeman and Company, San Francisco.
[9] Houtman M., Maks, J., 1985. Determining all maximal data subsets consistent with revealed
preference. Kwantitatieve methoden 19, 89–104.
[10] Karp, R.M.,1972. Reducibility among combinational problems. Complexity of Computer Computations 40, 4, 85–103.
[11] Korte, B., Vygen, J., 2008.

Combinational optimization: Theory and algorithms.

4th ed.,Springer, Berlin.
[12] Piaw, T.C., Vohra, R.V., 2003. Afriat’s theorem and negative cycles. mimeo.
[13] Smeulders, B., Cherchye, L., Spieksma, F.C.R., De Rock, B., 2013. The money pump as a measureof revealed preference violations: A comment. Journal of Political Economy 121, 6, 1248-1258.
[14] Smeulders, B., Spieksma, F.C.R., Cherchye, L., De Rock, B., 2014. Goodness-of-fit measures forrevealed preference tests: Complexity results and algorithms. ACM Transactions on Economics
and Computation archive 2, 1, 3.
[15] Talla Nobion, F., Smeulders, B., Spieksma, F.C.R., 2014. A note on testing axioms of revealed
preference. Journal of Optimization Theory and Application 1–8.
[16] Varian, H.R., 1982. The nonparametric approach to demand analysis. Econometrica 50, 4, 945–
973.
[17] Varian, H.R., 1990. Goodness-of-fit in optimizing models. Journal of Econometrics 46, 1, 125–140.

6