Positive zero-sum stochastic games with countable state and action spaces

DOI10.1007/S00245-018-9536-3MaRDI QIDQ2198159zbMATH OpenOpenAlexWikidataFDO

Authors Arkadi Predtetchinski, János Flesch, William D. Sudderth

Publication date 9 September 2020

Published in Applied Mathematics and Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00245-018-9536-3

zbMATH Keywords

fixed pointMarkov strategyoptimal strategyTarski fixed point theoremtransfinite algorithmvalue of the gamezero-sum stochastic game

Mathematics Subject Classification ID

2-person games (91A05) Stochastic games, stochastic differential games (91A15)

Review text

This paper deals with a positive zero-sum stochastic game with countable state and action spaces. In order to obtain conditions for the existence of the value, transfinite algorithms are constructed that output the upper value and the lower value of the game. If at every state at least one player has a finite action set, then the algorithms for the upper and lower values give the same answer. Therefore in this case, the game has a value. Further, in this case, player 2 has arbitrarily good Markov strategies. If the action set for player 2 is finite at every state, then the algorithm for the value simplifies and becomes the limit of the sequence of values of the \(n\)-stage games. In this simpler case, player 2 has an optimal stationary strategy.

Recommendations

• Zero-sum risk-sensitive stochastic games on a countable state space
• scientific article; zbMATH DE number 2067957
• Nonzero-sum semi-Markov games with countable state spaces
• scientific article; zbMATH DE number 18894
• Nonzero-sum risk-sensitive stochastic games on a countable state space
• scientific article; zbMATH DE number 3894186
• scientific article; zbMATH DE number 3894187
• Zero-sum average payoff stochastic games with general state space
• scientific article; zbMATH DE number 4025193

Cites work

• A lattice-theoretical fixpoint theorem and its applications
• An operator solution of stochastic games
• Borel stochastic games with lim sup payoff
• Characterization and simplification of optimal strategies in positive stochastic games
• Discounted and positive stochastic games
• Discounted, positive, and noncooperative stochastic games
• Existence of Value and Randomized Strategies in Zero-Sum Discrete-Time Stochastic Dynamic Games
• scientific article; zbMATH DE number 3835011 (Why is no real title available?)
• scientific article; zbMATH DE number 18891 (Why is no real title available?)
• scientific article; zbMATH DE number 44212 (Why is no real title available?)
• scientific article; zbMATH DE number 893883 (Why is no real title available?)
• scientific article; zbMATH DE number 3216771 (Why is no real title available?)
• Negative Dynamic Programming
• On Stochastic Games
• On stochastic games. II
• Simplifying optimal strategies in \(\limsup\) and \(\liminf\) stochastic games
• Stationary Strategies for Recursive Games
• Universally measurable strategies in zero-sum stochastic games

Cited in

(7)

• Zero-sum risk-sensitive stochastic games on a countable state space
• scientific article; zbMATH DE number 18891 (Why is no real title available?)
• scientific article; zbMATH DE number 2067957 (Why is no real title available?)
• Nonzero-sum semi-Markov games with countable state spaces
• Characterization and simplification of optimal strategies in positive stochastic games
• Superfair stochastic games
• Strategy complexity of reachability in countable stochastic 2-player games

This page was built for publication: Positive zero-sum stochastic games with countable state and action spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198159)