1 What are Stochastic Games?
Stochastic games ([[shapley1964|Shapley, 1953]]) are multi-player dynamic games in which a finite set of agents interact repeatedly over time in a shared, evolving environment. At each stage, every player observes the current state of the system, simultaneously chooses an action, receives a payoff, and the system transitions to a new state according to a Markov kernel that depends on the joint action profile. Each player aims to optimize their cumulative (discounted or average) payoff over the horizon.
Stochastic games unify and generalize two classical frameworks: Markov Decision Processes (the single-agent special case) and repeated games (the special case where the state never changes). The central solution concept is the Markov Perfect Equilibrium (MPE) — a profile of state-dependent strategies, one per player, such that no player can gain by deviating, given the others’ strategies.
2 Topics in Stochastic Games
- Preliminaries
- Stochastic Process
- Markov Processes
- Martingales
- Stochastic Differential Equations
- Stochastic Control
- Stochastic Process
- Foundations
- Formal model: states, action spaces, transition kernel, stage payoffs, horizon
- Relationship to MDPs and repeated games
- Equilibrium concepts: Nash, Sub-game Perfect, Markov Perfect, Correlated
- Existence results (Shapley 1953, Fink 1964)
- Computational complexity (PPAD-hardness of general-sum MPE)
- Discrete-Time Stochastic Games
- Finite-horizon games and backward induction
- Infinite-horizon discounted payoff
- Infinite-horizon average (ergodic) payoff
- Zero-sum games
- Shapley operator and value iteration
- Policy / strategy iteration (Hoffman–Karp)
- Linear programming formulation
- General-sum N-player games
- Nash value iteration and convergence conditions
- Homotopy / continuation methods (Herings–Peeters)
- Nonlinear complementarity and mathematical programming formulations
- Correlated equilibrium and no-regret learning
- Continuous-Time Stochastic Games
- Differential games (deterministic dynamics)
- Stochastic differential games (SDE-driven state)
- Zero-sum differential games and the Hamilton–Jacobi–Isaacs equation
- Non-zero-sum differential games and coupled HJB systems
- Special Structural Classes
- Potential games and Markov potential games
- Super-modular / monotone stochastic games
- Symmetric and anonymous games
- Cooperative stochastic games and the core
- Mean Field Games
- Finite-N to mean-field limit (propagation of chaos)
- Discrete-time mean-field games
- Continuous-time mean-field games
- HJB + Fokker-Planck Equation system
- McKean–Vlasov control
- Linear-quadratic mean-field games
- Mean-field games with major and minor players
- Numerical methods for mean-field games
- Multi-Agent Reinforcement Learning
- Nash-Q learning
- Policy gradient and actor–critic methods
- Two-timescale stochastic approximation
- No-regret dynamics and convergence to equilibrium
- MARL in the mean-field regime
- Heterogeneous Agent Games
- Markov-perfect industry dynamics (Ericson–Pakes framework)
- Oblivious equilibrium as a scalable approximation
- Computational methods for heterogeneous-state MPE
- Applications
- Dynamic industrial organization and oligopoly
- Finance: optimal stopping, systemic risk, algorithmic trading
- Robotics and autonomous multi-agent systems
- Evolutionary biology and population games