随机博弈

随机博弈（英语：stochastic game），或称随机赛局、随机对局，在博弈论中是一类由一个或多个参与者所进行的、具有状态概率转移的动态博弈，由劳埃德·夏普利（Lloyd Shapley）于20世纪50年代初期提出。^[1]

定义

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

数学描述

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

博弈以某个初始状态${\displaystyle m_{1}}$ 开始。在阶段${\displaystyle t}$ 中，参与者最先观测到${\displaystyle m_{t}}$ ，同时选择行动${\displaystyle s_{t}^{i}\in S^{i}}$，然后观测到行动组合${\displaystyle s_{t}=(s_{t}^{i})_{i}}$，然后以概率${\displaystyle P(\cdot \mid m_{t},s_{t})}$自然选择${\displaystyle m_{t+1}}$ 。一次随机博弈${\displaystyle m_{1},s_{1},\ldots ,m_{t},s_{t},\ldots }$定义了一个收益流${\displaystyle g_{1},g_{2},\ldots }$，其中${\displaystyle g_{t}=g(m_{t},s_{t})\,}$ 。

例子

下面给出随机博弈的一个例子：

当前有任意个装着球的桶，每个桶中球的数目也是任意的，两位参与者轮流从中取出球，且需要遵守如下规则：

1. 每一步应至少取出一只球，且只能从某一桶中取走部分或全部球；
2. 谁取到最后一只球，谁就获胜。

重要结论

贴现因子为${\displaystyle \lambda }$（${\displaystyle 0<\lambda \leq 1}$）的贴现博弈${\displaystyle \Gamma _{\lambda }}$ 中，参与者${\displaystyle i}$ 的收益是${\displaystyle \lambda \sum _{t=1}^{\infty }(1-\lambda )^{t-1}g_{t}^{i}}$ 。${\displaystyle n}$ 阶段博弈中，参与者${\displaystyle i}$ 的收益是${\displaystyle {\bar {g}}_{n}^{i}:={\frac {1}{n}}\sum _{t=1}^{n}g_{t}^{i}}$ 。

若存在有限多个状态和行动的二人零和博弈${\displaystyle \Gamma _{n}}$（各自是${\displaystyle \Gamma _{\lambda }}$）的值为${\displaystyle v_{n}(m_{1})}$（各自是${\displaystyle v_{\lambda }(m_{1})}$），则${\displaystyle v_{n}(m_{1})}$ 在${\displaystyle n}$ 趋于无穷时收敛到一个极限，且${\displaystyle v_{\lambda }(m_{1})}$在${\displaystyle \lambda }$趋于${\displaystyle 0}$时收敛到相同的极限。这一结论已被杜鲁门·彪利（Truman Bewley）和艾朗·克尔伯格（Elon Kohlberg）于1976年证明。^[2]

非贴现博弈${\displaystyle \Gamma _{\infty }}$中，参与者${\displaystyle i}$ 的收益是各阶段收益平均值的极限。在定义二人零和博弈${\displaystyle \Gamma _{\infty }}$的值与非零和博弈${\displaystyle \Gamma _{\infty }}$的均衡收益之前需要注意一些事情：若对于每一${\displaystyle \varepsilon >0}$都有正整数${\displaystyle N}$ 、参与者1的策略${\displaystyle \sigma _{\varepsilon }}$和参与者2的策略${\displaystyle \tau _{\varepsilon }}$，二人零和随机博弈${\displaystyle \Gamma _{\infty }}$的一致值（uniform value）${\displaystyle v_{\infty }}$存在，这样对于每一${\displaystyle \sigma }$、${\displaystyle \tau }$和每一${\displaystyle n\geq N}$，博弈中由${\displaystyle \sigma _{\varepsilon }}$和${\displaystyle \tau }$定义的概率的${\displaystyle {\bar {g}}_{n}^{i}}$期望至少为${\displaystyle v_{\infty }-\varepsilon }$，由${\displaystyle \sigma }$和${\displaystyle \tau _{\varepsilon }}$定义的概率的${\displaystyle {\bar {g}}_{n}^{i}}$期望至多为${\displaystyle v_{\infty }+\varepsilon }$。让·弗朗索瓦·梅顿斯（Jean Francois Mertens）和亚伯拉罕·奈曼（Abraham Neyman）于1981年证明二人零和随机博弈具有一致值。^[3]

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

应用

随机博弈在经济学、演化生物学和计算机网络中都有应用。^[5]事实上，随机博弈是重复博弈这类每一阶段都处于相同状态的博弈的一般化形式。

有关随机博弈的最全面的参考书籍是奈曼和索林编著的文集。^[2]菲拉尔和乌瑞兹所著的书籍更为基础，书中提供了马尔可夫决策过程（MDP）和二人随机博弈理论的严密的统一处理方法。^[6]他们创造了Competitive MDPs这一术语来概括一人和二人随机博弈。

参考文献

注释

1. Lloyd Stowell Shapley. Stochastic games. Proc. Nat. Acad. Sciences. October 1953, 39 (10): 第1095－1100页. ISSN 1091-6490. PMC 1063912 .
2. Abraham Neyman，Sylvain Sorin. Stochastic Games and Applications. Kluwer Academic Press. 2003年10月31日. ISBN 978-1402014932 （英语）.
3. Jean Francois Mertens，Abraham Neyman. Stochastic Games (PDF). International Journal of Game Theory. June 1981, 10 (2): 第53－66页. ISSN 0020-7276.^{[永久失效链接]} 电子版：ISSN 1432-1270
4. Nicolas Vieille. Stochastic games: Recent results. R.J. Aumann，S. Hart (编). Handbook of Game Theory with Economic Applications. North-Holland. 2002年9月2日: 第1833–1850页 [2010年9月7日]. ISBN 978-0-444-89428-1. doi:10.1016/S1574-0005(02)03011-4. （原始内容 (精装书)存档于2018年1月2日） （英语）.
5. Eitan Altman，Konstantin Avrachenkov，Nicolas Bonneau，Mérouane Debbah，Rachid El-Azouzi，Daniel Menasché. Constrained Stochastic Games in Wireless Networks. Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE. Washington, DC: 第315－320页. 2007年11月26日－30日 [2010年9月7日]. doi:10.1109/GLOCOM.2007.66. ISBN 978-1-4244-1043-9. （原始内容存档于2016年3月4日）. 请检查|date=中的日期值 (帮助) [] [1] （页面存档备份，存于互联网档案馆）
6. Jerzy A. Filar，Koos Vrieze. Competitive Markov Decision Processes. Springer-Verlag. 1996年11月15日. ISBN 978-0387948058 （英语）.

一般参考

• Anne Condon. The complexity of stochastic games. Information and Computation. 1992, 96 (2): 第203－224页 [2010-09-07]. ISSN 0890-5401. doi:10.1016/0890-5401(92)90048-K. （原始内容存档于2013-06-03）.