February 7, 2015

Welcome to Game Theory Week 1 - 2

本文為 MOOC 學習筆記。

課程為 University of Tokyo(東京大學) 在 Coursera 開的 Welcome to Game Theory

相關連結:


目錄


Week 1

Game Theory 跟電玩沒有直接關係。

1. Game 的定義

符合下列規則的都可以被當作 Game:

  • Individuals try to do their best against others
  • Under a certain set of rules.

在遊戲理論理,人們追求最好的“策略”,怎麼做才能達成想要的目的(取得最大利益、取得雙贏、取得最小損失等等),可運用在 政治學、經濟學、生物學、心理學等等 眾多領域。

  • 在簡單的 Game 中:人們使用 “Ad-hoc” approach, use intuituion to get the answer.
  • 在複雜的 Game 中:What is best for you depends on what others do

2. Game 的例子

所有玩家都想做出對自己最有利益的行為,但是要怎麼量化這個最有利益的動作?

一個簡單的想法是:”Maximizing Payoff”。將所有 Payoff 都給予一個數值,最有利益的行為就是想辦法取得最高的 Payoff 數值。

以兩個賭博遊戲為例子,滾珠轉輪盤以及莊家撲克牌:

轉輪盤:玩家與機器的對賭,輪盤上每一個數字出現的機率都是固定的(或是可被計算出來的),我們可以用簡單的期望值及機率建立數學模型,進而擬定最佳的戰術,取得最大利益。

撲克牌:玩家與玩家間的對賭,由於不確定對手可能採取的行為,我必須先”思考”對手可能會出什麼戰術,再來決定自己的戰術。但我必須考慮到,對手出戰術之前也會先思考我可能出的戰術,而他在思考我出什麼戰術時他心裡的那個我也在思考他可能會出什麼戰術..


We need to go deeper!

3. Nash Equilibrium

如果某情況下無一參與者可以通過獨自行動增加自己利益,則此狀態被稱為納許均衡點

- John Nash

John Nash ,著名的美國數學家,其一生充滿了戲劇定,後來被改編成電影美麗境界

Nash discovered that every social problem has a “stable point” where All individuals are doing their best against others. And that is the famous Nash Equilibrium.

如果某情況下無一參與者可以通過獨自行動增加自己利益,則此狀態被稱為納許均衡點

4. Game Theory 簡單數學模型

- 定義

  • Playersi - 玩家,i = 1,2,…,N。
  • ai - 每個玩家的戰術 Strategy
  • Ai - 每個玩家的戰術集合 Strategy set
  • gi(a1,a2,…,an) - 每個玩家的 Payoff,括號裡面為當下每個玩家的戰術,因為 Payoff 不僅受自己戰術影響,也受其他所有參與者戰術影響。

- 納許均衡點

納許均衡點時,All individuals are doing their best against others

  • 假設 Player 1 可以達到納許均衡點的 Strategy 是 a1#
  • 假設 Player 2 可以達到納許均衡點的 Strategy 是 a2#

