使用线性规划求解Minimax问题

最近工作中涉及到一个在零和博弈中求解Minimax的问题，算出的纯策略解效果并不好，于是想试试用线性规划来求解混合策略均衡解。

$$\log_{😄}😅=💧$$

线性规划主要解决的问题为：

$$\min_{x}c^Tx \quad \text{s.t.} \left \{\begin{array}{l} Ax\le b \\ A_{eq} x = b_{eq} \\ lb \le x \le ub \end{array}\right.,$$

其中$c$为价值向量，$A$和$b$为线性不等式约束，$A_{eq}$和$b_{eq}$为线性等式约束，$lb$和$ub$为变量下界和上界。

在Python中可以使用scipy.optimize.linprog来求解线性规划问题。

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='simplex', callback=None, options=None)

其中method是求解器的类型，比如单纯形法simplex。

案例：

$$\min_{x}f=-1 \times x_0 + 4 \times x_1 \\ \text{s.t.} \left\{\begin{array}{l} -3 \times x_0 + 1 \times x_1 \le 6 \\ 1 \times x_0 + 2 \times x_1 \le 4 \\ x_1 \ge -3 \end{array}\right.$$

用代码求解：

from scipy.optimize import linprog
c = [-1, 4]
A = [[-3, 1], [1, 2]]
b = [6, 4]
x0_bounds = (None, None)
x1_bounds = (-3, None)
res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds), method='simplex')

运行结果：

message: Optimization terminated successfully.
success: True
status: 0
    fun: -22.0
    x: [ 1.000e+01 -3.000e+00]
    nit: 5

最优解为$f=22$，$x_0=10$，$x_1=-3$。
对于最大值问题，只需将其转化为最小值问题即可。

Minimax问题

在零和博弈中，玩家的目标是最大化自己的收益，同时最小化对手的收益。换句话说，是在考虑对手选取其最优策略时，使其收益尽可能小，即求解双方收益的Minimax问题。

Maximin 和 Minimax 的区别

Maximin 和 Minimax 是博弈论和决策理论中两种基础策略，用于分析对抗性决策问题。它们的主要区别在于计算的目标和视角：

---

1. Maximin 策略

• 定义: 决策者假设对手会采取对自己最不利的策略，因此选择自己所有行动中收益的最小值中的最大值。

• 目标: 保证自己的“最坏情况”收益尽可能大。

• 步骤:

  1. 对于自己每个策略，计算在对手的所有可能反应下，自己能获得的最小收益。
  2. 从这些最小收益中选择最大值。

  数学表达:
  如果玩家 1 的收益矩阵为 ( M )，玩家 2 的策略为 ( j )，则：

  $$\text{Maximin} = \max_{i} \min_{j} M[i, j]$$

---

2. Minimax 策略

• 定义: 决策者假设对手会采取对自己最有利的策略，因此选择对手所有行动中收益的最大值中的最小值（即对手将最大化伤害自己）。

• 目标: 限制对手的“最优策略”给自己带来的损害。

• 步骤:

  1. 对于对手的每个策略，计算自己所有可能反应下对手能获得的最大收益。
  2. 从这些最大收益中选择最小值。

  数学表达:
  如果玩家 1 的收益矩阵为 (M )，玩家 1 的策略为 ( i )，则：

  $$\text{Minimax} = \min_{j} \max_{i} M[i,j]$$

---

直观理解

• Maximin: “我考虑所有最坏的可能情况，然后从中选择对我最不坏的一种策略。”
• Minimax: “我假设对手会选择最优策略来伤害我，然后我尽量限制对手的收益。”

---

无鞍点时:

• 如果博弈没有鞍点（例如收益矩阵不对称或无纯策略解），则 Maximin 和 Minimax 不相等。
  • 此时需要引入混合策略，通过概率分布计算期望收益，使得 Maximin 和 Minimax 相等（即纳什均衡）。

---

策略	目标	数学表达
Maximin	最大化自己在最坏情况下的收益	$\max_{i} \min_{j} A[i,j]$
Minimax	最小化对手在最优策略下能获得的收益（即限制对手的最大收益）	$\min_{j} \max_{i} A[i,j]$

对于零和博弈的Minimax问题，可以将其转化为线性规划问题来求解。
玩家1（最大化玩家）的线性规划形式：

