IDEAS home Printed from https://ideas.repec.org/a/ebl/ecbull/eb-15-00637.html
   My bibliography  Save this article

Note on goodness-of-fit measures for the revealed preference test: The computational complexity of the minimum cost index

Author

Listed:
  • Kohei Shiozawa

    (Graduate School of Economics, Osaka University)

Abstract

The purpose of this paper is to show that computing the minimum cost index (MCI) for a given price-amount data set, proposed by Dean and Martin (2010, 2015) as a goodness-of-fit measure for the revealed preference test, is NP-hard. Our proof uses a polynomial reduction from the feedback arc set problem, which is a decision problem known to be NP-complete. Our result refines the NP-hardness result in Dean and Martin (2010), which is presented in a more abstract framework than our economic data setting. Thus the computation of MCI is NP-hard even if we restrict our attention to the revealed preference setting for economic data. We also discuss computational procedures for MCI and provide a way of approximating MCI in polynomial-time using approximation algorithms for the (weighted) feedback arc set problem.

Suggested Citation

  • 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.
    • Handle: RePEc:ebl:ecbull:eb-15-00637
    as

    Download full text from publisher

    File URL: http://www.accessecon.com/Pubs/EB/2015/Volume35/EB-15-V35-I4-P246.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Varian, Hal R, 1982. "The Nonparametric Approach to Demand Analysis," Econometrica, Econometric Society, vol. 50(4), pages 945-973, July.
    2. Fleissig, Adrian R. & Whitney, Gerald A., 2005. "Testing for the Significance of Violations of Afriat's Inequalities," Journal of Business & Economic Statistics, American Statistical Association, vol. 23, pages 355-362, July.
    3. Bart Smeulders & Laurens Cherchye & Bram De Rock & Frits C. R. Spieksma, 2013. "The Money Pump as a Measure of Revealed Preference Violations: A Comment," Journal of Political Economy, University of Chicago Press, vol. 121(6), pages 1248-1258.
    4. 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.
    5. Gross, John, 1995. "Testing Data for Consistency with Revealed Preference," The Review of Economics and Statistics, MIT Press, vol. 77(4), pages 701-710, November.
    6. 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, Osaka University, Graduate School of Economics.
    7. Varian, Hal R., 1990. "Goodness-of-fit in optimizing models," Journal of Econometrics, Elsevier, vol. 46(1-2), pages 125-140.
    8. Satoru Fujishige & Zaifu Yang, 2012. "On Revealed Preference and Indivisibilities," Discussion Papers 12/02, Department of Economics, University of York.
    9. Heufer, Jan, 2008. "A Geometric Measure for the Violation of Utility Maximization," Ruhr Economic Papers 69, RWI - Leibniz-Institut für Wirtschaftsforschung, Ruhr-University Bochum, TU Dortmund University, University of Duisburg-Essen.
    10. repec:zbw:rwirep:0069 is not listed on IDEAS
    11. 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.
    12. Jose Apesteguia & Miguel A. Ballester, 2015. "A Measure of Rationality and Welfare," Journal of Political Economy, University of Chicago Press, vol. 123(6), pages 1278-1310.
    13. Bram De Rock & Bart Smeulders & Laurens Cherchye & Frits Spieksma, 2013. "Goodness of fit measures for revealed preference tests: Complexity results and algorithms," ULB Institutional Repository 2013/162939, ULB -- Universite Libre de Bruxelles.
    14. 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.
    15. Teo Chung Piaw & Rakesh V. Vohra, 2003. "Afrait's Theorem and Negative Cycles," Discussion Papers 1377, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    16. 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. Shiozawa, Kohei, 2016. "Revealed preference test and shortest path problem; graph theoretic structure of the rationalizability test," Journal of Mathematical Economics, Elsevier, vol. 67(C), pages 38-48.
    2. 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.

    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. 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.
    2. 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.
    3. 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.
    4. Shiozawa, Kohei, 2016. "Revealed preference test and shortest path problem; graph theoretic structure of the rationalizability test," Journal of Mathematical Economics, Elsevier, vol. 67(C), pages 38-48.
    5. 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.
    6. 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.
    7. Roy Allen & John Rehbeck, 2021. "Measuring rationality: percentages vs expenditures," Theory and Decision, Springer, vol. 91(2), pages 265-277, September.
    8. Nikolay Klemashev & Alexander Shananin, 2015. "Positively-homogeneous Konus-Divisia indices and their applications to demand analysis and forecasting," Papers 1501.05771, arXiv.org.
    9. Demuynck, Thomas & Hjertstrand, Per, 2019. "Samuelson's Approach to Revealed Preference Theory: Some Recent Advances," Working Paper Series 1274, Research Institute of Industrial Economics.
    10. Fleissig, Adrian R. & Whitney, Gerald A., 2015. "A revealed preference test of rationing a Monte Carlo analysis," Economic Modelling, Elsevier, vol. 45(C), pages 207-211.
    11. Jim Engle-Warnick & Natalia Mishagina, 2014. "Insensitivity to Prices in a Dictator Game," CIRANO Working Papers 2014s-19, CIRANO.
    12. Jan Heufer & Per Hjertstrand, 2015. "Homothetic Efficiency and Test Power: A Non-Parametric Approach," Tinbergen Institute Discussion Papers 15-064/I, Tinbergen Institute.
    13. Dziewulski, Paweł, 2020. "Just-noticeable difference as a behavioural foundation of the critical cost-efficiency index," Journal of Economic Theory, Elsevier, vol. 188(C).
    14. 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.
    15. Tipoe, Eileen, 2021. "Price inattention: A revealed preference characterisation," European Economic Review, Elsevier, vol. 134(C).
    16. 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.
    17. Andreas C Drichoutis & Rodolfo M Nayga, 2020. "Economic Rationality under Cognitive Load," The Economic Journal, Royal Economic Society, vol. 130(632), pages 2382-2409.
    18. Javier A. Birchenall, 2024. "Random choice and market demand," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 57(1), pages 165-198, February.
    19. Dieter Saelens, 2022. "Unitary or collective households? A nonparametric rationality and separability test using detailed data on consumption expenditures and time use," Empirical Economics, Springer, vol. 62(2), pages 637-677, February.
    20. repec:hal:wpaper:halshs-00870052 is not listed on IDEAS
    21. Forges, Françoise & Iehlé, Vincent, 2014. "Afriat’s theorem for indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 1-6.

    More about this item

    Keywords

    Revealed preference; goodness-of-fit measure; minimum cost index; NP-hard; feedback arc set problem;
    All these keywords.

    JEL classification:

    • D0 - Microeconomics - - General
    • C0 - Mathematical and Quantitative Methods - - General

    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:ebl:ecbull:eb-15-00637. 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: John P. Conley (email available below). General contact details of provider: .

    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.