那麼在納許均衡點時,Player 1 的 payoff 可以表示為:g1(a1#,a2#)。

如果某情況下無一參與者可以通過獨自行動增加自己利益,則此狀態被稱為納許均衡點

g1(a1#,a2#) >= g1(a1,a2#) 成立。

5. 簡單的 Nash Equilibrium 範例:

假設從甲城鎮到乙城鎮有A、B兩條路,現在想蓋下第三條路C,看看會不會減少通勤時間

  • Players:從甲城鎮通勤到乙城鎮的市民
  • Strategy:走A路、走B路、走C路
  • Payoff:-(所需時間)。所需時間越短,對玩家越好,故取負的所需時間。

許多 social problem 都可以簡化成上述數學模型,

而遊戲理論想探討的就是:能不能用一個 General Solution 來分析這街問題

計算看看,蓋下第三條路之前,通勤時間的納許均衡點是多少;

計算看看,蓋下第三條路之後,通勤時間的納許均衡點又是多少;

如果蓋下第三條路後,通勤時間的納許均衡點變少了,表示有蓋的價值。

6. Hotelling’s Location Game

請參閱維基百科的 Hotelling’s law

直接看這個影片:
Why do competitors open their stores next to one another? - Jac de Haan by TED-Ed。

這個理論也可以用來間接解釋產業聚集理論(Industrial Agglomeration Theory),不過產業聚集的成因有很多,location 只是其中一個因素。


Week 2

2-1 Nash equilibrium and the Prisoner’s Dilemma

回憶 Prisoner’s Dilemma 的表格:

嫌犯A / 嫌犯B 合作 背叛
合作 -1,-1 -15,0
背叛 0,-15 -10,-10

如果以嫌犯 B 的角度來看
- 嫌犯 A 選擇合作,嫌犯 B 選擇背叛 => 嫌犯 B 可獲得較輕的懲罰(由表格左上變成表格右上)
- 嫌犯 A 選擇背叛,嫌犯 B 也選擇背叛 => 嫌犯 B 也可獲得較輕的懲罰(由表格左下變成表格右下)

=> 不管嫌犯 A 合作或背叛,嫌犯 B “背叛”都能使自己得到較輕的懲罰
也就是說,Nash 的結果傾向 Individual rationality(表格右下角)

但若以兩個嫌犯“整體”來看,兩個人都“合作” 才是最佳決定(表格左上角)

這個例子順便也證明了,Group rationality != Individual rationality,group 跟 indiviual 的關係之後章節會更深入講解。

2-2 Coordination game and self-fulfilling prophecy

一個社會裡面可以有很多個 Nash equilibrium,而某個 Nash equilibrium 可能優於另一個 Nash equilibrium。

Once the society is trapped in a Nash equilibrium, it is difficult to get out,because everybody has to move out the Nash equilibrium simultaneously。

也就是所謂的歷史共業,e.g. HD DVD, Blu-ray, QWERTY 鍵盤等等。

A format that happend sto obtain a large enough market shares eventually becomes the de facto standard。

2-3 Market competition

簡單介紹 古諾競爭(Cournot competition)。

2-4 Why do people come to play Nash equilibrium?

我們知道 Nash equilibrium = Mutual best reply。

但是 How do people find out such situation?

  • Rational reasoning leads to Nash (e.g. prisoner’s dilemma)
  • Pre-play communication
  • Trial-and-error adjustment

Rationality + Correct beliefs => Nash equilibrium。

接下來證明:An agreement cannot be fulfilled, if it is NOT a Nash Equilibrium

舉例來說,回想剛剛的 prisoner’s dilemma,嫌犯 A 和 B 在偵訊前,先達成一個 agreement,約定兩人皆不要背叛對方。

以兩個嫌犯“整體”來看,兩個人都“合作” 才是最佳決定:

嫌犯A / 嫌犯B 合作 背叛
合作 -1,-1 -15,0
背叛 0,-15 -10,-10

雖然已經做好約定了,但兩個嫌犯任一人都可以藉由背叛對方減輕自己的刑責,因此嫌犯彼此很可能不會遵守約定,因為這個約定並 不是 Nash Equilibrium

用一些實驗來證明 Rational 的人類為了贏取最大利益,會觀察遊戲規則、嘗試錯誤,並逐漸修正自己的策略。

當所有人都這樣做時,最終結果會迎向 Nash Equilibrium。

2-7 Stylized facts and Nash equilibrium

在某些情況下,people might NOT play Nash equilibrium。

只要有人可以藉由 deviate 來增加自己的利益,他就會選擇 deviate,這個行為叫做 dynamic adjustment。

這個過程會一直持續,直到沒有人可以藉由 deviate 來增加自己的利益,也就是所謂的收斂 Conveges,而這剛好也就是 Nash equilibrium 的定義。

但是這個 dynamic adjustment 可能持續很長一段時間,一直都無法達到收斂 Conveges 的情形。

If a mode of behavior is not a Nash equilibrium, sooner or later someone finds out that she/he can be better off by changing her/his behavior. Hence this mode fails to be stable and therefore it cannot be a stylized fact. In other words, a stylized fact is likely to be a Nash equilibrium.

Stylized facts 也可以用 Nash equilibrium 來解釋:
社會約定成俗某些規則,當有人發現一些小聰明可以藉由不遵守規則來增進自己的利益時,會有更多人去模仿,導致某些世俗規則崩壞,此行為會不停重複,直到達到 Nash equilibrium。

然而,後面會介紹說 Nash equilibrium 其實是一種追求私利的行為,因此現實生活中若只靠 Nash equilibrium,社會將會陷入混沌,固現實社會中有法律、道德等來輔助。

2-8 Make yourself unpredictable: Mixed strategy equilibrium

這段課程用剪刀石頭布的遊戲證明 Game theory 中的 Mixed strategy equilibrium

兩個人玩剪刀時頭布,如果對手出剪刀、石頭跟布的機率都相等的話,那麼我不管出剪刀、石頭或布的 payoff 期望值都為 0,對我來說是如此,對對方來說也是如此,故此情形為 mutual reply。

也就是說剪刀石頭布遊戲有 Mixed strategy equilibrium。

2-9 Sports games and game theory

這段課程拿一段 1995~2000 間的足球 PK 數據,用 Game Theory 來預測球員踢向球門左方或右方的機率,預測結果與實際機率相互符合。

2-10 Nash equilibrium exists in all games

Nash discovered that any game has a Nash equilibrium (possibly in mixed strategies), if

  • There are finitely many players
  • Each player has finitely many strategies

條件一幾乎一定成立。
條件二在某些遊戲中不會成立,但我們可以藉由從無限的策略集合中 sample 出有限的策略集合,進而用 Nash equilibrium 做”推測”。

So, practically, Nash equilibrium exists in all games。

課程最後用 Matching pennies 的機率圖與咖啡表面的 Vortex 做比較,雖然有點牽強,不過整體而言蠻有趣的。