尝试使用 scipy 求解线性方程组但遇到麻烦

Question

尝试求解纳什均衡

我试图解决的数组是：

[[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]]

我知道 [0][0] 处存在平衡

我希望输出生成一个数组 [1, 0, 0, 0, 0]，显示最佳策略是在索引 0 处移动

看幻灯片，我们应该建立一个线性方程组来最大化 V 使得

0 * x1 + 1 * x2 + 1 * x3 + 1 * x4 + 1 * x5 - v >=0 对于第 1 行，对所有行重复。另外，x1 到 xn 的总和为 1。

我尝试使用 scipy 建立线性方程组，但总是收到错误消息或错误。现在我得到“优化失败：问题不可行。（HiGHS 状态 8：model_status 不可行；primal_status 处于下限/固定边界”

但之前我得到了一个 [0 0 0 0 0] 数组，这显然是无意义的，因为玩家必须采取行动，而且我曾经得到过一个 [1 -1 1 -1 1] 数组，它确实解决了系统线性方程，但我不希望 xn 为负数，因为它们代表概率

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

        # Coefficients for the objective function (maximizing v)
        c = np.zeros(n + 1)
        c[-1] = 1  # Coefficient for v (to maximize)

        # Coefficients for the equality constraints (M * x + v == 0)
        A_eq = np.hstack((NashArray, -np.ones((n, 1))))  # Coefficients for x and v
        b_eq = np.zeros(n)  # Right-hand side of the equalities

        # Additional equality constraint: sum of probabilities equals 1
        A_eq_sum = np.ones((1, n + 1))
        b_eq_sum = np.ones(1)

        # Stack the new equality constraint with the existing ones
        A_eq = np.vstack((A_eq, A_eq_sum))
        A_eq[-1][-1] = 0
        print(A_eq)
        b_eq = np.hstack((b_eq, b_eq_sum))
        print(b_eq)

        # Bounds for each variable (x and v)
        x_bounds = [(0, 1)] * n  # Players can choose any probability distribution
        v_bounds = (0, 2)  # v can take any value

        # Concatenate bounds for x and v
        bounds = x_bounds + [v_bounds]

        # Solve the linear programming problem

        result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=[*x_bounds, v_bounds])

        # Extract the solution
        if result.success:
            strategy = result.x[:-1]  # Extract mixed strategy for each player
            max_v = 1  # Maximum value of v (the value of the game)

            print("Mixed strategy for each player:", strategy)
            print("Value of the game (maximum v):", max_v)
            return strategy
        else:
            print("Optimization failed:", result.message)
            return None

Answer 1

使用

milp

代替

linprog

；还值得注意的是，最大化需要系数为-1。由于 v=0，这可能仍然没有多大意义，但这可能是您的定义中的问题（v 应该是向量吗？）

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint


def solve_nash_equilibrium(nash_array: np.ndarray) -> tuple[
    np.ndarray,
    float,
]:
    m, n = nash_array.shape

    # sum(x) = 1
    x_sum = LinearConstraint(
        A=np.concatenate((np.ones(n), (0,))),
        lb=1, ub=1,
    )
    
    # nash_array.x - v >= 0
    nash_constraint = LinearConstraint(
        A=np.hstack((nash_array, -np.ones((m, 1)))),
        lb=0,
    )

    result = milp(
        # Maximize v
        c=np.concatenate((np.zeros(n), (-1,))),
        integrality=np.zeros(n + 1, dtype=np.uint8),
        bounds=Bounds(lb=0),
        constraints=(x_sum, nash_constraint),
    )
    if not result.success:
        raise ValueError(result.message)
    x, (v,) = np.split(result.x, (-1,))
    return x, v


def demo() -> None:
    x, v = solve_nash_equilibrium(
        nash_array=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),
        )),
    )
    print('x =', x)
    print('v =', v)


if __name__ == '__main__':
    demo()

x = [0. 0. 0. 0. 1.]
v = -0.0