欢迎来到博弈论（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)： 若双方皆采取最佳策略，列博弈者预期能赢得的平均金额。

鼓励的话： 你一定行的！先练习识别鞍点——它们是博弈论题目中“唾手可得”的分数！