第五章多agent交互

1、交互式系統(tǒng)才是日常計算世界的典型形式，幾乎最普通的系統(tǒng)中也包含一些子系統(tǒng)，他們必須互相交互以成功地完成它們的任務。構(gòu)造單Agent->構(gòu)造Agent社會,多Agent系統(tǒng)的標準結(jié)構(gòu)（Jennings,2000）,標準結(jié)構(gòu)的說明,包含多個Agent，通過通信互相交互；Agent可以在環(huán)境中動作，不同的Agent有不同的作用范圍，表示它們可以控制、至少是影響環(huán)境的不同部分。在有些情況下，影響的范圍可能會有重疊，而影響范圍重疊的事

2、實會產(chǎn)生Agent之間的依賴關(guān)系。例如不能通過同一道門。Agent一般也會通過其他關(guān)系關(guān)聯(lián)起來，如“權(quán)力”的例子，一個Agent是另一個Agent的老板。,第五章 多Agent交互,博弈論相關(guān)介紹效用和偏好多Agent相遇優(yōu)勢策略與Nash平衡競爭與零和交互囚犯兩難多Agent系統(tǒng)的依賴關(guān)系,例子１．石頭、剪刀、布,豬八戒,石頭　　　　剪刀　　　布,孫悟空,石頭剪刀布,定義：博弈論是專門研究博弈如何出現(xiàn)均衡的規(guī)律的學

3、科。,例子２．諾曼底登陸,定義：博弈是指決策主體在相互對抗中，對抗雙方（或多方）相互依存的一系列策略和行動的過程集合。,德軍,馬賽設(shè)防　諾曼底設(shè)防,盟軍,馬賽登陸諾曼底登陸,博弈的四要素,參與者：參與博弈的決策主體。判斷博弈參與者的根本標志是是否是博弈的利害關(guān)系者。博弈的規(guī)則：對博弈作出具體規(guī)定的集合。它包含對參與者行動順序的規(guī)定、當某個參與者行動時他所知道的信息、有什么樣的行動可供選擇、選擇之后會有什么樣的結(jié)果，等等。結(jié)果：對所

4、有參與者的每一個可能的行動組合，會出現(xiàn)什么樣的結(jié)果。收益：在可能的每一個結(jié)果上，參與者的所得和所失，就是在所有可能的結(jié)果上參與者的偏好是什么，這意味著博弈的每一位參與者會在不同結(jié)果之間進行比較，以尋求最好的收益。,博　弈　的　表　述,可以用參與者、策略和收益函數(shù)來表述一個博弈。,孫悟空的策略函數(shù)：豬八戒的策略函數(shù)：,如石頭、剪刀、布的例子：,參與者集合：I={1,2}//其中１表示孫悟空，２表示豬八戒,收益函數(shù)是策略組合和收益之

5、間所建立的一種函數(shù)關(guān)系。 如：,博　弈　的　分　類,靜態(tài)博弈動態(tài)博弈完全信息博弈不（非）完全信息博弈,如果博弈雙方同時行動，即一方在作出行動時并不清楚對手是否已經(jīng)作出了行動，則為靜態(tài)博弈。如果一方在作出行動時，知道對手已經(jīng)作出了行動（可能不知道具體行動是什么），則為動態(tài)博弈。,如果所有參與者對其收益的信念是確定的，那么這個博弈就是完全信息的。也就是每一個參與者都能明確地計算出彼此的收益。相反，則為不完全信息博弈。

6、,博弈的其他例子,１．鴿派和鷹派２．燭光晚餐３．……思考：能否將身邊一些情況描述成博弈？具體例子？抽象成博弈的四個要素，并進行表述和分類。,效用和偏好,自利的：即每個Agent對世界應該是什么樣子有自己的偏好和愿望。存在一個關(guān)于Agent偏好的結(jié)局或者狀態(tài)的集合,假設(shè)只有兩個Agent為i和j,效用和偏好,可以用效用函數(shù)形式化地描述這兩個Agent的偏好，每個Agent有一個效用函數(shù)。給每個結(jié)局賦予一個實數(shù)，表示這個結(jié)局對

