Evolution and Game Theory

Presentation on theme: "Evolution and Game Theory"— Presentation transcript:

1 Evolution and Game Theory
期刊:Journal of Economic Perspectives—Volume 16, Number 2—Spring 2002—Pages 47–66 作者:Larry Samuelson 報告者:陳孝慈 林士全 日期:

2 Evolution and Game Theory
Glossary Introduction Evolutionary Models Why Equilibrium Which Equilibrium What Do We Take Away Conclusion

3 名詞解釋 賽局的標準式:以表格來呈現,表格的列與行分別為兩個參賽者的策略,而表格內的數字是對應不同策略組合下,兩參賽者的報酬
賽局的擴展式(extensive form):賽局以樹狀圖來表示,而且每個枝點即是參賽者的決策點

4 名詞解釋 優勢策略(Dominant Strategy):無論其他參賽者的策略為何,當一個策略所產生的報酬較另一個策略高時,我們稱此策略優於第二策略,若一個策略優於所有其他的策略,此稱優勢策略 優勢策略的均衡:若一賽局中,每一個參賽者都有一個優勢策略,則所有參賽者的優勢策略組合及其對應的報酬,即構成此一賽局的均衡

5 名詞解釋 合作解與非合作解(Cooperative and Non-cooperative Solutions):一個賽局的合作解是一組透過”協調”而選擇的策略與報酬,它可以經由契約或其他形式的執行方法,使每一個參賽者遵守契約.而在欠缺可強制執行的機制下,此時參賽者所選擇的策略或報酬就是此賽局的非合作解

6 名詞解釋 Nash均衡:在非合作賽局中,每個參賽者的策略互為最適反應策略時,這一組策略即為Nash均衡 　優勢策略 　　->Nash均衡

7 名詞解釋 Nash均衡的精緻化(Refinements of Nash Equilibrium):當賽局有多個Nash均衡時,我們可能想要透過一些法則排除一些較不可能均衡,以縮小均衡集合 純粹策略(Pure Strategies):於標準式中表達各列與各行伴隨報酬的策略

8 名詞解釋 混合策略:賦予標準式中純粹策略一個機率分配
貝氏學習法則(Bayesian learning):即當參賽者認為對手並非全然理性時,即無法推論對手策略為何,僅能根據經驗估計對手採取某”純粹”策略的機率(所謂貝氏學習法則,就是根據更新的資訊來修正經驗),在common knowledge of rationality的假設下,透過貝氏學習,參賽者會不斷地學習與修正他們的策略,最後採用”理性的混合策略”

9 名詞解釋 強與弱的劣勢策略(Strongly and Weakly Dominated Strategies):不論對手的策略為何,若參賽者選擇一策略的報酬”嚴格大於”第二個策略,即稱”第二個”策略相較於第一個策略為強的劣勢策略;若參賽者選擇一策略的報酬”不小於”第二個策略,而且在對手某些策略下,第一個策略的報酬將大於第二個策略,則相較於第一的策略,第二個策略可稱為弱的劣勢策略

10 名詞解釋 劣勢策略逐步消去法（iterated elimination of dominated strategies）：若一賽局有一強的劣勢策略，則將此劣勢策略刪去後的賽局與原賽局有相同的納許均衡。此消去法係依序將劣勢策略刪去，直到無劣勢策略可刪為止，且最後的簡化賽局與原賽局有相同的納許均衡

11 名詞解釋 手顫抖假設（trembling hand assumption）：若在一賽局中，每一個參賽者認為其他參賽者有非常小的機率會選錯策略時，及稱此參賽者以顫抖的手來決定策略。而若一賽局有多個納許均衡，其中某些均衡可能因參賽者以顫抖的手來決定策略而不可靠，在禁不起顫抖的手考驗下，均遭精緻化後刪去

12 名詞解釋 子賽局（subgame）：一個包括報酬與策略的賽局，若開始自一完全資訊點，及稱之
子賽局完美均衡（subgame perfect equilibrium）：所謂子賽局完美均衡，係指此均衡策略組合在每一子賽局中皆是Nash均衡

13 名詞解釋 後推法（backward induction）：一種發現子賽局完美均衡的方法，其步驟是先找出所有基本子賽局的均衡，然後再將每個基本子賽局的均衡報酬代回，以簡化賽局，重複此步驟直到所有完整小賽局都被分析完為止。 重複賽局（repeated game）：若某一賽局重複多次，再分析時便應是此一連串賽局唯一完整賽局，而分析所得的完美子賽局均衡就是此一系列賽局的均衡。

14 名詞解釋 有限次的重複賽局：當一次賽局有一純策略納許均衡時，則此納許均衡被重複玩就是重複賽局的子賽局完美均衡。換言之，當一社會困境賽局有一優勢策略均衡時，則優勢策略均衡被重複玩也會是此社會困境的子賽局完美均衡。 無限次重複賽局：若某一賽局可能重複多次，但並不確定多少回合後會結束，即可將此賽局稱為一無限次重複賽局。而分析所得的子賽局完美均衡，就是此一系列賽局的均衡。

