基于线性规划的“零和博弈混合策略纳什均衡”建模与求解示例
字数 5550 2025-12-24 20:10:22

基于线性规划的“零和博弈混合策略纳什均衡”建模与求解示例

1. 问题背景与描述

在博弈论中，零和博弈描述的是这样一种竞争场景：参与者的总收益在所有情况下之和为零，即一方的收益等于另一方的损失。在许多现实竞争场景（如扑克、围棋、军事对抗、竞价拍卖等）中，参与者常常需要采取随机化的策略来使对手无法预测自己的行为，从而实现最优的应对。
混合策略纳什均衡 是指在给定其他参与者策略的情况下，没有参与者能够通过单方面改变自己的策略来增加其期望收益。该均衡可以通过线性规划模型精确求解。

问题描述：
考虑一个二人零和博弈，两位参与者分别为行玩家（Player 1）和列玩家（Player 2）。

  • 行玩家有 \(m\) 个纯策略（行动），列玩家有 \(n\) 个纯策略。
  • 行玩家的收益矩阵为 \(A = (a_{ij})_{m \times n}\)。当行玩家选择策略 \(i\)，列玩家选择策略 \(j\) 时，行玩家获得收益 \(a_{ij}\)，列玩家获得收益 \(-a_{ij}\)（因为博弈是零和的）。

假设：

  • 行玩家希望最大化其期望收益；
  • 列玩家希望最小化行玩家的期望收益（即最大化自己的收益，因为总收益为零）。

我们要找到：

  1. 行玩家的最优混合策略（一个概率分布 \(x = (x_1, ..., x_m)\) 满足 \(x_i \ge 0, \sum_i x_i = 1\)）。
  2. 列玩家的最优混合策略（一个概率分布 \(y = (y_1, ..., y_n)\) 满足 \(y_j \ge 0, \sum_j y_j = 1\)）。
  3. 博弈的值 \(v\)（行玩家在均衡下的期望收益）。

2. 博弈论基本定理（冯·诺依曼最小最大定理）

定理：
对于任何有限二人零和博弈，存在一个值 \(v\) 和一对混合策略 \((x^*, y^*)\)，使得：

\[\max_x \min_y \, x^T A y = v = \min_y \max_x \, x^T A y \]

这个 \(v\) 称为博弈的值，\((x^*, y^*)\) 是一个混合策略纳什均衡。

解释：

  • 对行玩家来说，他选择策略 \(x\) 时，会考虑列玩家选择对行玩家最不利的 \(y\)，即最小化 \(x^T A y\)。行玩家希望最大化这个最小值。
  • 对列玩家来说，他选择策略 \(y\) 时，会考虑行玩家选择对行玩家最有利的 \(x\)，即最大化 \(x^T A y\)。列玩家希望最小化这个最大值。

这个定理保证了均衡的存在性，并且可以通过线性规划求解。

3. 线性规划建模

我们通常为行玩家建立线性规划模型，然后通过对偶理论得到列玩家的策略。

3.1 行玩家的最大化问题

行玩家的目标是：

\[\max_{x} \min_{1 \le j \le n} \sum_{i=1}^m a_{ij} x_i \]

因为一旦行玩家选定 \(x\)，列玩家会选择使行玩家期望收益最小（即列玩家收益最大）的列 \(j\)，所以行玩家的收益至少是 \(t = \min_j \sum_i a_{ij} x_i\)。行玩家希望最大化 \(t\)。

引入变量：

  • \(x_i \ge 0\)：行玩家选择策略 \(i\) 的概率。
  • \(t\)：行玩家的保证收益下界。

优化模型（主线性规划）：

\[\begin{aligned} \max \quad & t \\ \text{s.t.} \quad & \sum_{i=1}^m a_{ij} x_i \ge t, \quad j = 1, ..., n \quad (\text{对每一列 } j, \text{ 行玩家的收益至少为 } t) \\ & \sum_{i=1}^m x_i = 1 \\ & x_i \ge 0, \quad i = 1, ..., m \\ & t \in \mathbb{R} \end{aligned} \]

注意：这不是一个标准线性规划，因为变量 \(t\) 无约束，但我们可以通过变量替换转换为标准形式。

