IDEAS home Printed from https://ideas.repec.org/p/osk/wpaper/1518.html
   My bibliography  Save this paper

Note on the goodness-of-fit measure for GARP; NP-hardness of minimum cost index

Author

Listed:
  • Kohei Shiozawa

    (Graduate School of Economics, Osaka University)

Abstract

The purpose of this paper is to show that the problem of computing minimum cost index (MCI), which is proposed by Dean and Martin (2010, 2015) as a goodness-of-fit measure of GARP, is NP- hard. We show the result by using a reduction from maximum acyclic subgraph problem (MASP) which is a traditional decision problem known to be NP-complete.

Suggested Citation

  • Kohei Shiozawa, 2015. "Note on the goodness-of-fit measure for GARP; NP-hardness of minimum cost index," Discussion Papers in Economics and Business 15-18, Osaka University, Graduate School of Economics.
    • Handle: RePEc:osk:wpaper:1518
    as

    Download full text from publisher

    File URL: http://www2.econ.osaka-u.ac.jp/library/global/dp/1518.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Mark Dean & Daniel Martin, 2016. "Measuring Rationality with the Minimum Cost of Revealed Preference Violations," The Review of Economics and Statistics, MIT Press, vol. 98(3), pages 524-534, July.
    3. W. E. Diewert, 1973. "Afriat and Revealed Preference Theory," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 40(3), pages 419-425.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kohei Shiozawa, 2015. "Revealed Preference Test and Shortest Path Problem; Graph Theoretic Structure of the Rationalizability Test," Discussion Papers in Economics and Business 15-17-Rev., Osaka University, Graduate School of Economics, revised Jul 2015.
    2. Victor H. Aguiar & Roberto Serrano, 2018. "Classifying bounded rationality in limited data sets: a Slutsky matrix approach," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 9(4), pages 389-421, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Thomas Demuynck & John Rehbeck, 2023. "Computing revealed preference goodness-of-fit measures with integer programming," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(4), pages 1175-1195, November.
    2. Joshua Lanier & Matthew Polisson & John K. -H. Quah, 2024. "Money Pumps and Bounded Rationality," Papers 2404.04843, arXiv.org.
    3. Pawe{l} Dziewulski & Joshua Lanier & John K. -H. Quah, 2024. "Revealed preference and revealed preference cycles: a survey," Papers 2405.08459, arXiv.org.
    4. Jan Heufer & Per Hjertstrand, 2015. "Homothetic Efficiency and Test Power: A Non-Parametric Approach," Tinbergen Institute Discussion Papers 15-064/I, Tinbergen Institute.
    5. Dziewulski, Paweł, 2020. "Just-noticeable difference as a behavioural foundation of the critical cost-efficiency index," Journal of Economic Theory, Elsevier, vol. 188(C).
    6. Smeulders, Bart & Crama, Yves & Spieksma, Frits C.R., 2019. "Revealed preference theory: An algorithmic outlook," European Journal of Operational Research, Elsevier, vol. 272(3), pages 803-815.
    7. Kohei Shiozawa, 2015. "Note on goodness-of-fit measures for the revealed preference test: The computational complexity of the minimum cost index," Economics Bulletin, AccessEcon, vol. 35(4), pages 2455-2461.
    8. Laurens Cherchye & Thomas Demuynck & Bram De Rock & Joshua Lanier, 2020. "Are Consumers Rational ?Shifting the Burden of Proof," Working Papers ECARES 2020-19, ULB -- Universite Libre de Bruxelles.
    9. Tipoe, Eileen, 2021. "Price inattention: A revealed preference characterisation," European Economic Review, Elsevier, vol. 134(C).
    10. Eileen Tipoe & Abi Adams & Ian Crawford, 2022. "Revealed preference analysis and bounded rationality [Consume now or later? Time inconsistency, collective choice and revealed preference]," Oxford Economic Papers, Oxford University Press, vol. 74(2), pages 313-332.
    11. Yoram Halevy & Dotan Persitz & Lanny Zrill, 2018. "Parametric Recoverability of Preferences," Journal of Political Economy, University of Chicago Press, vol. 126(4), pages 1558-1593.
    12. Thomas Demuynck & Christian Seel, 2018. "Revealed Preference with Limited Consideration," American Economic Journal: Microeconomics, American Economic Association, vol. 10(1), pages 102-131, February.
    13. Pawel Dziewulski, 2018. "Just-noticeable difference as a behavioural foundation of the critical cost-efficiency," Economics Series Working Papers 848, University of Oxford, Department of Economics.
    14. Demuynck, Thomas & Hjertstrand, Per, 2019. "Samuelson's Approach to Revealed Preference Theory: Some Recent Advances," Working Paper Series 1274, Research Institute of Industrial Economics.
    15. Pawel Dziewulski, 2021. "A comprehensive revealed preference approach to approximate utility maximisation," Working Paper Series 0621, Department of Economics, University of Sussex Business School.
    16. Alan Beggs, 2021. "Afriat and arbitrage," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 9(2), pages 167-176, October.
    17. repec:spo:wpecon:info:hdl:2441/5rkqqmvrn4tl22s9mc0o6ctj2 is not listed on IDEAS
    18. repec:dau:papers:123456789/10574 is not listed on IDEAS
    19. Kohei Shiozawa, 2015. "Revealed Preference Test and Shortest Path Problem; Graph Theoretic Structure of the Rationalizability Test," Discussion Papers in Economics and Business 15-17-Rev.2, Osaka University, Graduate School of Economics, revised Aug 2016.
    20. Andreas C Drichoutis & Rodolfo M Nayga, 2020. "Economic Rationality under Cognitive Load," The Economic Journal, Royal Economic Society, vol. 130(632), pages 2382-2409.
    21. Federico Echenique & Taisuke Imai & Kota Saito, 2023. "Approximate Expected Utility Rationalization," Journal of the European Economic Association, European Economic Association, vol. 21(5), pages 1821-1864.
    22. Demuynck, Thomas & Salman, Umutcan, 2022. "On the revealed preference analysis of stable aggregate matchings," Theoretical Economics, Econometric Society, vol. 17(4), November.

    More about this item

    Keywords

    Revealed Preference; GARP; Goodness of Fit Measure; Minimum Cost Index; Com-putational Complexity;
    All these keywords.

    JEL classification:

    • C60 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - General
    • D11 - Microeconomics - - Household Behavior - - - Consumer Economics: Theory

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:osk:wpaper:1518. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: The Economic Society of Osaka University (email available below). General contact details of provider: https://edirc.repec.org/data/feosujp.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.