理论计算机科学电子笔记119（2005）3-9www.elsevier.com/locate/entcs在游戏中，如何和为什么？1Hugo Gimbert2 和Wiesl-aw Zielonka3LIAFA，Universit'eDenisDiderotParis7case7014，2 place Jussieu75251 Paris Cedex 05，France摘要在最近的一篇论文中，de Alfaro，Henzinger和Majumdar [8]观察到，自Shapley [16]的开创性论文以来，在经典随机博弈论中采用的连续支付贴现程序也适用于最近的随机奇偶博弈理论[7，6，5]，该理论被提出作为概率系统验证的工具我们发现，也许令人惊讶的是，[8]中使用的特定贴现实际上非常接近沙普利的原始思想。这一观察允许认识到，[8]供应商的特定贴现实际上来自一些不必要的限制。我们主张放弃[8]中的限制，从而得到一个更一般和更优雅的理论，其中包括奇偶性和平均支付博弈作为特殊的极限情况。关键词：平价博弈，折扣博弈1随机博弈我们介绍的适当框架是Shapley [16]引入的随机博弈。这样的游戏由两个玩家4玩：玩家0和玩家1。我们1本研究得到了欧洲研究培训网络的支持：游戏和Au- tomata的合成和验证2电子邮件地址：hugo@liafa.jussieu.fr3电子邮件地址：zielonka@liafa.jussieu.fr[4]我们在这里只考虑两个参与者1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.07.0054H. Gimbert，W.Zielonka/Electronic Notes in Theoretical Computer Science 119（2005）3∈|∈∈∈SJ∈Sp（SJ|s，a，b）= 1。在这样一个游戏中，一个游戏是无限序列的。给定一个有限的状态集S，对于每个状态S，我们有两个有限的动作集：A（s）-参与人0的动作，B（s）1. 如果系统处于状态sS，两个参与者同时独立地分别选择行动aA（s）和bB（s），系统继续以概率p（sJ）转移到新的状态sJs，a，b）我们可以看到，这取决于当前状态和选择的操作。我们假设条件概率是正确和一致的，即，，0≤p（s，J|s，a，b）≤1p=（s0，a0，b0），（s1，a1，b1），（s2，a2，b2）， . .属于集合的三元组（si，ai，bi）T={（s，a，b）|s∈S且a∈A（s），b∈B（s）}其元素将被称为过渡。直观地说，策略p描述了在博弈的每个阶段i，一个payo-payo映射u将每个可能的策略p映射到一个实数u（p）--玩家0从玩家1收到的来自策略p的支付。0的明显目标是以最大化他的收益的方式进行游戏，而参与人1试图最小化他的损失。两个玩家都使用策略，表明他们在游戏的每个阶段应该如何玩，即，将选择哪个可用动作通常，下一动作的选择可以取决于过去的历史，并且在本质上可以是概率性的，即，策略为当前阶段可用的行动提供了条件概率分布，请参阅以下教科书和专著[18，10，19，17]中的任何一本以获得正式定义。固定参与人0的策略σ和参与人1的策略τ以及初始状态s，在从s开始的波莱尔策略集上产生唯一的概率测度μs，σ，τ。现在我们可以更正式地说，参与人0的目标是选择，如果可能的话，最大化他的期望支付Es，σ，τ（u）=u（p）µs，σ，τ（dp）其中积分是在从s开始的所有策略p的集合上进行的（我们默认u是可积的）。改变支付映射u，我们得到不同类别的随机博弈。5 状态空间的不确定性实际上不是必需的。和H. Gimbert，W.Zielonka/Electronic Notes in Theoretical Computer Science 119（2005）35|∈∈n+1个i=0时我们说一个从s开始的博弈对于支付地图u有一个值，如果sup infEs，σ，τ（u）= inf supEs，σ，τ（u），στ τσ其中σ和τ在两个参与人的所有策略上变化。上面的等式意味着两个参与者都有ε-最优策略。随机博弈有两个简单但重要的子类。在完全信息随机博弈中，状态集S被划分为局中人0和局中人1的状态集S0和S1对于属于参与人i的Si的状态，他的对手可用的行动集只包含一个元素。这样的游戏允许一个简单的描述比一般的随机游戏。我们可以假设每个状态s都有一个有限的动作集合A（s）。 当我们处于状态s时，s（s∈Si）的所有者i选择一个动作a∈A（s）来执行，而a的执行导致一个新的 状态SJ∈ S，概率为p（SJ|s，a）。我们再次assumethatp（· |s，a，b）是一个固定的条件概率分布，SJ∈Sp（SJ|对于所有s和a∈ A（s），s，a）= 1。然而，甚至更简单的一类游戏是由确定性游戏。这是完美信息博弈，其中对于每个状态s和每个动作a A（s），有一个状态sJ使得p（sJs，a）= 1，即，A的选择明确地确定下一状态。2拼图的碎片不同类型的游戏模型共享上一节中描述的相同框架，不同之处仅在于它们的支付映射。2.1平均支付策略与折扣博弈让我们假设对于每个跃迁（s，a，b）T，我们有一个实数r（s，a，b）-一天的付款额。在平均支付博弈中，我们关注的是一天的平均值。 F或ap1 ayp=（s0，a0，b0），（s1，a1，b1），（s2，a2，b2）， . . tr=（ri）∞i=0是对应的一天奖励的序列（ri=r（si，ai，bi）），并且σ n（r）=1<$n r i它们在前n +1天的平均值。以来limit limn→∞σn（r）不需要存在，我们考虑上限或下限：lim supσn（r）= lim supσi（r）和lim infσn（r）= lim infσi（r）n→∞n→∞i≥nn→∞n→∞i≥n并将其中一个作为paym_n（p）对应于p_l_y_p。Σ6H. Gimbert，W.Zielonka/Electronic Notes in Theoretical Computer Science 119（2005）3Σ∈∈在折扣博弈中，我们固定一个折扣因子λ∈（0; 1），并且pl ayp=（s0，a0，b0），（s1，a1，b1），（s2，a2，b2）， . . 是由∞u λ（p）=（1 − λ）r i λ i，其中r i= r（s i，a i，b i）。（一）i=0时Shapley [16]证明了折扣博弈具有价值，并且双方都有最优的位置策略。Bewley和Kohlberg [1，2，3]证明了折扣对策的值的极限存在λ31。随后Mertens和Neyman [12]证明了这个极限实际上给出了平均支付随机博弈的值。Bewley，Kohlberg，[10]《明史》：“德者，德也;德者，德也。2.2奇偶博弈及其折现方法让 我 们 回 顾 一 下 ， 平 价 博 弈 首 先 在 Emerson 和 Jutla [9] （ 以 及Mostowski[13]）的确定性博弈框架中定义，有两个应用：无限树上自动机的互补问题和模态微演算。de Alfaro等人[6，5，7]在一系列论文中详细介绍和研究了随机奇偶博弈最后一篇论文通过微演算证明了这样的博弈有价值。在随机奇偶博弈中，一天的奖励，在这种情况下有时被称为颜色，是不存在的。负整数，r（s，a，b）∈N，（s，a，b）∈T，以及博弈的收益p=（s0，a0，b0），（s1，a1，b1），（s2，a2，b2）， . . 是由u_p_i（p）=（lim_sup_i）m_d2，其中r_i=r（s_i，a_i，b_i）。这是一个由最大值和最小值的函数组成的函数，它的最大值是最小的，最小值是最小的。尽管平均支付博弈和平价博弈有许多明显的相似之处，特别是在确定性博弈中[4，15]，这两种类型的游戏之间的确切关系仍然难以捉摸。至少在某种程度上，这是由于缺乏适当的折扣平价游戏。事实上，平均支付博弈最显著的特征之一就是可以用折扣博弈来近似它们。因此，似乎除非我们找到平价博弈的折扣对应物，否则平价博弈和平均支付博弈之间的类比应该被认为是超级模糊的。6通常，平价游戏中使用的一天支付金额或颜色与状态相关联，即， 假设每个状态SS被R（S）着色N. 我们更喜欢给“过渡”上色 以便允许用于平价/平均支付/折扣游戏的更统一的设置。H. Gimbert，W.Zielonka/Electronic Notes in Theoretical Computer Science 119（2005）37−Σ然而，事实证明，de Alfaro，Henzinger和Majumdar已经发现了平价游戏的折扣版本[8]。 更确切地说，这篇论文[8]主要涉及贴现的μ-演算，对博弈的引用是粗略的，只涉及最简单的情况，如可达性，安全性和Bu-hi博弈。 这可能是迄今为止他的方法没有得到充分利用的原因。事实上，通过微演算来统一平均支付博弈和平价博弈似乎是不太随机平均支付博弈需要更复杂的工具，他们的理论与非扩张映射理论有关[14]，一般来说，可能没有不动点。因此，博弈论似乎比微演算有更广阔的视角。第一个任务是将折扣微演算转化为博弈，即，为无限次游戏提供适当的支付能力映射。不需要立即提供相应的公式，因为我们可以很快认识到，通过这种转换获得的支付报酬映射只是Shapley最初考虑的贴现支付报酬的一个非常特殊的情况[16]。更准确地说，Shapley [16]考虑了总支付随机博弈，其中对于每个状态s ∈ S，存在一个固定的概率α（s），当访问s时，博弈停止。众所周知（并且可以容易地看到），在停止条件下的预期总收益与有限个非停止博弈的预期收益相同，其中每次通过状态s导致所有后续的一天收益以因子λ（s）= 1进行贴现。α（s）。因此，沙普利博弈可以被看作是这样的博弈：p=（s0，a0，b0），（s1，a1，b1），（s2，a2，b2）， . . 是由∞uShapley（p）= λ0. λ nrn， 其中λi ∈ N，λ i= λ（si），ri= r（si，ai，bi）.n=0例（二）许多不同的折扣因子的想法被抛弃在所有随后的论文和教科书有关折扣游戏，因为它原来基本上是无用的，许多折扣因子只会增加不必要的混乱。公式（1）只有一个贴现因子，普遍适用。然而，正如在[8]中所观察到的，许多不同的折扣因子对于折扣平价游戏是必不可少的。但是，当我们要研究极限支付时，公式（2）是不合适的，因为各种折扣因子都趋于1。 为此，我们首先应修改（2），并在其中添加以下补充因素：形式（1−λi）。 这产生了我们最终的多折扣支付映射。设λ是一个映射，对于每个转移（s，a，b）给出一个折扣因子λ（s，a，b）∈（0; 1）（对于不同的转移可以不同），如前所述，设r（s，a，b）∈R是相应的一天奖励。 对于策略p=（s0，a0，b0），（s1，a1，b1），（s2，a2，b2）， . . weset∈N，λi=λ（si，ai，bi）andd8H. Gimbert，W.Zielonka/Electronic Notes in Theoretical Computer Science 119（2005）3Σri=r（si，ai，bi）.则p的多折扣收益由下式给出：∞umulti（p）= （1−λn）λ0· · ·λn−1rn.（三）n=0例de Alfaro et al. [8]实际上对应于具有附加约束的支付条件（3(A) 一天的奖励r（s，a，b）仅取值0和1。在[8]中，当考虑多个折现因子趋于1的情况下，多个折现支付的极限出现了另一个限制。为了准确地解释它，我们应该首先改变贴现因子的语义。我们不再假设λ将区间（0; 1）的转换映射到固定实数，而是假设存在贴现变量或参数的有限集合Λ，λ是从转换集合到变量集合Λ的映射，不同的转换可以映射到同一个变量。多个discou-tpayme都可以看到一个功能，我们可以研究如果变量Λ倾向于1。当研究这样的极限时，[8]强加了一个额外的条件，从语法上限制了折扣因子在微演算公式中的出现。粗略地说，在游戏框架中，这个限制转化为以下条件：(B) 如果两个转换被映射到相同的折扣变量，则这些转换的一天奖励也相等，即，对于所有的（sJ，aJ，bJ），（s，a，b）∈T，若λ（SJ，AJ，BJ）=λ（s，a，b）∈Λ则r（SJ，AJ，BJ）=r（s，a，b）.然而，事实证明，最有趣的事情恰恰发生在我们放松（A）或（B）或同时放松这两个限制，并检查（3）贴现变量何时以某种顺序趋于1时。这导致了几个新的游戏，推广平价或平均支付游戏或两者兼而有之的限制。这种方法被证明是非常富有成效的，我们可以从关于经典随机博弈[10]的积累知识中获得很大的收益，以建立关于奇偶博弈及其扩展的等价结果。另一方面，这种方法也建议如何定义经典随机博弈的“优先级”版本，这可能对博弈论有一定的这个问题在[11]中得到了广泛的发展。引用[1] T. Bewley和E.科尔伯格随机对策中一个递归方程的渐近解。数学运筹学，1：321H. Gimbert，W.Zielonka/Electronic Notes in Theoretical Computer Science 119（2005）39[2] T. Bewley和E.科尔伯格随机博弈的渐近理论。运筹学数学，1：197[3] T. Bewley 和E.科尔伯格具有平稳最优策略的随机博弈。数学运筹学，3：104[4] HenrikBjürklund ， SvenSandber g ， anddSergeiVorobyov.Memorylessdeterminacyofparityand mean payo n博弈：一个简单的证明。TCS，310：365[5] L. de Alfaro和T.A.亨辛格并发ω-正则对策LICSIEEE Computer Society Press，2000.[6] L. de Alfaro，T.A.Henzinger和O.库普弗曼并发可达性游戏。在FOCSIEEE Computer SocietyPress，1998.[7] L. de Alfaro和R.马宗达Ω正则对策的定量解。在STOCACM Press，2001.最终版本将出现在计算机与系统科学杂志上。[8] 放大图片作者：Thomas A. Henzinger和Rupak Majumdar。系统理论中的未来贴现ICALP2003，LNCS第2719卷，第1022Springer，2003年。[9] E.A. Emerson 和C.朱特拉树自动机，μ-演算和确定性。在FOCSIEEE Computer SocietyPress，1991.[10] J. Filar和K.弗列兹 竞争马尔可夫决策过程 Springer，1997年。[11] Hugo Gimbert和Wies-law Zielonka平均支付博弈和平价博弈：硬币的两面。正在筹备中。[12] J.F. Mertens和A.内曼随机博弈International Journal of Game Theory，10：53[13] A. W. Mostowski. 游戏是与他或bi ddenpositions。 TechnicalReport78，UniwersyttGdan'sk i，Instytut Matematyki，1991.[14] 亚伯拉罕·奈曼随机 游戏 非扩张映射在 A. 内曼与S. Sorin，编辑，Stohastic Games and Applications，NATO Science Series C，Mathematicaland Pphysical Sciences，第570卷，第397-415页。Kluwer Academic Publishers，2003.[15] Anuj Puri混杂系统与离散事件系统理论。博士论文，EECS，加利福尼亚大学，1995年。[16] L. S.沙普利随机博弈 Proceedings Nat. Acad. of Science USA，39：1095 -1100，1953.[17] 西尔万·索林零和重复博弈（Zero-Sum Repeated Games）施普林格，2002年。[18] 西 尔 万 · 索 林 分 类 和 基 本 工 具 。 以 . Neyman 和 S. Sorin ， 编 辑 ， Stohastic Games andApplications ， NATO Science Series C ， Mathematical and Pphysical Sciences ， 第570Kluwer Academic Publishers，2003.[19] OJ· 弗里兹 具有有 限状态和 行动空间 的随机博弈 。CWI Tract. Centrum voor Wiskunde enInformatica，1987年。
我的内容管理
展开
