《社會博弈的邏輯與計算模擬研究》中期檢查報告

一、 研究進展情況

①研究計劃總體執(zhí)行情況及各子課題進展情況

本項目自開題以來，課題組在社會博弈的理論基礎(chǔ)、數(shù)理模型、計算復(fù)雜性和計算機模擬四個子課題上開展分工協(xié)作，研究工作按計劃有序進行。在國際權(quán)威期刊和國際會議發(fā)表論文9篇，主編論文集1部（world scientific出版），完成書稿1部。舉辦課題組成員集中討論1次。參加國際學(xué)術(shù)會議和國際合作15人次。

一、社會博弈的理論基礎(chǔ)方向:課題組研究人員開展了扎實的調(diào)研和研究工作，為整個項目后續(xù)的數(shù)理模型與計算機模擬研究提供了經(jīng)驗數(shù)據(jù)基礎(chǔ)和實證研究。目前已經(jīng)取得了很好的研究成果。

1. 首先，在經(jīng)驗研究上，我們開展了以西藏藏族地區(qū)為中心的人類學(xué)調(diào)研�；�于扎實的田野考察和全面的數(shù)據(jù)分析整理，我們對藏族群體（宗教）交流互動的語言模式、語用規(guī)則和基本模型進行了恰當(dāng)?shù)姆治雠c提煉。

2. 在理論研究上，我們進一步提出和發(fā)展了著重社會文化因素分析的廣義論證理論�；�于已有的人類學(xué)、社會學(xué)實證結(jié)果，我們拓展了當(dāng)代論證研究的社會文化維度，并分析了不同文化中的說理活動是否在論證類型或模式上的存在差別，并特別探討了中西文化群體論證性交際的社會文化差異。

3. 在應(yīng)用研究上，我們著重發(fā)展了一種社會選擇理論和判斷聚合理論。通過對個人意見匯聚機制的理論研究，我們探討了文化群體的社會理性和集體可接受性問題，提出了一種關(guān)于社會理性新的觀點，并證明了這種觀點可以解決經(jīng)典的集體選擇困境。以之為基礎(chǔ)，我們解決了一些與利益最大化、一致性和公平正義問題相關(guān)的理論問題。

二、社會博弈的數(shù)理模型方向:子課題成員在博弈論和智能體信念模型方面取得了以下的進展：

1.在博弈論方面，我們初步建立了幾個在不完全信息下的博弈模型。主要分為兩個方面。一個是不完全信息下博弈者對其他博弈者類型缺乏認(rèn)識的問題；另一個是不完全信息下博弈者對博弈策略本身缺乏完全認(rèn)識的問題。在這兩個方面，我們都建立了相應(yīng)的博弈模型，并進一步討論了這些博弈模型的各種重要性質(zhì)。已有相關(guān)論文發(fā)表于國際權(quán)威雜志上�；�于上述模型，我們還討論了其決策方法問題。我們使用了公理化方法探討了Yager決策理論中，在不確定條件下的決策模型。相關(guān)論文也已發(fā)表于國際權(quán)威雜志。

2.在智能體理論方面，我們主要討論了智能體的信念模型和信念修正問題。基于標(biāo)準(zhǔn)的信念修正理論，即AGM理論，我們給出了一種新的，具有一般性的信念修正函數(shù)。這種信念函數(shù)適用于智能體信念系統(tǒng)中有一部分核心信念的情況。在這種情況下，智能體的信念根據(jù)核心信念可按其可接受程度分級。信念修正的過程依賴于這種分級系統(tǒng)。我們已有相關(guān)論文發(fā)表于國際權(quán)威雜志。

3.提出了含混偏好下的博弈模型，考察社會個體在含混厭惡和極小化極大反悔條件下的博弈過程；為了推廣經(jīng)典期望效用理論，文獻提出了很多不確定性條件下的決策模型，基于聚類算子的決策模型為其中的一種重要模型。然而，這個理論缺乏公理化的基礎(chǔ)。對于一個形式的理論來說，公理化辯護是必要的，因為這樣的辯護不但可以揭示理論的預(yù)設(shè)，也可以為其基本概念提供語義解釋。 課題組為基于聚類算子的決策模型建立了公理化基礎(chǔ)。在這一研究中，我們確定了基于聚類算子決策模型的公理，證明了該理論的表征定理和相關(guān)的性質(zhì)，并為該理論的基本概念做出了合理的解釋。

