2人两阶段重复博弈ppt 最新協作平台活動 衛道中學程式設計 2人两阶段重复博弈

重複博弈

完全且非完美信息動態博弈

Unit 5

第 3 章和第 4 章要點

博弈類型 舉例 解的概念

簡單的完全且完美信息

動態博弈

Stackelberg

魯賓斯坦 (1982) 討價還 價模型

Backwards Induction

Outcome (BIO) 後向歸納結果 2 人兩階段重複博弈

(“ 同時行動” 意味著

“不完美信息” )

Lazear&Rosen

Tournaments (1981 ) _工作 競賽模型

Subgame Perfect

Outcome (SPO) 子博弈完美結果 動態博弈主題 _{: 可信威脅與}

承諾會影響現在的行為 下一次博弈開始前的所

有博弈的結果都能被觀 察到的重複博弈

Subgame- perfect Nash equilibrium

子博弈完美 NE

完全信息動態博弈 表述 Normal-form / Strategic-

form _{標準式 / 策略式}

Extensive-form 擴展式

解的概念

Nash Equilibrium (NE) Nash _均衡

Subgame-perfect Nash equilibrium (SPNE)

子博弈完美 Nash 均衡 Central Issue

中心問題

credibility threats or promise (self-enforcement) 可信性威脅或承諾

Theme 主題思想

一個完全信息動態博弈可能會有很多個納什均衡，但 是有些均衡包含了不可置信的威脅和承諾。子博弈完 美納什均衡就是通過了可信任檢測的均衡。

第 3 章和第 4 章要點

重複博弈

• _要點

– 在（參與者）重複關係中，關於將來行動的威脅或承諾能否影響 到當前的行動。

• 直觀

– 大部分直觀的結論是由兩階段的例子給出的 – 一些觀點需要討論無限次的情況

• 子博弈完美納什均衡

– 我們還將定義重複博弈中子博弈完美納什均衡的概念

• 這一定義在重複博弈的條件下表述比較容易理解，而在 2.4.B. 節分析一般完全信息動態博弈中則要複雜一些；

• 我們在本節先作簡要介紹，以便後面的展開。

兩階段重複博弈

• 兩階段囚徒困境

• 兩階段博弈的階段博弈有多個納什均衡

– 預測第二階段的行動

– 重複博弈的子博弈完美結果

兩階段囚徒困境

考慮囚徒困境

給定如圖 2.3.1 的標準式

–

–

參與人 2

參與人 1

L₂ R₂

L₁ 1,1 5, 0

R₁ 0,5 4, 4

圖 2.3.1

• 讓兩個參與人進行兩次囚徒困境博弈，觀察第二次博弈

開始之前第一次博弈的結果，並假設整個過程博弈的總

收益等於兩階段博弈收益的簡單相加 ( 即不考慮貼現因

素 ) 。

“2×2×2” 博弈和子博弈完美結果

• 兩階段囚徒困境博弈是“ 2×2 兩人同時行動”博弈的一

個特殊例子。在這個博弈中，我們在上一節利用後向歸納

法的思路分析了“子博弈完美結果”，具體見 _{2.2.1 。}

• 子博弈完美結果

如果參與人 ₁ 和 2 預測到參與人 3 和 4 在第二階段的行動將由 (a₃*(a₁,a₂) _{， a4}*(a₁,a₂)) 給出，則參與人 1 和 2 在第一階段的問題 就可以用以下的同時行動博弈表示：

1. 參與人 1 和 2 同時從各自的可行集 A₁ 和 A₂ 中選擇 a1 和 a2 ； 2. 收益情況為 u_i(a₁,a₂,a₃*(a₁,a₂),a₄*(a₁,a₂)) _{， i=1,2 ；}

假定（ a1*,a2* ）為以上同時行動博弈唯一的納什均衡，我們稱 (a1*,a2*,a3*(a1*,a2*),a4*(a1*,a2*)) 為這一兩階段博弈的子博弈完

兩階段囚徒困境

