Shapely's "Stochastic Games": An upper bound on each player's gain

Question

In a stochastic game the play proceeds by steps from position to position, according to transition probabilities controlled jointly by the two players. We shall assume a finite number, $N$, of positions, and finite numbers $m_k$, $n_k$ of choices at each position; nevertheless, the game may not be bounded in length. If, when at position $k$, the players choose their $i$th and $j$th alternatives, respectively, then with probability $s^k_{ij} > 0$ the game stops, while with probability $p^{kl}_{ij}$ the game moves to position $l$. Define $$ s = \min_{k, i, j} s^k_{ij} $$ Since $s$ is positive, the game ends with probability $1$ after a finite number of steps, because, for any number $t$, the probability that it has not stopped after $t$ steps is not more than $(1 - s)^t$.

Payments accumulate throughout the course of the play: the first player takes $a^k_{i,j}$ from the second whenever the pair $i$, $j$ is chosen at position $k$. If we define the bound $M$: $$ M = \max_{k, i, j} |a^k_{i,j}| $$ then we see that the expected total gain or loss is bounded by $$ M + (1 - s)M + (1 - s)^2M + \cdots = M / s $$

---

The above is the beginning of the classic article "Stochastic Games" by L. S. Shapely published in 1953. I don't understand the justification for the bound given in the last line. I would say that, setting $S := \max_{k, i, j} s^k_{ij}$, the expected total gain or loss is bounded by $$ (1 - s)S\cdot M + (1 - s)^2S\cdot 2M + (1 - s)^2S\cdot 3M + \cdots $$ since the probability for a game of length exactly $n$ is bounded above by $(1 - s)^nS$ and the gain for such a game is bounded above by $nM$.

Could someone please explain to me why the bound given by Shapely holds?

Answer 1

We implicitly assume that one of the game's positions $k^*$ is designated as the starting position and that one of the possible choices $(i^*, j^*)$ at that position is designated as the starting choice. The number of steps in the game is the length of the sequence of positions that the game assumed until it stopped, including the starting position.

Denote by $p_n$ the probability that the game's length is exactly $n \in \mathbb{N}_1 = \{1, 2, 3, \dots\}$ and by $P_n$ the probability that its length is at least $n$. Note that $P_{n} \leq (1 - s)^{n - 1}$. Then the following expression is an upper bound on the expected gain/loss of each player: $$ \sum_{n = 1}^\infty nM \cdot p_n $$

We will show that the last expression is bounded from above by the bound given by Shapely. $$ \begin{align} \sum_{n = 1}^\infty nM \cdot p_n & = \sum_{n = 1}^\infty \sum_{m = 1}^n Mp_n \\ & = \sum_{m = 1}^\infty \sum_{n = m}^\infty Mp_n \\ &= \sum_{m = 1}^\infty M \sum_{n = m}^\infty p_n \\ & = \sum_{m = 1}^\infty P_m \cdot M \\ & \leq \sum_{m = 1}^\infty (1 - s)^{m - 1} M \end{align} $$

Note that the last expression is precisely Shapely's bound.

Answer 2

the probability that it has not stopped after $t$ steps is not more than $(1−s)^t$.

I believe this is the key part of the author's reasoning. He is adding:

$$\sum_{t=1}^{\infty} \text{Hasn't stopped after t steps} \times \text{Payout for that step}$$

Since these aren't independent cases, the estimate is an over estimate, but with all the approximations made for $M$ and $s$ the overestimate is negligible. And the author is only establishing an upper bound.

You seem to be computing:

$$\sum_{t=1}^{\infty} \text{Stops after exactly t steps} \times \text{Payout for all of the steps}$$

which is more exact, but so many approximations went into the definition of $M$ and $s$ that the accuracy probably isn't helpful.

Also, my estimate is not tighter than Shapely's, it is in fact strictly bigger than his, since at some point S⋅nM will be strictly greater than M.

Your approximation should be written $SM + (1-s)S2M + \dots (1-s)^{k-1}SkM \dots$.

It is solvable:

$$f(x) = SM \sum_{k=0}^\infty kx^k$$ If $g(x) = \sum_{k=0}^\infty x^k = 1/(1-x)$, then $g'(x)xSM = f(x)$, so $$f(1-s) = \frac{(1 - s)MS}{s^2}$$

and comparing $\frac{(1 - s)MS}{s^2}$ to $M/s$, it seems to depend on the values of $S$ and $s$, but when $S=s$ then yours is lesser.