Goodness of fit measures for revealed preference tests: complexity results and algorithms
AbstractWe 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Katholieke Universiteit Leuven in its series Open Access publications from Katholieke Universiteit Leuven with number urn:hdl:123456789/393902.
Date of creation: 2013
Date of revision:
Publication status: Published in ACM Transactions on Economics and Computation (2013) v.accepted, p.-
Contact details of provider:
Web page: http://www.kuleuven.be
Other versions of this item:
- Smeulders, Bart & Cherchye, Laurens & De Rock, Bram & Spieksma, Frits, 2012. "Goodness of fit measures for revealed preference tests: complexity results and algorithms," Open Access publications from Katholieke Universiteit Leuven urn:hdl:123456789/359169, Katholieke Universiteit Leuven.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Francis Chu & Joseph Halpern, 2001.
"On the NP-completeness of finding an optimal strategy in games with common payoffs,"
International Journal of Game Theory,
Springer, vol. 30(1), pages 99-106.
- Francis C. Chu & Joseph Y. Halpern, 2000. "On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs," Game Theory and Information 0004011, EconWPA.
- Syngjoo Choi & Shachar Kariv & Wieland Mueller & Dan Silverman, 2011.
"Who Is (More) Rational?,"
Vienna Economics Papers
1105, University of Vienna, Department of Economics.
- Laurens CHERCHYE & Thomas DEMUYNCK & Bram DE ROCK, 2009.
"Testable implications of general equilibrium models: an integer programming approach,"
Center for Economic Studies - Discussion papers
ces09.14, Katholieke Universiteit Leuven, Centrum voor Economische Studiën.
- Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram, 2011. "Testable implications of general equilibrium models: An integer programming approach," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 564-575.
- Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram, 2009. "Testable implications of general equilibrium models: an integer programming approach," Open Access publications from Katholieke Universiteit Leuven urn:hdl:123456789/237726, Katholieke Universiteit Leuven.
- Cherchye, Laurens & Demuynck, Thomas & De Rock, Bram, 2011. "Testable implications of general equilibrium models: an integer programming approach," Open Access publications from Katholieke Universiteit Leuven urn:hdl:123456789/311998, Katholieke Universiteit Leuven.
- Laurens Cherchye & Thomas Demuynck & Bram De Rock, 2011. "Testable implications of general equilibrium models: An integer programming approach," ULB Institutional Repository 2013/131708, ULB -- Universite Libre de Bruxelles.
- Varian, Hal R., 1990. "Goodness-of-fit in optimizing models," Journal of Econometrics, Elsevier, vol. 46(1-2), pages 125-140.
- Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
- Richard Baron & Jacques Durieu & Hans Haller & Rahul Savani & Philippe Solal, 2008. "Good neighbors are hard to find: computational complexity of network formation," Review of Economic Design, Springer, vol. 12(1), pages 1-19, April.
- Philippe Février & Michael Visser, 2000.
"AStudyof Consumer Behavior Using Laboratory Data,"
2000-12, Centre de Recherche en Economie et Statistique.
- Philippe FÃ©vrier & Michael Visser, 2004. "A Study of Consumer Behavior Using Laboratory Data," Experimental Economics, Springer, vol. 7(1), pages 93-114, February.
- Philippe Fevrier & Michael Visser, 2000. "A Study of Consumer Behavior Using Laboratory Data," Econometric Society World Congress 2000 Contributed Papers 1095, Econometric Society.
- Sippel, Reinhard, 1997. "An Experiment on the Pure Theory of Consumer's Behaviour," Economic Journal, Royal Economic Society, vol. 107(444), pages 1431-44, September.
- Ariel Procaccia & Jeffrey Rosenschein & Aviv Zohar, 2008. "On the complexity of achieving proportional representation," Social Choice and Welfare, Springer, vol. 30(3), pages 353-362, April.
- Itzhak Gilboa & Eitan Zemel, 1988.
"Nash and Correlated Equilibria: Some Complexity Considerations,"
777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
- Cox, James C, 1997. "On Testing the Utility Hypothesis," Economic Journal, Royal Economic Society, vol. 107(443), pages 1054-78, July.
- Syngjoo Choi & Raymond Fisman & Douglas Gale & Shachar Kariv, 2007. "Consistency and Heterogeneity of Individual Behavior under Uncertainty," American Economic Review, American Economic Association, vol. 97(5), pages 1921-1938, December.
- Gerhard J. Woeginger, 2003. "Banks winners in tournaments are difficult to recognize," Social Choice and Welfare, Springer, vol. 20(3), pages 523-528, 06.
- Landsburg, Steven E, 1981. "Taste Change in the United Kingdom, 1900-1955," Journal of Political Economy, University of Chicago Press, vol. 89(1), pages 92-104, February.
- Mossin, Axel, 1972. "A Mean Demand Function and Individual Demand Functions Confronted with the Weak and the Strong Axioms of Revealed Preference: An Empirical Test," Econometrica, Econometric Society, vol. 40(1), pages 177-92, January.
- Varian, Hal R, 1982. "The Nonparametric Approach to Demand Analysis," Econometrica, Econometric Society, vol. 50(4), pages 945-73, July.
- Jose Apesteguia & Miguel Angel Ballester, 2010.
"A measure of rationality and welfare,"
Economics Working Papers
1220, Department of Economics and Business, Universitat Pompeu Fabra, revised Sep 2011.
- James Andreoni & John Miller, 2002. "Giving According to GARP: An Experimental Test of the Consistency of Preferences for Altruism," Econometrica, Econometric Society, vol. 70(2), pages 737-753, March.
- Koo, Anthony Y C & Hasenkamp, Georg, 1972. "Structure of Revealed Preference: Some Preliminary Evidence," Journal of Political Economy, University of Chicago Press, vol. 80(4), pages 724-44, July-Aug..
- Federico Echenique & Sangmok Lee & Matthew Shum, 2011. "The Money Pump as a Measure of Revealed Preference Violations," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1201 - 1223.
- Mattei, Aurelio, 2000. "Full-scale real tests of consumer behavior using experimental data," Journal of Economic Behavior & Organization, Elsevier, vol. 43(4), pages 487-497, December.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Carl Demeyere).
If references are entirely missing, you can add them using this form.