多Agent系統(tǒng)的標(biāo)準(zhǔn)結(jié)構(gòu)(Jennings,2000)

1、 交互式系統(tǒng)才是日常計(jì)算世界的典型形式，幾乎最普通的系統(tǒng)中也包含一些子系統(tǒng)，他們必須互相交互以成功地完成它們的任務(wù)。構(gòu)造單Agent-構(gòu)造Agent社會(huì)多Agent系統(tǒng)的標(biāo)準(zhǔn)結(jié)構(gòu)（Jennings,2000）作用范圍標(biāo)準(zhǔn)結(jié)構(gòu)的說(shuō)明w包含多個(gè)Agent，通過(guò)通信互相交互；wAgent可以在環(huán)境中動(dòng)作，不同的Agent有不同的作用范圍，表示它們可以控制、至少是影響環(huán)境的不同部分。在有些情況下，影響的范圍可能會(huì)有重疊，而影響范圍重疊的事實(shí)會(huì)產(chǎn)生Agent之間的依賴關(guān)系。例如不能通過(guò)同一道門。wAgent一般也會(huì)通過(guò)其他關(guān)系關(guān)聯(lián)起來(lái)，如“權(quán)力”的例子，一個(gè)Agent是另一個(gè)Agent的老板。第五章 多

2、Agent交互w博弈論相關(guān)介紹w效用和偏好w多Agent相遇w優(yōu)勢(shì)策略與Nash平衡w競(jìng)爭(zhēng)與零和交互w囚犯兩難w多Agent系統(tǒng)的依賴關(guān)系例子石頭、剪刀、布未定，未定休息，找水找水，休息找水，休息未定，未定休息，找水休息，找水找水，休息未定，未定豬八戒石頭剪刀布孫悟空石頭剪刀布定義：博弈論是專門研究博弈如何出現(xiàn)均衡的規(guī)律的學(xué)科。例子諾曼底登陸定義：博弈是指決策主體在相互對(duì)抗中，對(duì)抗雙方（或多方）相互依存的一系列策略和行動(dòng)的過(guò)程集合。失敗，成功成功，失敗成功，失敗失敗，成功德軍馬賽設(shè)防諾曼底設(shè)防盟軍馬賽登陸諾曼底登陸博弈的四要素v參與者：參與博弈的決策主體。判斷博弈參與者的根本標(biāo)志是是否是博弈的

3、利害關(guān)系者。v博弈的規(guī)則：對(duì)博弈作出具體規(guī)定的集合。它包含對(duì)參與者行動(dòng)順序的規(guī)定、當(dāng)某個(gè)參與者行動(dòng)時(shí)他所知道的信息、有什么樣的行動(dòng)可供選擇、選擇之后會(huì)有什么樣的結(jié)果，等等。v結(jié)果：對(duì)所有參與者的每一個(gè)可能的行動(dòng)組合，會(huì)出現(xiàn)什么樣的結(jié)果。v收益：在可能的每一個(gè)結(jié)果上，參與者的所得和所失，就是在所有可能的結(jié)果上參與者的偏好是什么，這意味著博弈的每一位參與者會(huì)在不同結(jié)果之間進(jìn)行比較，以尋求最好的收益。博弈的表述可以用參與者、策略和收益函數(shù)來(lái)表述一個(gè)博弈。孫悟空的策略函數(shù)：豬八戒的策略函數(shù)：211322112312( ), (), ();sssf aa f aa f aa112312211322( )

4、, (), ( );zzzf aaf aaf aa如石頭、剪刀、布的例子：參與者集合：I=1,2/其中表示孫悟空，表示豬八戒收益函數(shù)是策略組合和收益之間所建立的一種函數(shù)關(guān)系。 如：11123(,)uaaA 博弈的分類靜態(tài)博弈動(dòng)態(tài)博弈完全信息博弈不（非）完全信息博弈如果博弈雙方同時(shí)行動(dòng)，即一方在作出行動(dòng)時(shí)并不清楚對(duì)手是否已經(jīng)作出了行動(dòng)，則為靜態(tài)博弈。如果一方在作出行動(dòng)時(shí)，知道對(duì)手已經(jīng)作出了行動(dòng)（可能不知道具體行動(dòng)是什么），則為動(dòng)態(tài)博弈。如果所有參與者對(duì)其收益的信念是確定的，那么這個(gè)博弈就是完全信息的。也就是每一個(gè)參與者都能明確地計(jì)算出彼此的收益。相反，則為不完全信息博弈。博弈的其他例子鴿派和鷹派

