這是 coursera上 Game Theory 的筆記
What’s Game Theory
Game Theory (賽局理論、博弈論) 的 Game 並不是我們常說的 Game (遊戲)，而是一門關注 self-interested 的人/物之間策略性的互動。是經濟學中重要的學科(事實上這門課也是被歸在經濟學下面)，另外也被廣泛的被應用在電腦科學、政治學…等地方。
TCP Backoff Game
這裡用一個簡單的例子來解釋 Game 是什麼。
"TCP" 是一種網路傳輸協議，在這裡我們不用去理解它實際上在做什麼(事實上這下去又是一門課了:P)。總之我們在網路上傳輸資料時，規定了一個方式，如果 ：
- 雙方都遵守協議，那雙方都會感受到 1ms 的延遲
- 如果有一方不遵守，則不遵守的那方會感受到 0ms 的延遲。而遵守的那方會感受到 4ms 的延遲
- 如果雙方都不遵守，則雙方都會感受到 4ms 的延遲
在這裡可以探討一些問題，如：使用網路的人需要採取什麼策略(遵守 TCP 與否)、對於設計者而言他應該怎麼預期大家的選擇...。這些問題就是 Game Theory 在探討的。
Defining “Game”
總歸來講，一個 Game 由三樣東西所組成：
- Player：做出決策的人
- Action：採取的行動
- Payoff：取得的報酬
在前面提到的 TCP Game 來說，Player 就是使用網路的人、Action 就是遵守或不遵守規範、Payoff 則是得到的網路延遲。
Normal Form Game
又稱為 Strategic Form、Matrix Form。用來正規化賽局的一種描述方式，把上面所提到的元素用正規的描述的話就成為：
我數學不太好，大致來講就是就是可以理解成有 1~n 這些 player。而他們的action 則用 a 來代表，A 為所有可以採取的行動。payoff function 就是每個 player 對於每個 a 的行動所應該要獲得的回報。
恩…，有看沒有懂。
為什麼他又會被叫做 Matrix Form 呢？因為上面這些東西可以用矩陣來表示，當 player 只有兩個時，我們就可以畫出便於理解，以前面所提到的 TCP Game 為例子：
這個 Game 裡面有
- Player: player1, player2
- Action: Correctly TCP, Defective
- Payoff: 1,2 都採取C時 都會得到 -1 的延遲、1採取D 2採取C 時 1會得到 0 的延遲，而2會得到 -4 的延遲
Week1 最重要的應該就是看懂這張圖，分析都會由這張圖衍伸出來。
順帶一提，這個狀況就是有名的 Prisoner's Dilemma (囚徒困境)。
除了 Normal Form 外，Extensive Form 的分析再多考慮了時間推移，棋類、撲克牌之類的屬於這種，在後續章節會再介紹。
Nash Equilibrium
Nash Equilibrium (奈許均衡) 為在「賽局中沒有任何一方，可以藉由改變行為而取得更多獲益」的狀態。
Keynes Beauty Contest Game
有一個比賽讓所有參賽者選定 1~100 裡面的整數，選到最接近平均值 2/3 獲得勝利，如果有2個以上的人選到結果，則隨機選出一個獲勝者。
而在這個賽局裡，我們可以得出這個賽局的 Nash Equilibrium 為所有的人都選擇1。因為只有所有人都選擇 1 時，沒有人能夠藉由改變選擇來獲取更多利益。
Best Response
當已知所有人的行動後，所做出會讓你得到最多報酬的行動就稱為 Best Response。而用這個概念來說，奈許均衡就是所有人都做出 Best Response 的時候。
Dominant Strategies
但是所謂的 Best Response 或是 Nash Equilibrium 都是因為我們是旁觀者，才看的出來，對於參與者而言並不知道其他人的行為。所以參與者應該是要採取策略(strategy)，在這邊的策略就是選擇一個行為(稱之為 pure strategy)。當這個策略相較於其他策略會更佔優勢則稱之為 dominant strategy。
而 dominant strategy 又分為 strictly dominates 和 very weakly dominates。差別在於前者在任何狀況都可以獲得最佳收益，後者是在任何狀況都不會獲得比較差的收益。(「大於」其他策略和「大於等於」其他策略收益的差別)
以上圖來說，對於 player 1 而言 選擇 c 就是所謂的 strictly dominant strategy，因為無論對手如何選擇，他的收益都比選擇 abd 還高。對 player 2 來說，選擇 y 是 very weakly dominant strategy，因為當 1 選擇 a 時，x,y 的收益相同。
Pareto Optimality
前面的分析都是從 player 的角度出發，我們只關心做出什麼選擇對單一的 player 較為有利。這邊則是改成關心全體的產出 (outcome)。
假設在某些狀況下的產出分別為 o、o′，當有 agent 相對於 o′ 更滿意 o 的話，我們稱 o Pareto-dominates o′。當一個 o* 不能被任何的 o 所 Pareto-dominates，我們稱這個 o* 為 Pareto-optimal。而每個 game 都至少存在一個 Pareto-optimal。