IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v32y2015i06ns0217595915500438.html
   My bibliography  Save this article

Linear Programming and Zero-Sum Two-Person Undiscounted Semi-Markov Games

Author

Listed:
  • Prasenjit Mondal

    (Mathematics Department, Chandernagore College (Government), Chandernagore 712136, Hooghly, India)

Abstract

In this paper, zero-sum two-person finite undiscounted (limiting average) semi-Markov games (SMGs) are considered. We prove that the solutions of the game when both players are restricted to semi-Markov strategies are solutions for the original game. In addition, we show that if one player fixes a stationary strategy, then the other player can restrict himself in solving an undiscounted semi-Markov decision process associated with that stationary strategy. The undiscounted SMGs are also studied when the transition probabilities and the transition times are controlled by a fixed player in all states. If such games are unichain, we prove that the value and optimal stationary strategies of the players can be obtained from an optimal solution of a linear programming algorithm. We propose a realistic and generalized traveling inspection model that suitably fits into the class of one player control undiscounted unichain semi-Markov games.

Suggested Citation

  • 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.
    • Handle: RePEc:wsi:apjorx:v:32:y:2015:i:06:n:s0217595915500438
    DOI: 10.1142/S0217595915500438
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595915500438
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595915500438?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. S. R. Mohan & S. K. Neogy & T. Parthasarathy, 2001. "Pivoting Algorithms For Some Classes Of Stochastic Games: A Survey," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 3(02n03), pages 253-281.
    3. Mertens, Jean-Francois, 2002. "Stochastic games," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 47, pages 1809-1832, Elsevier.
    4. Prasenjit Mondal & Sagnik Sinha, 2015. "Ordered Field Property for Semi-Markov Games when One Player Controls Transition Probabilities and Transition Times," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 17(02), pages 1-26.
    5. Prasenjit Mondal & Sagnik Sinha, 2013. "Ordered Field Property In A Subclass Of Finite Ser-Sit Semi-Markov Games," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(04), pages 1-20.
    6. L. Jianyong & Z. Xiaobo, 2004. "On Average Reward Semi-Markov Decision Processes with a General Multichain Structure," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 339-352, May.
    7. A. Federgruen & P. J. Schweitzer & H. C. Tijms, 1983. "Denumerable Undiscounted Semi-Markov Decision Processes with Unbounded Rewards," Mathematics of Operations Research, INFORMS, vol. 8(2), pages 298-313, May.
    8. William S. Jewell, 1963. "Markov-Renewal Programming. II: Infinite Return Models, Example," Operations Research, INFORMS, vol. 11(6), pages 949-971, December.
    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. Prasenjit Mondal, 2016. "On undiscounted semi-Markov decision processes with absorbing states," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 83(2), pages 161-177, April.
    2. 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.
    3. 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.

    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. 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.
    2. 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.
    3. Prasenjit Mondal, 2016. "On undiscounted semi-Markov decision processes with absorbing states," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 83(2), pages 161-177, April.
    4. Frank H. Page & Myrna H. Wooders, 2009. "Endogenous Network Dynamics," Working Papers 2009.28, Fondazione Eni Enrico Mattei.
    5. Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2003. "The MaxMin value of stochastic games with imperfect monitoring," International Journal of Game Theory, Springer;Game Theory Society, vol. 32(1), pages 133-150, December.
    6. 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.
    7. János Flesch & Gijs Schoenmakers & Koos Vrieze, 2009. "Stochastic games on a product state space: the periodic case," International Journal of Game Theory, Springer;Game Theory Society, vol. 38(2), pages 263-289, June.
    8. Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 1999. "Stopping Games with Randomized Strategies," Discussion Papers 1258, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    9. Abraham Neyman & Sylvain Sorin, 2010. "Repeated games with public uncertain duration process," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 29-52, March.
    10. 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.
    11. Vieille, Nicolas, 2002. "Stochastic games: Recent results," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 3, chapter 48, pages 1833-1850, Elsevier.
    12. 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.
    13. Anna Jaśkiewicz & Andrzej Nowak, 2011. "Stochastic Games with Unbounded Payoffs: Applications to Robust Control in Economics," Dynamic Games and Applications, Springer, vol. 1(2), pages 253-279, June.
    14. Abreu, Dilip & Manea, Mihai, 2012. "Markov equilibria in a model of bargaining in networks," Games and Economic Behavior, Elsevier, vol. 75(1), pages 1-16.
    15. Rida Laraki & A.P. Maitra & William Sudderth, 2005. "Two -person zero-sum stochastic games with semicontinuous payoff," Working Papers hal-00243014, HAL.
    16. Casilda Lasso de la Vega & Oscar Volij, 2020. "The value of a draw," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(4), pages 1023-1044, November.
    17. Abraham Neyman, 2002. "Stochastic games: Existence of the MinMax," Discussion Paper Series dp295, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    18. Laraki, Rida & Sorin, Sylvain, 2015. "Advances in Zero-Sum Dynamic Games," Handbook of Game Theory with Economic Applications,, Elsevier.
    19. VIEILLE, Nicolas & ROSENBERG, Dinah & SOLAN, Eilon, 2002. "Stochastic games with a single controller and incomplete information," HEC Research Papers Series 754, HEC Paris.
    20. Aleka Papadopoulou & George Tsaklidis, 2007. "Some Reward Paths in Semi-Markov Models with Stochastic Selection of the Transition Probabilities," Methodology and Computing in Applied Probability, Springer, vol. 9(3), pages 399-411, September.

    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:wsi:apjorx:v:32:y:2015:i:06:n:s0217595915500438. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    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.