0

我正在尝试解决零和游戏，为玩家 I 找到最佳概率分布。为此，我使用 scipy linprog simplex 方法。

我看过一个例子，我需要改造这个游戏：

G=np.array([
[ 0  2 -3  0]
[-2  0  0  3]
[ 3  0  0 -4]
[ 0 -3  4  0]])

进入这个线性优化问题：

Maximize           z
Subject to:               2*x2 - 3*x3        + z <= 0
                  -2*x1 +             + 3*x4 + z <= 0
                   3*x1 +             - 4*x4 + z <= 0
                        - 3*x2 + 4*x3        + z <= 0
with              x1 + x2 + x3 + x4 = 1

这是我的实际代码：

def simplex(G):
    (n,m) = np.shape(G)

    A_ub = np.transpose(G)
    # we add an artificial variable to maximize, present in all inequalities
    A_ub = np.append(A_ub, np.ones((m,1)), axis = 1)
    # all inequalities should be inferior to 0
    b_ub = np.zeros(m)

    # the sum of all variables except the artificial one should be equal to one
    A_eq = np.ones((1,n+1))
    A_eq[0][n] = 0
    b_eq = np.ones(1)

    c = np.zeros(n + 1)
    # -1 to maximize the artificial variable we're going to add
    c[n] = -1

    res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0,None))

    return (res.x[:-1], res.fun)

这是我得到的分布： [5.87042987e-01 1.77606350e-10 2.79082859e-10 4.12957014e-01] 总和为 1，但我希望 [0 0.6 0.4 0]

我正在尝试一个带有 6 或 7 行（以及变量）的大型游戏，它甚至不等于 1.. 我做错了什么？

感谢您提供的任何帮助。

4

2 回答 2

2

（我想玩家 1（行玩家）正在最大化，玩家 2（列玩家）正在最小化。）

在这个博弈的纳什均衡中，玩家 1 的策略是任何[0, x2, x3, 0], 。4/7 <= x2 <= 3/5x2 + x3 = 1

在您的代码中，您缺少不等式约束的负号-G.T x + z <= 0。试试下面的代码：

def simplex(G, method='simplex'):
    (n,m) = np.shape(G)

    A_ub = -np.transpose(G)  # negative sign added
    # we add an artificial variable to maximize, present in all inequalities
    A_ub = np.append(A_ub, np.ones((m,1)), axis = 1)
    # all inequalities should be inferior to 0
    b_ub = np.zeros(m)

    # the sum of all variables except the artificial one should be equal to one
    A_eq = np.ones((1,n+1))
    A_eq[0][n] = 0
    b_eq = np.ones(1)

    c = np.zeros(n + 1)
    # -1 to maximize the artificial variable we're going to add
    c[n] = -1

    res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0,None),
                  method=method)  # `method` option added

    return (res.x[:-1], res.fun)

使用单纯形法：

simplex(G, method='simplex')

(array([0.        , 0.57142857, 0.42857143, 0.        ]), 0.0)
# 4/7 = 0.5714285...

用内点法：

simplex(G, method='interior-point')

(array([1.77606350e-10, 5.87042987e-01, 4.12957014e-01, 2.79082859e-10]),
 -9.369597151936987e-10)
# 4/7 < 5.87042987e-01 < 3/5

使用修改后的单纯形法：

simplex(G, method='revised simplex')

(array([0. , 0.6, 0.4, 0. ]), 0.0)
# 3/5 = 0.6

（使用 SciPy v1.3.0 运行）

于 2019-08-16T02:33:05.133 回答
0

自从找到解决方案后，我还没有更新帖子。我建议不要使用 Scipy linprog 函数，如果您对线性规划知之甚少，它的文档记录很糟糕，而且我发现它在许多示例中不精确且不一致（当时我确实尝试添加负号，如建议的那样奥亚马德）。

我切换到 PuLP python 库，从一开始就获得一致的结果没有问题。

于 2019-08-17T15:37:58.937 回答