隨機博弈:在博弈論中，隨機博弈是一種包含一個或多個參與者進行的具有狀態機 -百科知識中文網

概述

20世紀50年代早期，Lloyd Shapley提出了隨機博弈的概念。Neyman和Sorin所著的書籍是最完備的有關隨機博弈的參考材料。Filar和Vrieze所著的書更為基礎，在書中給出了嚴密的關於馬爾可夫決策過程和雙人隨機博弈的標準處理方法。他們創造了Competitive MDPs這個術語來概括單人和雙人隨機博弈這個概念。

規則

隨機博弈是指的是這樣的一個博弈遊戲，目前有任意堆石子，每堆石子個數也是任意的，雙方輪流從中取出石子，規則如下：

1、每一步應取走至少一枚石子；每一步只能從某一堆中取走部分或全部石子。

2、如果誰取到最後一枚石子就勝。

數學描述

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

博弈以某個初始狀態m1開始。在階段t中，參與者最先觀測到mt，同時選擇行動s^i_t\inS^i，然後觀測到行動組合s_t=(s^i_t)_i，然後以機率P(\cdot\midm_t,s_t)自然選擇mt+1。一次隨機博弈m_1,s_1,\ldots,m_t,s_t,\ldots定義了一個收益流g_1,g_2,\ldots，其中g_t=g(m_t,s_t)\,。

理論

在博弈論中，隨機博弈是一種包含一個或多個參與者進行的具有狀態機率轉移的動態博弈過程。隨機博弈由多個博弈階段組成。在每一個階段的開始，博弈處在某個特定狀態下。參與者選擇自身的策略並獲得相應的由當前狀態和策略決定的報酬。然後博弈按照機率的分布和參與者策略隨機轉移到下一個階段。在新的狀態階段，重複上一次的策略選擇過程，然後博弈繼續進行。參與者在隨機博弈中獲得的全部報酬一般用各個階段報酬的貼現值來計算，或者用各個階段報酬平均值的下限來計算。

如果隨機博弈中參與者的數量有限並且每個博弈階段可能的狀態數量有限，那么一個具有有限博弈階段的隨機博弈一般都存在一個納什均衡。同樣的，對於一個具有無窮階段的隨機博弈，如果使用各個階段報酬的貼現值來計算整個博弈階段的報酬，那么這個隨機博弈也是具有納什均衡的。Vieille已經證明具有有限階段和有限狀態的兩人隨機博弈當中，如果博弈過程的報酬使用各個階段報酬平均值的下限來計算的話，是具有逼近納什均衡的。然而，包含2個以上的參與者的隨機博弈是否存在納什均衡，仍然是個未決的問題。

隨機博弈在經濟學和演化生物學中都有套用。事實上，隨機博弈是重複博弈的一般化過程（重複博弈是指在每個博弈階段都處於相同的狀態）。

重要結論

貼現因子為λ（0<\lambda\leq1）的貼現博弈Γλ中，參與者i的收益是\lambda\sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^i_t。n階段博弈中，參與者i的收益是\bar{g}^i_n:=\frac1n\sum_{t=1}^ng^i_t。

若存在有限多個狀態和行動的二人零和博弈Γn（各自是Γλ）的值為vn(m1)（各自是vλ(m1)），則vn(m1)在n趨於無窮時收斂到一個極限，且vλ(m1)在λ趨於0時收斂到相同的極限。這一結論已被杜魯門·彪利（TrumanBewley）和艾朗·克爾伯格（ElonKohlberg）於1976年證明。

非貼現博弈\Gamma_\infty中，參與者i的收益是各階段收益平均值的極限。在定義二人零和博弈\Gamma_{\infty}的值與非零和博弈\Gamma_{\infty}的均衡收益之前需要注意一些事情：若對於每一\varepsilon>0都有正整數N、參與者1的策略\sigma_{\varepsilon}和參與者2的策略\tau_{\varepsilon}，二人零和隨機博弈\Gamma_\infty的一致值（uniformvalue）v_{\infty}存在，這樣對於每一σ、τ和每一n\geqN，博弈中由\sigma_{\varepsilon}和τ定義的機率的\bar{g}^i_n期望至少為v_{\infty}-\varepsilon，由σ和\tau_{\varepsilon}定義的機率的\bar{g}^i_n期望至多為v_{\infty}+\varepsilon。讓·弗朗索瓦·梅頓斯（JeanFrancoisMertens）和亞伯拉罕·奈曼（AbrahamNeyman）於1981年證明二人零和隨機博弈具有一致值。

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

套用

隨機博弈在經濟學、演化生物學和計算機網路中都有套用。事實上，隨機博弈是重複博弈的一般化過程（重複博弈是指在每個博弈階段都處於相同的狀態）。

亞伯拉罕·奈曼（AbrahamNeyman）和SylvainSorin所著的書籍是最完備的有關隨機博弈的參考材料。JerzyA.Filar和KoosVrieze所著的書更為基礎[1]，在書中給出了嚴密的關於[[馬爾可夫決策過程]（MDP）和雙人隨機博弈的標準處理方法。他們創造了CompetitiveMDPs這個術語來概括單人和雙人隨機博弈這個概念。