Submixing and shift-invariant stochastic games

DOI10.1007/S00182-023-00860-5MaRDI QIDQ6183353zbMATH OpenOpenAlexFDO

Authors Hugo Gimbert, Edon Kelmendi

Publication date 4 January 2024

Published in International Journal of Game Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1401.6575

zbMATH Keywords

stochastic gamesshift-invariantepsilon subgame perfect strategiesfinite memory optimal strategieshalf positionalsubmixing

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Abstract: We consider zero-sum stochastic games with perfect information and finitely many states and actions. The payoff is computed by a function which associates to each infinite sequence of states and actions a real number. We prove that if the payoff function is both shift-invariant and submixing, then the game is half-positional, i.e. the first player has an optimal strategy which is both deterministic and stationary. This result relies on the existence of epsilon-subgame-perfect strategies in shift-invariant games, a second contribution of the paper. The techniques can be used to establish a third result: for shift-invariant and submixing payoff functions, the existence of finite-memory strategies for player 2 in one-player games implies the same property for two-player games as well.

Recommendations

• Subgame-Perfect Equilibria for Stochastic Games
• On completely mixed stochastic games
• Subgame perfect equilibria in discounted stochastic games
• Strongly subgame consistent core in stochastic games
• Subgame-consistent cooperative solutions in randomly furcating stochastic dynamic games
• Subgame consistent solutions for cooperative stochastic dynamic games
• Sub-Gaussians in game-theoretic probability
• Subgame-perfect equilibria in stochastic timing games
• Subgame consistent cooperative solutions in stochastic differential games

Cites work

• scientific article; zbMATH DE number 177825 (Why is no real title available?)
• scientific article; zbMATH DE number 2013849 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• scientific article; zbMATH DE number 893883 (Why is no real title available?)
• scientific article; zbMATH DE number 7559480 (Why is no real title available?)
• A finite algorithm for the switching control stochastic game
• An expected average reward criterion
• Automata, logics, and infinite games. A guide to current research
• CONCUR 2005 – Concurrency Theory
• Compositional strategy synthesis for stochastic games with multiple objectives
• Correlated equilibria in stochastic games with Borel measurable payoffs
• Foundations of Software Science and Computation Structures
• Games with delays -- a Frankenstein approach
• Generalized mean-payoff and energy games
• Half-Positional Determinacy of Infinite Games
• Mathematical Foundations of Computer Science 2004
• On sequential decisions and Markov chains
• One-counter stochastic games
• Perfect Information Stochastic Priority Games
• Perfect-information stochastic games with generalized mean-payoff objectives
• Playing in stochastic environment: from multi-armed bandits to two-player games
• Probability with Martingales
• Pure Stationary Optimal Strategies in Markov Decision Processes
• Quantitative stochastic parity games
• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Stochastic Games
• Stochastic Games with Perfect Information and Time Average Payoff
• Subgame maxmin strategies in zero-sum stochastic games with tolerance levels
• The determinacy of Blackwell games

This page was built for publication: Submixing and shift-invariant stochastic games

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