转换为标准线性规划：
令 \(u_i = x_i / t\)（当 \(t > 0\) 时），但直接处理更方便的另一种常见方法是固定 \(t\) 的系数。更标准的方法是通过约束 \(\sum_i x_i = 1\) 消除 \(t\) 的自由度，不过我们直接对原始模型做变换：

设 \(v = 1/t\)（当 \(t \neq 0\)），但更简单的常见推导是从对偶角度。实际上，经典的线性规划形式是：

行玩家规划（最大化下界 \(t\)）：

\[\begin{aligned} \max \quad & t \\ \text{s.t.} \quad & \sum_{i=1}^m a_{ij} x_i \ge t, \quad j=1,...,n \\ & \sum_{i=1}^m x_i = 1 \\ & x_i \ge 0 \end{aligned} \]

这仍然是一个线性规划，因为 \(t\) 是自由变量。我们可以把它转化为只有非负变量的标准形式：

令 \(t' = t + M\)（其中 \(M\) 是一个足够大的常数，使 \(t' \ge 0\)）。但更方便的方法是利用对偶理论。

3.2 列玩家的最小化问题

由对偶理论，行玩家规划的对偶问题就是列玩家的最小化问题。我们直接写下列玩家的线性规划。

列玩家的目标是：

\[\min_{y} \max_{1 \le i \le m} \sum_{j=1}^n a_{ij} y_j \]

但更常用的等价形式是：列玩家希望最小化行玩家的最大可能收益，即：

\[\min_{y, w} w \]

满足：

\[\sum_{j=1}^n a_{ij} y_j \le w, \quad i=1,...,m \]

以及 \(y_j \ge 0, \sum_j y_j = 1\)。

标准形式（对偶线性规划）：

\[\begin{aligned} \min \quad & w \\ \text{s.t.} \quad & \sum_{j=1}^n a_{ij} y_j \le w, \quad i = 1, ..., m \\ & \sum_{j=1}^n y_j = 1 \\ & y_j \ge 0, \quad j = 1, ..., n \\ & w \in \mathbb{R} \end{aligned} \]

3.3 线性规划对应对

可以证明，行玩家规划与列玩家规划互为对偶线性规划。
若我们将行玩家规划写为：

\[\max t, \quad A^T x \ge t \mathbf{1}_n, \; \mathbf{1}_m^T x = 1, \; x \ge 0 \]

其对偶变量对应为 \(y \in \mathbb{R}^n\)（对前 \(n\) 个不等式）和 \(v \in \mathbb{R}\)（对等式 \(\mathbf{1}_m^T x = 1\)）。
对偶问题是：

\[\min v, \quad A y \le v \mathbf{1}_m, \; \mathbf{1}_n^T y = 1, \; y \ge 0 \]

这正好是列玩家的规划，其中 \(v = w\) 是博弈的值。

因此，求解行玩家规划及其对偶，即可同时得到双方的最优混合策略和博弈值。

4. 具体例子

考虑一个简单的“猜硬币”博弈的变体：
收益矩阵 \(A\)（对行玩家）：

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

这里，行玩家有两个策略（行1、行2），列玩家有两个策略（列1、列2）。
数值含义：若行玩家选行1，列玩家选列1，行玩家得2，列玩家得-2。

行玩家线性规划（主问题）：

\[\begin{aligned} \max \quad & t \\ \text{s.t.} \quad & 2x_1 - 3x_2 \ge t \quad (\text{当列玩家选列1}) \\ & -x_1 + 4x_2 \ge t \quad (\text{当列玩家选列2}) \\ & x_1 + x_2 = 1 \\ & x_1, x_2 \ge 0 \end{aligned} \]

代入 \(x_2 = 1 - x_1\)，得：

\[\begin{aligned} & 2x_1 - 3(1 - x_1) \ge t \implies 5x_1 - 3 \ge t \\ & -x_1 + 4(1 - x_1) \ge t \implies -5x_1 + 4 \ge t \end{aligned} \]

我们最大化 \(t\)，即：

\[t \le 5x_1 - 3, \quad t \le -5x_1 + 4 \]

