随机博弈 – 12Reads管理百科

随机博弈简介

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

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

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

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

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

数学描述

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

博弈以某个初始状态 $m 1$ 开始。在阶段 $t$ 中，参与者最先观测到 $m t$ ，同时选择行动 $s^i_t\in S^i$ ，然后观测到行动组合 $s_t=(s^i_t)_i$ ，然后以概率 $P(\cdot\mid m_t,s_t)$ 自然选择 $m t + 1$ 。一次随机博弈 $m_1,s_1,\ldots,m_t,s_t,\ldots$ 定义了一个收益流 $g_1,g_2,\ldots$ ，其中 $g_t=g(m_t,s_t)\,$ 。

随机博弈的阐析

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

如果随机博弈中参与者的数量有限并且每个博弈阶段可能的状态数量有限，那么一个具有有限博弈阶段的随机博弈一般都存在一个纳什均衡。同样的，对于一个具有无穷阶段的随机博弈，如果使用各个阶段报酬的贴现值来计算整个博弈阶段的报酬，那么这个随机博弈也是具有纳什均衡的。尼古拉斯·维勒（Nicolas 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:=\frac1n\sum_{t=1}^ng^i_t$ 。

若存在有限多个状态和行动的二人零和博弈 $Γ n$ （各自是 $Γλ$ ）的值为 $v n (m 1)$ （各自是 $v λ(m 1)$ ），则 $v n (m 1)$ 在 $n$ 趋于无穷时收敛到一个极限，且 $v λ(m 1)$ 在 $λ$ 趋于 $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}$ 存在，这样对于每一 $σ$ 、 $τ$ 和每一 $n\geq 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所著的书更为基础，在书中给出了严密的关于（MDP）和双人随机博弈的标准处理方法。他们创造了Competitive MDPs这个术语来概括单人和双人随机博弈这个概念。