7、于該Agent來說有多“好”，數(shù)值越大，從這個Agent的角度來說效用越好。,導出一個關(guān)于輸出的偏好排序,效用和金錢的比喻,富人和窮人,在一個小區(qū)內(nèi)，住著一個富人和一個窮人。組織夜間巡邏能有效防止偷盜，但夜間巡邏的成本為４。假設(shè)富人的財產(chǎn)為８，窮人的財產(chǎn)為2。如果兩人都巡邏，那么巡邏成本由兩人均攤，如果只有一人巡邏，則由巡邏者承擔。,窮人,巡邏　　不巡邏,富人,巡邏不巡邏,偏好排序,如果 和 是集合 中可能

8、的結(jié)局,有,則Agent i的結(jié)局 至少與 一樣好,簡寫為：,嚴格好于,偏好排序 的性質(zhì),自反性：具體含義見板書 傳遞性：具體含義見板書 比較性：具體含義見板書,說明：嚴格偏好關(guān)系僅滿足后兩個性質(zhì),顯然不是自反的。,多Agent相遇,前面所述為Agent偏好的模型，下面引入環(huán)境模型，使得Agent可以在這個環(huán)境中動作。用下面的環(huán)境函數(shù)表示：,說明：,,Agent i的動作,,Agent j的

9、動作,C代表合作，D代表不合作,每個Agent必須執(zhí)行一個動作，且它們不能看到其他Agent執(zhí)行的動作,環(huán)境函數(shù)例子,這個環(huán)境把每個動作組合映射成不同的結(jié)局，因此環(huán)境對每個Agent執(zhí)行的動作都是敏感的。思考？兩種極端怎么表示？？ 只對一個Agent的動作敏感只對一個動作敏感,標準的博弈論收益矩陣的表示法,優(yōu)勢策略,定義：優(yōu)勢假設(shè)兩個 的子集—— ，如果對i希望 中的每個結(jié)局超過

10、中的每個結(jié)局，則對于Agent i來說 優(yōu)勢于舉例見板書進一步引出強優(yōu)于,策略：將動作視為策略，在多Agent交互的情形下，對于Agent i的任何特定策略s，會有很多可能 的結(jié)局，用s*表示采用策略s產(chǎn)生的結(jié)局。,強優(yōu)勢策略弱優(yōu)勢策略,優(yōu)勢策略的作用？？如果有多個優(yōu)勢策略，怎么辦？？？,Nash（納什）平衡,兩個策略s1和s2是處于Nash平衡，如果：（1）在Agent i執(zhí)行s1這樣的假設(shè)下，Agent j最好執(zhí)行

11、s2;（2）在Agent j執(zhí)行s2這樣的假設(shè)下，Agent i最好執(zhí)行s1;,重要性是什么：？？？,然而，（1）并不是每個交互的情形都有Nash平衡； （2）有些交互的情形存在有一個以上的Nash平衡。,習題（1）,問題：哪些集合（如果存在的話）優(yōu)勢于另一些集合？當沒有集合優(yōu)勢于其他集合時，給出說明。,習題（2）,設(shè)想在古代的一個村莊有兩個獵人。為了簡化問題，假設(shè)主要的獵物只有兩種：鹿和兔子。在古代，人類的狩

12、獵手段比較落后，弓箭的威力也有限。在這樣的條件下，我們可以假設(shè)，兩個獵人一起去獵鹿，才能獵獲1只鹿。如果一個獵人單兵作戰(zhàn)，他只能打到4只兔子。從填飽肚子的角度來說，4只兔子算管4天吧，1只鹿卻差不多能夠解決一個月的問題。這樣，兩個人的行為決策就可以寫成以下的博弈形式：要么分別打兔子，每人得4；要么合作，每人得10(平分鹿之后的所得)。判斷其中的Nash平衡。,習題（3）,問題：（1）從非形式地分析各情形，決定兩個Agent應該做什

