歡迎來到博弈論（Game Theory）的世界！

歡迎來到離散數學中最引人入勝的章節之一。雖然這個名稱可能會讓你聯想到桌遊或電子遊戲，但博弈論實際上是經濟學家、軍事戰略家和生物學家用來模擬衝突與合作的強大工具。

在本章中，你將學習如何分析那些涉及兩位「博弈者」作出決策的情況，且每個人的結果都取決於對方的選擇。如果剛開始覺得這有點像邏輯謎題，別擔心，我們會一步步拆解它！


1. 收益矩陣（Pay-off Matrix）與零和博弈（Zero-Sum Games）

我們在這裡研究的每一場遊戲都是零和博弈。這意味著一方贏得多少，另一方就輸掉多少。遊戲中的「財富」總額始終保持為零。

我們使用收益矩陣來表示這些遊戲。按照慣例，矩陣中的數字顯示的是列博弈者（Row Player）的收益。如果數字為負，則意味著列博弈者輸掉了該金額（而行博弈者贏得了該金額）。

關鍵概念：

  • 列博弈者（Row Player, R）： 總是試圖最大化自己的收益。
  • 行博弈者（Column Player, C）： 總是試圖最小化列博弈者的收益（因為 R 的獲利即是 C 的損失）。
範例：想像商店 A（列）和商店 B（行）正在決定是否要打廣告。如果矩陣中顯示為 '5'，代表商店 A 獲得 5% 的市場份額，而商店 B 則損失 5%。
快速小結：

矩陣始終是從列博弈者的角度編寫的。高數值對列博弈者有利；低數值對行博弈者有利。


2. 簡化矩陣：優勢論點（Dominance Argument）

有時候，矩陣比實際需要的更大。我們可以使用優勢（Dominance）來簡化它。如果存在另一種策略，無論對手做什麼，它總是更好或相等，那麼原本的策略就是「受支配的（dominated）」。

如何簡化：

  1. 針對列： 如果第 1 列的每個元素都小於或等於第 2 列的對應元素，則第 1 列是受支配的。刪掉它！（列博弈者絕對不會選擇它）。
  2. 針對行： 如果第 1 行的每個元素都大於或等於第 2 行的對應元素，則第 1 行是受支配的。刪掉它！（記住：行博弈者想要的是更小的數字）。

記憶技巧： 列＝「越大越好」。行＝「越小越精明」。

關鍵小結：

務必先檢查是否有優勢策略。這能為你節省大量後續的計算時間！


3. 純策略：保險策略與穩定解

在投入複雜的數學計算之前，我們需要檢查是否存在純策略（Pure Strategy）。這是指兩位博弈者都能找到一個始終堅持採取的單一行動。

保險策略（Play-Safe Strategy）：

  • 列博弈者（Maximin）： 對於每一列，找出最小值。然後，從這些最小值中選擇最大值。
  • 行博弈者（Minimax）： 對於每一行，找出最大值。然後，從這些最大值中選擇最小值。

穩定解（鞍點 Saddle Points）：

如果 Maximin = Minimax，該遊戲就有一個穩定解或鞍點。在這種情況下，兩位博弈者都沒有動機去改變他們的行動。這個數值也被稱為遊戲價值（Value of the Game, V）。

你知道嗎？ 鞍點的名稱源於山徑的形狀（馬鞍）——它是山脊上的最低點，卻是山谷之間最高的地方！

納什均衡（Nash Equilibrium）：

納什均衡是指一組策略，其中任何博弈者在其他博弈者策略不變的情況下，單方面更改自己的策略都無法獲利。在具有穩定解的零和博弈中，鞍點就是納什均衡。

關鍵小結：

如果 Maximin = Minimax，遊戲就解開了！無需再進行進一步計算。


4. 混合策略：當沒有穩定解時

如果 Maximin 不等於 Minimax 怎麼辦？這種情況下，博弈者不應該堅持單一行動，否則會被對手預測到。相反，他們會使用混合策略（Mixed Strategy），以一定的機率採取不同的行動。

A. 解 2x2 遊戲（聯立方程式）

假設列博弈者以機率 \(p\) 採取策略 \(R_1\)，並以機率 \((1-p)\) 採取 \(R_2\)。我們要找到一個 \(p\) 值，使得無論行博弈者怎麼做，期望收益都相同。

逐步教學：

  1. 將 \(p\) 和 \((1-p)\) 分配給列博弈者的選項。
  2. 計算若行博弈者採取 \(C_1\) 時的預期收益。
  3. 計算若行博弈者採取 \(C_2\) 時的預期收益。
  4. 將這兩個算式設為相等，然後解出 \(p\)。
範例：如果行博弈者採取 \(C_1\) 得到 \(3p + 1(1-p)\)，而採取 \(C_2\) 得到 \(2p + 4(1-p)\)，我們解方程式：\(3p + 1 - p = 2p + 4 - 4p\)。

B. 解 2xN 遊戲（圖解法）

如果列博弈者有 2 個選項，但行博弈者有很多選項，我們就使用圖表。

  1. 設 x 軸為 \(p\)（從 0 到 1）。
  2. 對於行博弈者的每一種策略，畫一條代表列博弈者預期收益的線。
  3. 找出所有這些線的下邊界（lower boundary）（因為行博弈者會試圖最小化列博弈者的收益）。
  4. 這個下邊界上的最高點就是列博弈者的最佳 \(p\)。

剛開始覺得困難也不用擔心！ 只要記住：列博弈者想要的是圖表中「最低部分的最高點」。

關鍵小結：

混合策略是用來讓對手無法預測。我們計算機率以確保獲得一個保證的平均「遊戲價值」。


5. 進階策略：單純形法（Simplex Method）重構

對於比 2x2 或 2xN 更大的遊戲，簡單的代數和圖表是不夠的。我們必須將遊戲轉化為線性規劃（Linear Programming）問題，並使用單純形演算法來解決。

流程：

  1. 給矩陣中的所有元素加上一個常數，確保它們全部為正數（這不會改變策略，只會改變最終價值）。
  2. 定義變數 \(x_1, x_2, ... x_n\)，其中 \(x_i = \frac{p_i}{V}\)。
  3. 目標變為最大化 \(P = x_1 + x_2 + ... + x_n\)（這等同於最小化遊戲價值）。
  4. 根據矩陣的行建立約束條件。

常見錯誤： 忘記加上常數以使所有值變為正數。在這種設置下，單純形法無法直接處理負值的「價值」變數！

關鍵小結：

大型遊戲其實就是複雜的優化問題。我們利用單純形法來找出多種策略下的「最佳組合」。


最後總複習

  • 零和博弈： 我的收益 = 你的損失。
  • 優勢： 刪除「劣勢」列（低值）和「劣勢」行（高值）。
  • 保險策略： 列取 Maximin，行取 Minimax。
  • 鞍點： 當 Maximin = Minimax 時，遊戲穩定。
  • 混合策略： 當沒有鞍點時，使用機率（\(p\) 和 \(1-p\)）。
  • 價值 (V)： 若雙方皆採取最佳策略，列博弈者預期能贏得的平均金額。

鼓勵的話： 你一定行的！先練習識別鞍點——它們是博弈論題目中「唾手可得」的分數！