博弈邏輯語言表達力分析

1、博弈邏輯分析崔曉紅報告大綱：兩個問題:Q1，博弈和邏輯的聯(lián)系有哪些？Q2，模態(tài)邏輯對博弈的研究起什么作用1，博弈邏輯的語法，語義等2，博弈邏輯語言表達力分析（1）與一階語言比較（2）與PDL和，演算的比較3，一點討論4，博弈邏輯的應用Q1邏輯和博弈的聯(lián)系有哪些？一，關于邏輯的博弈關于邏輯的博弈這一類博弈都是確定性(determined)博弈，也即有窮深度的2人零和博弈.1，博弈語義（gametheeticsemantics，GTSfsh

2、t）這是Hintikka提出的一種真定義的方法:公式A在模型M中為真，當且僅當證實者(Verifier)在賦值博弈(MA)中有贏策略。例如A=，我們可以通過賦值博弈來判斷該公式在如下模型M中是否為真：。Q1邏輯和博弈的聯(lián)系有哪些？一，關于邏輯的博弈對模態(tài)公式以及演算中的公式，我們同樣能給出它們的賦值博弈語義解釋。Q1邏輯和博弈的聯(lián)系有哪些？一，關于邏輯的博弈2，模型比較博弈(modelcomparisongames)Ehrenfeuch

3、t(1957)Fraisse(1954)初等等價1930年，Tarski給出了初等等價概念的形式表述（兩個結構初等等價，當且僅當它們滿足相同的一階句子，也就是說用一階語言無法區(qū)分兩個初等等價的結構），后來Ehrenfeucht和Fraisse根據(jù)博弈這一概念給出了兩個結構初等等價的條件，這樣的博弈就被稱為EhrenfeuchtFraisse博弈（EFfsht），或者又叫backfthgame（versatileidea）。Q1邏輯和博弈

4、的聯(lián)系有哪些？一，關于邏輯的博弈雙仿3，對話博弈(Dialoguegame)aabcQ1邏輯和博弈的聯(lián)系有哪些？二，關于博弈的邏輯1，認知方面（epistemiccategy）認知邏輯通過引入知識博弈（Knowledgegame），我們可以刻畫不完美信息博弈中局中人所知道的和不知道的狀態(tài)。如cardgamemuddychildren.動態(tài)認知邏輯認知邏輯的擴張用以表達博弈中由于某些行動而引起局中人知識和信念的變化，隨之而產生的信念修正，

5、信念更新以及重復信念變化等等這樣的認知行動。Q1邏輯和博弈的聯(lián)系有哪些？二，關于博弈的邏輯均衡解概念的認知基礎納什均衡以及子博弈完美均衡的認知前提，以及逆向歸納也必須以某種形式的反事實條件推理為基礎。2，非認知方面（nonepistemiccategy）博弈邏輯GL(R.Parikh)聯(lián)盟邏輯CL(M.Pauly)Q2，模態(tài)邏輯對博弈的研究起什么作用這個問題又可以分解為這樣兩個問題：？邏輯無用？邏輯到底有什么用，換句話說，邏輯到底能解決

6、什么樣的博弈問題，最好是博弈論本身都沒有解決的問題Q2，模態(tài)邏輯對博弈的研究起什么作用動態(tài)邏輯最初是關于計算機程序的推理，后來又應用于更復雜行(agency)的推理。所有這些對程序的分析能否應用與對博弈的分析？R.Parikh于1985年在《博弈邏輯及其應用》(1985)一文中給出了有關博弈推理的理論工具。1，博弈邏輯的語法，語義等一，介紹在動態(tài)邏輯（DL）中，程序可看作是狀態(tài)空間中的運行，給定初始狀態(tài)s（輸入），程序將經歷一系列中間狀

