Stochastic games. (English) Zbl 0051.35805

Shapley, L. S.

Proc. Natl. Acad. Sci. USA 39, 1095-1100 (1953).

Es wird eine weitgehende Verallgemeinerung des (2-Personen-0-Summen-)Matrixspieles behandelt. \(N\) Positionen \(1,\dots ,N\) durchlaufen zwei Spieler \(A,B\) in der folgenden Weise: In der Position \(k\) wählen \(A\) und \(B\) unabhängig voneinander je eine natürliche Zahl \(i\) bzw. \(j\), \(1\leq i\leq m_k, 1\leq j\leq n_k\). Nachdem \(B\) an \(A\) den Betrag \(a_{ij}^k\) bezahlt hat, geht das Spiel mit der Wahrscheinlichkeit \(s_{ij}^k\) zu Ende und mit der Wahrscheinlichkeit \(p_{ij}^{kl}\) zur Position \(l\) über, wo in der gleichen Weise verfahren wird. \((a_{ij}^k),(s_{ij}^k),(p_{ij}^{kl})\) sind also für jedes \(k\) bzw. \(k,l\) definierte Matrizen mit reellen Koeffizienten, \(s_{ij}^k+\sum_l p_{ij}^{kl}=1\). Wird in \(k\) begonnen, so sei dadurch das Spiel \(\Gamma^k\) erklärt. Die Zusammenfassung \((\Gamma^1,\dots ,\Gamma^N)\) nennt Verf. das “stochastische Spiel” \(\Gamma \). \(\Gamma^k\) ist ein 2-Personen-0-Summenspiel. Wegen der nicht beschränkten Längen der einzelnen Partien ordnet sich \(\Gamma^k\) jedoch nicht unmittelbar in den Gültigkeitsbereich des Minmax-Prinzips J. v. Neumanns ein. Es wird aber gezeigt: \(\Gamma^k\) besitzt einen Wert \(\varPhi^k\) derart, dass \(A\) bzw. \(B\) durch gemischte Strategien im Mittel über eine genügend große Partienzahl \(\varPhi^k\) bzw. \(-\varPhi^k\) als Gewinn beliebig genau erzwingen kann. \(\varPhi=(\varPhi^1,\dots ,\varPhi^N)\) stellt sich als einzige Lösung des Systems \[ \varPhi^k=\mathrm{val}\left(a_{ij}^k+\sum_l \, p_{ij}^{kl} \varPhi^l\right),\quad k=1,\dots ,N, \] dar,wobei allgemein \(\mathrm{val}(r_{ik})\) der Wert des zur Matrix \((r_{ik})\) gehörigen Matrixspiels im v. Neumannschen Sinne ist. Unter den optimalen Strategien existieren für beide Spieler sogenannte stationäre, das sind solche, bei denen das Verhalten der Spieler in jeder Position \(k\) nur von \(k\) und nicht auch von dem vorausgegangenen Spielablauf abhängt.

Reviewer: W. Gaschütz

MSC:

91A15

Stochastic games, stochastic differential games

Keywords:

probability theory