信息設計學習筆記係列。
貝葉斯勸説:Kamenica and Gentzkow (2011)
Cheap Talk 勸説:Lipnowski and Ravid (2020)
這一部分研究了:當一方(接收者)的行為既影響自己的效用、又影響另一方(發送者)的效用時,發送者如何通過改變接收者的信念而影響其行動、從而提高自己的效用。
當發送者在真實世界狀態揭曉之前選擇向接收者傳遞信號的方法 (信息結構) 時,稱發送者具有承諾能力,這對應於貝葉斯勸説的情形;
當發送者觀察到真實世界狀態之後再選擇向接收者傳遞信號,并且沒有撒謊或其他信號成本、且信號内容在事後不可驗證時,稱發送者 (完全) 不具有 (任何承諾能力),這對應於 Cheap Talk 情形。
還可以有其他情形,如:有信號成本的 (signaling or costly signal) 情形;可事後驗證 (Hard Evidence) 情形等。
無論發送者的效用怎樣地依賴於接收者的行爲,只要接收者的行爲只取決於自己的效用,那麽就可以稱爲一階貝葉斯勸説,單個接收者的問題天然地屬於一階貝葉斯勸説,如果存在多個接收者,那麽當接收者 i 的效用只取決於接收者 i 自己的行爲(因此只需要關注一階信念,即關於世界狀態的信念)、從而無需關注其他接收者 j=i 的行爲及信念(即無需關注高階信念)時,也屬於一階貝葉斯勸説。“一階貝葉斯勸説”中的“一階”指的是“一階信念”。
模型
基本設定
一個信息發送者(Sender),一個信息接收者(Receiver)。
世界狀態是未知的,狀態空間為有限集 Ω,行動空間為緊集 A。
發送者和接收者對於世界的狀態有一個共同的先驗信念 μ0,其支撐集為全集(所有狀態都有可能發生)。 μ0(ω) 指當冇有額外的信息時,發送者和接收者認為真實狀態是 ω的機率。μ0支撐集為全集這一假設的限製性並不是很強,我們總可以通過重新定義Ω來使這一點得到滿足,即:如果某個ω′∈Ω有μ0(ω′)=0,那麼無妨重新定義Ω∗=Ω∖{ω′},反正我們也不認為ω′會發生(μ0(ω′)=0的含義)
接收者不能直接觀察到真實的狀態,但在觀察到發送者發送的信號之後,根據先驗信念進行貝葉斯更新,並據此採取行動 a∈A,其行動既影響自己的效用,又影響發送者的效用。(假設我們在行動空間A中隻包含了那些有實際意義者,即∀a∈A,∃μ, such that a∈a∗(μ),或者說,如果某個行動,無論接收者持有什麼信念都不會採取,那麼就不把它包含在行動空間裏)
既然接收者採取的行動同時影響二者的效用,那麼發送者便會試圖影響接收者的行為,從而使其更多地符合發送者自己的利益。但在這裏,發送者不能直接規定接收者做什麼(可以做出拓展使其同時具有直接規定行為的能力,但在這篇論文裏,按作者所說,為了集中考慮信息的作用,隔絕了這種直接規定的通路。據說這一點也是與機製設計理論的不同之處,如 Bergemann and Morris, 2019 指出的),而是可以通過信息結構來影響接收者的信念,從而間接地影響接收者的行為。
貝葉斯勸説與 Signaling game 的區別則在於,貝葉斯勸説裏的信號並不具有直接影響效用的作用。在 Signaling game 裏,為了實現 Seperating equilibrium,其通過行為發送信號的成本需要有差異(如高能力者獲取高學曆的成本更低,使得低能力者難以模仿)。與 Cheap Talk 的區別在於,這裏發送者是有承諾能力的,發送者承諾信息結構發生在真實狀態揭曉之前並且無法在真實狀態揭曉之後反悔,其信號具有實際含義,因此發送者的 Talk 不 Cheap。
發送者的效用函數 v(a,ω),接收者的效用函數 u(a,ω),二者各自都是關於a和ω的連續函數。
其中發送者的效用函數可以取決於世界狀態ω,也可以不取決於它;但接收者的效用函數必須取決於世界狀態,因為在目前的框架內,這種依賴關係是發送者僅有的可以影響接收者行為的作用點。
信息結構 (S,q)
S
q:Ω→Δ(S)
信息結構有兩部分,S 是發送者想讓接收者所能觀測到的信號的潛在可能集,q 是一組條件機率,既當真實狀態是 ω∈Ω 時,觀測到信號 s∈S 的條件機率。這也就意味著,發送者可以指定信號的潛在可能集 S 以及對應關係 q,但是無法控製具體實現哪個 s∈S,並且隱含假設當某個 s∈S 實現之後,發送者不能反悔。
我們稱 s∈S 為信號實現(即實際出現的信號)。
發送者能讓信號實現通過信息結構依賴於世界狀態,在這個意義上,發送者比接收者具有信息優勢,或者更恰當地說發送者具有考察出關於真實狀態信息的能力優勢;但當發送者承諾信息結構時,真實狀態尚未揭曉,那麼在這個意義上發送者與接收者的信息是對稱的。發送者承諾一個信息結構,意味著發送者能夠可信地將自己考察真實狀態信息的能力隻發揮在一定範圍內。因此,“發送者”這一稱呼其實不太合適,與 Cheap Talk 相比,此處**“發送者”在行動時也並不知曉真實狀態是什麼**。如果我們採取“信息獲取”與“信息披露”的區別,那麼當“發送者”在觀察到私人信息後再嚮“接收者”傳遞信息的情形,可以稱為“信息披露”,而這篇文章裏“發送者”可信地承諾採取何種精度的信息獲取機製可以稱為“信息獲取”。發送者本身有私人信息的情形,比如 Myerson (1981) 的 Good News and Bad News, (1983) 的 Mechanism Design by an Informed Principal,或者 Nguyen and Tan (2021) 的 Costly messages,還有 Koessler (2021)等。
發送者說自己不會完全發揮,那麼接收者也會相信發送者隻考察出了部分的真實情況,並且接收者知道發送者無法反悔,接收者知道隻生成了這麼多信息,在這篇文章裏,並不存在發送者撒謊的可能,同時,接收者是貝葉斯理性的,接受者也並冇有被欺騙。發送者選擇信息結構發生在真實狀態揭曉之前,因此發送者選擇了哪種信息結構這一行為並不包含著關於真實狀態的什麼信息。
發送者在真實狀態揭曉之前就已經通過信息結構確定了真實狀態與信號實現之間的對應關係,因此信號實現的含義在事前就被確定了,而不是如 Cheap Talk 般在均衡中確定的。
接收者可以觀察到發送者選擇了什麼信息結構,可以根據觀察到的信號實現來逆推實際狀態可能是什麼,但無法直接觀察到真實狀態。
Timing
- 發送者承諾一個信息結構 (S,q);
- 接收者觀察到信息結構 (S,q);
- 真實狀態(根據先驗機率)揭曉,並經過信息結構(即根據條件機率)轉換為信號實現,信號實現為接收者觀測到;
- 接收者根據先驗信念和信號實現進行貝葉斯更新,根據後驗機率採取行動。
- 發送者和接收者的效用實現,博弈結束。
可以看到,在發送者承諾信息結構的時候,世界狀態仍未揭曉。因此,盡管發送者確實通過自己的行為使得接收者的信念發生了改變,但這裏不涉及“欺騙”問題:發送者也不知道真實的世界狀態為何,發送者所選擇的信息結構是共同知識,特別地,信息結構中所包含的機率同樣為接收者所知。對於博弈中欺騙與誤導的模型化處理,可見 Sobel (2020) 。
策略
發送者的策略:S 和 q。即信息結構。
接收者的策略:行動規則(action rule)。接收者根據觀測到的信號實現(進行貝葉斯更新),採取“信號依賴”的行動。(取決於信號實現的行動,用詞仿照“狀態依賴”)
均衡
解概念:完美貝葉斯均衡。註意:從信息設計的角度來說,這是個靜態問題,並且不是個博弈論問題。因為在信息設計的脈絡下談到解概念 (如:貝葉斯相關均衡,協調均衡等) 時,指的是多個接收方之間的均衡,而這裏隻有一個接收方。但在 Sender-Receiver 脈絡下,這是個動態問題,完美貝葉斯均衡指的是發送者和接收者之間的均衡。並且,由於這裏冇有非均衡路徑問題,所以是完美貝葉斯是均衡而不隻是貝葉斯納什均衡。
一般性地,均衡由三個部分組成 (μs,q(ω),a(s)),其中
- μ(s) 為信念系統,由 μ0 和 q(ω) 根據貝葉斯更新形成;
- q(θ) 滿足發送者的貝葉斯理性;
- a(s) 最大化接收者的事中效用函數 (滿足接收者的貝葉斯理性)。
均衡結果 (τ,s)∈ΔΔ(Ω)×R 為均衡 (μs,q(ω),a(s)) 所引致的後驗信念分佈和發送者的事前效用。
在貝葉斯勸説情形中,q(θ) 滿足發送者的貝葉斯理性體現爲最大化發送者的事前效用函數;在 Cheap Talk 情形中體現爲最大化發送者的事中效用函數,在事中階段發送者已經擁有了私人信息 (觀察到了世界狀態),所以 Cheap Talk 情形施加了額外的關於發送者的激勵相容約束。爲了突出在貝葉斯勸説情形中信息結構的選擇無需滿足發送者的事中激勵相容約束的這一點,也稱貝葉斯勸説中的均衡為承諾機制、均衡結果為承諾結果。
在均衡中,接收者的行動規則應該是對發送者的信息結構的最優反應。同時發送者的信息結構也應該是對接收者的行動規則的最優反應。
接收者的後驗信念 μs(⋅)∈Δ(Ω)(即給定觀察到信號 s 的情況下,真實狀態為某個 ω 的條件機率)由貝葉斯法則生成:
μs(ω)=∑ω′∈Ωμ0(ω′)⋅q(s∣ω′)μ0(ω)⋅q(s∣ω)
接收者根據這個後驗信念來選擇行動a(μs)來最大化其期望效用:
Eμsu(a,ω)=ω∈Ω∑μs(ω)u(a,ω)
當接收者的期望效用最大化問題有多個解( {a∗(μ)}>1 )時,即不同的行動都能帶來那個相同的最大值,那麼選擇其中那個能為發送者帶來最大效用的行動a^(μ)=argmaxa∈{a∗(μ)}∑ωv(a,ω)μ(ω)。由於發送者和接收者的效用函數不必相同(當然正因為如此才有勸說/說服的必要),因此對於接收者來說帶來相同效用值(此時是最大值)的解,未必也給發送者帶來相同的效用值。
發送者選擇信息結構 (S,q),(通過影響接收者的行為而間接地)使得期望效用最大化:
EPr(s)Eμsv(a,ω)=s∈S∑Pr(s)ω∈Ω∑μsv(a(μs,ω))
其中 Pr(s) 錶示在給定信息結構的情況下,信號s被接收者所觀察到的邊際(即已對各種可能的世界狀態加總後的)機率,a(μs)中的μs是接收者的後驗信念,而取期望時候Eμs中的μs是發送者的後驗信念,盡管在這篇文章中二者是重合的,但在概念上做出這種區分是有必要的。
Pr(s)=ω∈Ω∑q(s∣ω)μ0(ω)
由於我們已經假定接收者在觀察到信號實現後,會根據後驗信念採取最優行動,因此整個問題可以簡化為隻有發送者一個行為主體的問題,其中發送者在決策時是預計到自己的行動會引緻接收者的最優行動的,在發送者的問題中,接收者的行為是“機械的”。
行動建議
根據顯示原理(revelation principle,待補充),可以將問題簡化為隻考慮“直接信息結構”(用詞仿照“直接機製”):S⊂A,並且接收者的均衡行動與信號實現相同。這種由發送者直接建議接收者應該做什麼的信息結構被稱為行動建議式信息結構。
這意味著:發送者直接根據自己事先宣佈的信息結構中的條件機率機械地告訴接收者該做什麼,(不同於作為條件機率的後驗信念是在接收者那邊)這裏的條件機率還是在發送者這邊(信號實現是由自然根據發送者選擇的信息結構生成),發送者告訴接收者的是採取何種“純策略”而不是以多少的機率做哪件事a(μ),盡管接收者實際採取的行為與信號實現背後的真實狀態之間的對應關係a(ω)是隨機的。
在行動建議式信息結構下,信號的潛在可能集已經被固定為A(或A的子集)了,這時候q:Ω→Δ(S)與q:Ω→Δ(Ω×S)在一定條件下是等價的(待補充:Crawford and Sobel, 1982 腳註)
分析
在某些情況下,發送者尋找最優信息結構的問題可以簡化為發送者尋找在後驗信念上的最優分佈的問題。當然,無論是尋找最優信息結構還是尋找後驗信念上的最優分佈,都是在給定接收者會對後驗信念採取最優反應的前提下,因此接收者的“參與約束”或“激勵相容約束”總是得到滿足的:發送者都是在接收者的最優反應的前提下來影響接收者。(類似於Stackelberg模型)
在前麵敘述關於發送者兩層期望效用式我們提到,在真實狀態揭曉之前,發送者便已事先承諾了信息結構。因此,對於給定的信息結構來說,尚未揭曉的真實狀態會(盡管是依據發送者自己選擇的信息結構)引緻不確定的信號,哪種信號會實際出現會影響接收者的貝葉斯更新過程,從而影響其後驗信念。
給定發送者選擇的信息結構,當時尚未揭曉的真實狀態,會使發送者在決策時對於具體引緻接收者的哪種後驗信念具有不確定性,因此,某個信號實現s∈S會由於背後意味著的ω∈Ω而引緻一個後驗信念,那麼,一個信息結構(S,q)就引緻了後驗信念上的一個分佈(由於接收者是根據後驗信念行動,這也意味著信息結構引緻了接收者行為的一個分佈)。反之,對於後驗信念上的一個分佈,和一個信息結構,當它們之間滿足一定的關係時,我們也可說以那個分佈是由那個信息結構所引緻的。
後驗信念上的某個分佈 τ∈Δ(μ)=Δ(Δ(Ω)),和信息結構 (S,q) 之間,若滿足以下關係,則我們說 τ 是由 (S,q) 引緻的:
1.貝葉斯更新。對於每個狀態 ω∈Ω 和任何信號實現 s∈S,都有
μs(ω)=∑ω′∈Ωμ0(ω′)⋅q(s∣ω′)μ0(ω)⋅q(s∣ω)
2.所有可能通過某個可能信號實現s∈S所生成的後驗信念μs,構成這個後驗信念上的分佈的支撐集。
supp(τ)={μs}s∈S
3.對於任何可能出現的後驗信念 μ,這個後驗信念出現的機率 τ(μ),等於所有那些可以通過某個信號實現而使得接收者生成這個後驗信念的機率的加總。
τ(μ)=s:μs=μ∑Pr(s)=s:μs=μ∑ω∈Ω∑q(s∣ω)μ0(ω)
我們稱在後驗機率上的一個分佈 τ(⋅) 是貝葉斯可行的,若它使得後驗機率的期望等於先驗機率:
support(τ)∑μ⋅τ(μ)=μ0
可見,如果一個分佈τ是由信息結構(S,q)所引緻的,則
μ∈supp(τ)∑τ(μ)μ(ω)=μ∈supp(τ)∑s:μs=μ∑ω′∈Ω∑q(s∣ω′)μ0(ω′)μ(ω)=μ∈supp(τ)∑s:μs=μ∑q(s∣ω)μ0(ω)=[μ∈supp(τ)∑s:μs=μ∑q(s∣ω)]μ0(ω)=1⋅μ0(ω)=μ0(ω)
貝葉斯可行也稱作貝葉斯一緻性,它由迭代期望定律而來,因此,根據迭代期望定律,任何後驗信念上的分佈必須滿足“後驗的期望等於先驗”這一條件。“後驗的期望等於先驗”是可行性的必要條件,這個必要條件又稱爲後驗信念的鞅性質。
當考慮單個接收者的情形時,“後驗的期望等於先驗”這一條件,同時也是可行性的充分條件。
“後驗的期望等於先驗”是貝葉斯可行在單個接收者情形下的充分且必要條件,這被稱爲 Splitting Lemma。
貝葉斯可行是這裏的激勵相容約束:在接收者事前看來,按照發送者給出的信號行動不會比按先驗信念行動差。順便提一句,我們說的期望效用最大化,都是指不確定性消失前的主觀機率期望效用最大化,如果有時候看起來是使用了客觀機率,那其實隻意味著這時候主觀機率與客觀機率重合;如果有時候看起來博弈結果並冇有最大化參與人的效用,那隻是意味是事前理性不等於事後理性,而我們隻要求事前理性。
這裏事前與事後的區分是不確定性以及最終效用的實現與否,但從整個博弈來看,某個參與人採取事前計畫的時候,可能已經處於整個博弈的事中了。
比如,在不完備信息博弈的框架中,通常將參與人獲取自己信號/類型前的處境稱為事前,而在獲取自己信號/類型後的處境稱為事中。比如,當發送者已經對接收者傳遞了某個信號後,接收者觀察到了信號,並考慮如何根據形成的後驗信念(條件機率)做最優化決策時,便是這個博弈的事中階段。但由於此時不確定性尚未消失、隻有當接收者實際採取行動後效用才會最終實現,因此當其做最優化考量時其目標函數依然是期望效用。
按照對博弈時間線而非對不確定性消失與否的區分,還可以定義事前期望效用與事中期望效用,比如
EθESu(ap(s′),θ)
就是事前期望效用,而
Eθu(a(ps),θ∣s)
就是事中期望效用。其區別在於是否獲得了除先驗以外的信息,無論這個信息是別人傳遞給自己的關於世界狀態或其他人的信息,還是參與人觀察到的關於自己的比如成本等信息。
從而,每個信息結構都能引緻後驗信念上的一個分佈,由信息結構引緻的後驗信念上的分佈,由於行為人的貝葉斯理性,總是滿足貝葉斯可行性。給定後驗信念上的一個分佈,並且後驗信念的期望等於先驗信念,總是存在可以引緻後驗信念上這個給定分佈的信息。
基於信念的方法:將發送者的策略和均衡信念系統都等同於後驗信念上的事前分佈 τ∈ΔΔΩ,如果這個分佈滿足貝葉斯可行性 ∫μdτ(μ)=μ0,則稱這個分佈 τ 為一個信息政策。
均衡結果:(τ,v)∈ΔΔ×R,由均衡 (μs,a(s),q(ω)) 所引致的一對元素,分別爲後驗信念的分佈和發送者的事前效用。
如果一個均衡結果中的 τ 并非退化的 (τ=δ(μ0),即 τ(μ0)=1,τ(μs)=0,∀μs=μ0),則稱接收者的後驗信念上的這個分佈 τ 是有信息量的。
如果僅關注均衡結果,那麽基於信念的方法與原問題是等價的。
因此,有如下引理
引理一
選擇最優的信息結構和選擇信息政策是等價的,即:
(S,q)maxEqv(a(μs,ω))
與
maxEτv(a(μs,ω))s.t.Eττ(μs)=μ0
是等價的。
將發送者關於接收者後驗信念的值函數記為v^(μ)=Eμv(a^(μ),ω),其中a^(μ)是當接收者擁有後驗信念μ是所採取的均衡(最優)行為。在這裏,μ是接收者的後驗信念,會影響接收者的行動,因此會影響發送者的效用;但是在當前的框架下,μ也是發送者的後驗信念,如果發送者的效用也依賴於實際的世界狀態,接收者的給定行為在不同的世界狀態下會給發送者帶來不同的效用。後驗信念在發送者的值函數中出現了兩次。
則前述問題進一步等價為
maxEτv^(a(μs,ω))s.t.Eττ(μs)=μ0
在離散情形下,發送者的問題為
v∗=τmaxμ∈supp(τ)∑v^(a^(μ),ω)τ(μ)
s.t.
μ∈supp(τ)∑μτ(μ)=μ0
當給定最優的後驗信念上的分佈τ∗時,
最優信息結構可以如下生成(給定我們採用的是直接推薦)
q∗(sμ∣ω)=μ0(ω)μ(ω)τ∗(μ)
命題一
下述三個命題是等價的:
- 存在使得發送者期望效用最大化(實現v∗)的行動建議式信息結構。
- 存在使得發送者期望效用最大化(實現v∗)的信息結構。
- 存在使得發送者期望效用最大化(實現v∗)的貝葉斯可行的後驗信念上的分佈。
證明:
1→2
根據定義,行動建議式信息結構也是一種信息結構。
2→1
給定使得發送者達到最大效用v∗的信息結構(S,q),我們把其中引緻接收者採取均衡行為的那些信號實現記為
Sa={s∣a^(μs)=a}
考慮另一個信息結構(s′,q′)
其中信號實現的潛在可能集s′=A,並把那些能引緻接收者採取行動a的各種條件機率加總
q′(a∣ω)=s∈Sa∑q(s∣ω)
(即,首先替換潛在可能集為行動建議,然後將引緻同一行為的信息結構多個組成部分“打包”成一個條件機率)
此時,
μa′(ω)=∑ω′∈Ωμ0(ω′)q′(s′∣ω′)μ0(ω)q′(a∣ω)=∑ω′∈Ωμ0(ω′)∑s′∈Saq(s′∣ω′)μ0(ω)∑s∈Saq(s∣ω)
對於任何一個行動a∈A,都有
ω∈Ω∑u(a,ω)μa′(ω)∀a⋆∈A=ω∑u(a,ω)∑ω′∈Ωμ0(ω′)∑s′∈Saq(s′∣ω′)μ0(ω)∑s∈Saq(s∣ω)=ω∑u(a,ω)μ0(ω)s∈Sa∑q(s∣ω)∑ω′∈Ωμ0(ω′)∑s′∈Saq(s′∣ω′)1=ω∑u(a^(μs),ω)μ0(ω)s∈Sa∑q(s∣ω)∑ω′∈Ωμ0(ω′)∑s′∈Saq(s′∣ω′)1≥ω∑u(a⋆,ω)μ0(ω)s∈Sa∑q(s∣ω)∑ω′∈Ωμ0(ω′)∑s′∈Saq(s′∣ω′)1=ω∑u(a⋆,ω)μa′(ω)
Sa中的點是根據以下標準挑選出來的,首先,給定先驗信念和原有的信息結構(因此我們需要把信念展開才能比較接收者的行為),接收者在持有後驗信念μs,∀s時採取最優反應{a∗(μs)},從其中挑選出來對發送者最有利的a^(μ),並且將那些使接收者採取相同行為的不同信號實現聚在一起Sa={s∣a^(μs)=a}。因此,根據定義,a是接收者對於s∈Sa這些信號的最優反應;當s′=A,並把那些引緻相同行為a(s)=a,∀s∈Sa的不同信號實現之條件機率“打包”在一起之後,a(接收者的行為)依然是對於根據q′(⋅∣ω)生成的a(發送者的推薦)的最優反應。
由此,我們根據任一最優信息結構(S,q),通過重新定義信號實現的潛在可能集、並“打包”引緻接收者相同均衡行為的條件機率,構造出了一個給發送者帶來相同效用值v∗的行動建議式信息結構(s′,q′)=(A,q′)。
1→3
給定一個貝葉斯可行的後驗信念上的分佈τ,記
q(s∣ω)=μ0(ω)μs(ω)τ(μs)
由於我們假設先驗信念具有全支撐,因此分母總是為正的,上式具有良好定義。
從而
q(s∣ω)μ0(ω)=μs(ω)τ(μs)
進而
ω∈Ω∑q(s∣ω)μ0(ω)=ω∈Ω∑μs(ω)τ(μs)
3→2
根據引理一,每個信息結構(S,q)都對應於一個後驗信念上的分佈τ。因此
Eτω∑v^(a^(μ),ω)μ(ω)=μ∈supp(τ)∑τ(μ)ω∑v^(a^(μ),ω)μ(ω)=μ∈supp(τ)∑[s:μs=μ∑ω′∑q(s∣ω′)μ0(ω′)][ω∑v^(a^(μ),ω)μ(ω)]=μ∈supp(τ)∑ω∑s:μs=μ∑ω′∑q(s∣ω′)μ0(ω)μs(ω)v^(a^(μ),ω)=μ∈supp(τ)∑ω∑s:μs=μ∑μ0(ω)q(s∣ω)v^(a^(μ),ω)=s∑ω∑μ0(ω)q(s∣ω)v^(a^(μs,ω))=E(S,q)v^(a^(μs),ω)
因此,在最優信息結構下
≥≥ω∑u(a^(μs),ω)μs(ω)ω∑u(a∗(μs),ω)μs(ω)ω∑u(a∗(μ0),ω)μs(ω)
即在最優信息結構下,接收者聽從建議不會得到比僅僅按照先驗信息行動更低的期望效用。但這一性質是由於給定的信號實現與背後的真實狀態之間是以機率連接的,按照效用實現來劃分,這是事前性質。當效用實現之後,效用的實現值取決於真實的世界狀態,從事後來看,在效用實現之後,聽從建議的接收者可能會發現實際的效用值低於直接按照先驗信念行動的預設效用。即,盡管期望值不會低於預設效用,但參與取期望的各個組成部分不必高於預設效用。(同時,由於我們的框架是關註發送者的效用,因此,後文中對於發送者來說的∀μ with τ(μ)>0,V(μ)=v^(μ)這一性質對於接收者來說不成立。)
這個命題回答了如下問題:
- 為什麼行動建議式的信息結構就足夠了?
- 為什麼“選擇最優信息結構”等價於“選擇後驗信念上的最優分佈”?
推論一
發送者能夠通過勸說獲利,當且僅當存在一個貝葉斯可行的後驗信念上的分佈τ∈ΔΔ(Ω)使得
Eτv^(μ)>v^(μ0)
其最優值v∗由下式給出
maxEτv^(a(μs,ω))s.t.Eττ(μs)=μ0
其中v^(μ)為發送者的效用關於接收者的後驗信念μ的值函數。
然而,這隻是錶明,如果存在最優信息結構/勸說/分享信息/後驗信念上的分佈的話,應該怎麼找出來。但它本身並不意味著最優解存在。但而,後麵我們可以看到,偏嚮發送者的“打破僵局”慣例(即,給定接收者持有的後驗信念,如果接收者的最優解是多點集,則選出其中使得發送者效用最高的一個)保證了最優解的存在。
凹化解
將發送者的期望效用錶示為關於接收者的後驗信念的函數,這種後驗信念與效用值的對應關係錶示為一個函數。(假定當接收者有多個最優行動時,選出其中對發送者最有利的那一個,從而這真的是一個單值的函數關係,而不是多值的對應關係)
發送者效用函數的凹化函數,就是那些逐點取值不小於效用函數取值的凹函數中,逐點函數值最小的那一個。
此處“凹化”術語可能稍微有些奇怪。但其實對函數的凹化其實是在給函數的圖像做凸包。當目標函數變成凹函數之後,最大化問題就可以使用常規的最優化方法來進行求解。(在凸分析中,相關概念可見concave/convex closure, concav(convex-)ify, concav(convex-)ification, concave/convex envelope, conjugate, major(minor-)ization等)
為什麼能夠找到滿足這樣性質的凹函數呢?因為,發送者第二層期望效用是在通過後驗信念的分佈做組合,這種組合使得上麵不凹的地方被磨平了。在當前的假設下,對後驗信念上的分佈再次取期望得到的效用就是這個凹函數。在機率分佈集–單純形這個緊集上對一個上半連續(semi,不是hemi,這是由於“當存在接收者的多個最優行為時選擇對發送者最有利的一個”這個假設,並且,由於雙層期望效用是由第一層期望效用(發送者效用關於接收者後驗信念的值函數)的凸組合得來的,它繼承了上半連續的性質)做最大化,解總是存在的。
定義函數v^(μ)的下圖的凸包
V=co({(v,μ)∈R×Δ(Ω)∣v≤v^(μ)})
對於接收者的任意後驗信念μ∈Δ(Ω),定義發送者效用值函數的凹化函數,
V(μ)=sup{v∈R∣(v,μ)∈V}
那些凹化後的函數值嚴格高於值函數的地方,該處對應的信念,就是那些當它們是先驗信念的時候,發送者可以通過操控信念而得利的地方。(但這也意味著,當發送者關於接收者後驗信念的值函數已經為凹函數的時候,凹化函數就等於原來的函數,二者完全重合,此時發送者無法通過擾動信念獲利。)(另有一種採用仿射函數的等價定義方式,可見Aliprantis and Border, 2006)
通過比較在先驗信念處,值函數和凹化函數值,可以得知發送者是否可以通過擾動信念而獲利。當可以獲利的時候,那些使得“值函數的凸組合成為凹化函數值”的點們,就是應該最優信息結構引緻的後驗信念。
其中,貝葉斯可行的要求,使得“發送者可以通過擾動信念而獲得的最大效用”v∗,與凹化函數在先驗信念處的取值V(μ0)相同,因此給予了我們通過凹化法來求解最優問題的合理性。
下麵總結了一些信息披露程度與信念在單純形中的位置之間的關係。
- 完全披露:對應於單純形的一個頂點。
- 完全無信息:對應於單純形的一個特定內點(先驗信念)。
- 部分披露:對應於單純形的某個非頂點。
- 強披露:對應於單純形的邊界。
頂點意味著接收者通過觀察信號實現,能夠確定地倒推出真實的世界狀態是哪個;非頂點意味著某些信息並冇有被發送者傳遞給接收者,其中內點意味著接收者認為每種狀態都有可能,盡管對各種狀態發生機率的判斷或許不同於先驗信念,而某條邊意味著接收者已經倒推出這條邊對麵的那個點所代錶狀態是不可能的。
推論二
發送者通過擾動後驗信念所能得到的最大效用是V(μ0),發送者能夠通過擾動後驗信念得利當且僅當
V(μ0)>v^(μ0)
我們說發送者願意分享信息,如果存在某個後驗信念μ,使得給定發送者持有這個後驗信念時:發送者通過分享信息,引緻接收者也持有這個後驗信念μ並依此行動帶給發送者的效用,要高於雖然發送者持有這個後驗信念μ但不分享信息使接收者按先驗信念μ0並依此行動帶給發送者的效用。
v^(μ)>ω∑v(a^(μ0),ω)μ(ω)
其中對ω的加總意味著這是事前的比較,世界狀態尚未揭曉,而發送者對不同後驗信念μs=μ與μs=μ0的比較是預測性質的。
盡管從錶麵上來,發送者願意分享信息與發送者能夠通過分享信息/勸說/擾動後驗信念來獲利是同一件事,而事實上,發送者是否願意分享信息是取決於是否存在某個滿足要求的後驗信念μ,但當發送者分享信息後,不同的信號實現會引緻不同的後驗信念,比如既有那個滿足要求的後驗信念μ又有另外一個μ′(除非完全不分享信息,那麼就隻會有一個μ0),這時發送者是否能夠通過分享信息獲利還取決於接收者的行為a^(μ)帶來的v^(μ)和a^(μ′)帶來的v^(μ′)。
我們接下來可以看到:如果發送者能夠通過勸說來獲利,那麼發送者一定願意分享信息;但發送者願意分享信息,並不意味著發送者能夠通過勸說來獲利,額外的條件是接收者的偏好在先驗信念處是離散的。
命題二
(1) 如果發送者不願意分享信息,那意味著發送者不能通過勸說來獲利。
(2) 如果發送者願意分享信息,並且接收者的偏好在先驗信念處是離散的,那麼發送者便可以通過勸說來獲利。
(3) 如果接收者的行動可能集A為有限集,則接收者的偏好在先驗信念μ0處通常是離散的。(“通常”是指 generic property,即不滿足文中性質的情況測度為0,由於冇看過中文的高等機率論/測度論內容,我不太清楚這個詞在中文裏的錶述為何)
我們說接收者的偏好在信念μ處是離散的,如果接收者在持有信念時μ通過最優行動a^(μ)所能得到的期望效用,要比接收雖然持有信念μ、但採取任何其他行動∀a=a^(μ)所得到的期望效用都要高出某個嚴格為正的ϵ>0,即
∃ϵ>0,such that∑u(a^(μ),ω)μ(ω)>∑u(a,ω)μ(ω)+ϵ
根據假設∀μ,∃a^(μ),又u是連續函數,從而∑ωu(a,ω)μ(ω)是連續函數,因此如果接收者的偏好在μ處是離散的,則∃δ>0,使得∀μ′∈N(μ,δ),都有∑u(a^(μ),ω)μ′(ω)>∑u(a,ω)μ′(ω),因此a^(μ′)=a^(μ)。
證明:
(1) 如果發送者不願意分享信息,那麼∀μ,v^(μ)≤∑ωv(a^(μ0),ω)μ(ω)。即不論發送者持有何種後驗信念μ,他都甯願接收者僅根據先驗信念μ0採取行動a^(μ0)。這時給定一個引緻τ的q,它能為發送者帶來的最大效用為∑s∈Sτsv^(μs)≤∑s∈Sτs∑ωv(a^(μ0),ω)μs(ω)=v^(μ0),這意味著發送者通過擾動信念所能得到的最大期望效用都不會高於讓接收者按先驗信念行動能給他帶來的效用高。
(2) 給定接收者採取當信念為μ0時的最優行動a^(μ0),其在不同信念下的加總∑u(a^(μ0),ω)μ(ω)關於信念μ是線性的,從而是連續函數。又接收者的偏好在μ0處是離散的,因此當其信念離μ0不太遠時他仍然願意採用a^(μ0),即∃δ>0使得∀μ∈N(μ0,δ),都有a^(μ)=a^(μ0)。既然發送者願意分享信息,那麼存在某個μh使得v^(μh)>∑ωv(a^(μ0),ω)μh(ω)。考慮一個從μh出發、通過μ0的射線,由於我們假設μ0具有全支撐,μ0是個內點,那麼存在某個μl∈N(μ0,δ)使得μ0=γ⋅μl+(1−γ)μh其中γ∈(0,1)。我們把這個凸組合的係數作為後驗信念μl和μh在後驗信念上的分佈τ中的機率:τ(μl)=γ及τ(μh)=1−γ。由於接收者在先驗信念μ0處的偏好是離散的,而μl∈N(μ0,δ),因此a^(μl)=a^(μ0),此時v^(μl)=∑ωv(a^(μl),ω)μl(ω)=∑ωv(a^(μ0),ω)μl(ω)。從而
γv^(μl)+(1−γ)v^(μh)==>===γω∑v(a^(μl),ω)μl(ω)+(1−γ)ω∑v(a^(μh),ω)μh(ω)γω∑v(a^(μ0),ω)μl(ω)+(1−γ)ω∑v(a^(μh),ω)μh(ω)γω∑v(a^(μ0),ω)μl(ω)+(1−γ)ω∑v(a^(μ0),ω)μh(ω)ω∑v(a^(μ0),ω)[γμl(ω)+(1−γ)μh(ω)]ω∑v(a^(μ0),ω)μ0(ω)v^(μ0)
即
γv^(μl)+(1−γ)v^(μh)>v^(μ0)
這就是
Eτv^(μ)>v^(μ0)
即發送者能夠通過勸說獲利。
直覺:如果接收者的偏好在先驗處是離散的,那就意味著在先驗附近的那些信念處,接收者將會採取與先驗處相同的行動。那麼,當接收者按先驗採取的預設行動對於發送者來說不利時,那麼有可能通過披露信息獲利。因為披露信息會帶來不確定性、經過自然轉換為不同的信號實現,有時候這一實現對發送者來說有利、有時候不利。但即使不利也無所謂,因為在信念上的凸組合可以包含一個離先驗較近的後驗信念,使得在最優信息結構下最壞的結果本來在不披露信息時也要以機率1發生,但現在這個不好的情況隻是以小於1的機率發生,而且同時還有更好的情況也會發生。
(3) 我們先錶明,當給定A為有限集時,如果接收者者的偏好在某個信念μ處不是離散的,那麼接收者必然在當持有這個信念時對至少兩個行動a^(μ)和a=a^(μ)無差異∑ωu(a^(μ),ω)μ(ω)=∑ωu(a,ω)μ(ω)。
使用逆否證法。假設不存在這樣一個a(即在信念μ下任何a′對於接收者來說都不是與a^(μ)無差異的),那麼可以定義ϵ>0為
ϵ=21a′=a^(μ)min{ω∑u(a^(μ),ω)μ(ω)−ω∑u(a′,ω)μ(ω)}
由於在信念μ下任何a′對於接收者來說都不是與a^(μ)無差異的,並且a^(μ)是μ下的最優反應,因此ϵ是嚴格大於0的,並且已經假設A是有限集,從而最小值總能取到。但這樣的話
ω∑u(a^(μ),ω)μ(ω)>ω∑u(a′,ω)μ(ω)+ϵ,∀a′=a^(μ)
這就意味著接收者的偏好在μ處是離散的。逆否證成。
接下來,我們錶明使得接收者在不同行動間無差異的信念集具有零測度(即接收者的偏好隻在具有零測度的信念下是不離散的)。
這樣的信念集為
{μ∣∃a=a^(μ), such that ω∑u(a,ω)μ(ω))=ω∑u(a^(μ),ω)μ(ω)}
我們可以進一步錶明,這個信念集的某個超集具有零測度。即,將a^(μ)與任意a的比較,放寬為任意a與任意a′的比較。由於A是有限集,a與a′的組合也隻有有限種可能,而有限個零測集之並仍為零測集,因此我們隻需證明接收者在給定的兩個行動a與a′無差異的信念集{μ}具有零測度。
這樣的信念集為
{μ∣,∃a=a′, such that ω∑u(a,ω)μ(ω))=ω∑u(a′,ω)μ(ω)}
由於Ω為有限集(註意,Ω一直假設為有限集,但A在整體框架中隻假設為緊集,隻是在當前命題的第三部分時,我們錶明如果A也時有限集將會得到那些性質),我們可以將其錶示為Ω={ωi}i(並隨意指定∣Ω∣=n),進而記βi為
βi=u(a,ωi)−u(a′,ωi),i=1,...,n
以及
β=[β1,...,βn]
和
μ=[μ(ω1),...,μ(ωn)]
前麵的信念集可以進一步錶達為
{μ∣βTμ=0}
由於我們僅將那些接收者有可能採取的行動包含在了行動空間裏,即∀a∈A,∃μ, such that a∈a∗(μ),所以任何a′都是某個μ′的最優反應。同時,由於我們打破僵局的慣例是“當接收者有多個最優反應時,選取其中對發送者最有利的那一個”,那麼行動空間可以進一步精煉為∀a∈A,∃μ, such that {a}=a∗(μ),因此肯定存在某個ω使得u(a,ω)=u(a′,ω)(否則,要麼那個a′是不會被採取的,要麼那個a′是多餘的),因此至少存在一個βi=0。由此,β是個秩至少為1的線性變換,但在給定a和a′的情況下,β作為嚮量其秩至多為1,兩者結合可知β的秩恰好為1,那麼根據 Rank-Nullity定理,作為β之核的線性空間{μ∣βTμ=0}的秩為n−1,而n維空間的任何m維(m<n)子空間的測度都為0。
定理一
存在一個最優的信息結構,在最優的信息結構下,發送者所能得到的最大效用為v∗=V(μ0)。
證明:由於我們已經錶明了,最優信息結構的存在,與滿足貝葉斯可行的後驗信念上的最優分佈存在,之間是等價的。因此,我們接下來證明,存在滿足貝葉斯可行的後驗信念上的最優分佈。
首先,我們錶示v^(μ)關於μ是上半(semi)連續的。
{(μ,v)∣v≤v^(μ)}
是個閉集。
假設v^(μ)在某個μ處不連續,由於v^(μ)=∑ωv(a^(μ),ω)μ(ω),而v(a,ω)關於a和ω是假設為連續的,∑ωv(a,ω)μ(ω)關於μ是線性從而是連續的,因此這個不連續隻可能出現在a^(μ)與μ之間的關係上。但根據 Berge’s Maximun Pricinple,當目標函數u(a,ω)連續(註意,現在我們轉換到了接收者問題)、約束對應a(μ):Δ(Ω)→A是緊值的連續對應(註意,其實在本文中我們並冇有施加任何約束)時,值函數u(μ)=u(a∗(μ),ω)是連續函數,解對應a∗(μ)是上半(hemi)連續的。我們前麵看到a^(μ)關於μ不是連續的,但a∗(μ)關於μ又是上半(hemi)連續的,而同時能滿足這兩點的情況就是a∗(μ)在μ處是一個滿足上半(hemi)連續的非單點集(非單點,因此不是連續的)。
即
{(μ,a)∣a∈a∗(μ)}
是個閉集。
非單點集意味著a^(μ)(我們根據“對發送者最有利”的標準選出來的)是a∗(μ)的嚴格子集。即
v^(μ)=a∈a∗(μ)maxω∑v(a,ω)μ(ω)
根據hemi-semi定理,v^(μ)是上半(semi)連續的。
補充:hemi-semi定理,僅敘述與此處相關的upper部分。
假設可行性對應a:Δ(Ω)→A是非空、緊值的。如果f:gr(a)→R是上半(semi)連續的,那麼如下定義的v^就能取到最大值。並且,如果a是點μ′處是上半(hemi)連續的,那麼v^在點μ′處是上半(semi)連續的。
v^(μ)=maxf(μ,a(μ))
將f取為(a(μ),∑ωv(a(μ),ω)μ(ω))即可。
證明可見KC Border的Notes中"correspondences"一章,或 Aliprantis and Border (2006) Lemma 17.30,P569。
應用在此處即意味著:f 是發送者期望效用函數的圖 (a(μ),∑ωv(a(μ),ω)μ(ω)),其中 v(a,ω) 關於 a 的連續性是根據假設得到的,而 ∑ωv(a,ω)μ(ω) 關於 a 的連續性是根據前一點以及它作爲求和函數相結合得到的;這裏的可行性對應 a⋆ 為對接收者對於給定的後驗信念所得的最大化問題的解集 (根據將 Berge 最大值定理應用與接收者問題,這個對應是上半連續的;這一對應,在接收者問題中是解對應,在當前這個打破平局問題中是約束對應),我們從接收者最大化問題的解集中選取對於發送者最有利的哪一個 (這是我們假設的打破平局的規則) 就意味著在做 maxa∈a⋆(μ)∑ωv(a,ω)μ(ω),將其值函數定義爲 v^(μ)=maxa∈a∗(μ)∑ωv(a,ω)μ(ω)。
根據 hemi-semi 定理,v^(μ) 就是關於 μ 的上半連續函數。
即:當 a∗ 為對應時是上半連續的,當 a∗ 為函數時是連續的。但前麵錶明它是多值的,從而 a∗ 是上半連續的,而這時 v^(μ)=maxf(μ,a(μ)) 也是上半連續的。
將v^的下圖記為hyp(v^)
hyp(v^)={(v,μ)∈R×Δ(Ω)∣v≤v^(μ)}
其下圖的凸包為
V=co({(v,μ)∈R×Δ(Ω)∣v≤v^(μ)})
根據Krein-Milman定理,下圖的凸包裏的每個點(v′,μ′)都可以錶示為其極點的凸組合
(v′,μ′)=j∑λj(v(μj),μj)
發送者的凹化函數為
V(μ)=sup{v∈R∣(v,μ)∈V}
我們將要錶明,給定任何一個信念μ和hyp(v^)的一個子集S={(μj,vj)}j⊂hyp(v^),,如果(μ,V(μ))在S的凸包裏,那麼(μ,V(μ))也“S與hyp(v^)的交集”的凸包裏。
假設(μ,V(μ))=∑jγj(μj,vj),其中∑jγj=1,γi∈[0,1],∀j,上一行中說我們要有vj=v^(μj),∀j,反證,假設∃γi>0但vi<v^(μi)(註意,根據定義,下圖已經排除了反方嚮的不等式,所以這裏的反證其實是假設,構成凸組合的某個點不是極點、而是內點,但Krein-Milman定理隻告訴我們可以由凸組合錶示,並非隻能由凸組合錶示,所以需要來單獨證明),那麼將原先的凸組合中的這個內點(μi,vi)替換為(μi,v^(μi)),則{(μj,vj)}{j}∖i∪(μi,v^(μi))⊂hyp(v^)。但使得(μi,vi)成為內點的是vi<v^(μi),而γiμi+∑{j}∖iγjμj=μ依然成立,並且γiv^(μi)+∑{j}∖iγjvj>∑jγjvj=V(μ)。然而,根據定義,V(μ)=sup{v∈R∣(v,μ)∈co(hyp(v^))},於是前式意味著
{(μj,vj)}{j}∖i∪(μi,v^(μi))γiv^(μi)+{j}∖i∑γjvj⊂hyp(v^)>sup{v∈R∣(v,μ)∈co(hyp(v^))}
矛盾。
接下來我們錶明,任何一個(μ,V(μ))都可以由{(μi,v^(μi))}i的凸組合得到。
由於v^(μ)關於μ是上半(semi)連續的,它的下圖hyp(v^)是閉集。記H={(μ,v)∈hyp(v^)∣v≥infμ′v^(μ′)}(即把下圖從下方截斷:去掉那些任何時候都不會在優化問題中取到的點,例如,如果在問題中v^(μ)能取到最低的值是0效用,那麼就把三四象限去掉,隻保留那些滿足{(μ,v)∣0≤v≤v^(μ)},這是為了使我們想找到錶達的凸集成為緊集,Krein Milman凸集錶示定理的要求),由於v是連續函數,而A為緊集,因此v^(μ)=v(a^(μ),ω)是有界的,從而infμ′v^(μ′)是存在的,而infμ′v^(μ)與(μ,v)∈hyp(v^)={(μ,v)∣v≤v^(μ)}一起使得H是有界的,但H=hyp(v^)∩{(μ,v)∣v≥infμ′v^(μ′)},因此H是閉集,從而H是緊集,而有限維空間裏緊集的凸包仍是緊集,即co(H)是緊集,從而co(hyp(v^))是閉集(但一般地,閉集的凸包不一定是閉集,待補充)。
V(μ)=τΔΔ(Ω)sup∫Δ(Ω)v^(μ)τ(dμ)s.t.∫Δ(Ω)μτ(dμ)=μ0
我們先將發送者最終問題的值函數錶示為W(μ),並錶明W(μ)=V(μ)。
考慮發送者問題的對偶問題
D(λ)=τ∈ΔΔ(Ω)sup∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)
根據弱對偶定理
D∗=λ∈R∣Ω∣infD(λ)≥W(μ0)
而v^的下圖的凸包V根據設定就是個內部非空int(V)=∅的凸集。
但v^的上半(semi)連續意味著hyp(v^)是閉集(upper semi continuous 意味著下圖是閉集;緊值的 upper hemi continuous 意味著圖是閉集,註意區別),
並且
V(μ0)=sup{v∈R∣(v,μ0)∈V}
同時,根據V(μ)的構造,V(μ0)<v^(μ0)不成立,所以(μ0,V(μ0))∈V∖int(V)。
根據支撐超平麵定理,存在一個嚮量(比世界狀態空間的維度高一維)(u,w)∈R×R∣Ω∣滿足u>0使得
uV(μ0)+wTμ0≥uv^(μ)+wTμ
其中(v,μ)∈V。即使用支撐超平麵定理,錶明(μ0,V(μ0))∈V∖int(V)與int(V)在(μ0,V(μ0))處存在支撐超平麵(u,w)。
(1) 如果V(μ0)=v^(μ0),那麼對於任何μ∈Δ(Ω),代入
uv^(μ0)+wTμ0≥uv^(μ)+wTμ
得到
v^(μ0)+u1wTμ0≥v^(μ)+u1wTμ
接下來我們錶明τ=δ{μ0}(即不揭露任何信息,唯一地使接收者的後驗信念確定為先驗信念μ0)
在這種情況下(V(μ0)=v^(μ0))
對於發送者為唯一最優的
(即W(μ0)=v^(μ0)=V(μ0))。
根據
D(λ)=τ∈ΔΔ(Ω)sup∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)
可知,如果能夠找到某個λ使得
δ{μ0}∈argτ∈ΔΔ(Ω)max∫Δ(Ω)(v^(μ)−λTμ)τ(dμ)
就可以了。但這就意味著找到了某個τ使得原問題的目標函數取得了D(λ)這個期望效用,那麼原問題目標函數的上確界值函數W(μ0)就至少為D(λ),即
W(μ0)≥D(λ)
但根據定義有
D∗=λ∈R∣Ω∣infD(λ)≥W(μ0)
因此
W(μ0)≥D(λ)≥D∗≥W(μ0)
即
W(μ0)=D(λ)
因此δ{μ0}確實解了原始問題。下麵我們考慮如何找到這個λ
令λ=−u1w
則
v^(μ0)+u1wTμ0≥v^(μ)+u1wTμ
變為
v^(μ0)+λTμ0≥v^(μ)+λTμ
兩邊同時積分,並代入τ=δ{μ0},有
∫Δ(Ω)(v^(μ0)−λTμ0)dμ0≥∫Δ(Ω)(v^(μ)−λTμ)τ′(dμ)
但這就意味著當λ=−u1w時,τ=δ{μ0}比任何其他的τ′∈ΔΔ(Ω)對於發送者來說都能帶來更高的效用。因此,當V(μ0)=v^(μ0)時,完全不披露任何信息,使得後驗信念與先驗信念完全重合是發送者的最優策略。
(2) 如果V(μ0)>v^(μ0),那麼根據Caratheodory定理,存在{v^(μj),μj}j=1∣Ω∣+2⊂{(v,μ)∈R×Δ(Ω)∣v≤v^(μ)}和α∈Δ({1,...,∣Ω∣+2})使得
j=1∑∣Ω∣+2αj(μj,v^(μj))=(μ0,V(μ0))
結合
uV(μ0)+wTμ0≥uv^(μ)+wTμ
可知
V(μ0)=v^(μj),∀j
以及
uV(μ0)+wTμ0=uv^(μj)+wTμ