三、博弈模型的計算復(fù)雜性方向:劉虎教授研究一種無界合作博弈(GUCG博弈)，這種博弈中，每個玩家賦予一個經(jīng)典命題公式作為目標(biāo)。劉虎研究了各種均衡的計算復(fù)雜性。由于命題邏輯在博弈論中的作用，趙希順、沈榆平研究了作為經(jīng)典計算模型的命題邏輯與非單調(diào)邏輯程序之間的簡潔性問題，并證明了它們之間的不可比較性。這個結(jié)果意味著如果我們用命題邏輯去刻畫一些博弈問題，在某些實例下它與邏輯程序刻畫相比將節(jié)省指數(shù)多的公式；反之，使用邏輯程序去刻畫一些博弈問題，在某些實例下將比命題邏輯節(jié)省指數(shù)多的公式。課題組成員還研究了博弈論中常涉及到的組合原理的證明強度及組合命題強度的新定義，并得到一系列反直觀的結(jié)果，如多數(shù)組合原理本質(zhì)上是相當(dāng)弱的。

四、社會博弈的計算機模擬方向:課題組采用基于agent的計算建模方法，構(gòu)造人工社會模型對主要的社會博弈問題進行了研究。我們針對網(wǎng)絡(luò)結(jié)構(gòu)的社會博弈，對平等規(guī)范的涌現(xiàn)以及公平合作行為的涌現(xiàn)進行了分析。規(guī)范的涌現(xiàn)與演化是社會現(xiàn)象的重要特點。從復(fù)雜性和計算建模的角度對其進行研究已經(jīng)成為社會科學(xué)的重要研究方向。我們重點考慮社會博弈行為者的特點，尤其是agent社會性行為特征。在社會博弈中，agent之間的博弈涉及到大量個體之間的互動，這個互動博弈的個體之間往往具有比較復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，而這種互動結(jié)構(gòu)對社會博弈有重要的影響。我們通過計算模擬，分析了社會博弈中agent互動網(wǎng)絡(luò)結(jié)構(gòu)和平等規(guī)范涌現(xiàn)的關(guān)系，并考慮了在社會博弈中，平等規(guī)范如何能夠從社會網(wǎng)絡(luò)中agent的分布式互動中產(chǎn)生出來，以及不同的社會網(wǎng)絡(luò)結(jié)構(gòu)對平等規(guī)范的涌現(xiàn)具有何種不同的影響等問題。我們的貢獻是對不同網(wǎng)絡(luò)結(jié)構(gòu)如規(guī)則網(wǎng)格、小世界網(wǎng)絡(luò)以及BA無標(biāo)度等幾種重要的網(wǎng)絡(luò)結(jié)構(gòu)類型對平等規(guī)范產(chǎn)生的影響進行了深入的分析。結(jié)果表明平等的規(guī)范確實可以從大量agent的互動中涌現(xiàn)出來，但是不同的社會結(jié)構(gòu)有不同的影響，更趨于平等網(wǎng)絡(luò)節(jié)點度數(shù)分布的網(wǎng)絡(luò)結(jié)構(gòu)如WS小世界網(wǎng)絡(luò)更加有利于平等規(guī)范的涌現(xiàn)。此外，我們還分析了網(wǎng)絡(luò)結(jié)構(gòu)中的其他因素如鄰域的大小，agent社會學(xué)習(xí)對結(jié)果的影響。我們的另外一個貢獻是修改了agent初始策略分布。在現(xiàn)有的研究中，agent策略的初始分布式離散的，取有限的幾種離散值進行討價還價策略，我們在研究中將agent策略擴展為分布在[0,1]區(qū)間的連續(xù)值。顯然這種設(shè)置更加符合現(xiàn)實的情況，而且在這種情況下，我們通過計算模擬還是可以發(fā)現(xiàn)平等規(guī)范從agent的博弈中產(chǎn)生。這方面研究對于深入理解社會博弈的特點，社會規(guī)范的產(chǎn)生與演化是很有意義的工作。

②調(diào)查研究及學(xué)術(shù)交流情況

