Note on goodness-of-fit measures for the revealed preference test: The computational complexity of the minimum cost index

Kohei Shiozawa ()
Additional contact information
Kohei Shiozawa: Graduate School of Economics, Osaka University

Economics Bulletin, 2015, vol. 35, issue 4, 2455-2461

Abstract: 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 (search for similar items in EconPapers)
JEL-codes: C0 D0 (search for similar items in EconPapers)
Date: 2015-11-21
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.accessecon.com/Pubs/EB/2015/Volume35/EB-15-V35-I4-P246.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ebl:ecbull:eb-15-00637

Access Statistics for this article

More articles in Economics Bulletin from AccessEcon
Bibliographic data for series maintained by John P. Conley ().