本文详解如何用 SciPy 的 milp 函数正确建模并求解二人零和博弈的混合策略纳什均衡，重点解决线性规划建模中目标函数方向、变量非负约束、不等式转化及可行性保障等关键问题。
本文详解如何用 scipy 的 `milp` 函数正确建模并求解二人零和博弈的混合策略纳什均衡，重点解决线性规划建模中目标函数方向、变量非负约束、不等式转化及可行性保障等关键问题。
在求解有限二人零和博弈的混合策略纳什均衡时，标准方法是将其转化为一个线性规划（LP）问题：最大化值 (v)（即博弈的值），使得对手任意纯策略下的期望收益不低于 (v)，同时保证策略向量 (\mathbf{x} = (x_1, \dots, x_n)) 是合法的概率分布（即 (x_i \geq 0) 且 (\sum_i x_i = 1)）。对于给定的收益矩阵 (M \in \mathbb{R}^{n \times n})，该 LP 可形式化为：
[ \begin{aligned} \max_{\mathbf{x},\, v} \quad & v \ \text{s.t.} \quad & M \mathbf{x} - v \cdot \mathbf{1} \geq \mathbf{0}, \ & \mathbf{1}^\top \mathbf{x} = 1, \ & \mathbf{x} \geq \mathbf{0}. \end{aligned} ]
⚠️ 注意：原代码中使用 linprog 并设置 A_eq 强制等式约束 Mx - v = 0 是错误的——这过度约束了问题，导致不可行（报错 Infeasible）；而纳什均衡要求的是不等式约束 Mx ≥ v·1（即无论对手选哪一行，己方收益都不低于 (v)），这才是支撑极小极大定理的基础。
此外，linprog 默认求解最小化问题，若要最大化 (v)，目标系数必须设为 -1（而非 +1）；同时，linprog 不支持混合约束类型（既有等式又有不等式）的简洁表达，易出错。推荐改用 SciPy 1.9+ 引入的更鲁棒、语义更清晰的 milp 接口（即使不启用整数变量，它也完美支持一般线性规划）。
以下为完整、可运行的正确实现：
import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint
def solve_nash_equilibrium(nash_array: np.ndarray) -> tuple[np.ndarray, float]:
"""
求解二人零和博弈的混合策略纳什均衡（行玩家视角）
Parameters:
-----------
nash_array : ndarray, shape (n, n)
行玩家的收益矩阵（即对手选第j列时，行玩家得分为 matrix[i,j]）
Returns:
--------
x : ndarray, shape (n,)
行玩家的最优混合策略（概率向量）
v : float
博弈值（行玩家可保证的最小期望收益）
"""
m, n = nash_array.shape
# 约束1：概率和为1 → sum(x) = 1
x_sum_constraint = LinearConstraint(
A=np.concatenate((np.ones(n), [0])), # [1,1,...,1,0] 作用于 [x; v]
lb=1.0, ub=1.0
)
# 约束2：对所有对手纯策略 i，有 (M x)_i >= v → M x - v * 1 >= 0
# A = [M | -ones(m,1)], 作用于 [x; v]
A_ineq = np.hstack((nash_array, -np.ones((m, 1))))
nash_constraint = LinearConstraint(
A=A_ineq,
lb=np.zeros(m) # 下界为 0，即 Mx - v >= 0
)
# 目标：maximize v → minimize -v
c = np.concatenate((np.zeros(n), [-1.0])) # [0,...,0,-1]
# 变量边界：x_i >= 0, v 无下界？但实践中 v 可为负，故仅需 x >= 0；v 自由
# 注意：Bounds(lb=0) 会将所有变量（含 v）下界设为 0 → 错误！
# 正确做法：为 x 设置 lb=0，v 不设下界（即 -np.inf）
bounds = Bounds(
lb=np.concatenate((np.zeros(n), [-np.inf])),
ub=np.concatenate((np.ones(n), [np.inf]))
)
# 求解（integrality 全为 0 → 实数 LP）
result = milp(
c=c,
constraints=(x_sum_constraint, nash_constraint),
bounds=bounds,
method='highs' # 推荐使用 HiGHS 求解器
)
if not result.success:
raise RuntimeError(f"LP 求解失败: {result.message}")
x_opt, v_opt = result.x[:-1], result.x[-1]
return x_opt, v_opt
# 示例：求解严格优势策略博弈
if __name__ == "__main__":
M = np.array([
[ 0, 1, 1, 1, 1],
[-1, 0, 1, 1, 1],
[-1, -1, 0, 1, 1],
[-1, -1, -1, 0, 1],
[-1, -1, -1, -1, 0]
])
x, v = solve_nash_equilibrium(M)
print(f"x = {np.round(x, 6)}") # [0. 0. 0. 0. 1.]
print(f"v = {v:.6f}") # ≈ 0.0（因最后一行全非负，纯策略即最优）✅ 关键修正点总结：
- ✅ 使用 milp 替代 linprog：支持统一接口定义等式/不等式约束，避免 A_eq/A_ub 混用错误；
- ✅ 目标函数系数为 [-1]（因 milp 默认最小化，最大化 (v) 需最小化 (-v)）；
- ✅ 约束类型正确：Mx ≥ v·1 是不等式约束（LinearConstraint + lb=0），非等式；
- ✅ 边界设置精准：仅对策略分量 (x_i) 施加 ([0,1]) 约束，(v) 应为自由变量（-np.inf 到 np.inf）；
- ✅ 概率和约束单独建模为 LinearConstraint，逻辑清晰、不易出错。
? 延伸提示：若结果出现多个非零概率（如 [0.2, 0, 0.8, 0, 0]），说明存在真正混合均衡；若输出为标准基向量（如 [0,0,0,0,1]），表明存在纯策略纳什均衡——这与示例矩阵最后一行完全占优（全 ≥ 0）的直觉完全一致。
通过以上规范建模，你可稳定、可解释地求解各类零和博弈的均衡策略，为博弈论分析与算法设计提供坚实基础。