為開展社會博弈的理論基礎(chǔ)研究，課題組員在西藏藏族地區(qū)開展了為期近半年的人類學(xué)實證研究，收集了大量的經(jīng)驗數(shù)據(jù)，并完成了相關(guān)的數(shù)據(jù)整理和分析工作。在基于扎實的田野考察和全面的數(shù)據(jù)分析整理，我們對藏族群體（宗教）交流互動的語言模式、語用規(guī)則和基本模型進行了恰當(dāng)?shù)姆治雠c提煉，進一步提出和發(fā)展了著重社會文化因素分析的廣義論證理論。立項以來課題組先后10余人次參加國際學(xué)術(shù)會議。鞠實兒、謝耘還先后赴埃及、葡萄牙進行學(xué)術(shù)交流活動，發(fā)表了相關(guān)的研究成果，并拓展了與國外學(xué)者和機構(gòu)的合作研究。其中，在葡萄牙舉辦的“首屆歐洲論證研究國際學(xué)術(shù)會議”(2015年6月9日-12日)，鞠實兒教授和謝耘副教授的報告引起了眾多國際學(xué)者的關(guān)注。 在社會博弈的計算復(fù)雜性和數(shù)理基礎(chǔ)方向，課題組成員積極進行學(xué)術(shù)交流及舉辦有重要影響的國際學(xué)術(shù)會議。劉虎應(yīng)邀在第13屆亞洲邏輯會議上作特邀報告。在2014年7月，趙希順、沈榆平等赴奧地利維也納參加維也納邏輯之夏系列學(xué)術(shù)會議，特別地，在知識表示與推理國際會議上報告了課題組的研究成果；2014年5月，課題組成員在希臘召開的SETN人工智能會議上報告了信息不完全條件下進行規(guī)劃的邏輯系統(tǒng)研究成果。此外，課題組王瑋副教授、尹一木副教授分別赴新加坡、法國等地學(xué)術(shù)機構(gòu)進行學(xué)術(shù)訪問與交流。鮮于波參加國際會議 International Conference on Management Science and Industrial Engineering（ICMSIE2014） 和International Conference on Economics and Management Engineering (ICEME 2014)。2014年7月趙希順應(yīng)邀訪問德國帕德博恩大學(xué)計算機系交流研究成果。在2014、2015年上半年，德國Paderborn大學(xué)Hans Klein Buening教授和英國Swansea大學(xué)Oliver Kullmann博士來訪中山大學(xué)，就基于命題邏輯的計算模型相關(guān)復(fù)雜性問題進行了深入的合作。

二、 研究成果情況

①代表性成果簡介

1. 社會選擇的可接受性問題研究

本研究內(nèi)容主要圍繞兩個核心論點展開，一是社會理性與集體可接受性是等價的，社會理性的目的是實現(xiàn)集體可接受；二是對集體選擇結(jié)果可接受的理性要求下，能夠得到合理的判斷聚合規(guī)則，即克服判斷聚合的不可能性定理。我們首先對社會理性展開分析，指出如果將社會理性看做一種方法，它是一個具有個體主體性、目的性，以及強調(diào)個體的審思和人際間比較的方法。在可接受性方面，我們系統(tǒng)的研究了可接受性理論發(fā)展的歷史和現(xiàn)狀，在對概然主義和似真主義兩大實現(xiàn)可接受性的主要路徑批判的基礎(chǔ)上，我們在“可行能力”理論基礎(chǔ)上，提出了一種“可行的可接受性”實現(xiàn)方法。在此基礎(chǔ)上對社會理性和集體可接受性進行了深入的分析，并建立了兩者之間的關(guān)系，發(fā)現(xiàn)揭開最大化、一致性和公平正義等社會理性可能目的的面紗，社會理性的目的只有實現(xiàn)集體的可接受，換句話說，當(dāng)我們討論社會選擇是否理性的時候，實質(zhì)上只是在說能否達成社會共識，也即實現(xiàn)了社會的可接受。通過這一部分的研究，我們成功的將對社會理性的討論轉(zhuǎn)化為對集體可接受性的討論。

在前面分析的基礎(chǔ)上，我們提出了集體判斷的理性即為集體可接受性。為此，進一步構(gòu)建了基于“可行的可接受性”理論的兩階段方法，用以刻畫集體可接受性，并建立了形式化的模型，證明了該方法能夠克服判斷聚合困境，能夠在社會選擇中找到理性的判斷聚合規(guī)則。更進一步的，我們還證明了這種兩階段的集體可接受性刻畫模式是不能分離的，如果只是對結(jié)論的可接受性進行判定，有可能為一些看似不民主的聚合規(guī)則作出辯護，比如少數(shù)決定制。

總體上看，本研究提出了一種關(guān)于社會理性新的觀點，即可行的集體可接受性可以充分表達社會理性，并證明了這種觀點可以解決經(jīng)典的集體選擇邏輯困境。本書對于加深人們對于社會理性的認(rèn)識，對于推動社會選擇理論和判斷聚合理論的發(fā)展，對于在當(dāng)前這樣一個多元的社會，建立更為恰當(dāng)?shù)膫�人意見匯聚機制具有積極的理論意義和現(xiàn)實價值。

2. 博弈決策模型及信念修正

探討了在現(xiàn)實中，由于信息不完全造成的博弈者對博弈信息掌握的不確定性。在這種情況下，博弈者對同一個策略集可能有不同的最優(yōu)態(tài)度。熊衛(wèi)教授使用Hurwicz標(biāo)準(zhǔn)和Dempster-Shafer理論提出了一種決策規(guī)則，基于這種決策規(guī)則，給出了新的博弈模型，并討論了該博弈模型的各種性質(zhì)。進而討論博弈者對缺乏關(guān)于其它博弈者類型的信息問題，給出了該情況下的貝葉斯博弈模型，并討論了該模型的一系列重要性質(zhì)。袁永峰、文學(xué)峰還研究了博弈者的信念系統(tǒng)及其信念修正問題。給出了一種新的信念修正算子，用以處理在存在核心信息的情況下，如何根據(jù)新信念修正原有信念系統(tǒng)的問題。通過大量的文獻對比，說明給出的信念修正函數(shù)具有廣泛性和一般性。文章均發(fā)表在國際權(quán)威雜志International Journal of Intelligent Systems 和 Journal of Logic and Computation。

