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

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

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

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

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

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

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

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

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

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