{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T17:18:12Z","timestamp":1763140692758,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,3,1]],"date-time":"2014-03-01T00:00:00Z","timestamp":1393632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004040","name":"KU Leuven","doi-asserted-by":"publisher","award":["STRT1\/08\/004"],"award-info":[{"award-number":["STRT1\/08\/004"]}],"id":[{"id":"10.13039\/501100004040","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002749","name":"Belgian Science Policy Office","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002749","id-type":"DOI","asserted-by":"crossref"}]},{"name":"FWO","award":["G.0447.10"],"award-info":[{"award-number":["G.0447.10"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2014,3]]},"abstract":"<jats:p>\n            We provide results on the computational complexity of goodness-of-fit measures (i.e., Afriat\u2019s efficiency index, Varian\u2019s 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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1 \u2212 \u03b4<\/jats:sup>\n            ),\n            <jats:italic>\u03b4<\/jats:italic>\n            ;&gt; 0 exists for Varian\u2019s index, nor for Houtman-Maks\u2019 index (unless P = NP). Finally, we give an exact polynomial-time algorithm for finding Afriat\u2019s efficiency index.\n          <\/jats:p>","DOI":"10.1145\/2560793","type":"journal-article","created":{"date-parts":[[2014,3,24]],"date-time":"2014-03-24T13:45:50Z","timestamp":1395668750000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Goodness-of-Fit Measures for Revealed Preference Tests"],"prefix":"10.1145","volume":"2","author":[{"given":"Bart","family":"Smeulders","sequence":"first","affiliation":[{"name":"University of Leuven"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frits C. R.","family":"Spieksma","sequence":"additional","affiliation":[{"name":"University of Leuven"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurens","family":"Cherchye","sequence":"additional","affiliation":[{"name":"University of Leuven"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bram","family":"De Rock","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2525934"},{"key":"e_1_2_1_2_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall . R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2010.02.039"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00302"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2010.02.001"},{"key":"e_1_2_1_6_1","unstructured":"J. Apesteguia and M. Ballester. 2011. A measure of rationality and welfare. Working Paper Universitat Pompeu Fabra Departamento de Econom\u00eda y Empresa No. 1220.  J. Apesteguia and M. Ballester. 2011. A measure of rationality and welfare. Working Paper Universitat Pompeu Fabra Departamento de Econom\u00eda y Empresa No. 1220."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-003-0376-1"},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"Good neighbors are hard to find: Computational complexity of network formation","volume":"12","author":"Baron R.","year":"2008","unstructured":"R. Baron , J. Durieu , H. Haller , R. Savani , and P. Solal . 2008 . Good neighbors are hard to find: Computational complexity of network formation . Rev. Econ. Des. 12 , 1 -- 19 . R. Baron, J. Durieu, H. Haller, R. Savani, and P. Solal. 2008. Good neighbors are hard to find: Computational complexity of network formation. Rev. Econ. Des. 12, 1--19.","journal-title":"Rev. Econ. Des."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2008.04.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-009-0419-z"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11166-013-9167-7"},{"key":"e_1_2_1_12_1","first-page":"353","article-title":"Computational complexity of stable partitions with B-preferences","volume":"31","author":"Cechlarova K.","year":"2002","unstructured":"K. Cechlarova and J. Hajdukova . 2002 . Computational complexity of stable partitions with B-preferences . Int. J. Game Theory 31 , 353 -- 364 . K. Cechlarova and J. Hajdukova. 2002. Computational complexity of stable partitions with B-preferences. Int. J. Game Theory 31, 353--364.","journal-title":"Int. J. Game Theory"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2011.07.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.5.1921"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"S. Choi S. Kariv W. M\u00fcller and D. Silverman. 2011. Who is (More) rational? Tech. rep. National Bureau of Economic Research.  S. Choi S. Kariv W. M\u00fcller and D. Silverman. 2011. Who is (More) rational? Tech. rep. National Bureau of Economic Research.","DOI":"10.3386\/w16791"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820100066"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.02.015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0297.1997.tb00007.x"},{"volume-title":"Proceedings of the Conference on Revealed Preferences and Partial Identification.","author":"Dean M.","key":"e_1_2_1_20_1","unstructured":"M. Dean and D. Martin . 2010. How rational are your choice data? In Proceedings of the Conference on Revealed Preferences and Partial Identification. M. Dean and D. Martin. 2010. How rational are your choice data? In Proceedings of the Conference on Revealed Preferences and Partial Identification."},{"volume-title":"An efficient nonparametric test of the collective household model. Working Paper","author":"Deb R.","key":"e_1_2_1_21_1","unstructured":"R. Deb . 2010. An efficient nonparametric test of the collective household model. Working Paper , University of Toronto . R. Deb. 2010. An efficient nonparametric test of the collective household model. Working Paper, University of Toronto."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1086\/665011"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001820200106"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026266122863"},{"volume-title":"The complexity of Nash rationalizability. Tech. rep","author":"Galambos A.","key":"e_1_2_1_25_1","unstructured":"A. Galambos . 2009. The complexity of Nash rationalizability. Tech. rep ., Lawrence University . A. Galambos. 2009. The complexity of Nash rationalizability. Tech. rep., Lawrence University."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.91.5.1539"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_29_1","unstructured":"M. Houtman and J. Maks. 1985. Determining all maximal data subsets consistent with revealed preference. Kwantitatieve methoden 19 89--104.  M. Houtman and J. Maks. 1985. Determining all maximal data subsets consistent with revealed preference. Kwantitatieve methoden 19 89--104."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2008.12.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92182-0_18"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90011-0"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.2307\/1909164"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/1909142"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1086\/259921"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1086\/260951"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912704"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-2681(00)00132-3"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/1909729"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10614-010-9228-9"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0235-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0297.1997.tb00056.x"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912771"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4076(90)90051-T"},{"key":"e_1_2_1_46_1","unstructured":"H. R. Varian. 1993. Goodness-of-fit for revealed preference tests. Unpublished.  H. R. Varian. 1993. Goodness-of-fit for revealed preference tests. Unpublished."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"H. R. Varian. 2006. Revealed preference. In Samuelsonian Economics and the Twenty-First Century 99--116.  H. R. Varian. 2006. Revealed preference. In Samuelsonian Economics and the Twenty-First Century 99--116.","DOI":"10.1093\/acprof:oso\/9780199298839.003.0007"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003550200197"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2560793","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2560793","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:21Z","timestamp":1750234221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2560793"}},"subtitle":["Complexity Results and Algorithms"],"short-title":[],"issued":{"date-parts":[[2014,3]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["10.1145\/2560793"],"URL":"https:\/\/doi.org\/10.1145\/2560793","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2014,3]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}