隨機博弈

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

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

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

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

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

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

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

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