随机博弈
随机博弈(Stochastic games)
概述20世纪50年代早期，Lloyd Shapley提出了随机博弈的概念。Neyman和Sorin所著的书籍是最完备的有关随机博弈的参考材料。Filar和Vrieze所著的书更为基础，在书中给出了严密的关于马尔可夫决策过程和双人随机博弈的标准处理方法。他们创造了Competitive MDPs这个术语来概括单人和双人随机博弈这个概念。
随机博弈是指的是这样的一个博弈游戏，目前有任意堆石子，每堆石子个数也是任意的，双方轮流从中取出石子，规则如下：
1、每一步应取走至少一枚石子；每一步只能从某一堆中取走部分或全部石子。
2、如果谁取到最后一枚石子就胜。
随机博弈的阐析在博弈论中，随机博弈是一种包含一个或多个参与者进行的具有状态概率转移的动态博弈过程。随机博弈由多个博弈阶段组成。在每一个阶段的开始，博弈处在某个特定状态下。参与者选择自身的策略并获得相应的由当前状态和策略决定的报酬。然后博弈按照概率的分布和参与者策略随机转移到下一个阶段。在新的状态阶段，重复上一次的策略选择过程，然后博弈继续进行。参与者在随机博弈中获得的全部报酬一般用各个阶段报酬的贴现值来计算，或者用各个阶段报酬平均值的下限来计算。
如果随机博弈中参与者的数量有限并且每个博弈阶段可能的状态数量有限，那么一个具有有限博弈阶段的随机博弈一般都存在一个纳什均衡。同样的，对于一个具有无穷阶段的随机博弈，如果使用各个阶段报酬的贴现值来计算整个博弈阶段的报酬，那么这个随机博弈也是具有纳什均衡的。Vieille已经证明具有有限阶段和有限状态的两人随机博弈当中，如果博弈过程的报酬使用各个阶段报酬平均值的下限来计算的话，是具有逼近纳什均衡的。然而，包含2个以上的参与者的随机博弈是否存在纳什均衡，仍然是个未决的问题。
随机博弈在经济学和演化生物学中都有应用。事实上，随机博弈是重复博弈的一般化过程（重复博弈是指在每个博弈阶段都处于相同的状态）[1]。