5、燭光晚餐思考：能否將身邊一些情況描述成博弈？具體例子？抽象成博弈的四個(gè)要素，并進(jìn)行表述和分類。效用和偏好w自利的：即每個(gè)Agent對(duì)世界應(yīng)該是什么樣子有自己的偏好和愿望。w存在一個(gè)關(guān)于Agent偏好的結(jié)局或者狀態(tài)的集合w假設(shè)只有兩個(gè)Agent為i和j,21效用和偏好 可以用效用函數(shù)形式化地描述這兩個(gè)Agent的偏好，每個(gè)Agent有一個(gè)效用函數(shù)。給每個(gè)結(jié)局賦予一個(gè)實(shí)數(shù)，表示這個(gè)結(jié)局對(duì)于該Agent來(lái)說(shuō)有多“好”，數(shù)值越大，從這個(gè)Agent的角度來(lái)說(shuō)效用越好。RuiRuj導(dǎo)出一個(gè)關(guān)于輸出的偏好排序效用和金錢的比喻富人和窮人在一個(gè)小區(qū)內(nèi)，住著一個(gè)富人和一個(gè)窮人。組織夜間巡邏能有效防止偷盜，但夜間巡

6、邏的成本為。假設(shè)富人的財(cái)產(chǎn)為，窮人的財(cái)產(chǎn)為2。如果兩人都巡邏，那么巡邏成本由兩人均攤，如果只有一人巡邏，則由巡邏者承擔(dān)。6，04，28，00，0窮人巡邏不巡邏富人巡邏不巡邏偏好排序 如果 和 是集合 中可能的結(jié)局,有) ()(iiuu則Agent i的結(jié)局 至少與 一樣好,簡(jiǎn)寫為：ii嚴(yán)格好于偏好排序 的性質(zhì)i 自反性：具體含義見(jiàn)板書 傳遞性：具體含義見(jiàn)板書 比較性：具體含義見(jiàn)板書說(shuō)明：嚴(yán)格偏好關(guān)系僅滿足后兩個(gè)性質(zhì),顯然不是自反的。多Agent相遇前面所述為Agent偏好的模型，下面引入環(huán)境模型，使得Agent可以在這個(gè)環(huán)境中動(dòng)作。用下面的環(huán)境函數(shù)表示： AcAc:,DCAc 說(shuō)明：Agent

7、 i的動(dòng)作Agent j的動(dòng)作C代表合作，D代表不合作每個(gè)Agent必須執(zhí)行一個(gè)動(dòng)作，且它們不能看到其他Agent執(zhí)行的動(dòng)作環(huán)境函數(shù)例子1),(DD這個(gè)環(huán)境把每個(gè)動(dòng)作組合映射成不同的結(jié)局，因此環(huán)境對(duì)每個(gè)Agent執(zhí)行的動(dòng)作都是敏感的。思考？?jī)煞N極端怎么表示？ 只對(duì)一個(gè)Agent的動(dòng)作敏感只對(duì)一個(gè)動(dòng)作敏感2),(CD3),(DC4),(CC標(biāo)準(zhǔn)的博弈論收益矩陣的表示法i不合作i合作j不合作j合作44141141優(yōu)勢(shì)策略定義：優(yōu)勢(shì)假設(shè)兩個(gè) 的子集 ，如果對(duì)i希望 中的每個(gè)結(jié)局超過(guò) 中的每個(gè)結(jié)局，則對(duì)于Agent i來(lái)說(shuō) 優(yōu)勢(shì)于舉例見(jiàn)板書進(jìn)一步引出強(qiáng)優(yōu)于21 和1212策略：將動(dòng)作視為策略，在多Ag

8、ent交互的情形下，對(duì)于Agent i的任何特定策略s，會(huì)有很多可能 的結(jié)局，用s*表示采用策略s產(chǎn)生的結(jié)局。強(qiáng)優(yōu)勢(shì)策略弱優(yōu)勢(shì)策略優(yōu)勢(shì)策略的作用？如果有多個(gè)優(yōu)勢(shì)策略，怎么辦？Nash（納什）平衡兩個(gè)策略s1和s2是處于Nash平衡，如果：（1）在Agent i執(zhí)行s1這樣的假設(shè)下，Agent j最好執(zhí)行s2;（2）在Agent j執(zhí)行s2這樣的假設(shè)下，Agent i最好執(zhí)行s1;重要性是什么：？然而，（1）并不是每個(gè)交互的情形都有Nash平衡； （2）有些交互的情形存在有一個(gè)以上的Nash平衡。習(xí)題（1）,654321451326iiiii,62433432311問(wèn)題：哪些集合（如果存在的話）

9、優(yōu)勢(shì)于另一些集合？當(dāng)沒(méi)有集合優(yōu)勢(shì)于其他集合時(shí)，給出說(shuō)明。習(xí)題（2）設(shè)想在古代的一個(gè)村莊有兩個(gè)獵人。為了簡(jiǎn)化問(wèn)題，假設(shè)主要的獵物只有兩種：鹿和兔子。在古代，人類的狩獵手段比較落后，弓箭的威力也有限。在這樣的條件下，我們可以假設(shè)，兩個(gè)獵人一起去獵鹿，才能獵獲1只鹿。如果一個(gè)獵人單兵作戰(zhàn)，他只能打到4只兔子。從填飽肚子的角度來(lái)說(shuō)，4只兔子算管4天吧，1只鹿卻差不多能夠解決一個(gè)月的問(wèn)題。這樣，兩個(gè)人的行為決策就可以寫成以下的博弈形式：要么分別打兔子，每人得4；要么合作，每人得10(平分鹿之后的所得)。判斷其中的Nash平衡。習(xí)題（3）i不合作i合作j不合作j合作-1-121-1-112i不合作i合作j

10、不合作j合作33422411問(wèn)題：（1）從非形式地分析各情形，決定兩個(gè)Agent應(yīng)該做什么行動(dòng)。（2）根據(jù)結(jié)局對(duì)Agent的偏好進(jìn)行排序。（3）決定哪個(gè)策略是強(qiáng)優(yōu)勢(shì)策略或弱優(yōu)勢(shì)策略。（4）判斷出任何Nash平衡。競(jìng) 爭(zhēng)w競(jìng)爭(zhēng)的定義：Agent i希望得到結(jié)局 超過(guò)得到結(jié)局 ，當(dāng)且僅當(dāng)Agent j希望得到 超過(guò)得到結(jié)局 這樣，局中人的偏好相互處在完全對(duì)立的位置上：一個(gè)Agent要提高其效用，必須以另一個(gè)Agent的付出為代價(jià)。w例子？ji當(dāng)且僅當(dāng)零和交互w定義：對(duì)于任何特定的結(jié)局，兩個(gè)Agent的效用之和為零。對(duì)所有, 0)()(jiuu任何零和的情形都是嚴(yán)格的競(jìng)爭(zhēng)。囚犯兩難兩個(gè)人被共同起訴一

11、項(xiàng)罪名，被關(guān)押在隔離的牢房里，它們沒(méi)有辦法互相通信，也沒(méi)有辦法達(dá)成任何一致，這兩個(gè)人被告知：（1）如果其中一人承認(rèn)有罪而另一個(gè)人沒(méi)有承認(rèn)，承認(rèn)有罪者將被釋放，另一個(gè)人將被關(guān)押3年；（2）如果兩個(gè)人都承認(rèn)有罪，則每人將被關(guān)押2年；（3）如果都不承認(rèn)有罪，則每個(gè)人將被關(guān)押1年。思考和討論：如果是你，你將怎么做？囚犯兩難問(wèn)題的收益矩陣i不合作i合作j不合作j合作22053350課堂習(xí)題:根據(jù)收益矩陣寫出效用函數(shù)，并對(duì)每個(gè)結(jié)局進(jìn)行排序；分析有沒(méi)有強(qiáng)優(yōu)勢(shì)策略，如果有，是什么？分析是否存在Nash平衡，如果有，是什么？思考為什么說(shuō)是囚犯兩難？囚犯兩難問(wèn)題的改進(jìn)（Axelrod）進(jìn)行一次以上的對(duì)策?？芍貜?fù)進(jìn)

