IDEAS home Printed from https://ideas.repec.org/p/inu/caeprp/2017006.html

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, 2017. "A Divide and Conquer Algorithm for Exploiting Policy Function Monotonicity," CAEPR Working Papers 2017-006, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
    • Handle: RePEc:inu:caeprp:2017006
    as

    Download full text from publisher

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

    Other versions of this item:

    Citations

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


    Cited by:

    1. 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.
    2. 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.
    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, March.
    4. Yasin Kürsat Önder & Jose Villegas, 2025. "Price Frictions in Credit Markets: Evidence from Belgium's 2020 Credit Guarantee Scheme," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 25/1118, Ghent University, Faculty of Economics and Business Administration.
    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 & Pablo Guerron-Quintana, 2019. "A Quantitative Theory of Hard and Soft Sovereign Defaults," 2019 Meeting Papers 412, Society for Economic Dynamics.
    10. Grey Gordon, 2019. "Efficient Computation with Taste Shocks," Working Paper 19-15, Federal Reserve Bank of Richmond.

    More about this item

    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
    • E32 - Macroeconomics and Monetary Economics - - Prices, Business Fluctuations, and Cycles - - - Business Fluctuations; Cycles
    • F34 - International Economics - - International Finance - - - International Lending and Debt Problems

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:2017006. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.