IDEAS home Printed from https://ideas.repec.org/p/kob/dpaper/dp2014-24.html
   My bibliography  Save this paper

An Application of Kleene's Fixed Point Theorem to Dynamic Programming: A Note

Author

Listed:
  • Takashi Kamihigashi

    (Research Institute for Economics & Business Administration (RIEB), Kobe University, Japan)

  • Kevin Reffett

    (Department of Economics, Arizona State University)

  • Masayuki Yao

    (Department of Economics, Keio University)

Abstract

In this note, we show that the least fixed point of the Bellman operator in a certain set can be computed by value iteration whether or not the fixed point is the value function. As an application, we show one of the main results of Kamihigashi (2014, "Elementary results on solutions to the Bellman equation of dynamic programming:existence, uniqueness, and convergence," Economic Theory 56, 251-273) with a simpler proof.

Suggested Citation

  • Takashi Kamihigashi & Kevin Reffett & Masayuki Yao, 2014. "An Application of Kleene's Fixed Point Theorem to Dynamic Programming: A Note," Discussion Paper Series DP2014-24, Research Institute for Economics & Business Administration, Kobe University, revised Jul 2014.
  • Handle: RePEc:kob:dpaper:dp2014-24
    as

    Download full text from publisher

    File URL: https://www.rieb.kobe-u.ac.jp/academic/ra/dp/English/DP2014-24.pdf
    File Function: Revised version, 2014
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Van Zandt, Timothy, 2010. "Interim Bayesian Nash equilibrium on universal type spaces for supermodular games," Journal of Economic Theory, Elsevier, vol. 145(1), pages 249-263, January.
    2. Mirman, Leonard J. & Morand, Olivier F. & Reffett, Kevin L., 2008. "A qualitative approach to Markovian equilibrium in infinite horizon economies with capital," Journal of Economic Theory, Elsevier, vol. 139(1), pages 75-98, March.
    3. Takashi Kamihigashi, 2014. "An order-theoretic approach to dynamic programming: an exposition," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 2(1), pages 13-21, April.
    4. Takashi Kamihigashi, 2008. "On the principle of optimality for nonstationary deterministic dynamic programming," International Journal of Economic Theory, The International Society for Economic Theory, vol. 4(4), pages 519-525, December.
    5. Vassilakis, Spyros, 1992. "Some economic applications of Scott domains," Mathematical Social Sciences, Elsevier, vol. 24(2-3), pages 173-208, November.
    6. Jaime McGovern & Olivier Morand & Kevin Reffett, 2013. "Computing minimal state space recursive equilibrium in OLG models with stochastic production," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(3), pages 623-674, November.
    7. Takashi Kamihigashi, 2014. "Elementary results on solutions to the bellman equation of dynamic programming: existence, uniqueness, and convergence," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 251-273, June.
    8. Michel, Philippe, 1990. "Some Clarifications on the Transversality Condition," Econometrica, Econometric Society, vol. 58(3), pages 705-723, May.
    9. Balbus, Łukasz & Reffett, Kevin & Woźny, Łukasz, 2014. "A constructive study of Markov equilibria in stochastic games with strategic complementarities," Journal of Economic Theory, Elsevier, vol. 150(C), pages 815-840.
    10. Leonard Mirman & Olivier Morand & Kevin Reffett, "undated". "A Qualitative Theory of Markovian Equilibrium in Infinite Horizon Economies with Capital," Working Papers 2133376, Department of Economics, W. P. Carey School of Business, Arizona State University.
    11. Łukasz Balbus & Paweł Dziewulski & Kevin Reffett & Łukasz Woźny, 2019. "A qualitative theory of large games with strategic complementarities," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 67(3), pages 497-523, April.
    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. Robert A. Becker & Juan Pablo Rincón-Zapatero, 2017. "Arbitration and Renegotiation in Trade Agreements," CAEPR Working Papers 2017-007, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
    2. Becker, Robert A. & Rincón-Zapatero, Juan Pablo, 2021. "Thompson aggregators, Scott continuous Koopmans operators, and Least Fixed Point theory," Mathematical Social Sciences, Elsevier, vol. 112(C), pages 84-97.
    3. Robert Becker & Juan Pablo Rincon-Zapatero, 2018. "Recursive Utility and Thompson Aggregators, I: Constructive Existence Theory for the Koopmans Equation," CAEPR Working Papers 2018-006, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
    4. Takashi Kamihigashi & Masayuki Yao, 2015. "Infnite-Horizon Deterministic Dynamic Programming in Discrete Time: A Monotone Convergence Principle," Discussion Paper Series DP2015-32, Research Institute for Economics & Business Administration, Kobe University.
    5. Takashi Kamihigashi & Masayuki Yao, 2015. "Deterministic Dynamic Programming in Discrete Time: A Monotone Convergence Principle," Discussion Paper Series DP2015-15, Research Institute for Economics & Business Administration, Kobe University.

    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. Rabah Amir, 2018. "Special issue: supermodularity and monotone methods in economics," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(3), pages 547-556, October.
    2. Takashi Kamihigashi, 2014. "Elementary results on solutions to the bellman equation of dynamic programming: existence, uniqueness, and convergence," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 251-273, June.
    3. Balbus, Lukasz & Dziewulski, Pawel & Reffett, Kevin & Wozny, Lukasz, 2022. "Markov distributional equilibrium dynamics in games with complementarities and no aggregate risk," Theoretical Economics, Econometric Society, vol. 17(2), May.
    4. Takashi Kamihigashi & Masayuki Yao, 2015. "Infnite-Horizon Deterministic Dynamic Programming in Discrete Time: A Monotone Convergence Principle," Discussion Paper Series DP2015-32, Research Institute for Economics & Business Administration, Kobe University.
    5. Takashi Kamihigashi & Masayuki Yao, 2015. "Deterministic Dynamic Programming in Discrete Time: A Monotone Convergence Principle," Discussion Paper Series DP2015-15, Research Institute for Economics & Business Administration, Kobe University.
    6. Ronaldo Carpio & Takashi Kamihigashi, 2015. "Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to Infinite-Horizon Dynamic Programming in Discrete Time," Discussion Paper Series DP2015-11, Research Institute for Economics & Business Administration, Kobe University.
    7. Lukasz Balbus & Wojciech Olszewski & Kevin Reffett & Lukasz Wozny, 2022. "Iterative Monotone Comparative Statics," KAE Working Papers 2022-072, Warsaw School of Economics, Collegium of Economic Analysis.
    8. Ronaldo Carpio & Takashi Kamihigashi, 2016. "Fast Bellman Iteration: An Application of Legendre-Fenchel Duality to Deterministic Dynamic Programming in Discrete Time," Discussion Paper Series DP2016-26, Research Institute for Economics & Business Administration, Kobe University.
    9. Rodrigo Jardim Raad, 2016. "Recursive equilibrium with Price Perfect Foresight and a minimal state space," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 61(1), pages 1-54, January.
    10. Bar Light, 2019. "Stochastic Comparative Statics in Markov Decision Processes," Papers 1904.05481, arXiv.org, revised Jan 2020.
    11. Takashi Kamihigashi & Masayuki Yao, 2016. "Infinite-Horizon Deterministic Dynamic Programming in Discrete Time: A Monotone Convergence Principle and a Penalty Method," Discussion Paper Series DP2016-05, Research Institute for Economics & Business Administration, Kobe University, revised May 2016.
    12. Agnieszka Wiszniewska-Matyszkiel & Rajani Singh, 2020. "When Inaccuracies in Value Functions Do Not Propagate on Optima and Equilibria," Mathematics, MDPI, vol. 8(7), pages 1-25, July.
    13. Manjira Datta & Kevin Reffett & Łukasz Woźny, 2018. "Comparing recursive equilibrium in economies with dynamic complementarities and indeterminacy," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 66(3), pages 593-626, October.
    14. Balbus, Łukasz & Reffett, Kevin & Woźny, Łukasz, 2013. "A constructive geometrical approach to the uniqueness of Markov stationary equilibrium in stochastic games of intergenerational altruism," Journal of Economic Dynamics and Control, Elsevier, vol. 37(5), pages 1019-1039.
    15. John Stachurski, 2009. "Economic Dynamics: Theory and Computation," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262012774, December.
    16. Manuel Santos, 2007. "Consistency Properties of a Simulation-Based Estimator for Dynamic Processes," Working Papers 0705, University of Miami, Department of Economics.
    17. Łukasz Balbus & Paweł Dziewulski & Kevin Reffett & Łukasz Woźny, 2015. "Differential information in large games with strategic complementarities," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 59(1), pages 201-243, May.
    18. Li, Huiyu & Stachurski, John, 2014. "Solving the income fluctuation problem with unbounded rewards," Journal of Economic Dynamics and Control, Elsevier, vol. 45(C), pages 353-365.
    19. Lilia Maliar & Serguei Maliar, 2016. "Ruling Out Multiplicity of Smooth Equilibria in Dynamic Games: A Hyperbolic Discounting Example," Dynamic Games and Applications, Springer, vol. 6(2), pages 243-261, June.
    20. Takashi Kamihigashi & John Stachurski, 2012. "Existence, Uniqueness and Stability of Stationary Distributions: An Extension of the Hopenhayn-Prescott Theorem," Discussion Paper Series DP2012-27, Research Institute for Economics & Business Administration, Kobe University.

    More about this item

    Keywords

    Dynamic programming; Bellman equation; Value function; Fixed point;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    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:kob:dpaper:dp2014-24. 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: Office of Promoting Research Collaboration, Research Institute for Economics & Business Administration, Kobe University (email available below). General contact details of provider: https://edirc.repec.org/data/rikobjp.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.