随机博弈

20世纪50年代早期，Lloyd Shapley提出了随机博弈的概念。Neyman和Sorin所著的书籍是最完备的有关随机博弈的参考材料。Filar和Vrieze所著的书更为基础，在书中给出了严密的关于马尔可夫决策过程和双人随机博弈的标准处理方法。他们创造了Competitive MDPs这个术语来概括单人和双人随机博弈这个概念。

随机博弈是指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：

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

2、如果谁取到最后一枚石子就胜。

随机博弈的组成部分有：有限参与者集I ；状态空间M （可以是有限集，也可以是可测空间(M,{mathcal A})）；对于每一参与者iin I，存在行动集S^i,（可以是有限集，也可以是可测空间(S^i,{mathcal S}^i)）；P 是Mtimes S到M 的转移概率，其中S=times_{iin I}S^i是行动组合，P(A mid m, s)是下一状态处于A 中的概率，而A 给定了当前状态m 和当前行动组合s ；从Mtimes S到R^I,的收益函数g，其中g 的第i 个坐标g^i,是参与者i 的收益，而g^i, 是状态m 和行动组合s 的函数。

博弈以某个初始状态m1 开始。在阶段t 中，参与者最先观测到mt ，同时选择行动s^i_tin S^i，然后观测到行动组合s_t=(s^i_t)_i，然后以概率P(cdotmid m_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 leq 1）的贴现博弈Γλ 中，参与者i 的收益是lambda sum_{t=1}^{infty}(1-lambda)^{t-1}g^i_t 。n 阶段博弈中，参与者i 的收益是bar{g}^i_n:=frac1nsum_{t=1}^ng^i_t 。

若存在有限多个状态和行动的二人零和博弈Γn（各自是Γλ）的值为vn(m1)（各自是vλ(m1)），则vn(m1) 在n 趋于无穷时收敛到一个极限，且vλ(m1)在λ趋于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}存在，这样对于每一σ、τ和每一ngeq N，博弈中由sigma_{varepsilon}和τ定义的概率的bar{g}^i_n期望至少为v_{infty} -varepsilon，由σ和tau_{varepsilon}定义的概率的bar{g}^i_n期望至多为v_{infty} +varepsilon。让·弗朗索瓦·梅顿斯（Jean Francois Mertens）和亚伯拉罕·奈曼（Abraham Neyman）于1981年证明二人零和随机博弈具有一致值。

若参与者数量有限且行动集和状态集有限，则有限阶段随机博弈总有纳什均衡，对于总收益是贴现和的无限多阶段随机博弈也是如此。尼古拉斯·维勒（Nicolas Vieille）已经证明当总收益是各阶段收益平均值的下极限时，所有具有有限状态和行动空间的二人随机博弈都有近似纳什均衡。不过，当参与者多于2名时，随机博弈是否存在这类均衡仍是一个极具挑战性的开放性问题。

随机博弈在经济学、演化生物学和计算机网络中都有应用。事实上，随机博弈是重复博弈的一般化过程（重复博弈是指在每个博弈阶段都处于相同的状态）。

亚伯拉罕·奈曼（Abraham Neyman）和Sylvain Sorin所著的书籍是最完备的有关随机博弈的参考材料。Jerzy A. Filar和Koos Vrieze所著的书更为基础[1]，在书中给出了严密的关于[[马尔可夫决策过程]（MDP）和双人随机博弈的标准处理方法。他们创造了Competitive MDPs这个术语来概括单人和双人随机博弈这个概念。^[1]