隨機賽局

隨機賽局（英語：stochastic game），或稱隨機博弈、隨機對局，在賽局理論中是一類由一個或多個參與者所進行的、具有狀態概率轉移的動態賽局，由勞埃德·夏普利（Lloyd Shapley）於20世紀50年代初期提出。

定義

這類賽局由一系列階段組成。在賽局中每一階段的起始，賽局處於某種特定狀態。每一參與者選擇某種行動，然後會獲得取決於當前狀態和所選擇行動的收益。之後，賽局發展到下一階段，處於一個新的隨機狀態，這一隨機狀態的分布取決於先前狀態和各位參與者選擇的行動。在新狀態中重複上述過程，然後賽局繼續進行有限或無限個數的階段。一個參與者得到的總收益常用各階段收益的貼現和，或是各階段收益平均值的下極限來計算。

數學描述

隨機賽局的組成部分有：有限參與者集$I$ ；狀態空間$M$ （可以是有限集，也可以是可測空間$(M,{\mathcal {A}})$）；對於每一參與者$i\in I$，存在行動集$S^{i}\,$（可以是有限集，也可以是可測空間$(S^{i},{\mathcal {S}}^{i})$）；$P$ 是$M\times S$到$M$ 的轉移概率，其中$S=\times _{i\in I}S^{i}$是行動組合，$P(A\mid m,s)$是下一狀態處於$A$ 中的概率，而$A$ 給定了當前狀態$m$ 和當前行動組合$s$ ；從$M\times S$到$R^{I}\,$的收益函數$g$，其中$g$ 的第$i$ 個坐標$g^{i}\,$是參與者$i$ 的收益，而$g^{i}\,$ 是狀態$m$ 和行動組合$s$ 的函數。

賽局以某個初始狀態$m_{1}$ 開始。在階段$t$ 中，參與者最先觀測到$m_{t}$ ，同時選擇行動$s_{t}^{i}\in S^{i}$，然後觀測到行動組合$s_{t}=(s_{t}^{i})_{i}$，然後以概率$P(\cdot \mid m_{t},s_{t})$自然選擇$m_{t+1}$ 。一次隨機賽局$m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots$定義了一個收益流$g_{1},g_{2},\ldots$，其中$g_{t}=g(m_{t},s_{t})\,$ 。

例子

下面給出隨機賽局的一個例子：

當前有任意個裝著球的桶，每個桶中球的數目也是任意的，兩位參與者輪流從中取出球，且需要遵守如下規則：

1. 每一步應至少取出一隻球，且只能從某一桶中取走部分或全部球；
2. 誰取到最後一隻球，誰就獲勝。

重要結論

貼現因子為$\lambda$（$0<\lambda \leq 1$）的貼現賽局$\Gamma _{\lambda }$ 中，參與者$i$ 的收益是$\lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}$ 。$n$ 階段賽局中，參與者$i$ 的收益是${\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}$ 。

若存在有限多個狀態和行動的二人零和賽局$\Gamma _{n}$（各自是$\Gamma _{\lambda }$）的值為$v_{n}(m_{1})$（各自是$v_{\lambda }(m_{1})$），則$v_{n}(m_{1})$ 在$n$ 趨於無窮時收斂到一個極限，且$v_{\lambda }(m_{1})$在$\lambda$趨於$0$時收斂到相同的極限。這一結論已被杜魯門·彪利（Truman Bewley）和艾朗·克爾伯格（Elon Kohlberg）於1976年證明。

非貼現賽局$\Gamma _{\infty }$中，參與者$i$ 的收益是各階段收益平均值的極限。在定義二人零和賽局$\Gamma _{\infty }$的值與非零和賽局$\Gamma _{\infty }$的均衡收益之前需要注意一些事情：若對於每一$\varepsilon >0$都有正整數$N$ 、參與者1的策略$\sigma _{\varepsilon }$和參與者2的策略$\tau _{\varepsilon }$，二人零和隨機賽局$\Gamma _{\infty }$的一致值（uniform value）$v_{\infty }$存在，這樣對於每一$\sigma$、$\tau$和每一$n\geq N$，賽局中由$\sigma _{\varepsilon }$和$\tau$定義的概率的${\bar {g}}_{n}^{i}$期望至少為$v_{\infty }-\varepsilon$，由$\sigma$和$\tau _{\varepsilon }$定義的概率的${\bar {g}}_{n}^{i}$期望至多為$v_{\infty }+\varepsilon$。讓·弗朗索瓦·梅頓斯（Jean Francois Mertens）和亞伯拉罕·奈曼（Abraham Neyman）於1981年證明二人零和隨機賽局具有一致值。

若參與者數量有限且行動集和狀態集有限，則有限階段隨機賽局總有納許均衡，對於總收益是貼現和的無限多階段隨機賽局也是如此。尼古拉斯·維勒（Nicolas Vieille）已經證明當總收益是各階段收益平均值的下極限時，所有具有有限狀態和行動空間的二人隨機賽局都有近似納許均衡。不過，當參與者多於2名時，隨機賽局是否存在這類均衡仍是一個極具挑戰性的開放性問題。

應用

隨機賽局在經濟學、演化生物學和計算機網絡中都有應用。事實上，隨機賽局是重複賽局這類每一階段都處於相同狀態的賽局的一般化形式。

有關隨機賽局的最全面的參考書籍是奈曼和索林編著的文集。菲拉爾和烏瑞茲所著的書籍更為基礎，書中提供了馬爾可夫決策過程（MDP）和二人隨機賽局理論的嚴密的統一處理方法。他們創造了Competitive MDPs這一術語來概括一人和二人隨機賽局。

參考文獻

一般參考

• Anne Condon. The complexity of stochastic games. Information and Computation. 1992, 96 (2): 第203－224頁 [2010-09-07]. ISSN 0890-5401. doi:10.1016/0890-5401(92)90048-K. （原始內容存檔於2013-06-03）.