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

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

No 15-18, Discussion Papers in Economics and Business from Osaka University, Graduate School of Economics

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 NP- hard. 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; Com-putational Complexity (search for similar items in EconPapers)
JEL-codes: C60 D11 (search for similar items in EconPapers)
Pages: 9 pages
Date: 2015-06
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www2.econ.osaka-u.ac.jp/library/global/dp/1518.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:osk:wpaper:1518

Access Statistics for this paper

More papers in Discussion Papers in Economics and Business from Osaka University, Graduate School of Economics Contact information at EDIRC.
Bibliographic data for series maintained by The Economic Society of Osaka University ().