# 賽局論補充包 Game Theory Big Pack I.
閱覽此補充包以將賽局理論安裝至你的系統。
第一份補充包：每本書都會有的，後半段不太一樣。

Published on May XX, 2024 by Chen YanLong.

###### tags: `game theory`
---


Photo by <a href="https://unsplash.com/@rihok?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash">Riho Kroll</a> on <a href="https://unsplash.com/photos/closeup-photo-of-dices-m4sGYaHYN5o?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash">Unsplash</a>

## Table of contents
* Intro.
* Basics
* Nash Equilibrium
* Win-or-Lose Game
* Value
* Strictly Competitve Gam
* Summary
* Ref.

---

# Intro.
待在經濟系五年下來，其實花了超過一半的時間在修系外的課，不過唯有一堂課我可以一修再修，那就是賽局論（Game Theory）。一個很重要的原因是我認為賽局是無論在何處都會用到的，當然一整個經濟學本身也是，不過賽局更令人著迷一點，而且也在我所要繼續前往的道路上有很大的需要。所以接下來會以一個快要畢業的經濟系大學生的角度來跟大家介紹一下我所知道的賽局論，以不那麼數學、也不那麼嚴謹的方式（希望）。途中若有任何我講錯或你不認同的地方。請直接在留言區吐槽不要客氣，你的吐槽是我前進的動力。

---

# Basics
## History
講到賽局理論，我相信大家唯一聽過的名字應該是 Nash 均衡的 Nash，不過在 John von Neumann (唸法是 noimen) 發表論文 《On the Theory of Games of Strategy》的時候他也才剛出生，事實上在柏拉圖的文章中就已經出現賽局的概念。賽局理論在 1944 年時由 von Neumann 和 Oskar Morgenstern 提出了數學形式，但在當時論文提出的概念只適用在特定的條件底下（零和賽局），而後在 1950 年 John Nash 才提出 Nash Equilibrium ，且證明了更普遍的賽局中皆存在納許均衡。

## Game
何謂賽局，賽局的組成要素是什麼。
剪刀石頭布其實是一個很難的賽局，不過因為大家都知道，所以我用這個來解釋。
首先要猜拳，非得要有兩個人來猜，這兩個人稱為參賽者（players），參賽者可以出剪刀、石頭、布，這稱為行動（actions），接著行動會造成贏或輸的結果（outcomes），結果會帶有報酬（payoffs），在猜拳中的報酬可能是成就感，可能是贏了可以偷吃你的冰淇淋一口，可能是明天你要代替我去打老師的頭一下，不知道，但就是這件事在你心中的份量有多少。

所以我們大致上可以將賽局分成幾個元素：
* players
* actions
* outcomes
* payoffs

## Assumptions
經濟學最大的假設就是所有人都是理性的，而在賽局中也毫不例外，正所謂不要跟瘋子玩賽局。瘋子不可理喻，不在乎自己獲得多少的人是不能拿來討論的，這其實也是賽局一個很大的問題，在某種程度來說我們都是瘋子，因為我們都不是完全理性的，也就是說，很多時候我們不知道結果對我們來說的效用（payoffs）是多少。我不知道我吃水餃會比較開心還是吃烏龍麵會比較開心，ううん，ダメです。

賽局假設的是所有參賽者都要想盡一切辦法最大化自己的效益，換句話說，每個人都要知道怎麼「算」自己的效用。對不起，我們只跟聰明人玩賽局。

## Type
賽局有好多好多種 Type（所以應該很好追吧，沒）。
1. 合作 v.s. 非合作

這個應該很淺顯易懂，就是兩個人是否可以串通。大家所熟知的囚犯困境（不要在只會囚犯困境了）如果是合作賽局的話，整個結論都會大不相同。

2. 同步 v.s. 非同步

這個應該也很淺顯，就是兩個參賽者做決定是同時做決定還是不同時。

3. 完美 v.s 不完美（perfect v.s. imperfect）

這個應該也很，不淺顯。這大概是我聽過那麼多次之後，每一次都還要回去確認到底是什麼意思的賽局。這裡的完不完美指的是訊息，不完美賽局指的是後面行動的人並不知道前面行動的人做了什麼行動。

4. 完全 v.s. 不完全（complete v.s. imcomplete）

完全不完全指的也是訊息，這下你知道為什麼我每次都要再確認一次了。
不完全信息指的是我不知道對手的 type 是什麼，我不知道他做這個決定對他來講的 payoff 是多少。我不知道閃我大燈的計程車司機是不是土匪，所以我很難決定我要轉身扁他還是不要，大概是這種感覺。

