给定m*n收益矩阵,推导二人零和博弈的混合策略均衡等价于一个线性规划问题以及对应对偶问题的意义

二人零和博弈的混合策略均衡等价于一个线性规划问题。具体来说，给定一个$m \times n$的收益矩阵$A$，其中$A_{i,j}$表示玩家1采取策略$i$，玩家2采取策略$j$时的收益。我们可以将玩家1的策略表示为一个概率分布向量$x \in \mathbb{R}^m$，其中$x_i$表示玩家1采取策略$i$的概率；类似地，我们可以将玩家2的策略表示为一个概率分布向量$y \in \mathbb{R}^n$，其中$y_j$表示玩家2采取策略$j$的概率。

对于任意一组策略$(x,y)$，玩家1的收益为$x^T A y$，玩家2的收益为$-x^T A y$，因为这是一个零和博弈。因此，玩家1的最大收益是：

$$\max_{x} \min_{y} x^T A y$$

玩家2的最大收益是：

$$\min_{y} \max_{x} x^T A y$$

这两个问题等价，因为它们都是同一个博弈的不同表达方式。这个博弈的混合策略均衡就是这两个问题的解。我们可以将这两个问题转化为标准的线性规划问题：

$$\max_{x} \ \ \ \min_{y} \ \ x^T A y$$

$$\text{s.t.} \ \ \ x \geq 0, \ \sum_{i=1}^{m} x_i = 1$$

$$\text{s.t.} \ \ \ y \geq 0, \ \sum_{j=1}^{n} y_j = 1$$

和

$$\min_{y} \ \ \ \max_{x} \ \ x^T A y$$

$$\text{s.t.} \ \ \ x \geq 0, \ \sum_{i=1}^{m} x_i = 1$$

$$\text{s.t.} \ \ \ y \geq 0, \ \sum_{j=1}^{n} y_j = 1$$

这两个问题的对偶问题分别为：

$$\min_{y} \ \ \ \max_{x} \ \ x^T A y$$

$$\text{s.t.} \ \ \ x \geq 0, \ \sum_{i=1}^{m} x_i = 1$$

$$\text{s.t.} \ \ \ y \geq 0, \ A^T y \leq 0$$

和

$$\max_{x} \ \ \ \min_{y} \ \ x^T A y$$

$$\text{s.t.} \ \ \ x \geq 0, \ A x \geq 0$$

$$\text{s.t.} \ \ \ y \geq 0, \ \sum_{j=1}^{n} y_j = 1$$

这里的意义是，对偶问题的解给出了原始问题的解的下界或上界。在这个博弈中，对偶问题的解给出了玩家1和玩家2的最小收益和最大收益，因此，如果对偶问题的解是相等的，那么这个博弈有一个纯策略均衡。如果对偶问题的解是不相等的，那么这个博弈的混合策略均衡就是对偶问题的解。