IDEAS home Printed from https://ideas.repec.org/a/spr/snopef/v3y2022i4d10.1007_s43069-022-00150-y.html
   My bibliography  Save this article

On Completely Mixed Stochastic Games

Author

Listed:
  • Purba Das

    (University of Oxford)

  • T. Parthasarathy

    (Chennai Mathematical Institute)

  • G. Ravindran

    (Indian Statistical Institute, Chennai Centre)

Abstract

In this paper, we consider a two-person finite state stochastic games with finite number of pure actions for both players in all the states. In particular, for a large number of results we also consider one-player controlled transition probability and show that if all the optimal strategies of the undiscounted stochastic game are completely mixed then for $$\beta$$ β sufficiently close to 1; all the optimal strategies of $$\beta$$ β -discounted stochastic games are also completely mixed. A counterexample is provided to show that the converse is not true. Further, for single-player controlled completely mixed stochastic games if the individual payoff matrices are symmetric in each state, then we show that the individual matrix games are also completely mixed. For the non-zerosum single-player controlled stochastic game under some non-singularity conditions, we show that if the undiscounted game is completely mixed, then the Nash equilibrium is unique. For non-zerosum $$\beta$$ β -discounted stochastic games when Nash equilibrium exists, we provide equalizer rules for corresponding value of the game.

Suggested Citation

  • Purba Das & T. Parthasarathy & G. Ravindran, 2022. "On Completely Mixed Stochastic Games," SN Operations Research Forum, Springer, vol. 3(4), pages 1-26, December.
    • Handle: RePEc:spr:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00150-y
    DOI: 10.1007/s43069-022-00150-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s43069-022-00150-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s43069-022-00150-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. A. Hordijk & L. C. M. Kallenberg, 1979. "Linear Programming and Markov Decision Chains," Management Science, INFORMS, vol. 25(4), pages 352-362, April.
    2. Jerzy A. Filar & T. E. S. Raghavan, 1984. "A Matrix Game Solution of the Single-Controller Stochastic Game," Mathematics of Operations Research, INFORMS, vol. 9(3), pages 356-362, August.
    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. Lodewijk Kallenberg, 2013. "Derman’s book as inspiration: some results on LP for MDPs," Annals of Operations Research, Springer, vol. 208(1), pages 63-94, September.
    2. Dijk, N.M. van, 1989. "Truncation of Markov decision problems with a queueing network overflow control application," Serie Research Memoranda 0065, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    3. İzgi, Burhaneddin & Özkaya, Murat & Üre, Nazım Kemal & Perc, Matjaž, 2024. "Matrix norm based hybrid Shapley and iterative methods for the solution of stochastic matrix games," Applied Mathematics and Computation, Elsevier, vol. 473(C).
    4. Yevgeny Tsodikovich & Xavier Venel & Anna Zseleva, 2021. "Repeated Games with Switching Costs: Stationary vs History-Independent Strategies," Working Papers halshs-03223279, HAL.
    5. Yevgeny Tsodikovich & Xavier Venel & Anna Zseleva, 2021. "Repeated Games with Switching Costs: Stationary vs History Independent Strategies," Papers 2103.00045, arXiv.org, revised Oct 2021.
    6. Jérôme Renault & Xavier Venel, 2017. "Long-Term Values in Markov Decision Processes and Repeated Games, and a New Distance for Probability Spaces," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 349-376, May.
    7. Daniel F. Silva & Bo Zhang & Hayriye Ayhan, 2018. "Admission control strategies for tandem Markovian loss systems," Queueing Systems: Theory and Applications, Springer, vol. 90(1), pages 35-63, October.
    8. D. P. de Farias & B. Van Roy, 2003. "The Linear Programming Approach to Approximate Dynamic Programming," Operations Research, INFORMS, vol. 51(6), pages 850-865, December.
    9. Hui Zhang & Christian Wernz & Danny R. Hughes, 2018. "A Stochastic Game Analysis of Incentives and Behavioral Barriers in Chronic Disease Management," Service Science, INFORMS, vol. 10(3), pages 302-319, September.
    10. Prasenjit Mondal, 2020. "Computing semi-stationary optimal policies for multichain semi-Markov decision processes," Annals of Operations Research, Springer, vol. 287(2), pages 843-865, April.
    11. Prasenjit Mondal, 2015. "Linear Programming and Zero-Sum Two-Person Undiscounted Semi-Markov Games," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-20, December.
    12. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    13. Guillot, Matthieu & Stauffer, Gautier, 2020. "The Stochastic Shortest Path Problem: A polyhedral combinatorics perspective," European Journal of Operational Research, Elsevier, vol. 285(1), pages 148-158.
    14. Prasenjit Mondal, 2018. "Completely mixed strategies for single controller unichain semi-Markov games with undiscounted payoffs," Operational Research, Springer, vol. 18(2), pages 451-468, July.
    15. Tetsuichiro Iki & Masayuki Horiguchi & Masami Kurano, 2007. "A structured pattern matrix algorithm for multichain Markov decision processes," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 66(3), pages 545-555, December.
    16. B. Curtis Eaves & Arthur F. Veinott, 2014. "Maximum-Stopping-Value Policies in Finite Markov Population Decision Chains," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 597-606, August.
    17. Yevgeny Tsodikovich & Xavier Venel & Anna Zseleva, 2021. "Repeated Games with Switching Costs: Stationary vs History-Independent Strategies," AMSE Working Papers 2129, Aix-Marseille School of Economics, France.
    18. Michael O’Sullivan & Arthur F. Veinott, Jr., 2017. "Polynomial-Time Computation of Strong and n -Present-Value Optimal Policies in Markov Decision Chains," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 577-598, August.
    19. Dmitry Krass & O. J. Vrieze, 2002. "Achieving Target State-Action Frequencies in Multichain Average-Reward Markov Decision Processes," Mathematics of Operations Research, INFORMS, vol. 27(3), pages 545-566, August.
    20. Yevgeny Tsodikovich & Xavier Venel & Anna Zseleva, 2022. "Folk Theorems in Repeated Games with Switching Costs," Working Papers hal-03888188, HAL.

    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:spr:snopef:v:3:y:2022:i:4:d:10.1007_s43069-022-00150-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.