賽局論基礎
一句話解釋
在 zero-sum game 中，玩家選策略對抗；pure strategy 若有 saddle point 則遊戲已解，否則需要 mixed strategy。
Zero-Sum Game
基本設定
定義
Zero-sum game（零和賽局）：
- 兩個玩家：Row Player（R）和 Column Player（C）
- R 的收益 = C 的損失（總和為 0）
- 完全對抗性（adversarial）
Payoff Matrix（報酬矩陣）
$m \times n$ 矩陣 $A$：
- R 有 $m$ 個策略（選第 $i$ 列）
- C 有 $n$ 個策略（選第 $j$ 行）
- $A[i, j]$ = R 的收益（= C 的損失）
範例：剪刀石頭布（簡化版）
| 石頭 | 剪刀 | 布 | |
|---|---|---|---|
| 石頭 | 0 | 1 | -1 |
| 剪刀 | -1 | 0 | 1 |
| 布 | 1 | -1 | 0 |
正數 = R 贏，負數 = C 贏，0 = 平手
Pure Strategy（純策略）
確定性策略
定義
Pure strategy： 每次都選同一個動作（確定性）
- R 選第 $i$ 列
- C 選第 $j$ 行
Value of the Row (VR)
定義： R 選第 $i$ 列時的**最壞情況**收益（C 會最佳反應）
$$
VR_i = \min_j A[i, j]
$$
R 的最佳 pure strategy： 最大化最壞情況
$$
VR = \max_i \min_j A[i, j]
$$
稱為 **maxmin value**（最大最小值）。
Value of the Column (VC)
定義： C 選第 $j$ 行時的**最壞情況**損失（R 會最佳反應）
$$
VC_j = \max_i A[i, j]
$$
C 的最佳 pure strategy： 最小化最壞情況
$$
VC = \min_j \max_i A[i, j]
$$
稱為 **minmax value**（最小最大值）。
基本不等式
Theorem
對任何 zero-sum game：
$$
VR \leq VC
$$
即：maxmin $\leq$ minmax
證明： 對任意 $i, j$：
$$
\min_k A[i, k] \leq A[i, j] \leq \max_k A[k, j]
$$
取 $\max_i$ 和 $\min_j$：
$$
\max_i \min_k A[i, k] \leq \min_j \max_k A[k, j]
$$
💡 直覺：
- R 先選（被 C 看到）→ 收益最多 $VR$
- C 先選（被 R 看到）→ 損失最多 $VC$
- 後手有優勢 → $VR \leq VC$
Saddle Point（鞍點）
Pure Equilibrium
定義
Saddle point： 位置 $(i^*, j^*)$ 滿足：
$$
A[i^*, j^*] = \max_i \min_j A[i, j] = \min_j \max_i A[i, j]
$$
即：$VR = VC$
等價條件：
1. $A[i^*, j^*] = \max_i A[i, j^*]$ （該行最大）
2. $A[i^*, j^*] = \min_j A[i^*, j]$ （該列最小）
鞍點的意義
若遊戲有 saddle point：
- 純策略 Nash 均衡
- 雙方都沒有動機偏離
- 遊戲已「解決」（solved）
範例：有 Saddle Point 的遊戲
| C1 | C2 | C3 | Row Min | |
|---|---|---|---|---|
| R1 | 3 | 2 | 5 | **2** |
| R2 | 1 | 0 | 4 | 0 |
| R3 | -1 | 1 | 3 | -1 |
| Col Max | 3 | **2** | 5 |
- Row Min 最大：2（R1 列）
- Col Max 最小：2（C2 行）
- $VR = VC = 2$，位置 $(R1, C2)$ 是 saddle point
- 最優策略： R 選 R1，C 選 C2，遊戲值 = 2
沒有 Saddle Point
範例：剪刀石頭布（無 Saddle Point）
| 石頭 | 剪刀 | 布 | Row Min | |
|---|---|---|---|---|
| 石頭 | 0 | 1 | -1 | **-1** |
| 剪刀 | -1 | 0 | 1 | **-1** |
| 布 | 1 | -1 | 0 | **-1** |
| Col Max | **1** | **1** | **1** |
- $VR = \max(-1, -1, -1) = -1$
- $VC = \min(1, 1, 1) = 1$
- $VR < VC$ → 無 saddle point
- 需要 mixed strategy（隨機策略）！
為什麼需要 Mixed Strategy？
Pure Strategy 的限制
可預測性問題
如果總是用 pure strategy：
- 對手可以觀察/預測你的選擇
- 對手可以完美反制
- 你的期望收益 $\leq VR$（可能更糟）
例子：配對硬幣
Matching Pennies
| Head | Tail | |
|---|---|---|
| Head | 1 | -1 |
| Tail | -1 | 1 |
- R 想配對成功（收益 +1）
- C 想配對失敗（損失 -1）
- $VR = -1$，$VC = 1$ → 無 saddle point
Pure strategy 失敗：
- 若 R 總選 Head → C 選 Tail → R 收益 -1
- 若 R 總選 Tail → C 選 Head → R 收益 -1
解決： R 隨機選（50% Head, 50% Tail）
- C 無論選什麼，R 的期望收益 = 0
Mixed Strategy 的優勢
不可預測性：
- 對手無法完美反制
- 保證至少拿到遊戲的「真實價值」
下一篇： von Neumann Minimax Theorem、Yao’s Principle
VR 與 VC 的計算
演算法
計算 VR（maxmin）：
```
VR = -∞
for i = 1 to m:
row_min = min_j A[i, j]
VR = max(VR, row_min)
```
計算 VC（minmax）：
```
VC = +∞
for j = 1 to n:
col_max = max_i A[i, j]
VC = min(VC, col_max)
```
檢查 Saddle Point：
```
if VR == VC:
找到對應的 (i*, j*)
return "Saddle point at (i*, j*), value = VR"
else:
return "No saddle point, need mixed strategy"
```
複雜度
- 計算 VR：$O(mn)$
- 計算 VC：$O(mn)$
- 總時間：$O(mn)$
總結
賽局論基礎為隨機演算法分析提供框架：
- Zero-sum game： 完全對抗，總和為 0
- Payoff matrix： 描述所有策略組合的收益
- VR (maxmin) 與 VC (minmax)：
- $VR \leq VC$ 恆成立
- 若 $VR = VC$ → 有 saddle point
- Saddle point：
- Pure strategy 已足夠
- 遊戲已解決
- 無 saddle point：
- 需要 mixed strategy（隨機化）
- von Neumann Minimax Theorem 保證解存在
下一步： Mixed strategy、von Neumann 定理、Yao’s Principle
參考資料
- von Neumann & Morgenstern, Theory of Games and Economic Behavior
- Motwani & Raghavan, Randomized Algorithms, Chapter 2
- Osborne, An Introduction to Game Theory