随机博弈

维基百科,自由的百科全书
跳转至: 导航搜索

随机博弈(stochastic game)在博弈论中是一类由一个或多个参与者所进行的、具有状态概率转移动态博弈,由劳埃德·夏普利(Lloyd Shapley)於20世纪50年代初期提出。[1]

定义[编辑]

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

数学描述[编辑]

随机博弈的组成部分有:有限参与者集I ;状态空间M (可以是有限集,也可以是可测空间(M,{\mathcal A}));对於每一参与者i\in I,存在行动集S^i\,(可以是有限集,也可以是可测空间(S^i,{\mathcal S}^i));PM\times SM 的转移概率,其中S=\times_{i\in I}S^i是行动组合,P(A \mid m, s)是下一状态处於A 中的概率,而A 给定了当前状态m 和当前行动组合s ;从M\times SR^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)\,

例子[编辑]

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

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

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

重要结论[编辑]

贴现因子\lambda 0<\lambda \leq 1)的贴现博弈\Gamma_\lambda 中,参与者i 的收益是\lambda \sum_{t=1}^{\infty}(1-\lambda)^{t-1}g^i_tn 阶段博弈中,参与者i 的收益是\bar{g}^i_n:=\frac1n\sum_{t=1}^ng^i_t

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

非贴现博弈\Gamma_\infty中,参与者i 的收益是各阶段收益平均值的极限。在定义二人零和博弈\Gamma_{\infty}的值与非零和博弈\Gamma_{\infty}的均衡收益之前需要注意一些事情:若对於每一\varepsilon>0都有正整数N 、参与者1的策略\sigma_{\varepsilon}和参与者2的策略\tau_{\varepsilon},二人零和随机博弈\Gamma_\infty的一致值(uniform value)v_{\infty}存在,这样对於每一\sigma\tau和每一n\geq N,博弈中由\sigma_{\varepsilon} \tau定义的概率的\bar{g}^i_n期望至少为v_{\infty} -\varepsilon ,由\sigma \tau_{\varepsilon}定义的概率的\bar{g}^i_n期望至多为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. 1953-10, 39 (10): 第1095-1100页. ISSN 1091-6490. PMC 1063912. 
  2. ^ 2.0 2.1 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. International Journal of Game Theory. 1981-06, 10 (2): 第53-66页. ISSN 0020-7276.  电子版:ISSN 1432-1270ISSN 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页. doi:10.1016/S1574-0005(02)03011-4. ISBN 978-0-444-89428-1 (英文). 
  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. 2007年11月26日-30日: pp. 第315-320页. doi:10.1109/GLOCOM.2007.66. ISBN 978-1-4244-1043-9.  [] [1]
  6. ^ Jerzy A. Filar,Koos Vrieze. Competitive Markov Decision Processes. Springer-Verlag. 1996年11月15日. ISBN 978-0387948058 (英文). 

一般參考[编辑]