Nothing Special   »   [go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/inu/caeprp/2015002.html
   My bibliography  Save this paper

A Divide and Conquer Algorithm for Exploiting Policy Function Monotonicity

Author

Listed:
  • Grey Gordon

    (Indiana University)

  • Shi Qiu

    (Indiana University)

Abstract
A divide and conquer algorithm for exploiting policy function monotonicity is proposed and analyzed. To solve a discrete problem with n states and n choices, the algorithm requires at most n log2(n) + 5n objective function evaluations. In contrast, existing methods for non-concave problems require n^2 evaluations in the worst case. For concave problems, the solution technique can be combined with a method exploiting concavity to reduce evaluations to 14n + 2 log2(n). A version of the algorithm exploiting monotonicity in two state variables allows for even more efficient solutions. The algorithm can also be efficiently employed in a common class of problems that do not have monotone policies, including problems with many state and choice variables. In the sovereign default model of Arellano (2008) and the real business cycle model, the algorithm reduces run times by an order of magnitude for moderate grid sizes and orders of magnitude for larger ones. Sufficient conditions for monotonicity are provided.

Suggested Citation

  • Grey Gordon & Shi Qiu, 2015. "A Divide and Conquer Algorithm for Exploiting Policy Function Monotonicity," CAEPR Working Papers 2015-002, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
    • Handle: RePEc:inu:caeprp:2015002
    as

    Download full text from publisher

    File URL: https://caepr.indiana.edu/RePEc/inu/caeprp/caepr2015-002.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Carroll, Christopher D., 2006. "The method of endogenous gridpoints for solving dynamic stochastic optimization problems," Economics Letters, Elsevier, vol. 91(3), pages 312-320, June.
    2. S. Rao Aiyagari, 1994. "Uninsured Idiosyncratic Risk and Aggregate Saving," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 109(3), pages 659-684.
    3. Cristina Arellano, 2008. "Default Risk and Income Fluctuations in Emerging Economies," American Economic Review, American Economic Association, vol. 98(3), pages 690-712, June.
    4. Satyajit Chatterjee & Dean Corbae & Makoto Nakajima & José-Víctor Ríos-Rull, 2007. "A Quantitative Theory of Unsecured Consumer Credit with Risk of Default," Econometrica, Econometric Society, vol. 75(6), pages 1525-1589, November.
    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. Grey Gordon & Aaron Hedlund, 2017. "Accounting for the Rise in College Tuition," NBER Chapters, in: Education, Skills, and Technical Change: Implications for Future US GDP Growth, pages 357-394, National Bureau of Economic Research, Inc.
    2. Grey Gordon & Pablo Guerron-Quintana, 2019. "A Quantitative Theory of Hard and Soft Sovereign Defaults," 2019 Meeting Papers 412, Society for Economic Dynamics.
    3. Burkhard Heer & Alfred Maußner, 2024. "Dynamic General Equilibrium Modeling," Springer Texts in Business and Economics, Springer, edition 3, number 978-3-031-51681-8.
    4. Yongquan Cao & Grey Gordon, 2019. "A Practical Approach to Testing Calibration Strategies," Computational Economics, Springer;Society for Computational Economics, vol. 53(3), pages 1165-1182, March.
    5. Yongquan Cao & Grey Gordon, 2016. "A Practical Approach to Testing Calibration Strategies," Caepr Working Papers 2016-004_updated Classifi, Center for Applied Economics and Policy Research, Economics Department, Indiana University Bloomington.
    6. Kaldorf, Matthias & Röttger, Joost, 2023. "Convenient but risky government bonds," Discussion Papers 15/2023, Deutsche Bundesbank.
    7. Erosa, Andrés & Fuster, Luisa & Martinez, Tomás R., 2023. "Public financing with financial frictions and underground economy," Journal of Monetary Economics, Elsevier, vol. 135(C), pages 20-36.
    8. Bommier, Antoine & Harenberg, Daniel & Le Grand, François, 2017. "Household Finance and the Value of Life," VfS Annual Conference 2017 (Vienna): Alternative Structures for Money and Banking 168189, Verein für Socialpolitik / German Economic Association.
    9. Grey Gordon, 2019. "Efficient Computation with Taste Shocks," Working Paper 19-15, Federal Reserve Bank of Richmond.

    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. Maliar, Lilia & Maliar, Serguei, 2022. "Deep learning classification: Modeling discrete labor choice," Journal of Economic Dynamics and Control, Elsevier, vol. 135(C).
    2. Juan Carlos Conesa & Timothy J. Kehoe, 2017. "Gambling for redemption and self-fulfilling debt crises," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 64(4), pages 707-740, December.
    3. Xavier Mateos-Planas & Jose-Victor Rios-Rull & Cristina Arellano, 2013. "Partial Default," 2013 Meeting Papers 765, Society for Economic Dynamics.
      • Cristina Arellano & Xavier Mateos-Planas & José-Víctor Ríos-Rull, 2019. "Partial Default," NBER Working Papers 26076, National Bureau of Economic Research, Inc.
      • Cristina Arellano & Xavier Mateos-Planas & José-Víctor Ríos-Rull, 2019. "Partial Default," Staff Report 589, Federal Reserve Bank of Minneapolis.
      • Cristina Arellano & Xavier Mateos-Planas & Jose-Victor Rios-Rull, 2019. "Partial Default," Discussion Papers 1911, Centre for Macroeconomics (CFM).
    4. xavier Ragot & Francois Le Grand, 2018. "Sovereign Default and Liquidity: The Case for a World Safe," 2018 Meeting Papers 889, Society for Economic Dynamics.
    5. Lizarazo, Sandra Valentina, 2013. "Default risk and risk averse international investors," Journal of International Economics, Elsevier, vol. 89(2), pages 317-330.
    6. Le Grand, François & Ragot, Xavier, 2021. "Sovereign default and liquidity: The case for a world safe asset," Journal of International Economics, Elsevier, vol. 131(C).
    7. Yamada, Tomoaki, 2012. "Income risk, macroeconomic and demographic change, and economic inequality in Japan," Journal of Economic Dynamics and Control, Elsevier, vol. 36(1), pages 63-84.
    8. Durdu, C. Bora & Nunes, Ricardo & Sapriza, Horacio, 2013. "News and sovereign default risk in small open economies," Journal of International Economics, Elsevier, vol. 91(1), pages 1-17.
    9. Arellano, Cristina & Bai, Yan & Zhang, Jing, 2012. "Firm dynamics and financial development," Journal of Monetary Economics, Elsevier, vol. 59(6), pages 533-549.
    10. Youngsoo Jang, 2016. "Income Inequality, Medical Conditions, and Household Bankruptcy," Proceedings of Economics and Finance Conferences 4206835, International Institute of Social and Economic Sciences.
    11. Xavier Ragot, 2017. "Hétérogénéité et économie : inégalité et imperfections financières," Revue d'économie financière, Association d'économie financière, vol. 0(4), pages 109-124.
    12. Michael Irwin, 2023. "The Impact of Unemployment Insurance and Unsecured Credit on Business Cycles," Staff Working Papers 23-22, Bank of Canada.
    13. Andrew Clausen & Carlo Strub, 2012. "Envelope theorems for non-smooth and non-concave optimization," ECON - Working Papers 062, Department of Economics - University of Zurich.
    14. Jang, Youngsoo, 2019. "Credit, Default, and Optimal Health Insurance," MPRA Paper 95397, University Library of Munich, Germany.
    15. Youngsoo Jang & Soyoung Lee, 2021. "A Generalized Endogenous Grid Method for Default Risk Models," Staff Working Papers 21-11, Bank of Canada.
    16. Arellano, Cristina & Maliar, Lilia & Maliar, Serguei & Tsyrennikov, Viktor, 2016. "Envelope condition method with an application to default risk models," Journal of Economic Dynamics and Control, Elsevier, vol. 69(C), pages 436-459.
    17. repec:hal:spmain:info:hdl:2441/666pgupb1p905befsuijtv7nqq is not listed on IDEAS
    18. Alonso, Cristian, 2018. "Hard vs. soft financial constraints: Implications for the effects of a credit crunch," Journal of Macroeconomics, Elsevier, vol. 58(C), pages 198-223.
    19. Makoto Nakajima & José-Víctor Ríos-Rull, 2014. "Credit, Bankruptcy, and Aggregate Fluctuations," NBER Working Papers 20617, National Bureau of Economic Research, Inc.
    20. repec:hal:spmain:info:hdl:2441/3jhmd4ib388m99gnolvi8klga2 is not listed on IDEAS
    21. Clausen, Andrew & Strub, Carlo, 2020. "Reverse Calculus and nested optimization," Journal of Economic Theory, Elsevier, vol. 187(C).
    22. repec:hal:wpspec:info:hdl:2441/3jhmd4ib388m99gnolvi8klga2 is not listed on IDEAS
    23. Sandra Lizarazo, 2009. "Contagion of Financial Crises in Sovereing Debt Markets," Working Papers 0906, Centro de Investigacion Economica, ITAM.

    More about this item

    Keywords

    Grid search; monotone policies; value function iteration;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C88 - Mathematical and Quantitative Methods - - Data Collection and Data Estimation Methodology; Computer Programs - - - Other Computer Software

    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:inu:caeprp:2015002. 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: Center for Applied Economics and Policy Research (email available below). General contact details of provider: https://edirc.repec.org/data/caeprus.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.