Goodness of Fit Measures for Revealed Preference Tests : Complexity Results and Algorithms

We provide results on the computational complexity of goodness of t measures (i.e. Afriat's effi ciency index, Varian's effi ciency vector-index and the Houtman-Maks index) associated with several revealed preference axioms (i.e. WARP, SARP, GARP and HARP). These results explain the computational di fficulties that have been observed in literature when computing these indices. Our NP-Hardness results are obtained by reductions from the independent set problem. We also show that this reduction can be used to prove that no constant factor approximations algorithm exists for Varian's index, nor for Houtman-Maks' index (unless P = NP). Finally, we give an exact polynomial time algorithm for finding Afriat's effi ciency index