15 名詞解釋 以牙還牙（tit for tat）：在一社會困境重複賽局中，以牙還牙策略係指先在第一回合選擇「合作」。但若對手在這一回合選擇「背離」，在下一回合便還以「背離」；相反地，若對手在此一回合選擇「合作」，在下一回合就還以「合作」。 族群賽局（population game）：若是一族群的成員隨機配對參與賽局，亦即不同類型的參與者將採取不同的策略，這整個系列的賽局就是族群賽局

16 名詞解釋 演化穩定策略（evolutionarily stable strategy，ESS）：一個納許均衡若是在複製動態調整機制下是穩定的，則此納許均衡就是一個演化穩定策略。 複製動態（replicator dynamic）：根據複製調整動態的機制，採用某策略的族群比例將隨採取此策略相對於平均報酬差距的增加而增加。

17 名詞解釋 協調賽局(Coordination Game):當賽局有兩個或更多的Nash均衡時,參賽者將難以抉擇,因為每一個均衡都可能發生,因此她們必須協調策略. 最後通牒賽局(Ultimatum Game):最後通牒賽局是指先由一人提出將分配整個利益的多少比例給另一個人,如果另一個人反對此分法,則兩個人的報酬都是為0.

18 名詞解釋 突變(mutant):指參賽者以隨機（無目的性）的方式選擇策略，因此突變策略可能獲得較高報酬也可能獲得較低報酬，突變一般很少發生。新的突變也必須經過選擇，並且只有獲得較高報酬的策略才能生存（Survive） 薛林點(Schelling point):在協調賽局中,若有任何線索引導參賽者相信其中一個均衡較其他均衡更可能發生,則這個最可能的均衡便稱為薛林點

19 名詞解釋 扣板機策略(Trigger Strategy):在一個無限次重複賽局中,若參賽者發現對手選擇非合作賽局時,一如扣板機般地予以往後回合的反擊 恐怖型扣板機策略(Grim Trigger strategy):一但發現對手採取“非合作行動”,在往後回合皆使用非合作行動(即使往後回合對手釋出善意).

20 Introduction 賽局理論最早是由John von Neumann and Oskar Morgensten(1944)提出,後來由John Nash(1950)提出均衡的概念,1980年後開始盛行. 1980年代的賽局理論會假設參賽者是perfect rational.1990年後,就不在強調參賽者是rational.=>以理性為基礎的模型會有限制.

21 Introduction 賽局觀念並非僅限於分析人類而已，反過來說，生物演化學的觀念，如演化穩定策略，也可用來詮釋人類行為習慣的演化
古典經濟學者與大部分的賽局分析都假設，參賽者將極大化報酬或是選擇最適反應策略，但是，有些學者認為，人的行為並都不是極大化報酬的，人們的理性是有限的（bounded）：人們因欠缺充份認知能量，因此並不一定極大化報酬或是選擇最適反應策略，反而會仰賴啟發法來做選擇，此即有限理性。

22 Evolutionary Models 假設爭食是隨機的,每隻動物可以選擇攻擊或是逃開.
1)若兩隻動物都攻擊,將兩敗俱傷,此時payoff是 1/2(V-C) 2)若不攻擊,各得V/2 3)若一隻攻擊,另一隻逃開,則攻擊者全得V

23 Evolutionary Models If V<C,則此Nash均衡為(O,V),(V,O)
　且根據replicator Dynamic,會有V/C的機率的人選則Hawk

24 Evolutionary Models 鷹鴿賽局兩個結論
　1)一個演化穩定策略就是納許均衡，也就是「在此策略下，不存在任一突變策略被任一小族群採用，並得以生存且持續繁殖」。 2)不是所有納許均衡都是演化穩定的策略，因為不是所有納許均衡在複製動態調整的結果都是穩定的。

25 Evolutionary Models 此模型的Nash均衡(In,In)and(Out,Out), 但是前者發生發生的可能性會大於後者,因
為參賽者應該避免弱的劣勢策略 Strategy In是優勢策略

26 Evolutionary Models Tit-for-tat strategy的四大特點：
　1.與人為善：先採取合作態度，不在於每一步都把自己的 利益最大化 　2.以牙還牙：如果對方做出損害我方利益的舉措，必須立 即回應，禁止對方變本加厲 　3.不記舊仇：如果對方願意重回合作軌道，則既往不咎， 停止制裁 　4.策略清晰：要讓對手清楚明白自己的決策過程 常常用在repeated prisoner’s dilemma

27 Evolutionary Models 此為一round robin tournament 有較高的機率是當一個人選擇X(Y),另一個
人的選擇不同 (X,Y)or(Y,X) 所以此時的最適選擇是(9,9) and (8,8)

