一句話解釋

von Neumann Minimax Theorem 保證 mixed strategy 下遊戲有解；Yao’s Principle 用對偶性證明隨機演算法的 lower bound。

Mixed Strategy（混合策略）

隨機化策略

定義

Mixed strategy： 以機率分佈選擇 pure strategy

R 的 mixed strategy： 機率向量 $\mathbf{p} = (p_1, \dots, p_m)$ - $p_i \geq 0$，$\sum_i p_i = 1$ - 以機率 $p_i$ 選第 $i$ 列 C 的 mixed strategy： 機率向量 $\mathbf{q} = (q_1, \dots, q_n)$ - $q_j \geq 0$，$\sum_j q_j = 1$ - 以機率 $q_j$ 選第 $j$ 行

期望收益

給定 $\mathbf{p}$ 和 $\mathbf{q}$，R 的期望收益： $$ E(\mathbf{p}, \mathbf{q}) = \sum_{i=1}^m \sum_{j=1}^n p_i q_j A[i, j] = \mathbf{p}^T A \mathbf{q} $$

為什麼需要？

回顧：Matching Pennies

Head Tail
Head 1 -1
Tail -1 1

Pure strategy：$VR = -1$，$VC = 1$（無 saddle point）

Mixed strategy：

  • R 用 $\mathbf{p} = (1/2, 1/2)$（各 50%）
  • C 用 $\mathbf{q} = (1/2, 1/2)$

期望收益：

\[E = \frac{1}{2} \cdot \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot \frac{1}{2} \cdot (-1) + \frac{1}{2} \cdot \frac{1}{2} \cdot (-1) + \frac{1}{2} \cdot \frac{1}{2} \cdot 1 = 0\]

這是均衡！任何一方偏離都不會更好。

von Neumann Minimax Theorem

存在性定理

Minimax 值（Mixed Strategies）

R 的保證收益（maxmin）： $$ V_R^* = \max_{\mathbf{p}} \min_{\mathbf{q}} E(\mathbf{p}, \mathbf{q}) $$ R 選最優 $\mathbf{p}$，保證無論 C 如何反應，期望收益 $\geq V_R^*$。 C 的保證損失（minmax）： $$ V_C^* = \min_{\mathbf{q}} \max_{\mathbf{p}} E(\mathbf{p}, \mathbf{q}) $$ C 選最優 $\mathbf{q}$，保證無論 R 如何選，損失 $\leq V_C^*$。

定理

Theorem: von Neumann Minimax Theorem (1928)
對任何 finite zero-sum game（有限零和賽局）： $$ \max_{\mathbf{p}} \min_{\mathbf{q}} E(\mathbf{p}, \mathbf{q}) = \min_{\mathbf{q}} \max_{\mathbf{p}} E(\mathbf{p}, \mathbf{q}) $$ 即：$V_R^* = V_C^* = V^*$ 意義： - 遊戲有唯一的「真實價值」$V^*$ - 存在最優 mixed strategies $(\mathbf{p}^*, \mathbf{q}^*)$ 達成此值 - $(\mathbf{p}^*, \mathbf{q}^*)$ 是 **Nash 均衡**

🎯 核心洞察：
Pure strategy：$VR \leq VC$（可能有 gap）
Mixed strategy：$V_R^* = V_C^*$（gap 消失！）

隨機化「解決」了沒有 saddle point 的遊戲。

證明概念（簡化版）

Proof Sketch（用 LP Duality）： 1. R 的問題： 找 $\mathbf{p}$ 最大化 $\min_j \sum_i p_i A[i,j]$ 等價 LP： $$ \begin{align} \text{maximize} \quad & v \\ \text{subject to} \quad & \sum_i p_i A[i,j] \geq v, \quad \forall j \\ & \sum_i p_i = 1, \quad p_i \geq 0 \end{align} $$ 2. C 的問題： 找 $\mathbf{q}$ 最小化 $\max_i \sum_j q_j A[i,j]$ 等價 LP： $$ \begin{align} \text{minimize} \quad & u \\ \text{subject to} \quad & \sum_j q_j A[i,j] \leq u, \quad \forall i \\ & \sum_j q_j = 1, \quad q_j \geq 0 \end{align} $$ 3. **這兩個 LP 互為對偶（dual）！** 4. LP Strong Duality： 若原始問題和對偶問題都有可行解，則最優值相等。 5. 因此： $V_R^* = V_C^* = V^*$ □

Loomis’s Lemma

弱對偶性

引理

Lemma: Loomis's Lemma
對任何 mixed strategies $\mathbf{p}, \mathbf{q}$： $$ \min_{\mathbf{q}} E(\mathbf{p}, \mathbf{q}) \leq \max_{\mathbf{p}} E(\mathbf{p}, \mathbf{q}) $$ 因此： $$ \max_{\mathbf{p}} \min_{\mathbf{q}} E(\mathbf{p}, \mathbf{q}) \leq \min_{\mathbf{q}} \max_{\mathbf{p}} E(\mathbf{p}, \mathbf{q}) $$

