博弈論模板課件

上次內(nèi)容回顧博弈論的定義什么是博弈博弈的要素（參與人、策略集和效用）共同知識假設(shè)博弈論的知識體系完全信息靜態(tài)博弈及其表示占優(yōu)策略和占優(yōu)均衡嚴(yán)劣策略和重復(fù)剔除嚴(yán)劣策略均衡1學(xué)習(xí)交流PPT局中人2LRU局中人1MD5，10，21，34，14，22，3Nodominantstrategiesanddominatedstrategies,whatabouttheresult?2學(xué)習(xí)交流PPTBestResponse(BR)UdoesbestagainstL;MdoesbestagainstR3學(xué)習(xí)交流PPTL、R概率為0.5時ExpectedpayoffofU：2.5ExpectedpayoffofM：2.5ExpectedpayoffofD：3此時，Ddoesbest。4學(xué)習(xí)交流PPT假定1認(rèn)為2選擇r的概率為p(r)，

則1選U、M、D的期望收益分別為

Eu1(U，p(r))=(1-p(r))×5+p(r)×0

Eu1(M，p(r))=(1-p(r))×1+p(r)×2

Eu1(D，p(r))=(1-p(r))×4+p(r)×25學(xué)習(xí)交流PPT）6學(xué)習(xí)交流PPTBR是期望收益最大時的反應(yīng)

圖中x=1/3，y=3/5由圖可知，p(r)≤1/3時，1的最佳反應(yīng)是選U；1/3≤p(r)≤3/5時，1的最佳反應(yīng)是選D；p(r)≥3/5時，1的最佳反應(yīng)是選M。7學(xué)習(xí)交流PPT8學(xué)習(xí)交流PPT點球博弈9學(xué)習(xí)交流PPT10學(xué)習(xí)交流PPTPartnershipGame2人擁有一家公司，每人分享利潤的一半每人的策略:精力投入水平，Si=[0,4]利潤：4×[S1+S2+bS1S2]b=[0,1/4]U1=2×[S1+S2+bS1S2]-S1S1U2=2×[S1+S2+bS1S2]–S2S211學(xué)習(xí)交流PPT參與人的BR是什么？12學(xué)習(xí)交流PPTb=1/4時13學(xué)習(xí)交流PPT14學(xué)習(xí)交流PPT納什均衡15學(xué)習(xí)交流PPTNashEquilibriumTheactionprofiles*isaNashEquilibriumif,foreveryplayeriandeveryactionsiofplayeri,s*isatleastasgoodasaccordingtoplayeri’spreferencesasthetheactionprofile(si*,s-i*)inwhichplayerichoosessi*whileeveryotherplayerchooses-i*.Equivalently,foreveryplayeri,ui(s*)≥ui(si,s-i*),Foreveryactionofplayeri16學(xué)習(xí)交流PPTDefinitionInthen-playergameG={S1,…,Sn;u1,…,un},thestrategiesprofile(s1*…,sn*)areaNashequilibriumif,foreachplayeri,si*is(atleasttiedfor（至少不劣于）)playeri’sbestresponsetothestrategiesspecifiedforthen-1otherplayers,(s1*…,sn-1*,sn+1*,…,sn*):ui(s1*…,sn-1*,si*,

sn+1*,…,sn*)

≥ui(s1*…,sn-1*,si

,

sn+1*,…,sn*)(NE)

17學(xué)習(xí)交流PPTforeveryfeasiblestrategysiinSi;Thatis,si*solves

maxui(s1*…,sn-1*,si,

sn+1*,…,sn*).si∈Si

上述均衡概念是1951年由數(shù)學(xué)家約翰·納什（JohnNash）首先提出的，稱為納什均衡。18學(xué)習(xí)交流PPT納什均衡(NashEquilibrium)定義。對于一個策略式表述的博弈G={N,Si,ui,i∈N}。稱策略組合s*=(s1,…si,…,sn)是一個納什均衡，如果對于每一個i∈N,si*是給定其他參與人選擇s-i*={s1*,…,si-1*,si+1*,…,sn*}情況下參與人i的最優(yōu)策略（經(jīng)濟理性策略），即：ui(si*,s-i*)≥ui(si,s-i*),對于任意的si∈Si,任意的i∈N均成立。19學(xué)習(xí)交流PPT納什均衡的通俗定義

