尝试使用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，其他行也要重复这个过程。同时，x1到xn的总和要等于1。

我尝试用scipy来建立这个线性方程组，但总是得到错误信息或者出错。目前我得到的提示是“优化失败：问题不可行。（HiGHS状态8：模型状态不可行；原始状态在下限/固定边界）”。

之前我得到了一个数组[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