3.基于邏輯的計算模型能力研究

經(jīng)典的命題邏輯被作為一個通用的形式系統(tǒng)，在自動推理、知識表示、博弈問題的刻畫等領(lǐng)域得到廣泛地應(yīng)用，它也是第一個被證明是NP完全問題，因此對其計算能力的研究是非常重要的。特別的，非單調(diào)的邏輯程序也是一個NP完全推理難度的系統(tǒng)，近年來廣泛用于知識表示、自動談判等領(lǐng)域。從計算模型角度研究二者的區(qū)別，吸引了許多學(xué)者開展工作。在2006年，美國學(xué)者Vladimir Lifschitz教授及哥德爾獎得主、A. Razborov教授證明了存在一些用邏輯程序可以簡潔刻畫的問題，在命題邏輯下無法簡潔刻畫。也就是說，使用邏輯程序在刻畫某些問題時有較強的簡潔表示能力。但是，是否邏輯程序在所有問題的刻畫，都有較強的簡潔表示能力呢？ 課題組成員最近證明存在一些問題，使用命題邏輯可以進行簡潔的刻畫，而邏輯程序無法簡潔刻畫。結(jié)果表明，這兩個計算模型在計算能力或簡潔性上，是不可比較的。該結(jié)果發(fā)表在人工智能領(lǐng)域內(nèi)知名的-知識表示與推理國際會議，得到許多國際同行的積極評價。如一名國際同行審稿人稱此成果為“...nice work that closes a gap by proving a rather interesting and at first glance may be somewhat unintuitive result. I find these questions fascinating and worth of study.”

4. 社會博弈Nash討價還價模型的模擬研究

課題組在改進的Nash討價還價模型上，研究agent的偏好能否通過分布式博弈趨向于平等的規(guī)范。研究了不同網(wǎng)絡(luò)結(jié)構(gòu)如規(guī)則網(wǎng)格、小世界網(wǎng)絡(luò)以及BA無標(biāo)度等幾種重要的網(wǎng)絡(luò)結(jié)構(gòu)類型對平等規(guī)范產(chǎn)生的影響。研究的結(jié)果表明平等的規(guī)范確實可以從大量agent的互動中涌現(xiàn)出來，但是不同的社會結(jié)構(gòu)有不同的影響，更趨于平等網(wǎng)絡(luò)節(jié)點度數(shù)分布的網(wǎng)絡(luò)結(jié)構(gòu)如WS小世界網(wǎng)絡(luò)更加有利于平等規(guī)范的涌現(xiàn)。此外，網(wǎng)絡(luò)結(jié)構(gòu)中的其他因素如鄰域的大小，agent社會學(xué)習(xí)對結(jié)果的影響也得到了計算模型的研究。這對于研究社會系統(tǒng)中規(guī)范包括平等規(guī)范的涌現(xiàn)具有較好的理論價值，加深對社會科學(xué)動態(tài)演化過程的理解。在修改后的Nash討價還價網(wǎng)絡(luò)模型中，研究平等規(guī)范的涌現(xiàn)。論文的一個貢獻是修改了agent初始策略分布。在現(xiàn)有的研究中，agent策略的初始分布式離散的，取有限的幾種值和討價還價策略，我們在研究中將agent策略擴展為分布在[0,1]區(qū)間的連續(xù)值，并在此及情況下，研究了平等規(guī)范的涌現(xiàn)以及網(wǎng)絡(luò)結(jié)構(gòu)等因素對該規(guī)范產(chǎn)生的影響。該研究對于進一步理解社會規(guī)范涌現(xiàn)的條件與可能性提供了理論上更加一般化的解釋。

本模型編寫的計算模型程序提供了一個計算實驗的平臺，據(jù)此我們可以對影響價格的相關(guān)因素選取不同的值進行多次重復(fù)的計算模擬實驗，得到相關(guān)因素對價格的影響。因此通過這樣的一個計算和評估的平臺，我們可以檢測各種模型參數(shù)調(diào)整對價格的影響，因此能夠通過計算實驗各種因素對市場價格和演化的影響，從而對干預(yù)策略的制定具有一定的參考價值。這方面的工作涉及到計算機制設(shè)計的研究，是將來的一個研究方向。 

課題組供稿