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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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