随机博弈

随机博弈(Stochastic Games)

　　在博弈论中，随机博弈是一类由一个或多个参与者进行的、具有状态概率转移的动态博弈，是由劳埃德·夏普利（Lloyd Shapley）于20世纪50年代初期提出。

　　随机博弈由一系列阶段组成。在博弈中每一阶段的起始，博弈处于某种特定状态。每一参与者选择某种行动，然后会获得取决于当前状态和所选择行动的收益。之后，博弈发展到下一阶段，处于一个新的随机状态，这一随机状态的分布取决于先前状态和各位参与者选择的行动。在新状态中重复上述过程，然后博弈继续进行有限或无限个数的阶段。一个参与者得到的总收益常用各阶段收益的贴现和，或是各阶段收益平均值的下限来计算。

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

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

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

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

　　博弈以某个初始状态m₁ 开始。在阶段t 中，参与者最先观测到m_t ，同时选择行动，然后观测到行动组合，然后以概率自然选择m_{t + 1} 。一次随机博弈定义了一个收益流，其中 。

　　随机博弈由多个博弈阶段组成。在每一个阶段的开始，博弈处在某个特定状态下。参与者选择自身的策略并获得相应的由当前状态和策略决定的报酬。然后博弈按照概率的分布和参与者策略随机转移到下一个阶段。在新的状态阶段，重复上一次的策略选择过程，然后博弈继续进行。参与者在随机博弈中获得的全部报酬一般用各个阶段报酬的贴现值来计算，或者用各个阶段报酬平均值的下限来计算。

　　如果随机博弈中参与者的数量有限并且每个博弈阶段可能的状态数量有限，那么一个具有有限博弈阶段的随机博弈一般都存在一个纳什均衡。同样的，对于一个具有无穷阶段的随机博弈，如果使用各个阶段报酬的贴现值来计算整个博弈阶段的报酬，那么这个随机博弈也是具有纳什均衡的。尼古拉斯·维勒（Nicolas Vieille）已经证明具有有限阶段和有限状态的两人随机博弈当中，如果博弈过程的报酬使用各个阶段报酬平均值的下限来计算的话，是具有逼近纳什均衡的。然而，包含2个以上的参与者的随机博弈是否存在纳什均衡，仍然是个未决的问题。

　　贴现因子为λ（）的贴现博弈Γ_λ 中，参与者i 的收益是 。n 阶段博弈中，参与者i 的收益是 。

　　若存在有限多个状态和行动的二人零和博弈Γ_n（各自是Γ_λ）的值为v_n(m₁)（各自是v_λ(m₁)），则v_n(m₁) 在n 趋于无穷时收敛到一个极限，且v_λ(m₁)在λ趋于0时收敛到相同的极限。这一结论已被杜鲁门·彪利（Truman Bewley）和艾朗·克尔伯格（Elon Kohlberg）于1976年证明。

　　非贴现博弈中，参与者i 的收益是各阶段收益平均值的极限。在定义二人零和博弈的值与非零和博弈的均衡收益之前需要注意一些事情：若对于每一都有正整数N 、参与者1的策略和参与者2的策略，二人零和随机博弈的一致值（uniform value）存在，这样对于每一σ、τ和每一，博弈中由和τ定义的概率的期望至少为，由σ和定义的概率的期望至多为。让·弗朗索瓦·梅顿斯（Jean Francois Mertens）和亚伯拉罕·奈曼（Abraham Neyman）于1981年证明二人零和随机博弈具有一致值。

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

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

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