基于线性规划的零和博弈混合策略纳什均衡求解示例
我将为你讲解如何利用线性规划求解一个两人零和博弈的混合策略纳什均衡。这是一个将博弈论与线性规划结合的经典应用。
题目描述
考虑一个经典的石头剪刀布游戏。我们将它稍作变形，构建一个两人零和博弈的收益矩阵。
- 玩家：有两位玩家，玩家A（行玩家，希望最大化自己的收益）和玩家B（列玩家，希望最小化自己的损失/最小化玩家A的收益）。
- 策略：每位玩家都有两个纯策略：策略1和策略2。
- 收益矩阵（A的收益）：对于玩家A，当(A选择i, B选择j)时，其收益为 \(a_{ij}\)。此矩阵如下（B的收益即为 \(-a_{ij}\))：
| A\B | B选择1 | B选择2 |
|---|---|---|
| A选择1 | 3 | -1 |
| A选择2 | -2 | 4 |
目标：求解该博弈的混合策略纳什均衡。即，找出玩家A选择其策略的概率分布 \(x = (x_1, x_2)\)（其中 \(x_1 + x_2 = 1, x_1, x_2 \ge 0\)）和玩家B选择其策略的概率分布 \(y = (y_1, y_2)\)（其中 \(y_1 + y_2 = 1, y_1, y_2 \ge 0\)），使得在对方策略固定的情况下，任何单方面改变自己的混合策略都不能带来严格更高的期望收益（对A）或更低的期望损失（对B）。
解题过程
根据Von Neumann的极小极大定理，在零和博弈中，混合策略纳什均衡可以通过求解一对对偶的线性规划问题来获得。我们将循序渐进地推导和求解。
步骤1：理解博弈值与线性规划的联系
设博弈的值为 \(V\)。在均衡时：
- 玩家A选择混合策略 \(x\)，保证无论B采取什么纯策略，A的期望收益至少为 \(V\)。即，A的策略是针对B最坏反应的“安全策略”，目的是最大化这个保证值 \(V\)。
- 玩家B选择混合策略 \(y\)，保证无论A采取什么纯策略，A的期望收益至多为 \(V\)。即，B的策略是针对A最好反应的“安全策略”，目的是最小化这个上限值 \(V\)。
步骤2：构建玩家A的线性规划模型（最大化问题）
从玩家A的视角出发：A希望找到概率向量 \(x = (x_1, x_2)\) 和一个值 \(V\)，使得：
- 如果B选择纯策略1，A的期望收益为 \(3x_1 + (-2)x_2 \ge V\)。
- 如果B选择纯策略2，A的期望收益为 \((-1)x_1 + 4x_2 \ge V\)。
- \(x_1 + x_2 = 1\)，且 \(x_1, x_2 \ge 0\)。
- A希望这个保证值 \(V\) 尽可能大。
因此，玩家A的线性规划问题为：
决策变量: \(x_1, x_2, V\)
目标函数: 最大化 \(V\)
约束条件:
\[\begin{aligned} 3x_1 - 2x_2 &\ge V \quad \text{(针对B的纯策略1)} \\ -1x_1 + 4x_2 &\ge V \quad \text{(针对B的纯策略2)} \\ x_1 + x_2 &= 1 \\ x_1, x_2 &\ge 0 \end{aligned} \]
\(V\) 是自由变量（可取正负）。
为了将其转化为标准形式的线性规划，我们通常进行一个变换：令 \(p_i = x_i / V\)（当 \(V > 0\)）或进行更通用的处理。更常见且简便的做法是将决策变量转换为与概率分布相关的 \(t = 1/V\) 关系。但这里我们使用一个直接标准化方法：将约束中的 \(V\) 移到左边。
重写A的线性规划如下：
最大化 \(V\)
满足：
\[\begin{aligned} 3x_1 - 2x_2 - V &\ge 0 \\ -x_1 + 4x_2 - V &\ge 0 \\ x_1 + x_2 &= 1 \\ x_1, x_2 &\ge 0 \end{aligned} \]
这个模型可以直接输入到某些求解器中。但为了更清晰地展示对偶性，我们通常将其写成另一种等价形式（通过引入辅助变量转换）。
实际上，更经典的推导是建立玩家B的线性规划，因为它是标准的最小化问题。
步骤3：构建玩家B的线性规划模型（最小化问题）
从玩家B的视角出发：B希望找到概率向量 \(y = (y_1, y_2)\) 和一个值 \(W\)，使得：
- 如果A选择纯策略1，B的期望损失（即A的收益）为 \(3y_1 + (-1)y_2 \le W\)。
- 如果A选择纯策略2，B的期望损失为 \((-2)y_1 + 4y_2 \le W\)。
- \(y_1 + y_2 = 1\)，且 \(y_1, y_2 \ge 0\)。
- B希望这个损失上限 \(W\) 尽可能小。可以证明，在均衡时 \(W = V\)。
因此，玩家B的线性规划问题为：
决策变量: \(y_1, y_2, W\)
目标函数: 最小化 \(W\)
约束条件:
\[\begin{aligned} 3y_1 - 1y_2 &\le W \quad \text{(针对A的纯策略1)} \\ -2y_1 + 4y_2 &\le W \quad \text{(针对A的纯策略2)} \\ y_1 + y_2 &= 1 \\ y_1, y_2 &\ge 0 \end{aligned} \]
将其重写为标准形式，将 \(W\) 移到左侧：
最小化 \(W\)
满足：
\[\begin{aligned} 3y_1 - y_2 - W &\le 0 \\ -2y_1 + 4y_2 - W &\le 0 \\ y_1 + y_2 &= 1 \\ y_1, y_2 &\ge 0 \end{aligned} \]
我们选择求解玩家B的线性规划，因为它可以方便地转化为一个标准形式。
步骤4：转化为标准线性规划并求解
令 \(y_1, y_2 \ge 0\)，且 \(y_1 + y_2 = 1\)。我们可以用 \(y_2 = 1 - y_1\) 代入约束和目标函数，将问题简化为关于单个变量 \(y_1\) 和 \(W\) 的问题，但这里我们保留原形式以展示一般性。
将B的模型整理成更清晰的形式。定义 \(y_3 = W\)（重命名）。约束变为：
\[\begin{aligned} 3y_1 - y_2 - y_3 &\le 0 \quad ... (1)\\ -2y_1 + 4y_2 - y_3 &\le 0 \quad ... (2)\\ y_1 + y_2 &= 1 \quad ... (3)\\ y_1, y_2 &\ge 0, \quad y_3 \text{ 自由} \end{aligned} \]
目标：最小化 \(y_3\)。
这是一个线性规划。我们可以使用图解法或单纯形法。由于只有两个有效概率变量（由等式(3)相关），我们可以用 \(y_1\) 表示 \(y_2 = 1 - y_1\)，其中 \(0 \le y_1 \le 1\)。将其代入不等式(1)和(2)：
代入 (1): \(3y_1 - (1 - y_1) - y_3 \le 0 \Rightarrow 4y_1 - 1 - y_3 \le 0 \Rightarrow y_3 \ge 4y_1 - 1\)
代入 (2): \(-2y_1 + 4(1 - y_1) - y_3 \le 0 \Rightarrow -2y_1 + 4 - 4y_1 - y_3 \le 0 \Rightarrow -6y_1 + 4 - y_3 \le 0 \Rightarrow y_3 \ge -6y_1 + 4\)
因此，为了同时满足两个约束，我们需要：
\[y_3 \ge \max(4y_1 - 1, \; -6y_1 + 4) \quad \text{对于 } 0 \le y_1 \le 1. \]
而B的目标是最小化 \(y_3\)。所以，最优解将在 \(y_3\) 等于这个最大值函数的最小可能值时取得。即，我们需要找到 \(y_1\) 使得两条直线 \(L1: y_3 = 4y_1 - 1\) 和 \(L2: y_3 = -6y_1 + 4\) 的最大值尽可能小。
步骤5：图解法与计算
我们在 \(y_1$-\)y_3$ 平面上分析：
- \(L1\): 当 \(y_1=0\)， \(y_3=-1\)；当 \(y_1=1\)， \(y_3=3\)。
- \(L2\): 当 \(y_1=0\)， \(y_3=4\)；当 \(y_1=1\)， \(y_3=-2\)。
两条直线相交于：
\[4y_1 - 1 = -6y_1 + 4 \implies 10y_1 = 5 \implies y_1 = 0.5 \]
代入得 \(y_3 = 4*0.5 - 1 = 2 - 1 = 1\)。所以交点为 \((0.5, 1)\)。
对于任意 \(y_1\)，函数 \(f(y_1) = \max(4y_1-1, -6y_1+4)\)。观察可知，在交点左侧，\(L2 > L1\)；在交点右侧，\(L1 > L2\)。因此，这个最大值函数的最小值恰好出现在交点处，即当 \(y_1 = 0.5\) 时，此时 \(f(0.5) = 1\)。
因此，玩家B的最优解为：
\[y_1^* = 0.5, \quad y_2^* = 1 - y_1^* = 0.5, \quad W^* = y_3^* = 1. \]
即，博弈值 \(V = W^* = 1\)。
步骤6：利用对偶求玩家A的策略
在线性规划中，玩家B的问题的对偶问题恰好就是玩家A的极大极小问题。我们可以通过对偶性质直接读取玩家A的最优策略，或者对称地求解A的问题。
当我们求解B的问题（原始问题）时，其约束(1)和(2)对应的对偶变量（记作 \(x_1\) 和 \(x_2\)）分别代表了A选择策略1和策略2的概率权重（需要进行归一化）。在最优单纯形表中，对偶变量的值（或影子价格）与A的概率成比例。
更简单的方法是，知道了博弈值 \(V=1\)，我们可以利用均衡条件来求解A的策略 \(x=(x_1, x_2)\)。均衡条件之一是：如果B在其某个纯策略上的概率大于0，那么A使用均衡策略时，B的该纯策略给A带来的期望收益必须等于博弈值 \(V\)（否则B可以调整概率获益）。反之亦然。
这里 \(y_1^*=0.5>0, y_2^*=0.5>0\)，所以B的两个纯策略都被积极使用。因此，A的均衡策略必须使得：
- 当B选择纯策略1时： \(3x_1 - 2x_2 = V = 1\)
- 当B选择纯策略2时： \(-x_1 + 4x_2 = V = 1\)
再加上概率和为1的条件： \(x_1 + x_2 = 1\)。
我们使用前两个等式之一与第三个等式联立即可。
用第一个等式和概率和等式：
\[\begin{aligned} 3x_1 - 2(1 - x_1) &= 1 \\ 3x_1 - 2 + 2x_1 &= 1 \\ 5x_1 &= 3 \\ x_1 &= 3/5 = 0.6 \end{aligned} \]
因此，\(x_2 = 1 - 0.6 = 0.4\)。
验证第二个等式： \(-0.6 + 4*0.4 = -0.6 + 1.6 = 1\)，符合。
步骤7：结论
该两人零和博弈的混合策略纳什均衡为：
- 玩家A以概率 \(0.6\) 选择策略1，以概率 \(0.4\) 选择策略2。
- 玩家B以概率 \(0.5\) 选择策略1，以概率 \(0.5\) 选择策略2。
- 该博弈的值（玩家A的期望收益）为 \(V = 1\)。
这意味着，如果双方都采用上述混合策略，那么玩家A平均每局可以获得1个单位的收益，玩家B平均损失1个单位。任何一方单方面偏离这个混合策略，在长期对抗中都无法获得更好的结果（对A而言收益不会超过1，对B而言损失不会低于1）。