矩阵对策问题及其解法

背景

对策论研究具有竞争性质的现象。有权决定自身行为的对策参加者称为局中人，所有局中人构成集合 \(I\)，在一局对策中可供剧中人选择的一个实际可行的完整的行动方案成为策略，对于任意剧中人 \(i \in I\)，都有自己的策略集 \(S_i\)。一局对策中由各剧中人选定的策略构成的策略组称为局势 \(s=(s_1,...,s_n)\)，而全体局势集合 \(S=S_1\times ... \times S_n\)。

局势决定了对策的结果，对局势 \(s \in S\)，局中人 \(i\) 可以得到收益 \(H_i(s)\)，也称为局中人 \(i\) 的赢得函数。

矩阵对策即二人有限零和对策，是一类较为简单的对策模型。

矩阵对策基础

我们假设，局中人 I 有纯策略 \(\alpha_1,...,\alpha_m\)，局中人 II 有纯策略 \(\beta_1,...,\beta_n\)，二者各选择一个纯策略则构成 \(m\times n\) 个纯局势 \((\alpha_i, \beta_j)\)，将 \((\alpha_i,\beta_j)\) 下 I 的赢得值记为 \(a_{i,j}\)，设矩阵 \(A=[a_{i,j}]\)，称为 I 的赢得矩阵或 II 的支付矩阵。局中人 II 的赢得矩阵就是 \(-A^T\)。

最优纯策略

若纯局势 \((a_{i^*},b_{j^*})\) 满足

\[\displaystyle\max_i\min_ja_{i,j} = \min_j\max_ia_{i,j}=a_{i^*,j^*} \]

则称为矩阵对策 \(\{ S_1,S_2;A \}\) 的最优纯策略。显然，最有纯策略在赢得矩阵中对应的元素一定满足，其是所在行的最小元素，也是所在列的最大元素，即矩阵的鞍点。

混合策略

当纯策略不存在时，我们希望给出一个选取不同策略的概率分布。我们记 I,II 的概率分布向量分别为 \(x,y\)，所有概率分布向量构成的集合为 \(S_1,S_2\)，则局中人 I 的赢得函数为 \(E(x,y)=x^TAy\)。纯策略是混合策略的特例。

若混合局势 \((x^*,y^*)\) 满足

\[\displaystyle\max_x\min_yE(x,y) = \min_y\max_xE(x,y) = E(x^*,y^*) \]

则称为矩阵对策 \(\{ S_1,S_2;A \}\) 的最优混合策略。同样，混合策略 \((x^*,y^*)\) 是最有混合策略的充要条件也是 \((x^*,y^*)\) 是函数 \(E(x,y)\) 的鞍点。

可以证明，任意矩阵对策一定存在混合策略意义下的解。

超优原则

若矩阵 \(A\) 中第 \(i\) 行元素均不小于第 \(j\) 行对应元素，则称 I 的纯策略 \(a_i\) 超优于 \(a_j\)。推广一下，超优者也可以是若干纯策略的线性组合。

如果局中人 I 的纯策略 \(a_i\) 被其它纯策略或若干纯策略的线性组合超优时，可以将 \(a_i\) 删去而不影响结果，称为超优原则。超优原则在一些情况下可以简化计算。

矩阵对策的解法

公式法

公式法用于求解 \(2\times 2\) 矩阵对策问题。

考虑当 \(A\) 没有鞍点时，如何求解最优混合策略。因为没有鞍点，所以对于 I 的行动，有

\[a_{11}x_1+a_{21}x_2=a_{12}x_1+a_{22}x_2=v, \quad x_1+x_2=1 \]

对 II 也是同理。在没有鞍点的条件下方程组一定严格非负解。

图解法

图解法用于求解 \(2\times n\) 或 \(m\times 2\) 矩阵对策问题。

对于一个 \(2\times n\) 的矩阵对策问题，考虑局中人 I 的混合策略 \((x,1-x)^T, x \in [0,1]\)，过数轴上 \((0,0),(1,0)\) 分别作垂线一条，垂线上点的纵坐标值分别表示局中人 I 采取纯策略 \(\alpha_1=(1,0)^T, \alpha_2=(0,1)^T\) 时，I 的赢得值。

当局中人 I 选择每一策略 \((x,1-x)^T\) 时，他最少可能收入为所有局中人 II 选择确定的若干条直线在 \(x\) 处的纵坐标的最小者。要使得 I 在最坏情况下的收入尽可能多，它应当使得直线 \(x\) 与那若干条直线交出的点的纵坐标最小值最大。这转化成了一个非常直观的问题，作出若干条直线，列方程求解交点坐标，原问题得以解决。

现在考虑 \(m\times 2\) 的矩阵对策问题，我们将局中人 I 的 \(m\) 种纯策略作出直线，然后考虑每个横坐标处的交点最大值即可。

先前提到的超优原则在图解法上的体现则更加直观。对于 \(2\times n\) 矩阵对策问题，若 II 的纯策略 \(\beta_i\) 超优于 \(\beta_j\)，则 \(i\) 所对应的线段始终不出现在 \(j\) 的上方。此时它对求解最大的最小值没有任何影响，因此可以删去。当然，删去后虽然最优解的值不变，但可能会导致解集变小。

线性方程组法

线性方程组法是对公式法的推广 ，即将 \(2\times 2\) 推广到 \(m \times n\) 的情形，其思路是相同的，在此不作赘述。

线性规划方法

根据

\[\sum_i a_{ij}x_i \ge v, \quad \sum_i x_i =1, \quad x_i \ge 0 \]

以及

\[\sum_j a_{ij} y_j \le v,\quad \sum_j y_j=1, \quad y_j \ge 0 \]

对其进行变换，令 \(x_i'=x_i/v, y_j'=y_j/v\)，得线性规划问题 P

\[\min z=\sum_i x_i',\quad \sum_i a_{ij}x_i'\ge 1, \quad x_i'\ge 0 \]

对后者进行变换可得其对偶问题 D。

一般先求问题 D 的解，而问题 P 的解可以从问题 D 的解的最后一个单纯形表上得到。