7、態(tài)，結束于最后狀態(tài)t（輸出）停止。博弈邏輯（GL）是通過在命題動態(tài)邏輯（PDL）的語言中增加對偶算子擴張而成的。PDL可看作是GL的程序片斷（programfragment）。盡管博弈邏輯只是對其增加了一個對偶算子，但兩者在表達力，公理化方法以及復雜性上都有所不同。1，博弈邏輯的語法，語義等二，博弈邏輯語法和語義我們首先來看二人博弈中個人能力的推理問題，局中人1通常被稱為Angel局中人2Demon。定義1（博弈邏輯語法）：給定為原子博

8、弈集，是原子命題集，博弈和命題如下語法形式：其中，。1，博弈邏輯的語法，語義等在給出博弈模型之前，我們可以通過一個例子來獲得一些直觀上的理解。我們說局中人有策略獲得X，如果該局中人能保證博弈結束于X中的某一狀態(tài)。1，博弈邏輯的語法，語義等定義2（博弈模型）：一個博弈模型由以下三部分組成：狀態(tài)集，上單調，即且，那么。這里的又稱為功效函數(shù)（effectivityfunction）。定義3（博弈邏輯語義）：當且僅當其中1，博弈邏輯的語法，語義

9、等非原子博弈歸納定義如下，令：1，博弈邏輯的語法，語義等三，公理系統(tǒng)定義4（博弈邏輯公理系統(tǒng)）所有命題重言式的代人，公理模式：推理規(guī)則：1，博弈邏輯的語法，語義等定理1：博弈邏輯對所有博弈模型是可靠的。博弈邏輯對所有博弈模型是否完全，這仍然是一個待解決的問題。但我們有另外兩個較弱的完全性定理：定理2：不帶有對偶算子的博弈邏輯對所有博弈模型完全。定理3：不帶有迭代算子的博弈邏輯對所有博弈模型完全。對偶和迭代算子一起使得博弈邏輯有了不同與P

10、DL的表達力。2，博弈邏輯語言表達力分析四，Kripke模型上的博弈邏輯.定義5（Kripke模型）：給定原子博弈集，一個Kripke模型由一個非空狀態(tài)集S，一個賦值函數(shù)以及關系組成。形式上來說，一個博弈模型M和一個Kripke模型KM相對應如果成立當且僅當存在使得。每個Kripke模型都有與之相對應的博弈模型，然而，反之不然。定義6：稱一個博弈模型是析取的（disjunctive）當且僅當對每個，和，我們有定理4：每一個析取的博弈模型

11、都與某Kripke模型相對應。給定Kripke模型，我們可以重新給出博弈邏輯的語義解釋。2，博弈邏輯語言表達力分析四，雙仿象考慮Kripke模型間的雙仿關系一樣，我們同樣可以定義博弈模型間的雙仿關系。兩個狀態(tài)和雙仿，如果它們滿足同樣的原子公式；如果Angel在博弈g中從狀態(tài)開始有策略，她在此博弈中從狀態(tài)開始有策略，并且中的每一個狀態(tài)在中都有一個狀態(tài)與之雙仿；從開始的策略相類似。雙仿的狀態(tài)不能被任何模態(tài)語言區(qū)分。2，博弈邏輯語言表達力分析

12、定義7（雙仿）令和為兩個博弈模型，M和間的雙仿關系是非空關系，使得對于任何，有（1）（原子和諧）對于所有的原子公式，當且僅當；（2）（Zig條件）對于所有的并且：如果，那么使得并且；（3）（Zag條件）對于所有的并且：如果，那么使得并且。定義8（不變和安全）：一個博弈邏輯公式是雙仿不變，如果對于所有的博弈模型M和，蘊含；一個博弈邏輯博弈是雙仿安全的，如果對所有的博弈模型和，蘊含（1）如果，那么使得并且；（2）如果，那么使得并且。2，博弈

13、邏輯語言表達力分析定理5：所有博弈邏輯公式雙仿不變且所有博弈邏輯博弈雙仿安全。(ProgramConstructionsthatareSafefBisimulation)定義9：稱一個博弈模型具有一致有限性（unifmlyfinitary）當且僅當存在有窮多個有窮集合使得如果，那么存在使得并且。定理6：對于一致有限的博弈模型，滿足同樣博弈邏輯公式的狀態(tài)具有雙仿關系。（Fromprogramstogames:Invariancesafet