在最优时，\(t = \min(5x_1 - 3, \; -5x_1 + 4)\)。
最大化 \(t\) 就是让这两个线性函数的最小值尽可能大。
两条线在 \(5x_1 - 3 = -5x_1 + 4\) 时相交，解得 \(10x_1 = 7 \implies x_1 = 0.7, x_2 = 0.3\)。
此时 \(t = 5(0.7) - 3 = 3.5 - 3 = 0.5\)。

所以行玩家最优策略：\(x^* = (0.7, 0.3)\)，博弈值 \(v = 0.5\)。

列玩家线性规划（对偶问题）：

\[\begin{aligned} \min \quad & w \\ \text{s.t.} \quad & 2y_1 - y_2 \le w \quad (\text{对应行1}) \\ & -3y_1 + 4y_2 \le w \quad (\text{对应行2}) \\ & y_1 + y_2 = 1 \\ & y_1, y_2 \ge 0 \end{aligned} \]

代入 \(y_2 = 1 - y_1\)：

\[\begin{aligned} & 2y_1 - (1 - y_1) \le w \implies 3y_1 - 1 \le w \\ & -3y_1 + 4(1 - y_1) \le w \implies -7y_1 + 4 \le w \end{aligned} \]

列玩家希望最小化 \(w\)，即 \(w = \max(3y_1 - 1, \; -7y_1 + 4)\)。
最小化 \(w\) 就是让这两个线性函数的最大值尽可能小。
两条线在 \(3y_1 - 1 = -7y_1 + 4\) 时相交，解得 \(10y_1 = 5 \implies y_1 = 0.5, y_2 = 0.5\)。
此时 \(w = 3(0.5) - 1 = 1.5 - 1 = 0.5\)。

所以列玩家最优策略：\(y^* = (0.5, 0.5)\)，博弈值 \(v = 0.5\)（与行玩家规划结果一致）。

5. 一般求解步骤

对于一个 \(m \times n\) 收益矩阵 \(A\) 的零和博弈：

  1. 建立行玩家线性规划：

\[ \begin{aligned} \max \quad & t \\ \text{s.t.} \quad & \sum_{i=1}^m a_{ij} x_i \ge t, \quad j=1,...,n \\ & \sum_{i=1}^m x_i = 1 \\ & x_i \ge 0, \quad i=1,...,m \\ & t \in \mathbb{R} \end{aligned} \]

  1. 用单纯形法（或任何LP求解器）求解，得到：

    • 行玩家最优混合策略 \(x^*\)。
    • 博弈值 \(v = t^*\)。

  2. 从对偶变量读取列玩家策略：

    • 求解上述LP时，对偶变量 \(y_j\) 对应主问题中约束 \(\sum_i a_{ij} x_i \ge t\)。
    • 由强对偶定理，对偶问题的最优解 \(y^*\) 就是列玩家的最优混合策略。
    • 通常求解器会直接给出对偶变量的值。

6. 经济与策略解释

  • 博弈值 \(v = 0.5 > 0\) 表示这个博弈对行玩家有利（平均每局赢0.5单位）。
  • 行玩家应以0.7的概率选行1，0.3的概率选行2，来保证至少0.5的期望收益，无论列玩家怎么做。
  • 列玩家应以0.5的概率选列1，0.5的概率选列2，来阻止行玩家获得超过0.5的期望收益。
  • 如果任何一方单方面改变策略，对方可以调整策略使其收益更差（或不会更好）。

7. 扩展与应用

  • 非零和博弈的纳什均衡一般不能用单一线性规划求解，而需要非线性互补问题（LCP）或不动点算法。
  • 零和博弈的线性规划模型是线性规划对偶理论的经典应用，也证明了最小最大定理。
  • 在AI游戏中，可用来计算混合策略均衡，以应对不确定性对手。

这个例子展示了如何用线性规划求解二人零和博弈的混合策略纳什均衡，步骤清晰，易于计算，并且有直观的博弈论解释。

