|
| |
| 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 |
|