• _{得到 a}

_*(a

_,a

_{) ， a}

_*(a

_,a

₎

– 根據第一階段的行動 a1_{和 a}2，預測第二階段參與人的反應； – 請注意，在囚徒困境博弈中存在唯一的納什均衡，因此參與人

的反應獨立於其在第一階段的行動。

• _{計算 u}

_(a

_,a

_,a

_*(a

_,a

_),a

_*(a

_,a

_{)) ， i=1,2}

i 1 2 1' 1 2 2' 1 2

* *

i 1 2 1' 2'

* *

i 1 2 i 1' 2'

u (a ,a ,a (a ,a ),a (a ,a ))

= u (a ,a ,a ,a )

= u (a ,a )+ u (a ,a )

兩階段囚徒困境

• 第二階段博弈的結果為納什均衡 (L₁, L₂) ，兩人收益為 (1, 1) ；參與 人在兩階段囚徒困境博弈中第一階 段的交互行動如圖 _{2.3.2 所示；}

• 這個一次性博弈有唯一的納什均衡 (L₁,L₂) _。

參與人 2

參與人 1

L₂ R₂

L₁ 2,2 6, 1

R₁ 1,6 5, 5

圖 2.3.2

• 兩階段囚徒困境唯一的子博弈完美結果就是第一階段的 (L₁,L₂) 和第二階段的 (L₁,L₂) _。

• 在子博弈完美結果中，任意階段都不能達成相互合作 (R1^,R2⁾ 。

有限重複博弈 _{: 重複獨立}

• _{令 G = {A1}, ...,A_n; u₁, ..., u_n} 表示一個完全信息博弈，其中參與人 1 到 n 同時從各自的行動空間 A1到 An中分別選擇行動 a1到 an ，得到的 收益分別為 u₁(a1, ..., an) , ..., un(a1, ..., an), 我們稱博弈 G 為重複博弈

中的階段博弈。

• 定義 1

• 定理 1

，重複博弈 G(T) 有唯一的子博弈完美結果：即 G 的納什均衡結果 在每一階段重複進行。

兩階段重複博弈 _:

階段博弈有多個納什均衡

• 設圖 2.2.3 表示的階段博

弈重複進行兩次，並在第

二階段開始前可以觀察到

第一階段的結果。

• 我們可以證明在這一重複

博弈中存在一個子博弈完

美結果，其中第一階段的

策略組合為 _(M

_,M

_{) 。}

參與人 2

參與人 1

L₂ M₂ R₂

L₁ 1,1 5, 0 0, 0

M₁ 0,5 4, 4 0, 0

R₁ 0, 0 0, 0 3,3

圖 2.3.3

• 圖 2.2.3 中表示的博弈有兩

個納什均衡 _(L

_,L

_),(R

_,R

₎

兩階段重複博弈 _:

階段博弈有多個納什均衡

• 由於這個階段博弈有不止一個納什均衡，因此參與人可能會預測： 根 據第一階段的不同結果，在第二階段的博弈中將會出現不同的納什均衡

。

• 關鍵問題是：預測對第一階段的 行動 _{a1 和 a2 的反應。}

參與人 2

參與人 1

L₂ M₂ R₂

L₁ 1,1 5, 0 0, 0

M₁ 0,5 4, 4 0, 0

R₁ 0, 0 0, 0 3,3

第一階段 第二階段 收益

(L₁, L₂) (1,1)+(?,?) (R₁, R₂) (3,3)+(?,?) (M₁, M₂) (4,4)+(?,?) (M₁, L₂) (0,5)+(?,?) (L₁, M₂) (5,0)+(?,?) others (0,0)+(?,?)

圖 2.3.3

• 第二階段的結果 ?

信 號

• 設參與人預測到第一階段的結果是 (M1,M2) ，第二階段的結果將會是 (R1,R2) ；如果第一階段出現其他 8 個結果中任何一個，第二階段的 結果就會是 (L1,L2) 。那麼，這個 兩階段博弈就如同圖 _{2.3.4 的一次} 性博弈。

參與人 2

參與人 1

L₂ M₂ R₂

L₁ 2,2 6, 1 1, 1

M₁ 1,6 7,7 1, 1

R₁ 1, 1 1, 1 4,4

圖 2.3.4

• 在圖 2.3.4 所示的博弈中有 3 個純策略納什均衡 : (L₁,L₂), (M₁,M₂) 和 (R₁^,R₂⁾ 。

• 和圖 2.3.2 中一樣 , 這個一次性博弈中的納什均衡對應著重複博弈 的子博弈完美結果。

兩階段重複博弈的子博弈完美結果

• 標記

– 令 ((w, x), (y, z)) 表示重複博弈的一個結果——第一階段和第二階段 的行動分別為 (w, x) _{和 (y, z) 。}

• 圖 2.3.4 中的納什均衡 (L1,L2) 對應著重複博弈的子博弈完美結果 ((L1,L2), (L1,L2)) ，因為除第一階段的結果是 (M1,M2) _{外，其他任何情} 況發生時，第二階段的結果都是 (L1,L2) _。

• 類似地，圖 2.3.4 中的納什均衡 (R1,R2) 對應了重複博弈的子博弈完美 結果 ((R1,R2), (L1,L2)) 。重複博弈的這兩個子博弈完美結果都簡單地

由兩個階段博弈的納什均衡解相串而成。

• 第一階段的非合作傾向在第二階段遭到報復或懲罰 !

兩階段重複博弈的子博弈完美結果

• 圖 2.3.4 裏的第三個納什均衡結果與前兩者存在質的差別： – 圖 2.3.4 中的 (M1,M2) 對應的重複博弈子博弈完美結果為

((M₁,M2),(R1,R2)) _{，因為對 (M}1,M2) 之後第二階段結果預期是 (R1,R2), 亦即正如我們前面講過的，在重複博弈的子博弈完美結果中，_合作

可以在第一階段達成_。 下面是更為一般的情況

• _{如果 G = {A1, ...,An; u1, ..., un}} 是一個有多個納什均衡的完全信息靜態 博弈，則重複博弈 G(T) 可以存在子博弈完美結果，其中對每一 t < T, t 階段的結果都不是 G 的納什均衡。

– 重複博弈的子博弈完美結果允許在階段博弈中出現非 Nash 均衡_。

子博弈完美結果對可信性的要求

• 如果第一階段兩個參與人不選 擇 (M1,M2) ，那麼第二階段為什 麼不選擇可以獲得收益 (3,3) 、 帕累托優於 (L₁,L₂) _{的 (R1},R₂) _？

• 但是如果對每個第一階段的結 果，第二階段的結果都將是

(R₁,R₂) 的話，則第一階段選擇 (M₁,M₂) 的動機就被破壞了：

參與人 2

參與人 1

L₂ M₂ R₂

L₁ 1,1 5, 0 0, 0

M₁ 0,5 4, 4 0, 0

R₁ 0, 0 0, 0 3,3

–兩個參與人在第一階段面臨的局勢可以簡化為在 2.3.3 所示階段 博弈的每一單元格中的收益都加上 (3, 3) _{後形成的一次性博弈，} 於是 ⁱ 對 M_j ^{的最優反應就是 L}i 。

圖 2.3.3

問題 : 同時懲罰了懲罰者 ?

• 在基於圖 2.3.3 的兩階段重複博弈中，對一個參與人

在第一階段不守信用的懲罰，只能是在第二階段的

帕累托居劣均衡，從而同時懲罰了懲罰者。

參與人 2

參與人 1

L₂ M₂ R₂

L₁ 1,1 5, 0 0, 0

M₁ 0,5 4, 4 0, 0

R₁ 0, 0 0, 0 3,3

圖 2.3.3

三個均衡處於帕累托邊界上的博弈

• 四個純策略納什均衡： _{(L1,L2) 和} (R₁,R₂), _{同時有 (P1}, P₂) _{和 (Q1},Q₂). 與上例相同，和 _{(L1,L2) 相比，參與} 雙方都更傾向於選擇 _(R1,R2)

• 更重要的是，不存在一個納什均衡 (x, y) ，使參與雙方與 (P₁, P₂) _或

(Q₁,Q₂) _{或 (R1},R₂) 相比，都傾向於選 擇 (x, y)

• _{我們稱 (R1},R₂) 帕累托優於 (L₁,L₂)

• (P₁, P₂), (Q₁,Q₂) _{和 (R1},R₂) _都處於 圖

2.3.5 所示博弈的納什均衡收益的帕 累托邊界之上 _.

三個均衡處於帕累托邊界之上的博弈

• 假設參與人預期的第二階段結果如下： – 如果第一階段的結果是 (R1^,R2⁾ ， 第二階段將是 _{(M1,M2) ；}

– 如果第一階段的結果是 (M₁, w) _{，其中 w 為除} M₂ 之外的任意策略，則第二階段將是 _{(P1, P2) ；} – 如果第一階段的結果是 (x,M₂) ，其中 x 為除 M₁ 之外的任意策略，則第二階段將是 _{(Q1,Q2) ；}

– 如果第一階段的結果是 (y, z) ，其中 y 是除 M₁ 之外的任意策略除， z 是 M₂ 之外的任意策略， 則第二階段將是 (R₁^,R₂⁾ 。

• ((M₁,M₂) _{， (R1},R₂)) 是重複博弈的子博弈完美結果

•以這個博弈作為兩階段重複博 弈的階段博弈

• 這裏與圖 2.3.3 不同的是 , 有 三個均衡處於帕累托邊界之上

：

— 其中之一可以獎勵參與雙方在 第一階段的良好行為，

— 另外兩個則可以在懲罰第一階 段不守信用者的同時，獎勵 懲 罰者。

— 一旦在第二階段有必要實施懲 罰，懲罰者就不會再考慮選擇 階段博弈的其他均衡，也就無 法說服懲罰者就第二階段的行 動進行重新談判。

三個均衡處於帕累托邊界之上的博弈

•以這個博弈作為兩階段重 複博弈的階段博弈

效率工資

• 在效率工資的模型中，一個企業勞動力的產出決定於企業支付 的工資水平。

– 在發展中國家，更高的工資收入可提供良好的營養；在發達 國家，更高的工資收入可吸引更多有能力的工人到企業求

職，或者可以激勵現有工人更加努力工作。

• Shapiro and Stiglitz (1984) 建立了一個動態模型，其中企業為 激勵工人努力工作，一方面支付很高的薪水；同時又威脅一旦 被發現偷懶，立即開除。

– 作為這種高薪的一個後果，企業減少了對勞動力的需求，造 成部分工人的高薪就業，與其他工人（非自願）失業並存。 – 失業工人的人數越多，一個被解雇的工人尋找新的工作崗位 所需時間就越長，於是解雇的威脅就更加有效。

效率工資

– 在競爭均衡條件下，工資水平 w 和失業率 u 恰好可以使 i 工人不 去偷懶，並且企業在工資水平 w 時的勞動需求恰好使失業率等於 u

– 我們分析一個企業和一個工人的情況，從重複博弈的角度研究這 一模型（而不考慮其競爭均衡的特點）

工資效率 _{: 一階段偷懶模型}

一個企業和一個工人的兩階段博弈

1) 第一階段，企業開出一個工資水平 w _；

2) 第二階段，工人考慮工資水平 w 並決定接受或拒絕這份工 作；

2-1) 如果工人拒絕了 w ，則工人成為自我雇傭者，工資水 平為 wn；

2-2) 如果工人接受了 w ，則工人選擇是努力工作（會帶來 e 的負效用）還是偷懶（不會帶來任何負效用）。

3) 企業觀測工人的產出 y

3-1) 如果 y=0, 企業獲得收益 -w ， 工人獲得 w

