1、博弈逻辑分析,崔晓红,,报告大纲：,两个问题: Q1，博弈和逻辑的联系有哪些？ Q2，模态逻辑对博弈的研究起什么作用?1，博弈逻辑的语法，语义等2，博弈逻辑语言表达力分析（1）与一阶语言比较 （2）与PDL和， -演算的比较3，一点讨论4，博弈逻辑的应用,,Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈,关于逻辑的博弈这一类博弈都是确定性(determined)博弈，也即有穷深度的2-人零和博弈. 1，博弈语义（game-theoretic semantics，GTS for short）这是Hintikka提出的一种真定义的方法:公式A在模型M中为真 ，当且仅当证实者(Verifier)
2、在赋值博弈(M, A)中有赢策略。例如A= ，我们可以通过赋值博弈来判断该公式在如下模型M中是否为真：。,,Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈,对模态公式以及 -演算中的公式，我们同样能给出它们的赋值博弈语义解释。,,Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈,2，模型比较博弈 (model-comparison games)Ehrenfeucht(1957)-Fraisse(1954)初等等价1930年，Tarski 给出了初等等价概念的形式表述（两个结构初等等价，当且仅当它们满足相同的一阶句子，也就是说用一阶语言无法区分两个初等等价的结构），后来Ehrenfeuch
3、t 和Fraisse根据博弈这一概念给出了两个结构初等等价的条件，这样的博弈就被称为Ehrenfeucht-Fraisse博弈（EF for short），或者又叫back-and-forth game（versatile idea）。,,Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈,双仿3，对话博弈(Dialogue game),a,a,b,c,,Q1,逻辑和博弈的联系有哪些？ 二，关于博弈的逻辑,1，认知方面（epistemic category）认知逻辑通过引入知识博弈（Knowledge game），我们可以刻画不完美信息博弈中局中人所知道的和不知道的状态。如card game,
4、 muddy children.动态认知逻辑认知逻辑的扩张用以表达博弈中由于某些行动而引起局中人知识和信念的变化，随之而产生的信念修正，信念更新以及重复信念变化等等这样的认知行动。,,Q1,逻辑和博弈的联系有哪些？ 二，关于博弈的逻辑,均衡解概念的认知基础纳什均衡以及子博弈完美均衡的认知前提，以及逆向归纳也必须以某种形式的反事实条件推理为基础。2，非认知方面（non-epistemic category）博弈逻辑GL (R. Parikh)联盟逻辑CL (M. Pauly),,Q2，模态逻辑对博弈的研究起什么作用?,这个问题又可以分解为这样两个问题：？逻辑无用？逻辑到底有什么用，换句话说，逻辑
5、到底能解决什么样的博弈问题，最好是博弈论本身都没有解决的问题,,Q2，模态逻辑对博弈的研究起什么作用?,动态逻辑最初是关于计算机程序的推理，后来又应用于更复杂行(agency)的推理。 所有这些对程序的分析能否应用与对博弈的分析？R. Parikh于1985年在博弈逻辑及其应用(1985)一文中给出了有关博弈推理的理论工具。,,1，博弈逻辑的语法，语义等,一，介绍 在动态逻辑（DL）中，程序可看作是状态空间中的运行，给定初始状态s（输入），程序将经历一系列中间状态，结束于最后状态t（输出）停止。 博弈逻辑（GL）是通过在命题动态逻辑（PDL）的语言中增加对偶算子扩张而成的。PDL可看作是GL的
6、程序片断（program fragment）。尽管博弈逻辑只是对其增加了一个对偶算子，但两者在表达力，公理化方法以及复杂性上都有所不同。,,1，博弈逻辑的语法，语义等,二，博弈逻辑语法和语义我们首先来看二人博弈中个人能力的推理问题，局中人1通常被称为Angel,局中人2Demon。定义1（博弈逻辑语法）：给定 为原子博弈集， 是原子命题集，博弈 和命题 如下语法形式：其中 ， 。,,1，博弈逻辑的语法，语义等,在给出博弈模型之前，我们可以通过一个例子来获得一些直观上的理解。我们说局中人有策略获得X，如果该局中人能保证博弈结束于X中的某一状态。,,1，博弈逻辑的语法，语义等,定义2（博弈模型）：
7、 一个博弈模型 由以下三部分组成： 状态集， 上单调，即 且 ，那么 。这里的 又称为功效函数（effectivity function）。定义3（博弈逻辑语义）： 当且仅当 其中,,1，博弈逻辑的语法，语义等,非原子博弈归纳定义如下，令 ：,,1，博弈逻辑的语法，语义等,三，公理系统定义4（博弈逻辑公理系统） 所有命题重言式的代人，公理模式： 推理规则：,,1，博弈逻辑的语法，语义等,定理1：博弈逻辑对所有博弈模型是可靠的。博弈逻辑对所有博弈模型是否完全，这仍然是一个待解决的问题。但我们有另外两个较弱的完全性定理：定理2：不带有对偶算子 的博弈逻辑 对所有博弈模型完全。定理3：不带有迭代算子
8、 的博弈逻辑 对所有博弈模型完全。对偶和迭代算子一起使得博弈逻辑有了不同与PDL的表达力。,,2，博弈逻辑语言表达力分析,四，Kripke模型上的博弈逻辑.定义5（Kripke模型）：给定原子博弈集 ，一个Kripke-模型由一个非空状态集S，一个赋值函数 以及关系 组成。形式上来说，一个博弈模型M和一个Kripke模型KM相对应如果 成立当且仅当存在 使得 。每个Kripke模型都有与之相对应的博弈模型，然而，反之不然。定义6 ：称一个博弈模型是析取的（disjunctive）当且仅当对每个 ， 和 ，我们有定理4： 每一个析取的博弈模型都与某Kripke模型相对应。给定Kripke模型 ，
9、我们可以重新给出博弈逻辑的语义解释。,,2，博弈逻辑语言表达力分析,四，双仿象考虑Kripke模型间的双仿关系一样，我们同样可以定义博弈模型间的双仿关系。两个状态 和 双仿，如果它们满足同样的原子公式；如果Angel在博弈g中从状态 开始有 -策略，她在此博弈中从状态 开始有 -策略，并且 中的每一个状态 在 中都有一个状态与之双仿；从开始的策略相类似。双仿的状态不能被任何模态语言区分。,,2，博弈逻辑语言表达力分析,定义7（双仿）令 和 为两个博弈模型，M和 间的双仿关系是非空关系 ，使得对于任何 ，有（1）（原子和谐）对于所有的原子公式 ， 当且仅当 ；（2）（Zig条件）对于所有的 并且
10、 ：如果 ，那么 使得 并且 ；（3）（Zag条件）对于所有的 并且 ：如果 ，那么 使得 并且 。定义8（不变和安全）：一个博弈逻辑公式 是双仿不变，如果对于所有的博弈模型M和 ， 蕴含 ；一个博弈逻辑博弈 是双仿安全的，如果对所有的博弈模型 和 ， 蕴含（1）如果 ，那么 使得 并且 ；（2）如果 ，那么 使得 并且 。,,2，博弈逻辑语言表达力分析,定理5：所有博弈逻辑公式双仿不变且所有博弈逻辑博弈双仿安全。(Program Constructions that are Safe for Bisimulation)定义9：称一个博弈模型具有一致有限性（uniformly finitary
11、）当且仅当存在有穷多个有穷集合 使得如果 ，那么存在 使得 并且 。定理6：对于一致有限的博弈模型，满足同样博弈逻辑公式的状态具有双仿关系。（From programs to games: Invariance and safety for bisimulation）,,2，博弈逻辑语言表达力分析,定理7：两个Kripke-模型是Kripke-双仿当且仅当它们相对应的博弈模型双仿。 同样，如果不考虑迭代算子，博弈逻辑中博弈表达也能翻译成带有两个自由变元x和Y的一阶公式，例如，一个博弈逻辑博弈 可翻译成公式 定理8：一阶公式 等价于一个不含有迭代算子的GL-博弈的翻译当且仅当它是双仿安全的并且在
12、Y中单调。（Logic for social software）,,2，博弈逻辑语言表达力分析,六， -演算 -演算是有关程序推理的形式系统，它包含有一阶 -演算和命题 -演算，后者又称为模态 -演算。这里的 是最小固定点算子，通常用以描述迭代和递归概念，我们看这样一个表达式：表示最小的二元关系 使得 或者x与y具有R关系使得z 与y具有X关系，也即关系R的自反传递闭包 。,,2，博弈逻辑语言表达力分析,定义9：公式中变元的每一次自由出现是严格正出现当且仅当该变元前的否定符是偶数多个。令S为状态的集合，如果把 看作是作用在S上的集运算， 是一个变元赋值函数使得 ，则变元X在公式 中的每一次自由
13、出现都是严格正出现保证了 的单调性，且由Knaster-Tarski定理又保证了 有最小固定点。,,2，博弈逻辑语言表达力分析,下面我们讨论命题模态 -演算的语言和语义，通过把GL公式翻译成 -演算的公式来讨论GL的语言表达力。 命题模态 -演算的语言由模态语言加上最小和最大固定点运算组成，其中， 。定义10（ -演算语法）：给定为原子博弈集 ， 是原子命题集， -演算公式集 归纳定义如下：其中， ， ， 。,,2，博弈逻辑语言表达力分析,定义（ -演算模型）：一个 -演算模型 由博弈模型M和一个变元赋值函数 组成。定义（ -演算语义）：,,2，博弈逻辑语言表达力分析,现在来考察如何把博弈逻辑
14、嵌入 -演算。定义（翻译）：我们把GL的公式翻译成 -演算语言 ，对每个GL公式 ，通过博弈上的两个辅助翻译函数 和 ，如下递归定义翻译函数 如下：,,2，博弈逻辑语言表达力分析,例如：定理：存在翻译函数 使得对所有的博弈模型M，我们有 当且仅当 。,,2，博弈逻辑语言表达力分析,定理：对于每个GL公式 ，有 。定理：存在GL公式，它不等价于任何ad小于2的 -演算公式。定理：如果公式在GL的程序片断内，则ad( )1，也即，GL表达力强于PDL.,,3，一些讨论,1，GL公式能够被翻译成 -演算中带两个自由变元的片断， -演算中哪些部分与GL语言相对应，且 -演算是否真包含GL。2，不同语言
15、的表达力比较问题，都有哪些标准，这些标准之间有什么关系。3，博弈逻辑是否可以用来分析博弈中信息不对称情况。,,4，博弈逻辑的应用,一个分蛋糕的例子：n个人分一块大蛋糕，每个人都希望能最大化自己的所得，那么怎么分才公平呢？（这里的公平是指每个人都认为自己可以使自己分得的那部分不少于1/n.） 如果n = 2，可以使用历史悠久的“我分你选”算法，可以实行公平的分配。当n =3时，有几种可能的分法。我们讨论一种“修整法”：当第一个人切下一块“属于”他的蛋糕时，这块蛋糕必须由其他n 1个人进行审查，在审查过程中，如果有人觉得这块蛋糕太大，可以对它进行修整，切下的那些放回原处。蛋糕被轮流检查过以后，如果这n-1个人当中没有任何人修整它，这块蛋糕就属于第一个人，如果至少有一个人对它进行了修整，那么这块蛋糕就属于最后一个修整它的人。这种算法能保证蛋糕的公平分配，我们可以通过博弈逻辑这一工具对此加以证明。,Thank You !,
