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

被引：10
作者：
机构：
[1] ORSTAT, Faculty of Economics and Business, University of Leuven
[2] CES, Faculty of Economics and Business, University of Leuven
[3] ECARES-ECORE, Université Libre de Bruxelles
来源：
Smeulders, Bart (bart.smeulders@kuleuven.be) | 1600年 / Association for Computing Machinery卷 / 02期
基金：
欧洲研究理事会;
关键词：
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;
D O I：
10.1145/2560793
中图分类号：
学科分类号：
摘要：
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. © 2014 ACM.
引用
收藏
相关论文
共 49 条
  • [1] Afriat S.N., On a system of inequalities in demand analysis: An extension of the classical method, Int. Econ. Rev., 14, 2, pp. 460-472, (1973)
  • [2] Ahuja R.K., Magnanti T.L., Orlin J.B., Network Flows: Theory, Algorithms, and Applications, (1993)
  • [3] Alcantud J.C.R., Matos D.L., Palmero C.R., Goodness-of-fit in optimizing a consumer model, Math. Comput. Model, 52, 7-8, pp. 1088-1094, (2010)
  • [4] Andreoni J., Miller J., Giving according to garp: An experimental test of the consistency of preferences for altruism, Econometrica, 70, 2, pp. 737-753, (2002)
  • [5] Apesteguia J., Ballester M.A., The computational complexity of rationalizing behavior, J. Math. Econ., 46, pp. 356-363, (2010)
  • [6] Apesteguia J., Ballester M., A Measure of Rationality and Welfare, (2011)
  • [7] Baron R., Durieu J., Haller H., Solal P., Finding a Nash equilibrium in spatial games is an NP-complete problem, Econ. Theory, 23, pp. 445-454, (2004)
  • [8] Baron R., Durieu J., Haller H., Savani R., Solal P., Good neighbors are hard to find: Computational complexity of network formation, Rev. Econ. Des., 12, pp. 1-19, (2008)
  • [9] Brandt F., Fisher F., Computing the minimal covering set, Math. Social Sci., 56, pp. 254-268, (2008)
  • [10] Brandt F., Fisher F., Harrenstein P., Mair M., A computational analysis of the tournament equilibrium set, Social Choice Welfare, 34, pp. 597-609, (2010)
12345