14、yfbisimulation）2，博弈邏輯語言表達力分析定理7：兩個Kripke模型是Kripke雙仿當且僅當它們相對應的博弈模型雙仿。同樣，如果不考慮迭代算子，博弈邏輯中博弈表達也能翻譯成帶有兩個自由變元x和Y的一階公式，例如，一個博弈邏輯博弈可翻譯成公式定理8：一階公式等價于一個不含有迭代算子的GL博弈的翻譯當且僅當它是雙仿安全的并且在Y中單調。（Logicfsocialsoftware）2，博弈邏輯語言表達力分析六，演算演算是有關

15、程序推理的形式系統(tǒng)，它包含有一階演算和命題演算，后者又稱為模態(tài)演算。這里的是最小固定點算子，通常用以描述迭代和遞歸概念，我們看這樣一個表達式：表示最小的二元關系使得或者x與y具有R關系使得z與y具有X關系，也即關系R的自反傳遞閉包。2，博弈邏輯語言表達力分析定義9：公式中變元的每一次自由出現(xiàn)是嚴格正出現(xiàn)當且僅當該變元前的否定符是偶數(shù)多個。令S為狀態(tài)的集合，如果把看作是作用在S上的集運算，是一個變元賦值函數(shù)使得，則變元X在公式中的每一次自

16、由出現(xiàn)都是嚴格正出現(xiàn)保證了的單調性，且由KnasterTarski定理又保證了有最小固定點。2，博弈邏輯語言表達力分析下面我們討論命題模態(tài)演算的語言和語義，通過把GL公式翻譯成演算的公式來討論GL的語言表達力。命題模態(tài)演算的語言由模態(tài)語言加上最小和最大固定點運算組成，其中，。定義10（演算語法）：給定為原子博弈集，是原子命題集，演算公式集歸納定義如下：其中，，，。2，博弈邏輯語言表達力分析定義（演算模型）：一個演算模型由博弈模型M和一個

17、變元賦值函數(shù)組成。定義（演算語義）：2，博弈邏輯語言表達力分析現(xiàn)在來考察如何把博弈邏輯嵌入演算。定義（翻譯）：我們把GL的公式翻譯成演算語言，對每個GL公式，通過博弈上的兩個輔助翻譯函數(shù)和，如下遞歸定義翻譯函數(shù)如下：2，博弈邏輯語言表達力分析例如：定理：存在翻譯函數(shù)使得對所有的博弈模型M，我們有當且僅當。2，博弈邏輯語言表達力分析定理：對于每個GL公式，有。定理：存在GL公式，它不等價于任何ad小于2的演算公式。定理：如果公式在GL的程

18、序片斷內，則ad()＝1，也即，GL表達力強于PDL.3，一些討論1，GL公式能夠被翻譯成演算中帶兩個自由變元的片斷，演算中哪些部分與GL語言相對應，且演算是否真包含GL。2，不同語言的表達力比較問題，都有哪些標準，這些標準之間有什么關系。3，博弈邏輯是否可以用來分析博弈中信息不對稱情況。4，博弈邏輯的應用一個分蛋糕的例子：n個人分一塊大蛋糕，每個人都希望能最大化自己的所得，那么怎么分才公平呢？（這里的公平是指每個人都認為自己可以使自己

19、分得的那部分不少于1n.）如果n=2，可以使用歷史悠久的“我分你選”算法，可以實行公平的分配。當n=3時，有幾種可能的分法。我們討論一種“修整法”：當?shù)谝粋€人切下一塊“屬于”他的蛋糕時，這塊蛋糕必須由其他n–1個人進行審查，在審查過程中，如果有人覺得這塊蛋糕太大，可以對它進行修整，切下的那些放回原處。蛋糕被輪流檢查過以后，如果這n1個人當中沒有任何人修整它，這塊蛋糕就屬于第一個人，如果至少有一個人對它進行了修整，那么這塊蛋糕就屬于最后一