納什均衡是一種策略組合，給定對手的策略，每個參與人選擇自己的最優(yōu)策略。20學(xué)習(xí)交流PPT

1Ifgametheoryistoprovideauniquesolutiontoagame-theoreticproblemthenthesolutionmustbeaNashequilibrium,inthefollowingsense.Supposethatgametheorymakesauniquepredictionaboutthestrategyeachplayerwillchoose.Inorderforthispredictiontobecorrect,itisnecessarythateachplayerbewillingtochoosethestrategypredictedbythetheory.

21學(xué)習(xí)交流PPTThuseachplayer’spredictedstrategymustbethatplayer’sbestresponsetothestrategiesoftheotherplayers.Suchapredictioncouldbecalledstrategicallystableorself-enforcing,becausenosingleplayerwantstodeviatefromhisorherPredictedstrategy.WewillcallsuchapredictionaNashequilibrium.-----------------------------RobertGibbons22學(xué)習(xí)交流PPT2一種穩(wěn)定的策略組合：當(dāng)所有參與人的選擇公開以后，每個人都滿意自己作出了正確的選擇；沒有人能得到更好的結(jié)果了。在博弈論中這種結(jié)果被稱為NE。23學(xué)習(xí)交流PPT3NE的哲學(xué)含義：n個參與人在博弈之前協(xié)商達成一個協(xié)議，規(guī)定每一個參與人選擇一個特定的策略。問題是，給定其他參與人都遵守該協(xié)議，在沒有外在強制的情況下，是否有人選擇不遵守？24學(xué)習(xí)交流PPT只有當(dāng)遵守協(xié)議帶來的效用大于不遵守時，參與人才會遵守。如果沒有任何參與人有積極性不遵守這個協(xié)議，該協(xié)議是可以自動實施的（self-enforcing），構(gòu)成納什均衡；否則，就不是納什均衡。25學(xué)習(xí)交流PPT4納什均衡是一種策略組合，每個參與人的策略是對其他參與人策略的最優(yōu)反應(yīng)。納什均衡是博弈將會如何進行的“一致”（consistent）預(yù)測。如果所有參與人預(yù)測特定納什均衡會出現(xiàn)，那么沒有參與人有動力采用與均衡不同的行動。26學(xué)習(xí)交流PPT納什均衡（也只有納什均衡）一致預(yù)測性。任何非納什均衡的出現(xiàn)意味著至少有一個參與人“犯了錯”，或者是對對手行動的預(yù)測上犯了錯，或者是（給定那種預(yù)測）在最大化自己的收益時犯了錯。(JeanTirole)27學(xué)習(xí)交流PPT納什均衡的一致預(yù)測性

