06.1 vonNeumann極小極大定理1928#

本章導言#

當兩個對手的利益完全對立——你多得一分我即少得一分——「最優策略」是什麼意思？這個問題在賭桌上、在軍事參謀室裡、在兩家廠商的價格戰裡反覆出現，卻直到 20 世紀初才被轉化為嚴格的數學命題。1928 年，年僅 25 歲的 John von Neumann（馮．紐曼，1903–1957） 在《Mathematische Annalen》發表〈賽局論的數學原則〉（Zur Theorie der Gesellschaftsspiele），證明了極小極大定理（minimax theorem）：在兩人零和賽局中，雙方都存在使「最壞情況最好」的混合策略，且其值唯一。這是賽局論的第一塊基石，也是 20 世紀數學介入社會科學最具里程碑意義的時刻之一。

問題的由來：Borel 的猜想與 Zermelo 的逆流#

法國數學家 Émile Borel（波雷爾，1871–1956） 是最早把「策略」當作數學物件的人。1913 年起，他研究撲克牌與橋牌中的最優下注，1921 年在法國科學院的系列報告中提出：在有限零和賽局中，雙方的最優行為應該由一個可計算的「混合策略」給出，且存在一個「公平價值」（valeur du jeu）。但他只對極小的 \(2 \times 2\) 、 \(2 \times 3\) 矩陣給出論證，並猜想一般情形的解由「極小極大」原則決定——卻無法證明。

與此同時，另一條思潮主張「賽局無解」。1913 年德國數學家 Ernst Zermelo（策梅洛） 證明了定理：純粹靠邏輯，國際象棋在雙方都下得完美時必然是「先手勝、後手勝或和局」三者之一。這個結果看似強大，實際上卻什麼都沒告訴我們——它既不給出下法，也不給出可計算性，且 Zermelo 本人由此傾向於認為：涉及自由意志與對抗的遊戲大概無法數學化。Borel 與 Zermelo 的張力——「有解但不會算」與「大概無解」——正是 von Neumann 1928 年論文要劈開的困境。

極小極大定理的精確陳述#

設兩人零和賽局：行玩家（row player）選策略 \(i \in \{1,\dots,m\}\) ，列玩家（column player）選策略 \(j \in \{1,\dots,n\}\) ，行玩家得 \(a_{ij}\) 、列玩家得 \(-a_{ij}\) （矩陣 \(A = (a_{ij})\) 即全部資訊）。

若雙方允許隨機化，行玩家以機率向量 \(x \in \Delta_m\) （ \(\Delta_m = \{x \ge 0,\ \sum_i x_i = 1\}\) ）行動，列玩家以 \(y \in \Delta_n\) 行動，則期望收益為雙線性型：

\[ u(x, y) = \sum_{i=1}^m \sum_{j=1}^n a_{ij} x_i y_j = x^\top A y. \]

定理（von Neumann, 1928）：存在 \(x^* \in \Delta_m\) 、 \(y^* \in \Delta_n\) 與一個數 \(v\) （賽局值），使得

\[ \max_{x \in \Delta_m} \min_{y \in \Delta_n} u(x,y) \;=\; \min_{y \in \Delta_n} \max_{x \in \Delta_m} u(x,y) \;=\; v. \]

換言之，「行玩家先選、列玩家後觀察再選」與「列玩家先選、行玩家後觀察再選」——這個看似對行玩家極度不利的資訊順序——竟給出相同的值。允許混合策略，正是把「先後」的資訊優勢抹平的代價與成果。證明的關鍵工具是 Brouwer 不動點定理（1911）的凸性版本，這條定理將在第 5 章隨一般均衡理論（5.2 節）再度登場——同一把鑰匙，一次開賽局論的門、一次開 Arrow–Debreu 的門。

混合策略為何必要：一個純策略失敗的例子#

設 \(A = \begin{pmatrix} 2 & -1 \\ -1 & 1 \end{pmatrix}\) 。若雙方只用純策略：行玩家看列玩家而動，列玩家看行玩家而動，兩人同時決策時任何純策略組合都可被對方單方面改善——例如 \((1,1)\) 得 2，列玩家改選第 2 列得 \(-1\) 對列玩家更好（行玩家損失 3）。純策略下沒有安穩的「均衡點」（鞍點不存在： \(\max_i \min_j a_{ij} = -1\) ，而 \(\min_j \max_i a_{ij} = 1\) ，兩者不等）。

von Neumann 的答案是：雙方各自把自己的行動「保密地」隨機化。行玩家以機率 \(p\) 選第 1 行、列玩家以機率 \(q\) 選第 1 列。行玩家保證自己期望收益的方式，是讓列玩家無差異（否則列玩家會集中打擊期望收益較低的那一行）：

\[ 2q - 1(1-q) \;=\; -1 \cdot q + 1 \cdot (1-q) \quad\Longrightarrow\quad 3q - 1 = 1 - 2q \quad\Longrightarrow\quad q = \frac{2}{5}. \]