請別太擔心這些分類，事實上當你看到一個賽局的時候一瞬間就會理解了，無須太在意他的形容詞。

## Form
當我們想要系統化的研究一個賽局的時候，我們比需把文字傳達的故事內容轉換成能夠分析的形式，以下提供兩種形式。

1. Normal form

Normal form 是以矩陣的方式展示每個參賽者的策略以及其對應到的效益，這是一個沒辦法展示出行動先後順序的形式。
以上是 chicken game 的 normal form。左側的Ｃ、Ｄ代表的是 player 1 的策略，上方的則是 player 2 的。先看 Ｄ／Ｃ 這格中的 (8, 2)，他代表的是當１玩Ｄ且２玩Ｃ時，１會獲得８，且２會獲得２。

2. Extensive form

Extensive form 以樹狀圖的方式表示，可以表示出行動的先後順序。

這個應該不難理解，１先決定要出Ｃ或Ｄ，而後２才做決定。
而在 Extensive form 中有時候會看到用虛線連在一起。
以上表示的是在虛線連起來的兩個點中，2並不知道自己在上面那個點還是下面這個點，也就是說，他並不知道 1 做了什麼行動。也就相當於1、2是同時做決定的。

需要注意，Normal form 和 Extensive form 並沒有一對一的對應，端看你的需求而使用不同的形式。

---

# Nash Equilibrium

不免俗的要談論一下納許均衡 Nash Equilibrium。
定義一下 NE：

每個策略都是其對手策略的最佳回覆的一組策略對。

白話一點來說，當我看到你出策略 a 時，我應對 a 最好的方式是出策略 b，而剛好對你來說，出策略 a 是你應對 b 的最好策略。那（a, b）就是一個 NE 。有點像是我們在策略上達成了一個共識，使得對雙方來說，相互都做到了他能做的最好策略。


在拿這個賽局出來說明。當２使出Ｃ這個策略時，對１來說，玩Ｃ可以得到６，玩Ｄ可以得到８。所以我的最佳回應是出Ｄ。


而當１玩Ｄ這個策略時，對２來說玩Ｃ會得２，玩Ｄ會得０。所以最佳回應是玩Ｃ。在這裡兩個玩家就得到一個策略上的共識，也就是上面說的，１Ｄ對付２Ｃ最好，而２Ｃ對付１Ｄ也是最好，於是就產生了一個均衡，也就是ＮＥ。

用同樣的方式，讀者可以自己嘗試在這裡面找到第二個ＮＥ。

以上的ＮＥ我們稱為 純策略 pure strategy NE。也就是這個策略 100% 只玩Ｃ或Ｄ，這裡要介紹 混合策略 mixed strategy NE，也就是我有一定的機率玩Ｃ，另外一個機率玩Ｄ。

在這裡我不打算解釋如何解出 mixed strategy，只提出這個概念。在這個chicken game 中 （（1/2, 1/2), (1/2, 1/2)）是一個 mixed strategy NE，意思是１有 1/2 的機率玩Ｃ或Ｄ，２也同樣有 1/2 的機率玩Ｃ或Ｄ，兩個策略對彼此來說都是最佳回應。

---

# Win-or-Lose Game
在我們思考那些 payoff 是怎麼算出來的時候，我們不妨先把賽局再更簡化一點，只有贏或輸的賽局：Win-or-Lose Game。

這裡我們定義這個賽局
* 參賽者有兩位：Alan、Blan
* 規則：Alan 丟硬幣，Blan 猜硬幣，猜中的話 Alan 輸，否則 Alan 贏。
* W 代表 Alan 贏，Ｌ代表 Alan 輸。

以上的這個圖少了一個東西，所以是錯的。如果有仔細看前面的讀者會知道我們少了一條虛線。不過先不論那條虛線，這樣的賽局是什麼意思。意思是當 Blan 做決定時，他已經知道 Alan 丟的硬幣是朝上還是朝下。有可能 Blan 是全知全能的神，也有可能 Alan 笨到沒有把硬幣蓋好被偷看到了。

總之，這樣的賽局應該很容易解，我們會使用到一個稱為 backward induction 的技巧，也就是從後面來（？）。

Blan 在做決定是，肯定要讓自己是贏的，也就是在這裡的Ｌ。所以當 Blan 在上半部的節點時，他應該要選擇Ｈ。而在下半部節點的 Blan 應該要選擇Ｔ。那回推到最左邊節點的 Alan 做選擇時，他知道自己不管丟了Ｈ或Ｔ，Blan在下一階段都會贏，所以他是輸定了。


