博弈邏輯語言表達(dá)力分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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