如果 y>0, 企業的收益是 y-w, 工人的收益是 w-e 。

工資效率 _{: 一階段偷懶模型}

• 工人的努力程度企業無法觀測，但是 企業和工人都可以觀測到工人的產出 水平。

• 產出可能高也可能低，為簡單起見， 我們認為低水平的產出為 _{0 ，高水平} 的產出為 y >0

– 假設如果工人努力工作則肯定可 以得到高產出；

– 但是如果工人偷懶則以 p 的概率 得到高產出， 1 -p 的概率的到低產出

；

– 從而，在這個模型中，低產出是偷懶 無可辯駁的證據。

• 顯然地，企業不能強

制工人努力工作 ---

偷懶總是存在的。

• 為了聘請工人，企業

只需要支付工人 w

^---

支付更多的工資是沒

有意義的，因為偷懶

總是存在。

工資效率 _{: 社會效率}

• 如果企業以工資 w 雇傭工人 ^{，則參與人的收益為}

– 如果工人努力工作並帶來高產出，則

企業收益為： y - w ，工人收益為： w – e _；

– 如果工人偷懶，則 e= 0 ；

如果出現低產出，則 _{y= 0 ；}

• 我們假定 y - e >w

^{> py}

這就使得

• 工人付出努力工作是有社會效率的

