知乎日報:猜對我手裡有幾枚硬幣我就把它們都給你

  這就是一道博弈論的題目。

  如果按照題目的描述,我們可能會畫出這樣一棵博弈樹(也被稱為博弈的拓展形式 extended form)

  從上往下,首先由甲選擇藏起來的硬幣是 10 還是 20,再由乙猜測硬幣,最後的收益,前一個是甲的收益,後一個是乙的收益。

  但是這棵樹是有問題的:乙在決策的時候,其實不知道甲到底藏的是 10 還是 20,所以其實正確的博弈樹是這樣的:

  連上虛線的兩個點,表示在同一資訊集中(掌握了同樣多的資訊),這時候,我們可以把它等價地畫成支付矩陣(也被稱為博弈的標準形式或戰略形式 strategic form)

  拓展形式的博弈樹,通常用於表示博弈策略選擇有前後順序的情況(我們稱為 sequential game),而戰略形式的支付矩陣,則表示博弈策略選擇是同時進行的情況(我們稱為 simultaneous game)。在這個問題中,由於乙猜測時不知道甲藏的硬幣是多少,可以認為乙是在甲藏硬幣的同時進行猜測,因而可以寫成戰略形式的支付矩陣。

  接下來我們來求解這個博弈的解,這裡就是它的納什均衡。

  納什均衡的定義是,在均衡下,參與者不會單方面地改變自己的選擇。

  首先考察純策略納什均衡(雙方都只用一種策略),由於格子少, 所以我們可以逐格按照定義進行檢查,當然也可以用經典的劃線法:給定甲的策略,選出乙的最佳選擇,再給定乙的策略,選出甲的最佳選擇,如下圖:

  我們可以說,這時候不存在純策略納什均衡,任何一種結果下,都會有一方覺得自己本應有更好的選擇。

  我們轉而尋求混合策略納什均衡,就是雙方混合採取多種策略。

  混合策略納什均衡的求解辦法,如題主所做的那種是可以的,但這比較複雜,我們通常採用的是利用對手無差異性。

  對手無差異性的含義是,如果甲要混合選擇 10 和 20,那乙無論選擇 10 還是選擇 20,得到的收益應該是一樣的。否則,如果甲選擇混合策略之後,乙發現自己選擇 10 的收益更高,那麼甲應當預見到這一點,並轉而選擇 20,這說明甲有更好的策略;反之乙如果發現選擇 20 的收益更高也是同理。

  這樣一來,我們假定甲以 p 的機率選擇 10,1-p 的機率選擇 20,那麼由對手無差異性

  10p-15(1-p)=-15p+20(1-p)

  25p-15=20-35p

  解得 p=35/60=7/12

  同理可得乙以 q=7/12 的機率選擇 10,5/12 的機率選擇 20。計算結果和題主是一樣的~

  以上解答了題主提到的 Vladimir Arnold 提出的問題。

  接下來解答題主的問題。

  1. 此解法有一個假設,即『在遊戲開始後策略不改變』。在該假設下,此解法是否正確?

  答:並不需要這個假設,因為原題說的是甲乙雙方進行一次遊戲的情況,儘管這其中涉及機率,但不代表這個遊戲要進行很多次來統計頻率,而是參與人每一輪都根據機率進行選擇。

  題主想說的,其實是遊戲進行多輪的狀況,這種狀況被稱為重複博弈(repeated game)。

  重複博弈下,策略就更像是一種戰略,而不是戰術,它代表了玩家在每一輪如何選擇的一整套規則,這個規則可以是“根據上一回合的結果決定下一回合的選擇”,也可以是“在遊戲開始後策略不改變”。

  我用最經典的囚徒困境博弈來做個說明。

  囚徒困境進行一輪的時候,囚犯的策略是合作(C)或者背叛(D);

  囚徒困境重複進行時,囚徒的策略可以是永遠合作 ALLC,永遠背叛 ALLD,以牙還牙 Tit For Tat,冷酷策略 Grim Trigger 等等,這些策略是單輪博弈的策略(合作或者背叛)的有機組合。這裡“永遠合作”或者“永遠背叛”就是“在遊戲開始後策略不改變”的策略的例子,而“以牙還牙”和“冷酷策略”都是“根據上一回合的結果決定下一回合的選擇”的例子。

  2. 是否有一種『根據上一回合的結果決定下一回合的選擇』的策略,使得甲或者乙收益更多?如果有,是什麼?如果沒有,如何證明?

  答:這時候我們就要進一步劃分重複博弈。

  1)如果重複博弈進行有限輪,在最後一輪,雙方一定會選擇納什均衡。

  如果有多個納什均衡,而且各個納什均衡的收益不同,那麼可以透過威脅對方說,我會在最後一輪強制選擇較差的納什均衡,來逼迫對方在最後一輪之前選擇非納什均衡。

  然而,這道題中只有一個納什均衡(就是混合策略納什均衡),因此最後一輪雙方無論如何都只有這一種選擇,倒推到倒數第二輪,則雙方都無法威脅對方,那麼倒數第二輪也只能都選擇納什均衡,依此類推,我們就得到了一個定理:

  定理:若單輪博弈只有唯一納什均衡,則有限重複博弈中每一輪博弈雙方均選擇該納什均衡。

  這個定理用在囚徒困境上,就可以知道有限次囚徒困境中,雙方都永遠會選擇背叛。

  2)如果重複博弈進行無限輪,這時候就沒有“最後一輪”了,我們就不能從最後一輪來進行倒推了。這時候,我們就只好利用另一個定理(證明略),即無名氏定理(Folk Theorem)。

  在介紹定理之前,先來了解一下折現率(discount rate)的概念。簡單地說,就是沒到手的錢沒有已經到手的錢值錢,在今天看未來的收益,要打個折扣。這個也很好理解,比如我今天給你 100 塊和明年的今天給你 100 塊,肯定是今天拿到手合算,因為我可以拿去投資啊,最起碼可以多拿一年的利息,所以明年的 100 塊錢,在今天就要少一些,我們用折現率δ

  如果我們進行無限輪博弈,最後我們會得到一個總折現收益,這個總折現收益等價於每年固定拿一定量的錢的總折現收益,我們稱為平均折現收益。比如說,如果我今年拿 2 塊,從明年開始每年拿 1 塊,折現率是 1/2,那麼我的總折現收益是

  2+1/2+(1/2)2+...=3

  平均折現收益假設是 x,那麼有

  x+x*(1/2)+x*(1/2)2+...=3

  解得 x=3/2

  也就是說,“我今年拿 2 塊,從明年開始每年拿 1 塊,折現率是 1/2”,就相當於我每年拿 3/2 塊,折現率是 1/2。

  好了,我們回到無名氏定理。無名氏定理說的是,對於雙方高於其最小最大值(minimax)的收益,在折現率充分高的情況下,存在策略,使得雙方的平均折現收益達到該值。

  在零和博弈中(比如本題),最小最大值的收益就是納什均衡下的收益。而零和遊戲意味著提升一方的收益必然降低另一方收益,所以無法用無名氏定理證明存在這樣的策略。(= =!一個大寫的懵逼)

  (然而證明不存在的定理我們沒學過……)

  3. 此題讓我聯想到 Evolutionarily Stable Strategy(雖然只有兩個人),現實中(如生物、經濟等領域)是否有符合此題模型的現象?

  我還是想說這個問題本身只是一輪,不是多輪……所以本身並沒有 Evolutionary 的成分……不過如果放在演化博弈的視角下,這確實是一個 ESS。

版權宣告:本文源自 網路, 於,由 楠木軒 整理釋出,共 3200 字。

轉載請註明: 知乎日報:猜對我手裡有幾枚硬幣我就把它們都給你 - 楠木軒