2，博弈逻辑语言表达力分析.ppt

博弈逻辑分析 崔晓红 报告大纲： 两个问题: Q1，博弈和逻辑的联系有哪些？ Q2，模态逻辑对博弈的研究起什么作用? 1，博弈逻辑的语法，语义等 2，博弈逻辑语言表达力分析（1）与一阶语言比较 （2）与PDL和， -演算的比较 3，一点讨论 4，博弈逻辑的应用 Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈 关于逻辑的博弈 这一类博弈都是确定性(determined)博弈，也即有穷深度的2-人零和博弈. 1，博弈语义（game-theoretic semantics，GTS for short） 这是Hintikka提出的一种真定义的方法:公式A在模型M中为真 ， 当且仅当证实者(Verifier)在赋值博弈(M, A)中有赢策略。例如 A= ， 我们可以通过赋值博弈来判断该公式在如下模型M中是否为真： 。 Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈 对模态公式以及 -演算中的公式，我们同样能给出它们的赋值博弈语义 解释。 Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈 2，模型比较博弈 (model-comparison games)Ehrenfeucht(1957)- Fraisse(1954) 初等等价 1930年，Tarski 给出了初等等价概念的形式表述（两个结构初等等价，当且 仅当它们满足相同的一阶句子，也就是说用一阶语言无法区分两个初等等价的 结构），后来Ehrenfeucht 和Fraisse根据博弈这一概念给出了两个结构初等 等价的条件，这样的博弈就被称为Ehrenfeucht-Fraisse博弈（EF for short），或者又叫back-and-forth game（versatile idea）。 Q1,逻辑和博弈的联系有哪些？ 一，关于逻辑的博弈 双仿 3，对话博弈(Dialogue game) Q1,逻辑和博弈的联系有哪些？ 二，关于博弈的逻辑 1，认知方面（epistemic category） 认知逻辑 通过引入知识博弈（Knowledge game），我们可以刻画不完美信息 博弈中局中人所知道的和不知道的状态。如card game, muddy children. 动态认知逻辑 认知逻辑的扩张用以表达博弈中由于某些行动而引起局中人知识和信念 的变化，随之而产生的信念修正，信念更新以及重复信念变化等等这样 的认知行动。 Q1,逻辑和博弈的联系有哪些？ 二，关于博弈的逻辑 均衡解概念的认知基础 纳什均衡以及子博弈完美均衡的认知前提，以及逆向归纳也必须以某种 形式的反事实条件推理为基础。 2，非认知方面（non-epistemic category） 博弈逻辑GL (R. Parikh) 联盟逻辑CL (M. Pauly) Q2，模态逻辑对博弈的研究起什么作用? 这个问题又可以分解为这样两个问题： ？逻辑无用 ？逻辑到底有什么用，换句话说，逻辑到底能解决什么样的博弈问题，最好是 博弈论本身都没有解决的问题 Q2，模态逻辑对博弈的研究起什么作用? 动态逻辑最初是关于计算机程序的推理，后来又应用于更复杂行(agency) 的推理。 所有这些对程序的分析能否应用与对博弈的分析？R. Parikh于1985年在 《博弈逻辑及其应用》(1985)一文中给出了有关博弈推理的理论工具。 1，博弈逻辑的语法，语义等 一，介绍 在动态逻辑（DL）中，程序可看作是状态空间中的运行，给定初始状态s （输入），程序将经历一系列中间状态，结束于最后状态t（输出）停止。 博弈逻辑（GL）是通过在命题动态逻辑（PDL）的语言中增加对偶算子扩张 而成的。PDL可看作是GL的程序片断（pro