如果所有參與方都預(yù)測一個特定的博弈結(jié)果會出現(xiàn)，那么所有的參與方都不會利用該預(yù)測或者這種預(yù)測能力來選擇與預(yù)測結(jié)果不一致的策略，即沒有哪個參與方有偏離這個預(yù)測結(jié)果的愿望，因此這個預(yù)測結(jié)果最終就真會成為博弈的結(jié)果?！耙恢隆钡囊饬x在于各博弈方的實際行為選擇與他們的預(yù)測一致。28學(xué)習(xí)交流PPT假設(shè)各參與方預(yù)測的策略組合相同，以及各參與方都是完全理性的，也就是不會犯錯誤的情況下，不可能預(yù)測任何非納什均衡是博弈的結(jié)果。29學(xué)習(xí)交流PPT納什均衡的立法意義納什均衡是一種穩(wěn)定局面。給定別人遵守協(xié)議的情況下，沒有人有積極性偏離協(xié)議規(guī)定。如果一個協(xié)議不構(gòu)成納什均衡，它就不可能自動實施，因為至少有一個人會違背這個協(xié)議，不滿足納什均衡要求的協(xié)議是沒有意義的。30學(xué)習(xí)交流PPT立法的目標(biāo)與其實施的結(jié)果要一致，必須使得參與博弈的各方達到納什均衡。否則，立法就僅僅是正式或官方規(guī)則，而實際有效的支配人們的是潛規(guī)則。納什均衡的立法意義31學(xué)習(xí)交流PPT納什均衡的立法意義潛規(guī)則的要害是三方博弈：私下達成默契的雙方，蒙騙正式制度和公正原則的代表。預(yù)測是博弈分析最基本的目的之一。納什均衡的一致預(yù)測性質(zhì)是其預(yù)測能力的基本保證。32學(xué)習(xí)交流PPT納什均衡應(yīng)用的局限性我們對納什均衡應(yīng)用的廣泛性和有效性不能過分夸大，盡管納什均衡非常重要，但不是說學(xué)到了這種分析方法你就能預(yù)測所有博弈的結(jié)果。納什均衡分析僅僅保證個體理性的智能人的博弈結(jié)果是唯一純策略納什均衡時的預(yù)測。納什均衡分析并不能保證對所有博弈的結(jié)果都作出準(zhǔn)確的預(yù)測。33學(xué)習(xí)交流PPT納什均衡應(yīng)用的局限性現(xiàn)實中的博弈可能是下面三種情況之一：有許多博弈不存在純策略納什均衡；有些博弈是多重納什均衡；博弈方可能是集體理性或有限理性。34學(xué)習(xí)交流PPT35學(xué)習(xí)交流PPTExistenceofNashEquilibrium*Nash在1950年證明：任何有限博弈，都至少存在一個NE。Theorem(Nash1950):Inthen-playernormal-formgameG={S1,…,Sn;u1,…,un},ifnisfiniteandSiisfiniteforeveryithenthereexistsatleastoneNashequilibrium,possiblyinvolvingmixedstrategies.36學(xué)習(xí)交流PPTWilson（1971）證明，幾乎所有有限博弈，都存在有限奇數(shù)個NE，包括純策略NE和混合策略NE?！狾ddnessTheorem37學(xué)習(xí)交流PPT納什于1950年提出并證明了納什定理納什定理的主要內(nèi)容為：在一個有n個參與人的策略式博弈G={S1,…,Sn;u1,…,un}中，如果n是有限的，且Si是有限集（i=1,…,n），則該博弈至少存在一個納什均衡（在混合策略意義下）納什定理38學(xué)習(xí)交流PPT納什定理的一些說明納什定理的證明要用到不動點定理。所謂不動點定理，是指一個定義在X

X上的函數(shù)f(x)，集合X是非空的、閉的、有界的和凸的函數(shù)f是連續(xù)的則至少存在一個x，使得f(x)=x,x

