Title: Goodness of fit measures for revealed preference tests: complexity results and algorithms
Authors: Smeulders, Bart
Cherchye, Laurens
De Rock, Bram
Spieksma, Frits
Issue Date: Oct-2012
Publisher: KU Leuven - Faculty of Economics and Business
Series Title: FEB Research Report - KBI_1222 pages:1-16
Abstract: We provide results on the computational complexity of goodness of fit measures (i.e. Afriat's efficiency index, Varian's efficiency 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 difficulties 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 efficiency index.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
Department of Economics, Leuven - miscellaneous
Faculty of Business and Economics, Campus Kulak Kortrijk – miscellaneous
Mathematics, Campus Kulak Kortrijk

Files in This Item:
File Description Status SizeFormat
KBI_1222.pdfGoodness of fit measures for revealed preference tests: complexity results and algorithms Published 441KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.