當然 Alan 不是笨蛋，他當然要蓋好自己的硬幣，所以上面這個才是正確的圖，也就是增加了 information set (那條虛線)。Blan 當然不會知道 Alan 丟出什麼硬幣，換言之就是不知道自己正處在上面的節點還是下面的節點。

我們可以把上面的 Extensive Form 轉換成 Normal Form:


讀者可以用先前的方式找看看有沒有 pure strategy NE。

你可能會發現，不管怎麼樣的沒有一個互為最佳回應的最佳策略，於是你可能會想那應該有混合策略均衡吧。


沒錯！不過會是多少呢，其實回到遊戲本身，拋開這些系統化的表格，你可能也會知道答案就是猜一半一半吧。

---

# Value
我們再更深入解釋上面的 backward inductiuon。

## Subgame

子賽局，表示的是一個節點以及其後繼的所有部分，而這個初始節點不能被包在information set 中，也就是下圖中 G3 中下一個節點不能算是一個子賽局的初始節點。照這樣的定義來說，Ｇ本身也是一個子賽局，而這整個賽局擁有４個子賽局。


## Winning strategy
必勝策略，意思是在這個子賽局當中，無論對方做什麼行動自己都能贏。
回想一下前面的 win-or-lose game（如下圖），這個賽局中有三個子賽局。我們定義 value，如果在子賽局Ｈ中 player 1 有必勝策略，那這個子賽局的 value 就是 Ｗ。

在底下這張圖中的子賽局Ｇ1，Blan 有必勝策略Ｈ，所以 v(G1)=L。


結著我們可以簡化這個賽局如下面所示。
也就是將子賽局 G1、G2 替換成 value。


接著就可以很清楚的知道 v(G)=L，也就是在賽局Ｇ中，Blan 有必勝策略。
我們可以得到一個結論，在一個完美訊息且有限的 win-or-lose 賽局中必定存在 value。

---

# Strictly Competitive game
## Chess
西洋棋，如果你不知道西洋棋的話，你得去玩，那是我最愛的棋盤遊戲。

結論是西洋棋有 value。
西洋棋不是 win-or-lose game，他存在著和局，除了 W、L 之外還有一個 D（Draw）。這裡要介紹另一種賽局，稱為 strictly competitive game，簡單來說，對手如果較喜歡一種結果，那你就較討厭那種結果，你們對結果的偏好是完全相反的。

在下圖中是 player1 跟 player2 的在賽局結果上的角力，越左邊的結果player1 越喜歡，相對的 player2 就越討厭。在這樣 strictly competitve 的賽局中，player1 如果可以保證自己可以做到結果不差於 v ，而 player2 也可以做到保證結局不差於 v，那這場賽局的 value 就是 v。


而已經證明了一件事，在完美訊息的賽局中，一定能夠保證 “player1 能夠保證結局落在Ｔ中” 或 “player2能夠保證結局落在非Ｔ中”。

這個證明了 win-or-lose game 中必定有 value。結果有 Ｗ 或 Ｌ，要嘛player1 能保證結局落在 Ｗ 中，或是 player2 能夠保證結局落在 L 中。

綜合以上，西洋棋的雙方會保證 value 存在。

## Saddle Point
以下是一個 strictly competitive game 的 normal form，其中數字對 player1 和 player2 來說偏好是完全相反的，player1 希望數字越大越好， player2 則相反。


利用上一小節的結論在， player1 在 2、5、2 中可以做保證結果不差於 5 的策略，而 player2 在 6、5、6 中可以做保證結果不差於 5 的 策略，於是這裡產生了一個 saddle point，意思是同時是一個方向上的最高點也同時是另一個方向的最低點。saddle point 的值就是 value 的概念。

saddle point, photo from wikipedia.

而在 strictly competitve game 中，這樣的點也同時是NE。

雖然 NE 跟 value 注重的概念不一樣，一個注重結果，一個注重策略組合，但是他們的結論是一樣的。

---

# Summary
第一包補充包。補充了一些賽局的基礎，歷史，形式，解賽局的方式。後面我們先進入沒有數字的世界，解釋單純只有輸贏的 win-or-lose game ，接著稍微用一點數字解釋了比 win-or-lose game 更大一點的 strictly competitive game，稍微串起了 NE 跟 value 的關係。

下一個補充包：零和賽局。

---

# Ref.
* [Game Theory](https://plato.stanford.edu/entries/game-theory/)
* [Playing for Real: A Text on Game Theory](https://www.bookfinder.com/search/?isbn=978-0195300574&submitBtn=Search&mode=isbn&st=sr&ac=qr)

✨Donate me if you like my article: 0xddAdE2642C66A757e3850d6E8F89B02F9c63f659