All Rights Reserved
AccessEcon LLC 2006, 2008.
Powered by MinhViet JSC

Kohei Shiozawa
''Note on goodness-of-fit measures for the revealed preference test: The computational complexity of the minimum cost index''
( 2015, Vol. 35 No.4 )
The purpose of this paper is to show that computing the minimum cost index (MCI) for a given price-amount data set, proposed by Dean and Martin (2010, 2015) as a goodness-of-fit measure for the revealed preference test, is NP-hard. Our proof uses a polynomial reduction from the feedback arc set problem, which is a decision problem known to be NP-complete. Our result refines the NP-hardness result in Dean and Martin (2010), which is presented in a more abstract framework than our economic data setting. Thus the computation of MCI is NP-hard even if we restrict our attention to the revealed preference setting for economic data. We also discuss computational procedures for MCI and provide a way of approximating MCI in polynomial-time using approximation algorithms for the (weighted) feedback arc set problem.
Keywords: Revealed preference, goodness-of-fit measure, minimum cost index, NP-hard, feedback arc set problem
Manuscript Received : Sep 29 2015 Manuscript Accepted : Nov 21 2015

  This abstract has been downloaded 1267 times                The Full PDF of this paper has been downloaded 153793 times