基于线性规划的“零和博弈混合策略纳什均衡”建模与求解示例 1. 问题背景与描述 在博弈论中， 零和博弈 描述的是这样一种竞争场景：参与者的总收益在所有情况下之和为零，即一方的收益等于另一方的损失。在许多现实竞争场景（如扑克、围棋、军事对抗、竞价拍卖等）中，参与者常常需要采取随机化的策略来使对手无法预测自己的行为，从而实现最优的应对。 混合策略纳什均衡 是指在给定其他参与者策略的情况下，没有参与者能够通过单方面改变自己的策略来增加其 期望收益 。该均衡可以通过线性规划模型精确求解。 问题描述 ： 考虑一个二人零和博弈，两位参与者分别为 行玩家 （Player 1）和 列玩家 （Player 2）。 行玩家有 \(m\) 个纯策略（行动），列玩家有 \(n\) 个纯策略。 行玩家的 收益矩阵 为 \(A = (a_ {ij}) {m \times n}\)。当行玩家选择策略 \(i\)，列玩家选择策略 \(j\) 时，行玩家获得收益 \(a {ij}\)，列玩家获得收益 \(-a_ {ij}\)（因为博弈是零和的）。 假设： 行玩家希望最大化其 期望收益 ； 列玩家希望最小化行玩家的期望收益（即最大化自己的收益，因为总收益为零）。 我们要找到： 行玩家的最优混合策略（一个概率分布 \(x = (x_ 1, ..., x_ m)\) 满足 \(x_ i \ge 0, \sum_ i x_ i = 1\)）。 列玩家的最优混合策略（一个概率分布 \(y = (y_ 1, ..., y_ n)\) 满足 \(y_ j \ge 0, \sum_ j y_ j = 1\)）。 博弈的值 \(v\)（行玩家在均衡下的期望收益）。 2. 博弈论基本定理（冯·诺依曼最小最大定理） 定理 ： 对于任何有限二人零和博弈，存在一个值 \(v\) 和一对混合策略 \((x^ , y^ )\)，使得： \[ \max_ x \min_ y \, x^T A y = v = \min_ y \max_ x \, x^T A y \] 这个 \(v\) 称为博弈的 值 ，\((x^ , y^ )\) 是一个混合策略纳什均衡。 解释 ： 对行玩家来说，他选择策略 \(x\) 时，会考虑列玩家选择对行玩家最不利的 \(y\)，即最小化 \(x^T A y\)。行玩家希望最大化这个最小值。 对列玩家来说，他选择策略 \(y\) 时，会考虑行玩家选择对行玩家最有利的 \(x\)，即最大化 \(x^T A y\)。列玩家希望最小化这个最大值。 这个定理保证了均衡的存在性，并且可以通过线性规划求解。 3. 线性规划建模 我们通常为 行玩家 建立线性规划模型，然后通过 对偶理论 得到列玩家的策略。 3.1 行玩家的最大化问题 行玩家的目标是： \[ \max_ {x} \min_ {1 \le j \le n} \sum_ {i=1}^m a_ {ij} x_ i \] 因为一旦行玩家选定 \(x\)，列玩家会选择使行玩家期望收益最小（即列玩家收益最大）的列 \(j\)，所以行玩家的收益至少是 \(t = \min_ j \sum_ i a_ {ij} x_ i\)。行玩家希望最大化 \(t\)。 引入变量： \(x_ i \ge 0\)：行玩家选择策略 \(i\) 的概率。 \(t\)：行玩家的保证收益下界。 优化模型 （ 主线性规划 ）： \[ \begin{aligned} \max \quad & t \\ \text{s.t.} \quad & \sum_ {i=1}^m a_ {ij} x_ i \ge t, \quad j = 1, ..., n \quad (\text{对每一列 } j, \text{ 行玩家的收益至少为 } t) \\ & \sum_ {i=1}^m x_ i = 1 \\ & x_ i \ge 0, \quad i = 1, ..., m \\ & t \in \mathbb{R} \end{aligned} \] 注意 ：这不是一个标准线性规划，因为变量 \(t\) 无约束，但我们可以通过变量替换转换为标准形式。 转换为标准线性规划 ： 令 \(u_ i = x_ i / t\)（当 \(t > 0\) 时），但直接处理更方便的另一种常见方法是 固定 \(t\) 的系数 。更标准的方法是通过约束 \(\sum_ i x_ i = 1\) 消除 \(t\) 的自由度，不过我们直接对原始模型做变换： 设 \(v = 1/t\)（当 \(t \neq 0\)），但更简单的常见推导是从 对偶 角度。实际上，经典的线性规划形式是： 行玩家规划 （最大化下界 \(t\)）： \[ \begin{aligned} \max \quad & t \\ \text{s.t.} \quad & \sum_ {i=1}^m a_ {ij} x_ i \ge t, \quad j=1,...,n \\ & \sum_ {i=1}^m x_ i = 1 \\ & x_ i \ge 0 \end{aligned} \] 这仍然是一个线性规划，因为 \(t\) 是自由变量。我们可以把它转化为只有非负变量的标准形式： 令 \(t' = t + M\)（其中 \(M\) 是一个足够大的常数，使 \(t' \ge 0\)）。但更方便的方法是利用 对偶理论 。 3.2 列玩家的最小化问题 由对偶理论，行玩家规划的对偶问题就是列玩家的最小化问题。我们直接写下列玩家的线性规划。 列玩家的目标是： \[ \min_ {y} \max_ {1 \le i \le m} \sum_ {j=1}^n a_ {ij} y_ j \] 但更常用的等价形式是：列玩家希望最小化行玩家的最大可能收益，即： \[ \min_ {y, w} w \] 满足： \[ \sum_ {j=1}^n a_ {ij} y_ j \le w, \quad i=1,...,m \] 以及 \(y_ j \ge 0, \sum_ j y_ j = 1\)。 标准形式 （ 对偶线性规划 ）： \[ \begin{aligned} \min \quad & w \\ \text{s.t.} \quad & \sum_ {j=1}^n a_ {ij} y_ j \le w, \quad i = 1, ..., m \\ & \sum_ {j=1}^n y_ j = 1 \\ & y_ j \ge 0, \quad j = 1, ..., n \\ & w \in \mathbb{R} \end{aligned} \] 3.3 线性规划对应对 可以证明，行玩家规划与列玩家规划互为 对偶线性规划 。 若我们将行玩家规划写为： \[ \max t, \quad A^T x \ge t \mathbf{1}_ n, \; \mathbf{1}_ m^T x = 1, \; x \ge 0 \] 其对偶变量对应为 \(y \in \mathbb{R}^n\)（对前 \(n\) 个不等式）和 \(v \in \mathbb{R}\)（对等式 \(\mathbf{1}_ m^T x = 1\)）。 对偶问题是： \[ \min v, \quad A y \le v \mathbf{1}_ m, \; \mathbf{1}_ n^T y = 1, \; y \ge 0 \] 这正好是列玩家的规划，其中 \(v = w\) 是博弈的值。 因此， 求解行玩家规划及其对偶，即可同时得到双方的最优混合策略和博弈值 。 4. 具体例子 考虑一个简单的“猜硬币”博弈的变体： 收益矩阵 \(A\)（对行玩家）： \[ A = \begin{pmatrix} 2 & -1 \\ -3 & 4 \end{pmatrix} \] 这里，行玩家有两个策略（行1、行2），列玩家有两个策略（列1、列2）。 数值含义：若行玩家选行1，列玩家选列1，行玩家得2，列玩家得-2。 行玩家线性规划 （主问题）： \[ \begin{aligned} \max \quad & t \\ \text{s.t.} \quad & 2x_ 1 - 3x_ 2 \ge t \quad (\text{当列玩家选列1}) \\ & -x_ 1 + 4x_ 2 \ge t \quad (\text{当列玩家选列2}) \\ & x_ 1 + x_ 2 = 1 \\ & x_ 1, x_ 2 \ge 0 \end{aligned} \] 代入 \(x_ 2 = 1 - x_ 1\)，得： \[ \begin{aligned} & 2x_ 1 - 3(1 - x_ 1) \ge t \implies 5x_ 1 - 3 \ge t \\ & -x_ 1 + 4(1 - x_ 1) \ge t \implies -5x_ 1 + 4 \ge t \end{aligned} \] 我们最大化 \(t\)，即： \[ t \le 5x_ 1 - 3, \quad t \le -5x_ 1 + 4 \] 在最优时，\(t = \min(5x_ 1 - 3, \; -5x_ 1 + 4)\)。 最大化 \(t\) 就是让这两个线性函数的最小值尽可能大。 两条线在 \(5x_ 1 - 3 = -5x_ 1 + 4\) 时相交，解得 \(10x_ 1 = 7 \implies x_ 1 = 0.7, x_ 2 = 0.3\)。 此时 \(t = 5(0.7) - 3 = 3.5 - 3 = 0.5\)。 所以 行玩家最优策略 ：\(x^* = (0.7, 0.3)\)， 博弈值 \(v = 0.5\)。 列玩家线性规划 （对偶问题）： \[ \begin{aligned} \min \quad & w \\ \text{s.t.} \quad & 2y_ 1 - y_ 2 \le w \quad (\text{对应行1}) \\ & -3y_ 1 + 4y_ 2 \le w \quad (\text{对应行2}) \\ & y_ 1 + y_ 2 = 1 \\ & y_ 1, y_ 2 \ge 0 \end{aligned} \] 代入 \(y_ 2 = 1 - y_ 1\)： \[ \begin{aligned} & 2y_ 1 - (1 - y_ 1) \le w \implies 3y_ 1 - 1 \le w \\ & -3y_ 1 + 4(1 - y_ 1) \le w \implies -7y_ 1 + 4 \le w \end{aligned} \] 列玩家希望最小化 \(w\)，即 \(w = \max(3y_ 1 - 1, \; -7y_ 1 + 4)\)。 最小化 \(w\) 就是让这两个线性函数的最大值尽可能小。 两条线在 \(3y_ 1 - 1 = -7y_ 1 + 4\) 时相交，解得 \(10y_ 1 = 5 \implies y_ 1 = 0.5, y_ 2 = 0.5\)。 此时 \(w = 3(0.5) - 1 = 1.5 - 1 = 0.5\)。 所以 列玩家最优策略 ：\(y^* = (0.5, 0.5)\)， 博弈值 \(v = 0.5\)（与行玩家规划结果一致）。 5. 一般求解步骤 对于一个 \(m \times n\) 收益矩阵 \(A\) 的零和博弈： 建立行玩家线性规划 ： \[ \begin{aligned} \max \quad & t \\ \text{s.t.} \quad & \sum_ {i=1}^m a_ {ij} x_ i \ge t, \quad j=1,...,n \\ & \sum_ {i=1}^m x_ i = 1 \\ & x_ i \ge 0, \quad i=1,...,m \\ & t \in \mathbb{R} \end{aligned} \] 用单纯形法（或任何LP求解器）求解 ，得到： 行玩家最优混合策略 \(x^* \)。 博弈值 \(v = t^* \)。 从对偶变量读取列玩家策略 ： 求解上述LP时， 对偶变量 \(y_ j\) 对应主问题中约束 \(\sum_ i a_ {ij} x_ i \ge t\)。 由强对偶定理，对偶问题的最优解 \(y^* \) 就是列玩家的最优混合策略。 通常求解器会直接给出对偶变量的值。 6. 经济与策略解释 博弈值 \(v = 0.5 > 0\) 表示这个博弈对行玩家有利（平均每局赢0.5单位）。 行玩家应以0.7的概率选行1，0.3的概率选行2，来保证至少0.5的期望收益，无论列玩家怎么做。 列玩家应以0.5的概率选列1，0.5的概率选列2，来阻止行玩家获得超过0.5的期望收益。 如果任何一方单方面改变策略，对方可以调整策略使其收益更差（或不会更好）。 7. 扩展与应用 非零和博弈 的纳什均衡一般不能用单一线性规划求解，而需要非线性互补问题（LCP）或不动点算法。 零和博弈的线性规划模型是 线性规划对偶理论 的经典应用，也证明了 最小最大定理 。 在AI游戏中，可用来计算 混合策略均衡 ，以应对不确定性对手。 这个例子展示了如何用线性规划求解二人零和博弈的混合策略纳什均衡，步骤清晰，易于计算，并且有直观的博弈论解释。