Submixing and shift-invariant stochastic games

DOI10.1007/S00182-023-00860-5zbMATH Open1530.91048arXiv1401.6575OpenAlexW3157164353MaRDI QIDQ6183353FDOQ6183353

Authors: Hugo Gimbert, Edon Kelmendi 

Publication date: 4 January 2024

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

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.

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

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

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)

Cites Work

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

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)