• 工人自我雇傭要優於受雇於企業並偷懶

同樣意味著

•

企業不會事先預付工資，因為最低工資將超出

工資效率 _{: 階段博弈}

• 這一階段的子博弈完美結果是使人失望的：因為企業先

付給工人工資 w ，工人沒有動機去努力工作，於是企業

將會開出 w<w

，且工人會選擇自我雇傭。

• 在無限重複博弈中，企業給工人高於 w

的工資水平 w

， 並且威脅一旦出現低產出，就將工人開除。

• 下面我們將證明在某些取值範圍內，企業給出較高的工

資並借此激勵工人努力工作是值得的。

考慮無限重複博弈中下面的戰略，其中包含了將在以後決定的 。如果所有前面的工資開價都是 ，所有的開價都被接 受了，並且所有前期的產出都是高的，我們就稱博弈的過程是“高工 資、高產出”。

企業的策略為第一階段開出工資水平 ，並且在 其後的每一階段，如果博弈的過程是高工資、高產出，則繼續開出工 資水平 ；但其他情況下開出 。

工人的策略為如果 ，則接受企業的工資（否則， 選擇自我雇傭），並且如果博弈的過程（包括本階段的工資）是高工 資、高產出，則努力工作（否則偷懶）。

請注意，如果 ，但 ，則工人將接受企業的 工資但選擇偷懶。