$$\max _{x} v \text { s.t. }\left\{\begin{array}{ll} \sum_{i=1}^{n} x_{i} a_{i j} \geq v & \forall j \in\{1,2, \ldots, m\} \\ \sum_{i=1}^{n} x_{i}=1 & \\ x_{i} \geq 0 & \forall i \in\{1,2, \ldots, n\} \end{array}\right.$$

其中：

• $x = [x_1, x_2, \dots, x_n]$ 是玩家1的混合策略概率分布（需要满足非负性和总和为1的约束）。
• $a_{ij}$ 是收益矩阵，对应玩家1在策略$i$和玩家2在策略$j$时的收益。
• $v$ 是玩家1的最小收益（即最大化的目标）。

玩家2（最小化玩家）的线性规划形式可以表示为：

$$\min _{y} w \text { s.t. }\left\{\begin{array}{ll} \sum_{j=1}^{m} y_{j} a_{i j} \leq w & \forall i \in\{1,2, \ldots, n\} \\ \sum_{j=1}^{m} y_{j}=1 & \\ y_{j} \geq 0 & \forall j \in\{1,2, \ldots, m\} \end{array}\right.$$

其中：

• $y = [y_1, y_2, \dots, y_m]$ 是玩家2的混合策略概率分布。
• $w$ 是玩家2的最大收益（即最小化的目标）。

将两者统一为一个线性规划问题

通过对偶性原理，零和博弈的 Minimax 问题可以简化为单个线性规划问题。这里以玩家1为主的最大化问题为例，将其转化为标准的线性规划问题：

$$\min _{v',x} v' \text { s.t. }\left\{\begin{array}{ll} -\sum_{i=1}^{n} x_{i} a_{i j} \leq v' & \forall j \in\{1,2, \ldots, m\} \\ \sum_{i=1}^{n} x_{i}=1 & \\ x_{i} \geq 0 & \forall i \in\{1,2, \ldots, n\} \end{array}\right.$$

其中$v'$即为玩家1的最小收益的相反数。

示例代码

假设收益矩阵为：

$$A = \begin{bmatrix} 3 & 2 &1 \\ 0 & 1 &4 \end{bmatrix}$$

其中，玩家 1 有 2 种策略，玩家 2 有 3 种策略。通过线性规划求解玩家 1 的最优混合策略及其最小收益。
玩家1的最大化问题是：

$$\max_{v,x}v \quad \text{s.t.}\left\{\begin{array}{l} 3x_1+0x_2\geq v \\ 2x_1+1x_2\geq v\\ 1x_1+4x_2\geq v\\ x_1+x_2=1\\ x_1\geq 0, x_2 \geq 0 \end{array}\right.$$

通过上述统一式，将其转化为标准形式：

$$\min_{v',x}v' \quad \text{s.t.}\left\{\begin{array}{l} -3x_1-0x_2\leq v' \\ -2x_1-1x_2\leq v'\\ -1x_1-4x_2\leq v'\\ x_1+x_2=1\\ x_1\geq 0, x_2 \geq 0 \end{array}\right.$$

使用Python中的scipy.optimize.linprog求解：

• c 为目标函数系数，这里为 $[0, 0, 1]$。
• A_ub 为不等式约束系数矩阵，这里为 $[[-3, 0, -1], [-2, -1, -1], [-1, -4, -1]]$。
• b_ub 为不等式约束右侧常数向量，这里为 $[0, 0, 0]$。
• A_eq 为等式约束系数矩阵，这里为 $[[1, 1, 0]]$。
• b_eq 为等式约束右侧常数向量，这里为 $[1]$。
• bounds 为变量的上下界，这里为 $[(0, None), (0, None), (None, None)]$。

from scipy.optimize import linprog
import numpy as np

# 玩家 1 的收益矩阵
A = [[3, 2, 1],
     [0, 1, 4]]

# 矩阵转置以满足线性不等式 -A^T*x-v <= 0 的形式
A_ub = -1 * np.array(A).T  # 转置后取负号
A_ub = np.c_[A_ub, -1 * np.ones(len(A[0]))]
b_ub = [0] * len(A[0])    # 对应每列的约束

# x 的线性规划约束
c = [0, 0, 1]             # 最小化 v
A_eq = [[1, 1, 0]]         # x1 + x2 = 1
b_eq = [1]                 # 概率和为 1
bounds = [(0, None), (0, None), (None, None)]  # x1, x2 >= 0，v无上下界约束

# 使用线性规划求解
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='simplex')

# 输出结果
print("Optimal value (v):", -res.fun)
print("Optimal strategy for Player 1 (x):", res.x[:2])

输出：

Optimal value (v): 1.75
Optimal strategy for Player 1 (x): [0.75 0.25]

即玩家1的最优混合策略为$[0.75, 0.25]$，最小期望收益为$1.75$。