Stochastic limit-average games are in EXPTIME
Author
Abstract
Suggested Citation
DOI: 10.1007/s00182-007-0110-5
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- 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.
- Mertens, J.-F. & Neyman, A., 1981. "Stochastic games," LIDAM Reprints CORE 454, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- MERTENS, Jean-François, 2002. "Stochastic games," LIDAM Reprints CORE 1587, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Truman Bewley & Elon Kohlberg, 1976. "The Asymptotic Theory of Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 1(3), pages 197-208, August.
- A. J. Hoffman & R. M. Karp, 1966. "On Nonterminating Stochastic Games," Management Science, INFORMS, vol. 12(5), pages 359-370, January.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Jérôme Bolte & Stéphane Gaubert & Guillaume Vigeral, 2015. "Definable Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 171-191, February.
- Solan, Eilon, 2018. "Acceptable strategy profiles in stochastic games," Games and Economic Behavior, Elsevier, vol. 108(C), pages 523-540.
- Bernhard Stengel, 2010. "Computation of Nash equilibria in finite games: introduction to the symposium," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 1-7, January.
- Miquel Oliu-Barton, 2021. "New Algorithms for Solving Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 255-267, February.
- Eilon Solan & Nicolas Vieille, 2010.
"Computing uniformly optimal strategies in two-player stochastic games,"
Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 237-253, January.
- Nicolas Vieille & Eilon Solan, 2009. "Computing uniformly optimal strategies in two-player stochastic games," Post-Print hal-00528413, HAL.
- Endre Boros & Khaled Elbassioni & Vladimir Gurvich & Kazuhisa Makino, 2018. "A Potential Reduction Algorithm for Two-Person Zero-Sum Mean Payoff Stochastic Games," Dynamic Games and Applications, Springer, vol. 8(1), pages 22-41, March.
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.- Johannes Horner & Takuo Sugaya & Satoru Takahashi & Nicolas Vieille, 2009. "Recursive Methods in Discounted Stochastic Games: An Algorithm for delta Approaching 1 and a Folk Theorem," Cowles Foundation Discussion Papers 1742, Cowles Foundation for Research in Economics, Yale University, revised Aug 2010.
- Laraki, Rida & Sorin, Sylvain, 2015. "Advances in Zero-Sum Dynamic Games," Handbook of Game Theory with Economic Applications,, Elsevier.
- Eilon Solan & Nicolas Vieille, 2010.
"Computing uniformly optimal strategies in two-player stochastic games,"
Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 237-253, January.
- Nicolas Vieille & Eilon Solan, 2009. "Computing uniformly optimal strategies in two-player stochastic games," Post-Print hal-00528413, HAL.
- Rida Laraki, 2010. "Explicit formulas for repeated games with absorbing states," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 53-69, March.
- Eilon Solan & Nicolas Vieille, 2000.
"Uniform Value in Recursive Games,"
Discussion Papers
1293, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Eilon Solan & Nicolas Vieille, 2002. "Uniform value in recursive games," Post-Print hal-00465002, HAL.
- Frank H. Page & Myrna H. Wooders, 2009.
"Endogenous Network Dynamics,"
Working Papers
2009.28, Fondazione Eni Enrico Mattei.
- Frank H. Page, Jr. & Myrna H. Wooders, 2009. "Endogenous Network Dynamics," CAEPR Working Papers 2009-002, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
- Page, Frank H. & Wooders, Myrna H., 2009. "Endogenous Network Dynamics," Sustainable Development Papers 50476, Fondazione Eni Enrico Mattei (FEEM).
- 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.
- Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2001. "On the MaxMin Value of Stochastic Games with Imperfect Monitoring," Working Papers hal-00593645, HAL.
- Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2001. "On the MaxMin Value of Stochastic Games with Imperfect Monitoring," Discussion Papers 1344, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Eilon Solan & Dinah Rosenberg & Nicolas Vieille, 2001. "On the Max Min Value of Stochastic Games with Imperfect Monitoring," Discussion Papers 1337, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- VIEILLE, Nicolas & ROSENBERG, Dinah & SOLAN, Eilon, 2001. "On the maxmin value of stochastic games with imperfect monitoring," HEC Research Papers Series 760, HEC Paris.
- Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2002. "On the maxmin value of stochastic games with imperfect monitoring," Working Papers hal-00242999, HAL.
- Dinah Rosenberg & Eilon Solan & Nicolas Vieille, 2003. "The MaxMin value of stochastic games with imperfect monitoring," Post-Print hal-00464949, HAL.
- 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.
- 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.
- Dinah Rosenberg & Nicolas Vieille & Eilon Solan, 2001. "Stopping games with randomized strategies," Post-Print hal-00465029, HAL.
- 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.
- Jayakumar Subramanian & Amit Sinha & Aditya Mahajan, 2023. "Robustness and Sample Complexity of Model-Based MARL for General-Sum Markov Games," Dynamic Games and Applications, Springer, vol. 13(1), pages 56-88, March.
- Fabien Gensbittel & Marcin Peski & Jérôme Renault, 2021. "Value-Based Distance Between Information Structures," Working Papers hal-01869139, HAL.
- 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.
- Jérôme Renault & Xavier Venel, 2017. "Long-term values in Markov Decision Processes and Repeated Games, and a new distance for probability spaces," PSE-Ecole d'économie de Paris (Postprint) hal-01396680, HAL.
- Jérôme Renault & Xavier Venel, 2017. "Long-term values in Markov Decision Processes and Repeated Games, and a new distance for probability spaces," Post-Print hal-01396680, HAL.
- Jérôme Renault & Xavier Venel, 2017. "Long-term values in Markov Decision Processes and Repeated Games, and a new distance for probability spaces," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-01396680, HAL.
- 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.
- VIEILLE, Nicolas, 2001. "Stochastic games : recent results," HEC Research Papers Series 743, HEC Paris.
- Nicolas Vieille, 2002. "Stochastic Games : recent results," Working Papers hal-00242996, HAL.
- Nicolas Vieille, 2001. "Stochastic Games: recent results," Working Papers hal-00596229, HAL.
- Eilon Solan, 2018. "The modified stochastic game," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(4), pages 1287-1327, November.
- Bruno Ziliotto, 2016. "A Tauberian Theorem for Nonexpansive Operators and Applications to Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1522-1534, November.
- 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.
- 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.
- Dilip Abreu & Mihai Manea, 2011. "Markov Equilibria in a Model of Bargaining in Networks," Working Papers 1359, Princeton University, Department of Economics, Econometric Research Program..
- Jérôme Bolte & Stéphane Gaubert & Guillaume Vigeral, 2015. "Definable Zero-Sum Stochastic Games," Mathematics of Operations Research, INFORMS, vol. 40(1), pages 171-191, February.
- Rida Laraki & A.P. Maitra & William Sudderth, 2005. "Two -person zero-sum stochastic games with semicontinuous payoff," Working Papers hal-00243014, HAL.
More about this item
Keywords
Stochastic games; Limit-average payoff; Computational complexity;All these keywords.
Statistics
Access and download statisticsCorrections
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:jogath:v:37:y:2008:i:2:p:219-234. 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.