2014/01/25 by Hugo Gimbert, Gimbert, Hugo, Edon Kelmendi +1 · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic Policies and Impacts #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1401.6575
openalex publication_date 2014/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.