*

w _ w

^w

效率工資 _{: 無限重複博弈}

0

w _

w w �

w w _

w

w w� 0

子博弈

• 一個子博弈是全部博弈的一部分，當全部博弈進行到任何

一個階段，到此為止的進行過程已成為參與各方的共同知

識，而其後尚未開始進行的部分就是一個子博弈。

• _定義

– 由第 t + 1 階段開始有許多子博弈；到第 t 階段為止的每一可能的進 行過程之後都是不同的子博弈。

– 與在有限情況下相似，博弈 G(∞,δ) 到第 t 階段為止有多少不同 的可能進行過程，就有多少從 t + 1 階段開始的子博弈。

子博弈

• 請注意，重複博弈的第 t 階段本身（在有限情況下假

定 t < T ）並不是整個博弈的一個子博弈。

• 子博弈是原博弈的一部分，不只是說博弈到此為止的

進行過程已成為全體參與人的共同知識，還包括了原

博弈在這一點之後的所有進程。

• 只單獨分析第 t 階段的博弈就等於把第 t 階段稱為原

重複博弈的最後一個階段，這樣的分析也可能會得到

一些結論，但卻完全無助於對整個博弈的分析。

子博弈完美納什均衡

納什均衡是一個策略集，即對每一個參與人，其選

