Discounted Stochastic Game Equilibrium

Context

Fink1964 - Equilibrium in a Stochastic n-Person Game proves existence of stationary mixed-strategy equilibria for finite discounted stochastic n-person games. The proof is useful background for later Markov-game and MARL notes because it isolates the classical fixed-point structure before adding learning dynamics, constraints, or neural approximators.

Formal Statement

In the cost-minimizing convention, let:

• I be a finite state set;
• J_h(i) be player h’s finite action set at state i;
• P_{ijk} be the probability of next state k after state i and joint action j=(j_1,...,j_n);
• C_{hij} be player h’s one-step cost;
• alpha_h in (0,1) be player h’s discount factor.

Then there exists a stationary mixed profile x and value vector v such that, for every player h and state i, player h cannot lower its expected discounted cost by changing its own state-wise mixed action while the other players’ stationary strategies stay fixed:

$$v_{hi}=f(x,x,v{)}_{hi}=\underset{y^h(i)}{\min }f(x,y,v{)}_{hi}.$$

Equivalently, a finite discounted stochastic n-person game has a stationary mixed-strategy equilibrium.

Derivation / Construction

For a fixed stationary profile x, the expected discounted cost vector satisfies:

$$e_{hi}(x)=\sum _j\prod _m{x}_{j_m}^m(i)\left[C_{hij}+{\alpha }_h\sum _k{P}_{ijk}{e}_{hk}(x)\right].$$

The associated linear system has a unique solution because discounting keeps the relevant operator away from singularity.

For best responses, define f(x,y,v)_{hi} as the one-step expected cost plus discounted continuation value when all players other than h follow x, while player h uses the candidate mixed action y^h(i) at state i. Define:

$$T_{x}v=\underset{y}{\min }f(x,y,v).$$

Fink shows T_x is a contraction on the value-vector space with modulus at most a=max_h alpha_h. Hence, for every x, there is a unique fixed value vector beta(x).

Next define the best-response correspondence phi(x) as the set of mixed profiles attaining the componentwise minima against beta(x). The proof establishes that phi(x) is nonempty, convex, closed, and upper semicontinuous. Kakutani’s fixed-point theorem yields x in phi(x), so:

$$v=f(x,x,v)=\underset{y}{\min }f(x,y,v).$$

This is the desired stationary equilibrium condition.

Implications

• Discounting is the key contraction source; without it, equilibrium existence and value characterization require different machinery.
• The proof separates two tasks that modern MARL often entangles: evaluating a fixed joint policy and finding a mutually stable strategic profile.
• Fink observes that the argument still works on closed convex subsets of the stationary-strategy space, which gives a classical precursor to constrained-game existence questions.
• The theorem is an existence result, not a learning algorithm. It does not imply independent learners will converge to the equilibrium.

Links

• Source: Fink1964 - Equilibrium in a Stochastic n-Person Game
• Concept: Stochastic Games
• Related modern concept: Constrained Markov Potential Games