這是 weak duality（弱對偶性）。** von Neumann 定理說的是 **strong duality（強對偶性），兩者相等！

Yao’s Principle

演算法 Lower Bound

設定：演算法遊戲

把演算法問題看成 zero-sum game：

  • R（演算法設計者）： 選擇演算法 $A$
  • C（敵手/輸入生成者）： 選擇輸入 $I$
  • Payoff $A[A, I]$： 演算法 $A$ 在輸入 $I$ 上的成本（時間/空間等）

目標：

  • R 想最小化 worst-case 成本
  • C 想最大化 R 的成本

Yao’s Principle

Theorem: Yao's Principle (1977)
$$ \min_{\text{演算法 } A} \mathbb{E}_{\text{輸入 } I}[\text{Cost}(A, I)] \geq \mathbb{E}_{\text{輸入 } I}[\min_{\text{確定性演算法 } A} \text{Cost}(A, I)] $$ 更直白的版本： 1. **隨機演算法的期望成本（worst-case 輸入）** $$\geq$$ 2. **確定性演算法在隨機輸入上的期望成本（最佳確定性演算法）** 推論： 要證明隨機演算法 lower bound，可以： - 選一個輸入分佈 $D$ - 證明任何確定性演算法在 $D$ 下期望成本 $\geq L$ - 則任何隨機演算法的 worst-case 期望成本 $\geq L$

💡 為什麼有用？

  • 直接分析隨機演算法的 lower bound 很難（要考慮所有可能的隨機化）
  • Yao’s Principle 讓我們轉而分析確定性演算法在特定分佈下的表現
  • 這通常容易得多！

應用：Sorting Lower Bound

比較排序的下界

問題

比較排序（Comparison-based Sorting） 的 lower bound 是多少？

已知：Merge Sort 是 $O(n \log n)$（確定性、worst-case）

問：隨機化能做得更好嗎？

用 Yao’s Principle 證明

**Step 1：選輸入分佈** 令輸入是 $n!$ 種排列之一，**均勻隨機**選擇。 **Step 2：分析確定性演算法** 任何確定性比較排序演算法： - 決策樹有 $n!$ 個葉子（對應所有可能排列） - 樹高度（worst-case 比較次數）$\geq \log_2(n!)$ - **期望比較次數（對隨機輸入）** $\geq$ 平均葉深度 Information-theoretic bound： $$ \log_2(n!) = \Theta(n \log n) $$ 任何確定性演算法在隨機排列上期望比較 $\geq \Omega(n \log n)$。 **Step 3：應用 Yao's Principle** $$ \text{任何隨機演算法的 worst-case 期望} \geq \Omega(n \log n) $$

🎯 結論：
比較排序的 lower bound 是 $\Omega(n \log n)$，即使允許隨機化！
Merge Sort 和 Randomized QuickSort 都是漸近最優的。

Yao’s Principle vs. 直接分析

比較

方法 優點 缺點
**直接分析隨機演算法** 給出確切的 upper bound 可能很複雜（需分析隨機選擇）
**Yao's Principle** 證明 lower bound 更簡單 只給 lower bound，不構造演算法

使用場景

用 Yao’s Principle 當：

  • 想證明「沒有演算法可以做得更好」
  • 需要 lower bound 來評估現有演算法是否最優
  • 輸入有自然的機率分佈

不用 Yao’s Principle 當：

  • 想設計或分析具體演算法
  • 需要 upper bound 或演算法正確性證明

總結

Minimax Theorem 與 Yao’s Principle 連結了賽局論與演算法分析：

  1. Mixed Strategy： 以機率分佈選擇 pure strategy
  2. von Neumann Minimax Theorem：
    • $V_R^* = V_C^*$ （maxmin = minmax）
    • 任何 finite zero-sum game 都有解
    • 隨機化消除了 pure strategy 的 gap
  3. Yao’s Principle：
    • 演算法 ↔ 遊戲
    • 用對偶性證明 lower bound
    • 分析確定性演算法在隨機輸入 → 推出隨機演算法 lower bound
  4. 應用：
    • Sorting lower bound：$\Omega(n \log n)$
    • Searching lower bound
    • Online algorithms、Communication complexity 等

核心思想： 隨機化不僅是演算法設計工具，也是複雜度分析的強大框架。

參考資料

  • von Neumann, “Zur Theorie der Gesellschaftsspiele”, 1928
  • Yao, “Probabilistic computations: Toward a unified measure of complexity”, 1977
  • Motwani & Raghavan, Randomized Algorithms, Chapter 2
  • Arora & Barak, Computational Complexity, Chapter 15