查看“︁随机博弈”︁的源代码

{{NoteTA
|G1=博弈论
}}
'''随机博弈'''（{{lang-en|stochastic game}}），或称'''随机-{zh-cn:赛局; zh-hk:賽局; zh-tw:博弈;}-'''、'''随机對局'''，在[[博弈论]]中是一类由一个或多个参与者所进行的、具有状态'''概率转移'''的[[动态博弈]]，由[[劳埃德·夏普利]]（Lloyd Shapley）於20世纪50年代初期提出。<ref>{{cite journal |author=Lloyd Stowell Shapley |title=Stochastic games |journal=Proc. Nat. Acad. Sciences |volume=39 |issue=10 |pages=第1095－1100页 |pmc=1063912 |issn=1091-6490|date=October 1953}}</ref>

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

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

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

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

当前有任意个装着球的桶，每个桶中球的数目也是任意的，两位参与者轮流从中取出球，且需要遵守如下规则： 
# 每一步应至少取出一只球，且只能从某一桶中取走部分或全部球； 
# 谁取到最后一只球，谁就获胜。

== 重要结论 ==
[[贴现因子]]为<math>\lambda </math>（<math>0<\lambda \leq 1</math>）的贴现博弈<math>\Gamma_\lambda</math> 中，参与者<math>i</math> 的收益是<math>\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^i_t</math> 。<math>n</math> 阶段博弈中，参与者<math>i</math> 的收益是<math>\bar{g}^i_n:=\frac1n\sum_{t=1}^ng^i_t</math> 。

若存在有限多个状态和行动的二人[[零和博弈]]<math>\Gamma_n</math>（各自是<math>\Gamma_{\lambda}</math>）的值为<math>v_n(m_1)</math>（各自是<math>v_{\lambda}(m_1)</math>），则<math>v_n(m_1)</math> 在<math>n</math> 趋於无穷时收敛到一个极限，且<math>v_{\lambda}(m_1)</math>在<math>\lambda</math>趋於<math>0</math>时收敛到相同的极限。这一结论已被[[杜鲁门·彪利]]（Truman Bewley）和[[艾朗·克尔伯格]]（Elon Kohlberg）於1976年证明。<ref name="Neyman & Sorin"/>

