IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2603.04226.html

Optimal strategies in Markov decision processes with finitely additive evaluations

Author

Listed:
  • J'anos Flesch
  • Arkadi Predtetchinski
  • William D Sudderth
  • Xavier Venel

Abstract

We study infinite-horizon Markov decision processes (MDPs) where the decision maker evaluates each of her strategies by aggregating the infinite stream of expected stage-rewards. The crucial feature of our approach is that the aggregation is performed by means of a given diffuse charge (a diffuse finitely additive probability measure) on the set of stages. The results of Neyman [2023] imply that in this setting, in every MDP with finite state and action spaces, the decision maker has a pure optimal strategy as long as the diffuse charge satisfies the time value of money principle. His result raises the question of existence of an optimal strategy without additional assumptions on the aggregation charge. We answer this question in the negative with a counterexample. With a delicately constructed aggregation charge, the MDP has no optimal strategy at all, neither pure nor randomized.

Suggested Citation

  • J'anos Flesch & Arkadi Predtetchinski & William D Sudderth & Xavier Venel, 2026. "Optimal strategies in Markov decision processes with finitely additive evaluations," Papers 2603.04226, arXiv.org.
    • Handle: RePEc:arx:papers:2603.04226
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2603.04226
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Drew Fudenberg & David Levine, 2008. "Subgame–Perfect Equilibria of Finite– and Infinite–Horizon Games," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 1, pages 3-20, World Scientific Publishing Co. Pte. Ltd..
    2. Neyman, Abraham, 2023. "Additive valuations of streams of payoffs that satisfy the time value of money principle: characterization and robust optimization," Theoretical Economics, Econometric Society, vol. 18(1), January.
    3. Oliver Schirokauer & Joseph B. Kadane, 2007. "Uniform Distributions on the Natural Numbers," Journal of Theoretical Probability, Springer, vol. 20(3), pages 429-441, September.
    Full references (including those not matched with items on IDEAS)

    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. Blume, Andreas & Franco, April Mitchell, 2007. "Decentralized learning from failure," Journal of Economic Theory, Elsevier, vol. 133(1), pages 504-523, March.
    2. Paolo Zappalà & Amal Benhamiche & Matthieu Chardy & Francesco De Pellegrini & Rosa Figueiredo, 2025. "Analysis and Computation of the Outcomes of Pure Nash Equilibria in Two-Player Extensive-Form Games," Dynamic Games and Applications, Springer, vol. 15(3), pages 872-905, July.
    3. János Flesch & P. Jean-Jacques Herings & Jasmine Maes & Arkadi Predtetchinski, 2021. "Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels," Dynamic Games and Applications, Springer, vol. 11(4), pages 704-737, December.
    4. Kalai, Ehud & Stanford, William, 1988. "Finite Rationality and Interpersonal Complexity in Repeated Games," Econometrica, Econometric Society, vol. 56(2), pages 397-410, March.
    5. Hannu Salonen, 2010. "On the existence of Nash equilibria in large games," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(3), pages 351-357, July.
    6. Andreas Blume & April Franco, 2002. "Learning from failure," Staff Report 299, Federal Reserve Bank of Minneapolis.
    7. Mitri Kitti, 2013. "Conditional Markov equilibria in discounted dynamic games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 78(1), pages 77-100, August.
    8. Alós-Ferrer, Carlos & Ritzberger, Klaus, 2017. "Does backwards induction imply subgame perfection?," Games and Economic Behavior, Elsevier, vol. 103(C), pages 19-29.
    9. Mailath, George J. & Postlewaite, Andrew & Samuelson, Larry, 2005. "Contemporaneous perfect epsilon-equilibria," Games and Economic Behavior, Elsevier, vol. 53(1), pages 126-140, October.
    10. Vega-Redondo, Fernando, 1997. "Shaping long-run expectations in problems of coordination," European Journal of Political Economy, Elsevier, vol. 13(4), pages 783-806, December.
    11. Drew Fudenberg & David Levine, 2008. "Limit Games and Limit Equilibria," World Scientific Book Chapters, in: Drew Fudenberg & David K Levine (ed.), A Long-Run Collaboration On Long-Run Games, chapter 2, pages 21-39, World Scientific Publishing Co. Pte. Ltd..
    12. Heidhues, Paul & Rady, Sven & Strack, Philipp, 2015. "Strategic experimentation with private payoffs," Journal of Economic Theory, Elsevier, vol. 159(PA), pages 531-551.
    13. Martin W. Cripps & George J. Mailath & Larry Samuelson, 2004. "Imperfect Monitoring and Impermanent Reputations," Econometrica, Econometric Society, vol. 72(2), pages 407-432, March.
    14. Francesco Caruso & Maria Carmela Ceparano & Jacqueline Morgan, 2024. "Asymptotic behavior of subgame perfect Nash equilibria in Stackelberg games," Annals of Operations Research, Springer, vol. 336(3), pages 1573-1590, May.
    15. Drew Fudenberg & David Levine, 2008. "Corrigendum to "Continuous time limits of repeated games with imperfect public monitoring"," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 11(1), pages 237-237, January.
    16. Ryoichi Kunisada, 2022. "On the Additive Property of Finitely Additive Measures," Journal of Theoretical Probability, Springer, vol. 35(3), pages 1782-1794, September.
    17. Sekiguchi, Tadashi, 1997. "Efficiency in Repeated Prisoner's Dilemma with Private Monitoring," Journal of Economic Theory, Elsevier, vol. 76(2), pages 345-361, October.
    18. Sokolov, Mikhail V., 2024. "NPV, IRR, PI, PP, and DPP: A unified view," Journal of Mathematical Economics, Elsevier, vol. 114(C).
    19. Maskin, Eric & Tirole, Jean, 2001. "Markov Perfect Equilibrium: I. Observable Actions," Journal of Economic Theory, Elsevier, vol. 100(2), pages 191-219, October.
    20. Echenique, Federico, 2004. "Extensive-form games and strategic complementarities," Games and Economic Behavior, Elsevier, vol. 46(2), pages 348-364, February.

    More about this item

    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:arx:papers:2603.04226. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.