Definable zero-sum stochastic games
From MaRDI portal
Abstract: Definable zero-sum stochastic games involve a finite number of states and action sets, reward and transition functions that are definable in an o-minimal structure. Prominent examples of such games are finite, semi-algebraic or globally subanalytic stochastic games. We prove that the Shapley operator of any definable stochastic game with separable transition and reward functions is definable in the same structure. Definability in the same structure does not hold systematically: we provide a counterexample of a stochastic game with semi-algebraic data yielding a non semi-algebraic but globally subanalytic Shapley operator. Our definability results on Shapley operators are used to prove that any separable definable game has a uniform value; in the case of polynomially bounded structures we also provide convergence rates. Using an approximation procedure, we actually establish that general zero-sum games with separable definable transition functions have a uniform value. These results highlight the key role played by the tame structure of transition functions. As particular cases of our main results, we obtain that stochastic games with polynomial transitions, definable games with finite actions on one side, definable games with perfect information or switching controls have a uniform value. Applications to nonlinear maps arising in risk sensitive control and Perron-Frobenius theory are also given
Recommendations
Cites work
- A characterization of the optimal risk-sensitive average cost in finite controlled Markov chains
- A first course on zero-sum repeated games
- A nonsmooth version of Newton's method
- A zero-sum stochastic game with compact action sets and no asymptotic value
- Absorbing Games with Compact Action Spaces
- An Invitation to Tame Optimization
- An operator approach to zero-sum repeated games
- Asymptotic properties of monotonic nonexpansive mappings
- Asymptotics for a class of non-linear evolution equations, with applications to geometric problems
- Computing uniformly optimal strategies in two-player stochastic games
- Dynamic optimization of long-term growth rate for a portfolio with transaction costs and logarithmic utility.
- Existence of the limit value of two person zero-sum discounted repeated games via comparison theorems
- From max-plus algebra to nonexpansive mappings: A nonlinear theory for discrete event systems.
- Geometric categories and o-minimal structures
- Global subanalytic solutions of Hamilton--Jacobi type equations
- scientific article; zbMATH DE number 426213 (Why is no real title available?)
- scientific article; zbMATH DE number 3128726 (Why is no real title available?)
- scientific article; zbMATH DE number 1944711 (Why is no real title available?)
- scientific article; zbMATH DE number 2067976 (Why is no real title available?)
- scientific article; zbMATH DE number 2067977 (Why is no real title available?)
- scientific article; zbMATH DE number 3270364 (Why is no real title available?)
- Model Theory
- On the notion of value for games with infinitely many stages
- Repeated games with absorbing states
- Reversibility and oscillations in zero-sum discounted stochastic games
- Risk-Sensitive Control of Finite State Machines on an Infinite Horizon II
- Semianalytic and subanalytic sets
- Spectral theorem for convex monotone homogeneous maps, and ergodic control
- Stochastic games
- Stochastic Games
- Stochastic limit-average games are in EXPTIME
- Tame functions are semismooth
- The Asymptotic Solution of a Recursion Equation Occurring in Stochastic Games
- The Asymptotic Theory of Stochastic Games
- The maxmin of recursive games with incomplete information on one side
- The real field with convergent generalized power series
- The Semi-Algebraic Theory of Stochastic Games
- The value of repeated games with an informed controller
- The value of two-person zero-sum repeated games with lack of information on both sides
- Topical and sub-topical functions, downward sets and abstract convexity
- Uniform value in dynamic programming
- Zero Sum Absorbing Games with Incomplete Information on One Side: Asymptotic Analysis
Cited in
(16)- Uniformly supported approximate equilibria in families of games
- Solving two-state Markov games with incomplete information on one side
- An accretive operator approach to ergodic zero-sum stochastic games
- Communicating zero-sum product stochastic games
- The operator approach to entropy games
- The structure of Nash equilibria in Poisson games
- Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information
- Ergodicity conditions for zero-sum games
- Reversibility and oscillations in zero-sum discounted stochastic games
- Acyclic Gambling Games
- A zero-sum stochastic game with compact action sets and no asymptotic value
- Stochastic games
- The asymptotic value in finite stochastic games
- A formula for the value of a stochastic game
- Mertens conjectures in absorbing games with incomplete information
- Universal complexity bounds based on value iteration for stochastic mean payoff games and entropy games
This page was built for publication: Definable zero-sum stochastic games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5245020)
