資源描述：
《復(fù)雜網(wǎng)絡(luò)上的博弈演化》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、劉偉2009.11.21Qingdao復(fù)雜網(wǎng)絡(luò)上的博弈演化1、博弈2、復(fù)雜網(wǎng)絡(luò)上的演化博弈2.1、網(wǎng)絡(luò)演化博弈的策略更新規(guī)則2.2、網(wǎng)絡(luò)拓?fù)鋵?duì)合作的影響2.3、記憶對(duì)網(wǎng)絡(luò)博弈中的影響2.4、博弈動(dòng)力學(xué)與網(wǎng)絡(luò)拓?fù)涔惭莼?.5、學(xué)習(xí)機(jī)制導(dǎo)致合作的涌現(xiàn)3、展望一個(gè)個(gè)性和另一個(gè)個(gè)性的聯(lián)結(jié)對(duì)被聯(lián)結(jié)的個(gè)性的命運(yùn)具有多大的意義？你要知道，這是一生的事情，在我們的背后隱藏著無數(shù)的枝節(jié)?！铀纪滓蛩够?《白癡》第501頁一個(gè)游戲：兩人輪流向圓桌上放一元硬幣，誰無法再在圓桌上放硬幣則判負(fù)，另一方獲勝，假設(shè)所有的硬幣不允許重疊。你會(huì)先放還是后放，以何種策略確保自己獲勝?博弈研究的對(duì)
2、象是游戲(Game)，更確切的說，是指在具有雙方相互競(jìng)爭(zhēng)對(duì)立的環(huán)境條件下，參與者依靠所掌握的信息，在一定的規(guī)則約束下，各自選擇策略并取得相應(yīng)結(jié)果(或收益)的過程。博弈論就是使用數(shù)學(xué)模型研究沖突對(duì)抗條件下最優(yōu)決策問題的理論。博弈論被認(rèn)為是研究自然和人類社會(huì)中普遍存在的合作行為最為有力的手段。一、博弈論博弈模型反映了自私的個(gè)體之間的合作競(jìng)爭(zhēng)關(guān)系，能夠很好地刻畫生物系統(tǒng)中生物體之間的相互作用關(guān)系及演化動(dòng)力學(xué)。不論在自然或是社會(huì)系統(tǒng)中，經(jīng)典博弈論告訴我們自私個(gè)體博弈的結(jié)果必然是背叛。顯然是一個(gè)和實(shí)際情況不完全吻合結(jié)論。社會(huì)經(jīng)濟(jì)活動(dòng)中的絕大多數(shù)任務(wù)不可能由單人完成，需要群體
3、的分工和合作。問題:為什么自私的個(gè)體組成的群體會(huì)產(chǎn)生合作行為，存在什么樣的機(jī)制，以及什么樣的條件才會(huì)有合作行為涌現(xiàn)？通常博弈由以下4個(gè)部分所組成:(l)博弈個(gè)體：在一個(gè)博弈中至少有兩位決策者(agent)參與博弈.(2)策略集：個(gè)體的博弈策略可以是純策略，也可以是混合策略博弈的策略集由參與博弈的個(gè)體所有可能采用的策略所組成.(3)收益矩陣：當(dāng)博弈個(gè)體選定好自己的策略后，其所獲取的收益由收益矩陣中的相應(yīng)元素來確定.(4)策略演化:在多輪博弈過程中，博弈個(gè)體遵循自身收益最大化的最終目標(biāo)，即以此目標(biāo)為指導(dǎo)原則來進(jìn)行策略調(diào)整。納什均衡真實(shí)生活中的博弈問題是很復(fù)雜的，可能會(huì)
4、有很多的參與者，每個(gè)參與者都有不同的策略。當(dāng)參與者們?cè)谶M(jìn)行一項(xiàng)博弈的時(shí)候，他們應(yīng)該選擇什么樣的策略?是否有辦法預(yù)言出他們的策略組合(s1，s2，…，sN)?納什(Nash)均衡：其核心思想是對(duì)于兩人或多人博弈，個(gè)體的策略演化會(huì)趨向于一個(gè)均衡態(tài)，在此均衡態(tài)下所有的個(gè)體會(huì)同時(shí)采取“納什均衡策略”。Nash認(rèn)為，博弈問題的解應(yīng)該是這樣的一組策略，在這組策略中，每一個(gè)參與者都無法通過單獨(dú)改變自己的策略而獲得更多的收益。這樣的狀態(tài)就被稱作納什均衡態(tài).實(shí)際上納什均衡態(tài)對(duì)所有的參與者來說，不一定是最好的結(jié)局。下面以囚徒困境博弈和雪堆博弈為例來闡述納什均衡經(jīng)典博弈模型囚徒困境博弈
5、:兩個(gè)小偷A(chǔ)和B合伙作案，被捕后被隔離審訊.如果雙方都拒絕坦白同伴的罪行，兩人將會(huì)被輕判1年徒刑;為此，警方設(shè)計(jì)了一個(gè)機(jī)制:如果A揭發(fā)B的罪行，B拒不供認(rèn)A的罪行，則A將無罪釋放，而B將被重判5年徒刑;如果A、B都揭發(fā)對(duì)方罪行，則雙方均被判刑3年.在此情況下，自私的個(gè)體應(yīng)如何做出抉擇?合作(Cooperate-C)or背叛(defect一D)不論對(duì)手采取哪種策略，選擇背叛策略都是最佳的，即理性的個(gè)體最終會(huì)處于相互背叛的狀態(tài)(注意到此時(shí)的集體收益低于兩人同時(shí)選擇合作時(shí)的情況).這種相互背叛的狀態(tài)(D，D)就是系統(tǒng)的納什均衡態(tài)。對(duì)于兩人博弈，收益矩陣元通常用(R、S、
6、T、P)來表示相互合作則二人同獲得較大收益R，相互背叛則同獲較小收益P，一方合作一方背叛，則背叛者獲得最高收益T，而合作者獲得最低收益S，即參數(shù)滿足關(guān)系:T>R>P>S，此外2R>T+S，即相互合作能獲得集體最高收益.在一個(gè)風(fēng)雪交加的夜晚，兩人開車相向而行，被一個(gè)雪堆所阻，如圖所示.白色和灰色分別表示合作策略與背叛策略.與囚徒困境博弈不同，對(duì)于雪堆博弈，收益矩陣元滿足關(guān)系:T>R>S>P雪堆博弈:假設(shè)鏟除這個(gè)雪堆使道路通暢需要付出的勞動(dòng)量為c，道路通暢則帶給每個(gè)人的好處量化為b(>c)。如果兩人一齊動(dòng)手鏟雪，則他們的收益為R=b一c/2(分別承擔(dān)勞動(dòng)量c/2);如
7、果只有一人下車鏟雪，雖然兩人都能及時(shí)回家，但是背叛者逃避了勞動(dòng)，它的收益為T=b，而合作者的收益為S=b一c;如果兩人都選擇不合作，則兩人都無法及時(shí)回家，其收益量化為P=0.雪堆模型的收益矩陣可表示為那么，理性個(gè)體的最優(yōu)選擇是什么呢?如果對(duì)方選擇背叛策略(呆在車中)，那么另一方的最佳策略是下車鏟雪(因?yàn)榘磿r(shí)回家的利益b一c好于呆在車中的背叛收益0);反之，如果對(duì)方下車鏟雪，則自己的最佳策略是呆在舒服的車中.所以，不同于囚徒困境博弈，在雪堆博弈中存在兩個(gè)納什均衡態(tài)：(C，D)和(D，C).即雪堆博弈中的NE為兩人均以概率r選擇背叛，概率1-r選擇合作，其r=c/(2
8、b-c)稱
