IDEAS home Printed from https://ideas.repec.org/p/inu/caeprp/2017006.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, 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:

    References listed on IDEAS

    as
    1. S. Rao Aiyagari, 1994. "Uninsured Idiosyncratic Risk and Aggregate Saving," The Quarterly Journal of Economics, Oxford University Press, vol. 109(3), pages 659-684.
    2. 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.
    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. 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. 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.
    4. 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.
    5. Grey Gordon & Pablo Guerron-Quintana, 2019. "A Quantitative Theory of Hard and Soft Sovereign Defaults," 2019 Meeting Papers 412, Society for Economic Dynamics.

    More about this item

    Keywords

    Computation; Monotonicity; Grid Search; Sovereign Default;

    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.

    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). General contact details of provider: http://edirc.repec.org/data/caeprus.html .

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.