使用Scipy求解纳什均衡线性方程组遇问题求助

问题分析 #

你遇到的问题源于线性规划模型的错误构建，主要包括约束条件类型错误、约束方向颠倒、目标函数设置不当以及变量边界限制不合理。以下是具体问题和修正方案：

原代码的核心错误 #

1. 目标函数错误：linprog 默认执行最小化，但你试图直接最大化v，需改为最小化 -v（等价于最大化v）。
2. 约束类型错误：将应设为不等式的约束（sum(...) ≥ v）错误地设为等式约束，导致模型不可行。
3. 约束方向颠倒：针对行而非列构建约束（求解行玩家策略时，需保证对所有列策略的期望收益≥v）。
4. 变量边界限制：不必要地限制v的范围为(0,2)，可能排除有效解。
5. 硬编码v值：错误地将max_v设为1，应使用求解器返回的v值。

修正后的代码 #

import numpy as np
from scipy.optimize import linprog

def solve_nash_equilibrium(NashArray):
    n = NashArray.shape[0]

    # 目标函数：最大化v → 转化为最小化 -v
    c = np.zeros(n + 1)
    c[-1] = -1  # v的系数为-1

    # 不等式约束：对每个列j，sum(x_i * NashArray[i][j]) ≥ v → 转化为 -sum(x_i * NashArray[i][j]) + v ≤ 0
    A_ub = np.hstack((-NashArray.T, np.ones((n, 1))))
    b_ub = np.zeros(n)

    # 等式约束：概率和为1
    A_eq = np.ones((1, n + 1))
    A_eq[0, -1] = 0  # v不参与求和
    b_eq = np.array([1])

    # 变量边界：x_i为概率（0到1），v无限制
    x_bounds = [(0, 1)] * n
    v_bounds = (-np.inf, np.inf)
    bounds = x_bounds + [v_bounds]

    # 求解线性规划
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)

    if result.success:
        strategy = result.x[:-1]
        game_value = result.x[-1]
        # 处理数值精度问题，将极小值近似为0
        strategy = np.round(strategy, decimals=6)
        print("行玩家的最优策略：", strategy)
        print("游戏价值v：", game_value)
        return strategy
    else:
        print("求解失败：", result.message)
        return None

# 测试用例
NashArray = 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]
])

solve_nash_equilibrium(NashArray)

代码说明 #

1. 目标函数：通过将v的系数设为-1，把最大化v转化为linprog支持的最小化问题。
2. 不等式约束：针对每个列构建约束，确保行玩家的期望收益不低于v，转化为线性规划要求的≤形式。
3. 等式约束：保证策略的概率和为1。
4. 变量边界：放开v的限制，允许其取任意实数，符合游戏价值的实际可能范围。
5. 数值精度处理：对结果进行四舍五入，避免因求解器数值误差导致的极小非零值。

运行修正后的代码，将输出预期的最优策略[1. 0. 0. 0. 0.]和游戏价值0.0。

内容的提问来源于stack exchange，提问作者James Serrano