基于動態(tài)認知邏輯的博弈剔除算法研究及模型檢測.pdf

1、博弈論研究的核心就是尋找博弈問題的解。各種重復剔除算法對于快速約簡博弈模型、尋找合理置信的納什均衡具有極為重要的意義。傳統(tǒng)的博弈分析框架總是假定：博弈中的選手是貝葉斯理性的(Bayesian Rational)，并且“每個選手是理性的”是選手之間的公共知識(common knowledge)。然而，博弈論本身并沒有顯性地表達主體的認知成分，自然也就不能精確模型主體間認知交互的高階信息(higher-order information)變

2、化，從而導致利用某些經典的重復剔除算法求解均衡時出現(xiàn)認知悖論，阻礙了博弈論的進一步發(fā)展和完善。同時，盡管模型檢測技術作為有限狀態(tài)系統(tǒng)的自動化驗證技術已得到廣泛應用，并且也越來越多地在多主體系統(tǒng)(Multi-Agent Systems，簡記為MAS)等人工智能領域得到重視，但應用動態(tài)模型檢測工具判定博弈認知邏輯系統(tǒng)性質、博弈中選手認知狀態(tài)的屬性等方面的工作在國際上尚無研究涉及，這必然會成為基于博弈論研究多主體系統(tǒng)建模技術的發(fā)展障礙。

3、>　　 本文首先分析了策略式博弈中各種重復剔除算法的邏輯認知基礎，系統(tǒng)地比較了幾種常見剔除算法之間的強弱關系，并闡明了對于迅速化簡博弈、精煉納什均衡、尋求更為合理置信博弈解等方面都有著明顯優(yōu)勢的重復可允許算法(Iterated Admissibility)的邏輯研究和認知分析的重要意義。其次，基于可能世界語義的Kripke結構，我們分別構建了用于描述純策略型靜態(tài)博弈認知結構和混合策略型博弈認知結構的公理化邏輯系統(tǒng)ELG和PEGL(Po

4、rbability Epistemic Game Logic)。在這兩個系統(tǒng)中，定義出一種更為直觀、更符合現(xiàn)實生活中選手博弈時的理性概念，且嚴格形式化地證明了這種理性概念作為博弈選手問公共知識所導致的認知結果和作為公開宣告事實時所導致的宣告極限都是與IA算法簡求解博弈所取得的結果完全一致。因此，我們從靜態(tài)和動態(tài)兩種不同認知角度為該算法求解博弈所得的均衡提供了合理置信的認知解釋，并有效地克服了該算法背后的認知悖論。最后，基于動態(tài)認知模型檢

5、測工具DEMO(Dynamic EpistemicModeling)，我們開發(fā)了動態(tài)認知博弈檢測工具DEMOGAME。利用它可以檢測策略式博弈認知系統(tǒng)的性質以及判定博弈中選手認知狀態(tài)的屬性。實例表明該工具是有效的，同時通過它也成功驗證了我們理論成果的正確性。因此，本文研究成果不僅進一步促進了認知博弈論的發(fā)展和完善，而且擴展和豐富了當前的多主體體系統(tǒng)模型檢測技術。其主要意義體現(xiàn)在以下幾個方面：
　　 1)厘清了博弈論中常見剔除算法

6、之間的強弱關系；
　　 2)構建了描述策略式博弈認知結構的邏輯系統(tǒng)ELG和PEGL?；谶@些系統(tǒng)，結合本文提出理性定義，形式化證明了：這種理性概念作為博弈選手間公共知識所導致的認知結果，與利用重復可允許算法化簡求解博弈的結果是完全吻合，從而為該算法提供了合理置信的認知基礎，并避免了該算法背后的認知悖論。
　　 3)通過嚴格證明我們所定義的理性可以用作公開宣告邏輯PAL(PublicAnnouncement Logic)的

7、宣告事實，進一步表明重復宣告新的理性斷定所產生的宣告極限也是與IA算法求解博弈的結果完全一致。從而，動態(tài)地刻畫了IA算法，更為明晰形象地闡明了IA算法的認知基礎；
　　 4)基于動態(tài)認知模型檢測工具DEMO，開發(fā)了可以用于檢測雙人靜態(tài)博弈認知系統(tǒng)性質、判定博弈中選手認知狀態(tài)屬性的動態(tài)認知博弈模型檢測工具DEMOGAME，并用此工具驗證了我們理論研究成果的正確性，充分體現(xiàn)我們研究成果的實用價值。
　　 5)對DEMOGAM

8、E稍加改動，我們還成功實現(xiàn)了利用該工具驗測博弈論中經典的重復剔除嚴格劣策略LESD(Iterated Elimination ofStrictly Dominated Strategies)算法、可理性化(Rationalizability)算法等結果是否與文[1]中定義的理性主體所做出的認知預測結果相一致，并通過實例表明DEMOGAME還可用于求解雙人有限策略式博弈均衡，找出博弈中所有的均衡解以及博弈認知系統(tǒng)性質等問題的判定。

9、　　 以邏輯為工具研究博弈理論的博弈邏輯和多主體體系統(tǒng)模型檢測技術的研究不僅有重要的理論意義，還有重大的實際應用價值。本文是多主體互動理論邏輯建模和模型檢測的一些階段性成果。今后，我們將在此基礎上，深入研究PEGL系統(tǒng)，尋找高效的模型檢測算法，以實現(xiàn)具有模型檢測混合策略型博弈認知結構性質的判定工具。同時，將研究拓展到擴展式博弈研究領域，嘗試構建可以用于描述和刻畫擴展式博弈認知結構的公理化系統(tǒng)，以期消解動態(tài)博弈求解的經典算法——后向歸納