13、么行動。（2）根據(jù)結(jié)局對Agent的偏好進行排序。（3）決定哪個策略是強優(yōu)勢策略或弱優(yōu)勢策略。（4）判斷出任何Nash平衡。,競 爭,競爭的定義：Agent i希望得到結(jié)局 超過得到結(jié)局 ，當且僅當Agent j希望得到 超過得到結(jié)局 這樣，局中人的偏好相互處在完全對立的位置上：一個Agent要提高其效用，必須以另一個Agent的付出為代價。例子？？,零和交互,定義：對于任何特定的結(jié)局，兩

14、個Agent的效用之和為零。,任何零和的情形都是嚴格的競爭。,囚犯兩難,兩個人被共同起訴一項罪名，被關(guān)押在隔離的牢房里，它們沒有辦法互相通信，也沒有辦法達成任何一致，這兩個人被告知：（1）如果其中一人承認有罪而另一個人沒有承認，承認有罪者將被釋放，另一個人將被關(guān)押3年；（2）如果兩個人都承認有罪，則每人將被關(guān)押2年；（3）如果都不承認有罪，則每個人將被關(guān)押1年。,思考和討論：如果是你，你將怎么做？,囚犯兩難問題的收益矩陣,課堂習題

15、:根據(jù)收益矩陣寫出效用函數(shù)，并對每個結(jié)局進行排序；分析有沒有強優(yōu)勢策略，如果有，是什么？分析是否存在Nash平衡，如果有，是什么？,思考為什么說是囚犯兩難？,囚犯兩難問題的改進（Axelrod）,進行一次以上的對策?？芍貜瓦M行對局，且每個Agent都可以看到其對手前一輪的選擇。另外，假設(shè)對局將連續(xù)永不停止，那么，理性的動作是什么？如果你知道下一輪會遇到同一個對手，不合作的動機似乎會大大減少，這有兩個原因：（1）如果你現(xiàn)在不合作，

16、你的對手也可以通過不合作懲罰你，雖然這種懲罰不可能發(fā)生某一輪；（2）因為要進行無限輪的對局，某次的效用損失會在將來的輪次中“償還”，也就是，由于是無限期的對局，一個單元的效用損失只是獲得的整個效用的一小部分。,做試驗，采用幾個策略：ALL-DRANDOMTIT-FOR-TATTESTER或者更多策略，分析哪個測略更好,多Agent系統(tǒng)的依賴關(guān)系,,獨立：Agent之間沒有依賴關(guān)系； 單向依賴：一個Agent依賴于另一個A

17、gent，反之不成立 相互依賴：為了共同的目標，兩個Agent相互依賴； 交互依賴：為了某一目標第一個Agent依賴于第二個Agent，而第二個Agent為了實現(xiàn)某一目標也依賴于第一個Agent（兩個目標不必相同）。注意：相互依賴蘊含著交互依賴。這些關(guān)系可以通過局部信念還是全局信念加以限定。,局部信念：如果一個Agent相信依賴關(guān)系存在，但是不認為其他Agent相信依賴關(guān)系存在；全局信念：當Agent相信依賴關(guān)系存在，還相

18、信另一個Agent也知道這一點。,博弈論題目：屠夫砍人　 有一個屠夫抓了100人,讓他們面朝一個方向排成一堅列,然后給這100人分別戴上帽子,帽子只有黑和白兩種顏色,屠夫是隨機給他們帶上的,且自己看不見自己帽子的顏色,也不能回頭,只能看到自己前面人的顏色。 他們的視力很好,排最后的那個人(100號)可以看見前面所有人的帽子顏色，他們的聽力都很好,最前面的那個人(1號),可以聽見后面所有人說的話。屠夫會從100號開始要他猜自己