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

Shiozawa, Kohei

15-18pp.1 - 6 , 2015-06 , Graduate School of Economics and Osaka School of International Public Policy (OSIPP) Osaka University
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.

Number of accesses :  

Other information