隨機博弈

隨機博弈（英語：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）.