擇的策略是對其他參與人所選策略的最優反應。

• 定義 (Selten 1965)

如果參與人的策略在每一個子博弈中都構成了

納什均衡，則稱納什均衡是子博弈完美的。

子博弈完美納什均衡把納什均衡的概念進一步嚴

格化，即一個子博弈完美均衡首先必須是納什均

衡，然後還必須通過其他檢驗。

效率工資 : 子博弈完美納什均衡

• 下面我們將討論上述雙方的策略成為子博弈完美均衡

的條件。論證由兩部分組成 _:

(i) 導出雙方策略成為納什均衡的條件；

(ii) 證明他們是子博弈完美的。

效率工資 : 子博弈完美納什均衡

• 假設企業在第一階段開出的工資是 w*

• 給定企業的策略，工人接受這一工資水平是最優

的

– 如果工人努力工作，則他可以肯定得到高產出，那麼企 業將再次開出工資水平 w* ，而工人將在下一階段就努力 與否進行相同的決策。從而，如果對工人來講努力工作 是最優的，則工人收益的現值為

效率工資 : 子博弈完美納什均衡

– 如果工人偷懶，則工人將以 p 的概率得到高產出；

– 這時下一階段他還可以就努力與否進行決策；但工人還將 以 1-p 的概率得到低產出，這時企業將在以後永遠開出工資

w=0 ，於是工人亦將永遠選擇自我雇傭。

– 從而，如果對工人來講偷懶是最優的，則工人收益的現值 為

或

* _{{ (1 ) 0 }}

s s 1

V w _ pV p w

    



*

[(1 ) (1 ) 0] / (1 )(1 ) Vs  _ w _  p w _ p _

• 對工人來講，如果，選擇努力工作是最優的，即 (2.3.5)

• 於是，為激勵工人努力工作，企業必須向工人支付的，不僅足以 補償工人自我雇傭時的機會收入以及努力工作帶來的負效用

，還包括工資升水 。

– 很自然地，如果 p 接近於 1( 即如果偷懶很難被發現 ) ，則工資 升水必須非常高才可以激勵工人努力工作。

效率工資 : 子博弈完美納什均衡

e s

V _V

*

0 0

1 1

(1 )

(1 ) (1 )

w w p e w e

p p

 

 

 

   

�  

w

_ e

(1 p)^e









效率工資 : 子博弈完美納什均衡

即使 (2.3.5) 成立，從而令工人的策略為其對企業策略的

最優反應，還應該研究企業為什麼支付 _{w* 。}

• 給定工人的策略，企業在第一階段的問題可歸為就以下

進行選擇 :

(1) _{支付 w = w*} ，並通過威脅工人一旦出現低產出就將其開除來激勵 工人努力工作，這樣每一階段都可能得到 _{y-w* 的收益；}

(2) 支付 w= 0 ，促使工人選擇自我雇傭，自己在每一階段的收益均 為 0 。於是，企業策略成為工人戰略最優反應的條件為

效率工資 : 子博弈完美納什均衡

前面我們已假定 y-e > w

( 即對工人而言，選擇受雇

於企業並努力工作是有效率的 _{) 。}

• 要使這些策略成為子博弈完美均衡，我們要求進一步

的條件：

– (2.3.5) 和 (2.3.7) 合併為

對此，仍可沿用前面的解釋，即要使合作能夠得以

維持，貼現因子 _{δ 的值必須足夠大 。}

效率工資 : 子博弈完美納什均衡

• 到此為止，我們已證明如果 (2.3.5) 和 (2.3.7) 成立，則前面給出 的策

略為納什均衡。

(2.3.5)

y -w* >0 (2.3.7)

• 是工資升水。 1

(1 p) ^e









*

0 0

1 1

(1 )

(1 ) (1 )

w w p e w e

p p

 

 

 

   

�  

效率工資 : 子博弈完美納什均衡

• 要檢驗這些策略是子博弈完美的，參考教科書頁

111-2 _。

Assignment-1

Assignment-2