28 Evolutionary Models (承上)
大數法則(Law of Large numbers):在理性的基礎之下,大部分的人所做的選擇. 以薛林點的觀點來看,我們將大數法則當作線索來引導我們相信(9,9)會是比(8,8)更有可能的均衡 所以大部分的人會選擇(9,9),而不是選擇(8,8)

29 Evolutionary Models 此橫軸代表此群體中選擇X的比例
在已經選擇X的的狀況之下,會有80%以上的人選擇X,也就是策略(X,X)

30 Why Equilibrium 穩定(Stable) : If small perturbations away from the stationary state proportions cannot give rise to dynamics that take the system far from these proportions. 假如狀況是穩定的,大多數的人的payoff會得到相同的payoff.而且大部分的人會喜歡high-payoff策略勝過low-payoff策略 ,所以會破壞原本的穩定

31 Why Equilibrium 一個stationary state有可能不是一個Nash均衡,因為也許有較好的策略(A策略),但是不為大多數的人所採用的策略(B策略),因此原本的策略(B策略)會變的不穩定,此時大多數的人會傾向選擇payoff最高的策略(A策略),所以選擇A策略的人會越來越多. A stationary state是stable,只有在沒有更好的 　策略可選擇之下,這樣的stationary state才是 　Nash均衡

32 Why Equilibrium Evolutionary game theory provides a motivation for Nash equilibrium. An outcome is a Nash equilibrium if it is stable An evolutionary process must produce convergence to a Nash equilibrium

33 Which Equilibrium In figure 3,there are two pure-strategy equilibria,given by(X,X) and(Y,Y),each of which is strict. Harsanyi and Selten(1988)指出,常見的精練均衡亦是嚴格的Nash均衡,而此均衡, 反映出生物會選擇效用最高的策略.

34 Which Equilibrium Young(1993)and Kandori,Mailath and
Rob(1993)卻說,在limiting distribution allocate下(也就是50:50),有選擇(Y,Y)的 可能性. 為什麼上面兩派學者會有不同的看法,因為不同的事件會有不同的風險存在,所以因此會有不同的期望報酬,進而會影響到參賽者的決策.

35 Which Equilibrium Robson and Vega-Redondo(1996),指出Liminting stationary distribution有可能會使突變的機率變成零,當等待的時間非常長的時候,讓參賽者有時間去觀察其他參賽者的決策,會使每個人的決策趨於一致,而使突變的機率變的非常小. 在精練Nash均衡時,有個前提假設是我們不採用弱的劣勢策略.

36 Which Equilibrium Binmore,Gale and Samuelson (1995),
指出player1逼迫palyer2必須選擇較高的payoff 2或較低的payoff 1 也就是說當player1選擇Low時,player2不能選擇No,子賽局的完美均衡為(Low,Yes)

37 Which Equilibrium 對player2來說,No是一個劣勢策略,因為選擇Yes得到的報酬較高
有時候,問題太過複雜,此時我們就不能用逐步消去法(iterated eliminations)或由後往前解(backward induction)去去除掉弱的劣勢策略

38 Which Equilibrium (Davis and Holt,1993,chapter5;
Roth, 1995),實証結果也顯示由後往前解在問題太過愈雜時,沒辦法使用. Jehiel(2000) and Samuelson(2001)有提出解決的方式.指出可以利用learning或是experience去處理太過複雜的問題,方法是以目前的game’s context當作線索,找尋以前是否有類似的問題或是選擇行為,來當作解決此問題的參考.

39 What Do We Take Away Battalio, Samuelson and van Huyck (2001)
以上的三個模型的均衡均為(X,X)

40 What Do We Take Away 三個模型的決策速度會不一樣A>B>C,因為三者的貼水(premium)不同,或說選擇Y而不選擇X的機會成本太高 A:45-35=10 B:45-40=5 C:45-42=3

41 What Do We Take Away 所以透過學習法則,會使決策過程更有效率,求得均衡解的過程也會更加的快速
Abreu and Rubinstein(1988),Binmore and Samuelson(1992)提出懲罰的機制(punishment capability),就是在囚犯兩難問題中,訂定一個讓兩個人合作的契約,也就是約束力,懲罰機制越嚴格,兩個人越會合作,越不可能背叛,因為背叛後所遭受的報復會更強

42 What Do We Take Away Cosmides and Tooby(1992):建議人們應該具有察覺能力,與當有欺騙行為發生時的反應能力

43 Conclusion 一個Nash均衡若是在replicator dynamic 調整機制下是穩定的,則此Nash均衡就是一個evolutionarily stable strategy,一個ESS可能是一個混合策略,亦即族群成員的均衡策略是一套機率分配.而一如我們所熟悉的基本賽局,這些賽局經常有相同的均衡. 如同所有經濟學教科書中的理論一樣,經濟學理論應該與現實社會中存在的現象一致,甚至應該要能解釋所存在的經濟現象,在賽局理論中,參賽者作的決策,應與生物學中,生物的本能選擇一致.