非贴现博弈<math>\Gamma_\infty</math>中，参与者<math>i</math> 的收益是各阶段收益平均值的极限。在定义二人零和博弈<math>\Gamma_{\infty}</math>的值与非零和博弈<math>\Gamma_{\infty}</math>的均衡收益之前需要注意一些事情：若对於每一<math>\varepsilon>0</math>都有正整数<math>N</math> 、参与者1的策略<math>\sigma_{\varepsilon}</math>和参与者2的策略<math>\tau_{\varepsilon}</math>，二人零和随机博弈<math>\Gamma_\infty</math>的一致值（uniform value）<math>v_{\infty}</math>存在，这样对於每一<math>\sigma</math>、<math>\tau</math>和每一<math>n\geq N</math>，博弈中由<math>\sigma_{\varepsilon} </math>和<math>\tau</math>定义的概率的<math>\bar{g}^i_n</math>期望至少为<math>v_{\infty} -\varepsilon </math>，由<math>\sigma </math>和<math>\tau_{\varepsilon}</math>定义的概率的<math>\bar{g}^i_n</math>期望至多为<math>v_{\infty} +\varepsilon </math>。[[让·弗朗索瓦·梅顿斯]]（Jean Francois Mertens）和[[亚伯拉罕·奈曼]]（Abraham Neyman）於1981年证明二人零和随机博弈具有一致值。<ref>{{cite journal |author=Jean Francois Mertens，Abraham Neyman |title=Stochastic Games |journal=International Journal of Game Theory |volume=10 |issue=2 |pages=第53－66页 |url=http://www.springerlink.com/content/v44t0438n3323p23/fulltext.pdf |issn=0020-7276 |date=June 1981 }}{{Dead link|date=2020年1月 |bot=InternetArchiveBot |fix-attempted=yes }} 电子版：{{ISSN|1432-1270}}</ref>

若参与者数量有限且行动集和状态集有限，则有限阶段随机博弈总有[[纳什均衡]]，对於总收益是贴现和的无限多阶段随机博弈也是如此。[[尼古拉斯·维勒]]（Nicolas Vieille）已经证明当总收益是各阶段收益平均值的下极限时，所有具有有限状态和行动空间的二人随机博弈都有[[ε-均衡|近似纳什均衡]]。不过，当参与者多於2名时，随机博弈是否存在这类均衡仍是一个极具挑战性的开放性问题。<ref>{{cite book |author=Nicolas Vieille |title=Handbook of Game Theory with Economic Applications |year=2002年9月2日 |editor=R.J. Aumann，S. Hart |publisher=North-Holland |language=en |isbn=978-0-444-89428-1 |oclc= |doi=10.1016/S1574-0005(02)03011-4 |pages=第1833–1850页 |url=http://www.sciencedirect.com/science/handbooks/15740005 |chapter=Stochastic games: Recent results |chapterurl=http://www.sciencedirect.com/science/article/B7P5P-4FD79WM-C/2/652c29256e143fb1599845172ff8a614 |format=精装书 |access-date=2010年9月7日 |archive-date=2018年1月2日 |archive-url=https://web.archive.org/web/20180102025155/http://www.sciencedirect.com/science/handbooks/15740005 }}</ref>

== 应用 ==
随机博弈在[[经济学]]、[[演化生物学]]和[[计算机网络]]中都有应用。<ref>{{cite conference |author=Eitan Altman，Konstantin Avrachenkov，Nicolas Bonneau，Mérouane Debbah，Rachid El-Azouzi，Daniel Menasché |title=Constrained Stochastic Games in Wireless Networks |booktitle=Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE |pages=第315－320页 |date=2007年11月26日－30日 |location=Washington, DC |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.5089&rep=rep1&type=pdf |doi=10.1109/GLOCOM.2007.66 |id=ISBN 978-1-4244-1043-9 |conference= |access-date=2010年9月7日 |archive-date=2016年3月4日 |archive-url=https://web.archive.org/web/20160304224243/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.5089&rep=rep1&type=pdf }} [] [http://www-net.cs.umass.edu/~sadoc/mdp/main.pdf] {{Wayback|url=http://www-net.cs.umass.edu/~sadoc/mdp/main.pdf |date=20210918114257 }}</ref>事实上，随机博弈是[[重复博弈]]这类每一阶段都处於相同状态的博弈的一般化形式。

有关随机博弈的最全面的参考书籍是奈曼和索林编著的文集。<ref name="Neyman & Sorin">{{cite book |author=Abraham Neyman，Sylvain Sorin |date=2003年10月31日 |title=Stochastic Games and Applications |publisher=Kluwer Academic Press |isbn=978-1402014932 |language=en }}</ref>菲拉尔和乌瑞兹所著的书籍更为基础，书中提供了[[马尔可夫决策过程]]（MDP）和二人随机博弈理论的严密的统一处理方法。<ref>{{cite book |author=Jerzy A. Filar，Koos Vrieze |date=1996年11月15日 |title=Competitive Markov Decision Processes |publisher=Springer-Verlag |isbn=978-0387948058 |language=en }}</ref>他们创造了Competitive MDPs这一术语来概括一人和二人随机博弈。

==参考文献==
===註釋===
{{reflist|2}}

===一般參考===
<div class="references-small">
* {{cite journal |author=Anne Condon |year=1992 |month= |title=The complexity of stochastic games |journal=Information and Computation |volume=96 |issue=2 |pages=第203－224页 |doi=10.1016/0890-5401(92)90048-K |issn=0890-5401 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.3829&rep=rep1&type=pdf |access-date=2010-09-07 |archive-date=2013-06-03 |archive-url=https://web.archive.org/web/20130603202947/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.3829&rep=rep1&type=pdf }}
</div>
{{-}}
{{博弈论}}

[[Category:博弈论]]