對稱地，行玩家自己取 \(p = \frac{2}{5}\) 時列玩家也無差異。賽局值 \(v = 3 \cdot \frac{2}{5} - 1 = \frac{1}{5}\) 。鞍點在混合策略的空間裡被補齊了——這正是定理的幾何內容： \(\Delta_m \times \Delta_n\) 是緊凸集， \(u\) 對各自變數是線性的（凹凹），minimax 交換得以成立。

從賭桌到國防：理論的現實動因#

von Neumann 與同代人深切意識到理論的來源。1920–30 年代，軍事規劃、关税談判、海軍艦隊部署（運籌學的前身）都要求「在對手也最優的前提下做最壞打算」。von Neumann 與 Oskar Morgenstern（摩根斯坦，1902–1977） 1944 年合著的《賽局論與經濟行為》開宗明義：經濟主體間的「戰略互動」是古典與新古典理論的真空地帶——第 3、5 章的供給需求與一般均衡都假設「每個人把他人當作背景氣候」，一旦對手會對你的行動作出反應，最適化問題的本質就變了。零和模型是這個新世界的最簡起步：它對應的是利益完全衝突的談判、戰爭與競標（拍賣理論見 9.3 節）。

一個具體例題#

例題 06.1.1：兩家廠商爭奪同一筆訂單。行方有「大規模投標」（ \(A\) ）與「小規模投標」（ \(B\) ）兩策；列方有「強力攔截」（ \(C\) ）與「保守跟隨」（ \(D\) ）兩策。收益矩陣（行方所得，單位百萬元）為

\[ A = \begin{pmatrix} 6 & -2 \\ -1 & 3 \end{pmatrix}. \]

求雙方最優混合策略與賽局值。

解：先檢查鞍點：行玩家的保證水準 \(\max_i \min_j a_{ij} = \max(\min(6,-2),\ \min(-1,3)) = \max(-2,-1) = -1\) ；列玩家的保證水準 \(\min_j \max_i a_{ij} = \min(\max(6,-1),\ \max(-2,3)) = \min(6,3) = 3\) 。 \(-1 \ne 3\) ，無純策略鞍點，需用混合策略。

設行玩家以機率 \(p\) 取 \(A\) 、以 \(1-p\) 取 \(B\) 。列玩家會攻擊行玩家期望收益較低的一行，故行玩家取 \(p\) 使兩列誘惑相同：

\[ 6p - 1(1-p) \;=\; -2p + 3(1-p) \;\Longrightarrow\; 7p - 1 = 3 - 5p \;\Longrightarrow\; 12p = 4 \;\Longrightarrow\; p = \frac{1}{3}. \]

設列玩家以機率 \(q\) 取 \(C\) 。行玩家會集中於期望收益較高的一行，故列玩家取 \(q\) 使兩行無差異：

\[ 6q - 2(1-q) \;=\; -1 \cdot q + 3(1-q) \;\Longrightarrow\; 8q - 2 = 3 - 4q \;\Longrightarrow\; 12q = 5 \;\Longrightarrow\; q = \frac{5}{12}. \]

賽局值（行玩家在最優混合下的期望收益）：

\[ v = 6\cdot\frac{5}{12} + (-2)\cdot\frac{7}{12} = \frac{30 - 14}{12} = \frac{16}{12} = \frac{4}{3}. \]

以列視角驗算： \(6 \cdot \frac13 - 1 \cdot \frac23 = 2 - \frac23 = \frac43\) ，一致。一般 \(2 \times 2\) 公式 \(v = \dfrac{ad-bc}{(a+d)-(b+c)} = \dfrac{18-2}{9+3} = \dfrac{4}{3}\) 吻合。

結論：行方以 \((\frac13, \frac23)\) 混合投標規模、列方以 \((\frac{5}{12}, \frac{7}{12})\) 混合攔截姿態，行方長期平均每案穩得 \(\frac{4}{3}\) 百萬元——這個保證與列方是否「配合」無關，正是極小極大保證的精髓。

名詞速查表#

零和賽局：一方收益恆等於另一方損失的賽局，收益可用單一矩陣 \(A\) 表示。
混合策略：在策略集合上的機率分布；把純策略空間擴充為單純形 \(\Delta\) 。
**賽局值 \(v\) **：雙方採用最優混合策略時的期望收益，與對手選擇無關。
極小極大定理： \(\max_x \min_y u = \min_y \max_x u = v\) 在兩人零和混合策略賽局中成立。
鞍點：純策略下使 \(\max\min = \min\max\) 的矩陣元素位置。
Brouwer 不動點定理：緊凸集到自身的連續映射必有不動點；極小極大定理與一般均衡（5.2 節）共同的拓樸學引擎。

前因後果與驅動關係#

