使用 SciPy 求解零和博弈纳什均衡的正确建模与实现-Python教程-PHP中文网

使用 SciPy 求解零和博弈纳什均衡的正确建模与实现

本文详解如何用 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（因最后一行全非负，纯策略即最优）

✅ 关键修正点总结：