被稱為不動點39學(xué)習(xí)交流PPT納什定理的一些說明運用不動點定理證明納什定理的主要步驟是設(shè)計一個策略組合空間上的一個映射，說明該映射的任何不動點都是一個納什均衡使用不動點定理證明這個映射一定存在一個不動點40學(xué)習(xí)交流PPT不動點什么是不動點呢？想像有一個容器，里面充滿了大量的小球，現(xiàn)在用一個勺子任意攪拌這容器里的小球，攪拌過后，每一個小球都重新占據(jù)了容器中的一個位置，如果某個小球的新位置和舊位置重合，那么這個小球就是一個不動點。數(shù)學(xué)里面有一類經(jīng)典的定理，說的是這樣的不動點總是存在的。無論你怎么攪拌，總有這樣的不動點小球，以不變應(yīng)萬變，終點又回到起點！41學(xué)習(xí)交流PPT納什定理的一些說明映射選擇的是n人最優(yōu)反應(yīng)對應(yīng)其含義是，對于任意一個混合策略組合(p1,…,pn)，對于每一個參與人i，求出I針對其他參與人混合策略(p1,…,pi-1,pi+1,…,pn)的最優(yōu)反應(yīng)，然后構(gòu)建n個參與人最優(yōu)反應(yīng)對應(yīng)的卡氏積。一個最優(yōu)混合策略組合就是這一對應(yīng)集的不動點。42學(xué)習(xí)交流PPT納什定理的一些說明因此只要證明前面的最優(yōu)反應(yīng)對應(yīng)滿足不動點定理條件就可以了。43學(xué)習(xí)交流PPT納什均衡(NashEquilibrium)納什均衡、占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策略均衡的關(guān)系定理a每一個占優(yōu)均衡、重復(fù)剔除嚴(yán)劣策略均衡一定是納什均衡，但反過來不一定成立；定理b納什均衡一定不能通過重復(fù)剔除嚴(yán)劣策略方法剔除。下面對上述定理進行簡要證明44學(xué)習(xí)交流PPT兩個定理的證明首先證明定理b：納什均衡一定不能通過重復(fù)剔除嚴(yán)劣策略方法剔除。記納什均衡時的策略組合為s*=(s1*,…,si*,…,sn*)用反證法假定納什均衡在重復(fù)剔除嚴(yán)劣策略均衡中被剔除掉，不失一般性，假設(shè)s1*是s*中被首先剔除的策略，則在S1中，一定存在一個尚未被剔除的策略s1’’，相對參與人1而言，嚴(yán)格優(yōu)于s1*45學(xué)習(xí)交流PPT兩個定理的證明于是根據(jù)重復(fù)剔除嚴(yán)劣策略定義，對于此時所有尚未被剔除的其他參與人的任意一個策略組合s-1=(s2,…,si,…,sn)，均成立ui(s1’’,s-1)>ui(s1*,s-1)46學(xué)習(xí)交流PPT兩個定理的證明由于前面分析中假設(shè)策略s1*是s*=(s1*,…,si*,…,sn*)中首先被剔除的策略，因此在s1*被剔除的時候，s2*,…,si*,…,sn*尚未被剔除，自然滿足式，這顯然與s*是NE矛盾47學(xué)習(xí)交流PPT下面開始證明定理a:重復(fù)剔除嚴(yán)劣策略均衡一定是納什均衡(反證法)假設(shè)重復(fù)剔除嚴(yán)劣策略后，只剩下唯一的一個策略組合s*=(s1*,…,si*,…,sn*),但卻不是NE。則存在一個s1’∈S1，使得下列事實成立u1(s1*,…,si*,…,sn*)<u1(s1’,…,si*,…,sn*)但由于(s1’,…,si*,…,sn*)在中間過程中被剔除，而s*是被保留下來的唯一一個策略組合。兩個定理的證明48學(xué)習(xí)交流PPT按照嚴(yán)劣策略的定義，有u1(s1*,…,si*,…,sn*)<u1(s1’,…,si*,…,sn*)比較左右兩式，可以得出矛盾…兩個定理的證明49學(xué)習(xí)交流PPT劃線法先找出自己針對其他博弈方每種策略或策略組合（對多人博弈）的最佳對策，即自己的可選策略中與其他博弈方的策略或策略組合配合，給自己帶來最大得益的策略（這種相對最佳策略總是存在的，不過不一定唯一），然后在此基礎(chǔ)上，通過對其他博弈方策略選擇的判斷，包括對其他博弈方對自己策略判斷的判斷等，預(yù)測博弈的可能結(jié)果和確定自己的最優(yōu)策略。這就是劃線法。50學(xué)習(xí)交流PPT

參與人B參與人ALCRU0,44,05,3M4,00,45,3D3,53,56,6圖1-851學(xué)習(xí)交流PPT箭頭法箭頭法對于理解博弈關(guān)系很有好處,是尋找相對穩(wěn)定性策略組合的分析方法。對博弈中的每個策略組合進行分析，考察在每個策略組合處各個參與方能否通過改變自己的策略而增加得益。如能，則從所分析的策略組合對應(yīng)的得益數(shù)組引一箭頭到改變策略后策略組合對應(yīng)的得益數(shù)組。最后綜合對每個策略組合的分析情況，形成對博弈結(jié)果的判斷。劃線法和箭頭法的結(jié)果是一致的，可以相互替代。52學(xué)習(xí)交流PPT小雞博弈（thegameofchicken）湯姆和吉米進行勇氣比賽：兩人分別從一條獨木橋的兩端沖向?qū)Ψ剑l退卻誰就是“小雞”。如果兩個人都向前沖，則兩敗俱傷，收益均為-2；如果一個勇進一個退卻，勇進者收益為4，退卻者為-1；若兩人同時退卻，收益均為0.53學(xué)習(xí)交流PPT

吉米退卻勇進退卻湯姆勇進0，0-1，44，-1-2，-2有兩個均衡。實際會怎樣？54學(xué)習(xí)交流PPT局中人2LCRU局中人1MD4，3