博弈論 第3講2013學(xué)習(xí)專(zhuān)業(yè)資料

上次內(nèi)容回顧博弈論的定義什么是博弈博弈的要素（參與人、策略集和效用）共同知識(shí)假設(shè)博弈論的知識(shí)體系完全信息靜態(tài)博弈及其表示占優(yōu)策略和占優(yōu)均衡嚴(yán)劣策略和重復(fù)剔除嚴(yán)劣策略均衡12局中人2LRU局中人1MD5，10，21，34，14，22，3Nodominantstrategiesanddominatedstrategies,whatabouttheresult?BestResponse(BR)3UdoesbestagainstL;MdoesbestagainstRL、R概率為0.5時(shí)ExpectedpayoffofU：2.5ExpectedpayoffofM：2.5ExpectedpayoffofD：3此時(shí)，Ddoesbest。4假定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)×256）BR是期望收益最大時(shí)的反應(yīng)

圖中x=1/3，y=3/5由圖可知，p(r)≤1/3時(shí)，1的最佳反應(yīng)是選U；1/3≤p(r)≤3/5時(shí)，1的最佳反應(yīng)是選D；p(r)≥3/5時(shí)，1的最佳反應(yīng)是選M。78點(diǎn)球博弈910PartnershipGame2人擁有一家公司，每人分享利潤(rùn)的一半每人的策略:精力投入水平，Si=[0,4]利潤(rùn)：4×[S1+S2+bS1S2]b=[0,1/4]U1=2×[S1+S2+bS1S2]-S1S1U2=2×[S1+S2+bS1S2]–S2S211參與人的BR是什么？1213b=1/4時(shí)14納什均衡1516NashEquilibriumTheactionprofiles*isaNashEquilibriumif,foreveryplayeriandeveryactionsiofplayeri,s*isatleastasgoodasaccordingtoplayeri’spreferencesasthetheactionprofile(si*,s-i*)inwhichplayerichoosessi*whileeveryotherplayerchooses-i*.Equivalently,foreveryplayeri,ui(s*)≥ui(si,s-i*),Foreveryactionofplayeri17DefinitionInthen-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)

18foreveryfeasiblestrategysiinSi;Thatis,si*solves

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

sn+1*,…,sn*).

si∈Si

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

納什均衡是一種策略組合，給定對(duì)手的策略，每個(gè)參與人選擇自己的最優(yōu)策略。21

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

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

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

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

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

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

吉米退卻勇進(jìn)退卻湯姆勇進(jìn)0，0-1，44，-1-2，-2有兩個(gè)均衡。實(shí)際會(huì)怎樣？55局中人2LCRU局中人1MD4，35，