# 賽局論補充包 Game Theory Big Pack II.
閱覽此補充包以將賽局理論安裝至你的系統。
第二份補充包：零和遊戲

Published on Oct XX, 2024 by Chen YanLong.

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


Photo by <a href="https://unsplash.com/@mparzuchowski?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash">Michał Parzuchowski</a> on <a href="https://unsplash.com/photos/green-poker-chips-on-table-pvIVPYGM16o?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash">Unsplash</a>

## Table of contents
* Intro.
* Stategic form
* Security level
* Minimax and Maximin
* Summary
* Ref.

## Intro.
經歷了五個月，已經從即將畢業的大五生，變成了已經畢業的社會新鮮失業人口，想說是時候來更新賽局知識了，於是這是第二份關於零和賽局的補充包。零和遊戲指的是一方的收益等於另一方的損失，也就是你的錢就是我的錢，我的錢還是我的錢。毫無疑問，他是一種 strickly competitive game。過年常玩的射龍門就是一種零和遊戲，所有人贏的錢等於所有人輸的錢，沒有多也沒有少，順帶一提，不要玩射龍門，太邪門了我每次都撞柱。

對了，如果你還沒看過上一篇，建議你讀讀 [賽局論補充包 Game Theory Big Pack I.](https://medium.com/@chen_yanlong/%E8%B3%BD%E5%B1%80%E8%AB%96%E8%A3%9C%E5%85%85%E5%8C%85-game-theory-big-pack-i-0b8118133b67)。我們會講到裡面 value 的概念。

## Strategic form
簡單說明一下零和遊戲的策略形式，我們只介紹兩個人的零和遊戲。

因為在零和遊戲當中，你的損失就是我的收益，所以寫成寫成策略形式大概會長程下面這個樣子，兩個人 payoff 的總和要等於 0。


既然我們知道兩個人 payoff 的總和要等於 0，那麼多寫一個數字就顯得雜亂也不好分析，所以我們只寫一方的 payoff，有就是以下的形式：


## Security Level
Security Level 中文翻作安全水準，意思是“無論對方出什麼招，我可以保證自己至少可以獲得多少”。這是一個很悲觀的想法，因為你要一直考慮對手對你的最大威脅，然後選出這些威脅之中你能獲得的最好結果。

比如說 A 股票最多跌 50%，B 股票最多跌 30%，C 股票最多跌 10%，一定要買一支的話，C 股票的跌 10% 就是我的安全水準。我們不管裡面哪一支最多可以漲到哪，我們要以最悲觀的想法去分析，在這些跌到最慘的股票當中我們可以安全到什麼程度。


在上圖當中我標出了 player1 的 payoff，我們要找出安全水準是多少。當player1 出 s1 的時候，player2 能給出的最大威脅是 t2，也就是 0。player1 出 s2 的時候是 t3，也就是 2。出 s3 的時候是 1。那在 {0, 2, 1} 當中最大的是 2。所以 player1 的安全水準是 2。

用同樣的方法，我們可以找出 player2 的安全水準是 3。如果你算出 1 的話，確認一下我們的數字只表示 player1 的 payoff，所以在你找 player1 能給的最大威脅時，要以 player2 的角度來找最大值。那如果你算出其他數字的話，應該是我說錯了。

## Minimax and Maximin

我們要介紹的概念是由 Von Neumman 在 1928 年所提出的 Minimax Theorem，用來解零和賽局的均衡。但這節我們著重於 pure strategy。

在上一個小節中，我們算了兩個 player 的安全水準。回想一下 player1 的安全水準，我們在最小值中找到最大值：

$$\underline{m} \equiv \max_s\min_t\pi(s,t)$$

我們稱這個 $\underline{m}$ 為 maximin。
而另一方面，player2 的安全水準是在最大值中找最小值：

$$\bar{m} \equiv \min_t\max_s\pi(s,t)$$

我們稱 $\bar{m}$ 為 minimax。

那為什麼 minimax 是 $\bar{m}$，而 maximin 是 $\underline{m}$，原因是 $minimax \geq maximin$，也就是 $\bar{m} \geq \underline{m}$。原因很簡單，我們想像 $\bar{m}$ 在第 j 行，$\underline{m}$ 在第 i 列。$\bar{m}$ 是 j 行中最大的，所以他大於 $m_{ij}$，$\underline{m}$ 是 i 行中最小的，所以他小於 $m_{ij}$。所以 $\bar{m}>m_{ij}>\underline{m}$。


我們來想一想 minimax 跟 maximin 代表的是什麼意思。maximin 對 player1 來說就是一個 “我保證賽局的結果不差於 maximin”。反過來 player2 也可以 “保證賽局的結果不差於 minimax”。是不是很耳熟，當兩個人都能保證對他來說的結果不差於 v，那 v 就是這場賽局的 value。所以當 maximin 等於 minimax 的時後，那個值就是 value，而 value 就是 saddle point。


### Minimax Theorem
在這裡簡單介紹 Von Neumann 的 Minimax Theorem，因為我會碰到繁瑣的代數運算（並且需要知道混合策略的運算邏輯），所以我就直接講結論了。

如果我們允許玩家使用混合策略的話，Maximin 和 Minimax 會趨於一致。

也就是在混合策略底下，絕對會有 value。
結束這回合。

## Summary
從一開始我們介紹了 Zero-Sum game 的策略形式，然後我們談到了安全水準，表示一個玩家在不管對手出什麼的情況下至少可以拿到多少。接著結合 Maximin 和 Minimax 的概念，提到 value 在什麼時候會存在，最後簡單介紹了 Von Neumann 在 1928 年提出的 Minimax Theorem，闡述在混合策略中的結果。

這篇比我想像中的短很多很多，因為我一開始沒有注意到這部分的大部分都是數學證明。不過我相信想知道賽局的人的大部分人應該不會想知道太艱澀的數學證明，所以我就直接講結論啦。

下一個補充包：重複賽局。

## 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