Goodness of fit measures for revealed preference tests: Complexity results and algorithms

Bram De Rock, Bart Smeulders, Laurens Cherchye and Frits Spieksma

ULB Institutional Repository from ULB -- Universite Libre de Bruxelles

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 approximation algorithm achieving a ratio of O(n1-δ), δ > 0 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.

Keywords: Algorithms; Computational complexity; Economics; F.2.0 [analysis of algorithms and problem complexity]: general; G.2.2 [discrete mathematics]: graph theory - graph algorithms; Goodness-of-fit measures; NP-complete; Revealed preference; Testing individual rationality (search for similar items in EconPapers)
Date: 2013
Note: SCOPUS: ar.j
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Published in: ACM transactions on economics and computation (2013) v.2 n° 1

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:ulb:ulbeco:2013/162939

Ordering information: This working paper can be ordered from
http://hdl.handle.ne ... lb.ac.be:2013/162939

Access Statistics for this paper

More papers in ULB Institutional Repository from ULB -- Universite Libre de Bruxelles Contact information at EDIRC.
Bibliographic data for series maintained by Benoit Pauwels ().