12、行對(duì)局，且每個(gè)Agent都可以看到其對(duì)手前一輪的選擇。另外，假設(shè)對(duì)局將連續(xù)永不停止，那么，理性的動(dòng)作是什么？如果你知道下一輪會(huì)遇到同一個(gè)對(duì)手，不合作的動(dòng)機(jī)似乎會(huì)大大減少，這有兩個(gè)原因：（1）如果你現(xiàn)在不合作，你的對(duì)手也可以通過(guò)不合作懲罰你，雖然這種懲罰不可能發(fā)生某一輪；（2）因?yàn)橐M(jìn)行無(wú)限輪的對(duì)局，某次的效用損失會(huì)在將來(lái)的輪次中“償還”，也就是，由于是無(wú)限期的對(duì)局，一個(gè)單元的效用損失只是獲得的整個(gè)效用的一小部分。做試驗(yàn)，采用幾個(gè)策略：ALL-DRANDOMTIT-FOR-TATTESTER或者更多策略，分析哪個(gè)測(cè)略更好多Agent系統(tǒng)的依賴關(guān)系 獨(dú)立：Agent之間沒(méi)有依賴關(guān)系； 單向依賴：一

13、個(gè)Agent依賴于另一個(gè)Agent，反之不成立 相互依賴：為了共同的目標(biāo)，兩個(gè)Agent相互依賴； 交互依賴：為了某一目標(biāo)第一個(gè)Agent依賴于第二個(gè)Agent，而第二個(gè)Agent為了實(shí)現(xiàn)某一目標(biāo)也依賴于第一個(gè)Agent（兩個(gè)目標(biāo)不必相同）。注意：相互依賴蘊(yùn)含著交互依賴。這些關(guān)系可以通過(guò)局部信念還是全局信念加以限定。局部信念：如果一個(gè)Agent相信依賴關(guān)系存在，但是不認(rèn)為其他Agent相信依賴關(guān)系存在；全局信念：當(dāng)Agent相信依賴關(guān)系存在，還相信另一個(gè)Agent也知道這一點(diǎn)。博弈論題目：屠夫砍人博弈論題目：屠夫砍人 有一個(gè)屠夫抓了100人,讓他們面朝一個(gè)方向排成一堅(jiān)列,然后給這100人分別戴上帽子,帽子只有黑和白兩種顏色,屠夫是隨機(jī)給他們帶上的,且自己看不見(jiàn)自己帽子的顏色,也不能回頭,只能看到自己前面人的顏