什麼問題驅動了它：零和賽局是「戰略互動」的最小單元。19 世紀的邊際革命與一般均衡（第 1、5 章）把市場想成「原子式個人面對自然」，而軍事、談判與雙寡頭競爭（7.1 節）中，對手的收益恰是你的損失——這種結構無法用單人最適化處理，Borel 的直覺與 Zermelo 的悲觀顯示：不發明新數學工具就走不下去。

數學工具如何反過來改變實務：極小極大定理把「策略」變成可計算的機率向量，直接催生了三條應用軸線。其一，軍事與情報：二次大戰期間運籌學小組用 minimax 分析護航隊編隊與聲納部署，戰後 RAND 公司把這套語言帶進冷戰核威慑與軍控談判（核對抗是典型的零和結構）。其二，經濟學：von Neumann–Morgenstern（1944）把零和理論擴展為合作與非合作的完整體系，直接催生了第 6 章後續的 Nash 均衡（6.2 節）與第 7 章的寡占分析——Cournot（7.1 節）1838 年的雙寡頭模型其實就是一個非零和版本的雙線性最適化，零和理論為它提供了「解的存在性」典範。其三，管理決策：《管理的數學》第 8 章「決策分析」中的「不確定情況下的最壞情況準則（maximin）」正是極小極大定理的單人退化形式；兩者的差別——「大自然不與你作對」與「對手與你作對」——是決策論與賽局論的分水嶺。金融方面，對沖基金的最差情形優化（robust portfolio）與選擇權做市的庫存控制（《金融的數學》第 4、7 章）都直接引用 minimax 思想。

對政策的回頭影響：一旦「均衡值可算」，談判不再是心理博弈而是可驗算的分配問題；拍賣設計（9.3 節）把零和競標的收益分析發展為收入等價定理；而信息經濟學（第 9 章）則指出：當收益矩陣本身對一方隱藏時，零和框架立刻失效——逆向選擇與訊號傳遞（9.2 節）正是「非零和 × 信息不對稱」的產物。極小極大定理的歷史地位，因此不只是「證明了一個定理」，而是示範了把對抗性直覺公理化為可計算結構這條路徑本身。

年表速查#

1911：Brouwer 證明不動點定理（維數任意）。
1913：Zermelo 證明象棋的結果定理，同時質疑賽局的數學化。
1913–1921：Borel 研究撲克與橋牌的最優下注，提出混合策略直覺。
1921–1927：Borel 在法國科學院報告「賽局值」概念，僅解決小矩陣。
1928：von Neumann 證明一般兩人人零和賽局的極小極大定理（Math. Ann. 100）。
1937：Kakutani 推廣 Brouwer 定理為集合值映射的不動點定理（為 1950 年 Nash 定理鋪路）。
1944：von Neumann–Morgenstern《賽局論與經濟行為》出版，零和理論擴展為完整學科。

歷史啟示#

「無解」的悲觀往往只是工具不足：Zermelo 與 Borel 的對峙說明，同一代數學家對同一問題的分歧，常是可用工具的差異而非問題本身的性質。
擴充「策略」的定義即解決問題：從純策略到混合策略，一步之遙，卻需要拓樸學（緊凸集上的最值）作支撐——概念的躍遷有時依賴遙遠的數學分支成熟。
零和是邊界情況：它給出乾淨的存在性定理，但真實經濟幾乎都是非零和，這正是 Nash（6.2 節）必須另起爐灶的原因。

練習#

設 \(A = \begin{pmatrix} 1 & 3 \\ 4 & 2 \end{pmatrix}\) 。先判斷是否存在純策略鞍點，再求雙方最優混合策略與賽局值。
設 \(A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}\) （「猜銅板」型）。證明雙方最優策略皆為均勻混合 \((\frac12,\frac12)\) ，賽局值為 0；並說明為何任何「偏向」都使自己吃虧。
對一般 \(2 \times 2\) 矩陣 \(A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\) （設 \(a > c,\ d > b\) ，無鞍點），導出行玩家的 \(p^* = \dfrac{d-c}{(a-c)+(d-b)}\) 與列玩家的 \(q^* = \dfrac{d-b}{(a-c)+(d-b)}\) ，並用例題 06.1.1 驗算。
三策略例子： \(A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) （匹配賽局）。證明均勻混合 \((\frac13,\frac13,\frac13)\) 是雙方最優，值為 \(\frac13\) ；若行玩家不慎取 \((\frac12,\frac12,0)\) ，列玩家如何利用？
思考題：極小極大定理保證行玩家「不論列玩家怎麼選都有下限 \(v\) 」，但若雙方可以簽契約（如合縱連橫），零和框架還適用嗎？試以「兩家廠商協議瓜分市場」為例，說明為何合作賽局（von Neumann–Morgenstern 的另一條線）與非合作賽局（6.2 節）必須分開處理。

（本節完）