随机博弈

简述

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

规则

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

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

2、假使谁取到最后一枚石子就胜。

数学描述

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

博弈以某个初始状态m1开始。在阶段t中，参与者最先观测到mt，同期选择行动s^i_tinS^i，然后观测到行动组合s_t=(s^i_t)_i，然后以几率P(cdotmidm_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

若存在有限多个状态和行动的二人零和博弈Γ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}存在，如此对于每一σ、τ和每一ngeqN，博弈中由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这个术语来概括单人和双人随机博弈这个概念。^[1]