【数学建模算法】(21)对策论（上）

2019-08-20 本文已影响0人热爱学习的高老板

对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。

在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。

1.对策问题

对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。
先看一个大家都熟悉的例子。

例1 （囚徒困境）警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑 18 个月；如果双方都供认伪造了钱币，将各被判刑 3 年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑 7 年。将嫌疑犯 A 、 B 被判刑的几种可能情况列于表 1。

表1 各种情况对应的判刑年数

	供认	不供认
供认	（3,3）	（0,7）
不供认	（7,0）	（1.5,1.5）

我们从这个问题中看一看对策问题的基本要素

1.1.对策的基本要素

1.1.1.局中人

在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局中人。通常用 $I$ 表示局中人的集合．如果有 $n$ 个局中人，则 $I=\{1,2, \cdots, n\}$ 。一般要求一个对策中至少要有两个局中人。在例 1 中，局中人是 $A,B$ 两名疑犯。

1.1.2.策略集

一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人 $i, \quad i \in I$ ，都有自己的策略集 $S_{i}$ 。一般，每一局中人的策略集中至少应包括两个策略。

1.1.3.赢得函数（支付函数）

再一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若 $s_{i}$ 是第 $i$ 个局中人的一个策略，则 $n$ 个局中人的策略组
$S=\left(S_{1}, S_{2}, \cdots, S_{n}\right)$
就是一个局势。全体局势的集合 $S$ 可用各局中人策略集的笛卡尔积表示，即：
$S=S_{1} \times S_{2} \times \cdots \times S_{n}$
当局势出现后，对策的结果也就确定了。也就是说，对任一局势， $s \in S$ ，局中人 $i$ 可以得到一个赢得 $H_{i}(s)$ 。显然， $H_{i}(s)$ 是局势 $s$ 的函数，称之为第 $i$ 个局中人的赢得函数。这样，就得到一个向量赢得函数 $H(s)=\left(H_{1}(s), \cdots, H_{n}(s)\right)$ 。
本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中去。

1.2.零和对策（矩阵对策）

零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。
设局中人Ⅰ，Ⅱ的策略集分别为：
$S_{1}=\left\{\alpha_{1}, \cdots, \alpha_{m}\right\}, S_{2}=\left\{\beta_{1}, \cdots, \beta_{n}\right\}$
当局中人Ⅰ选定策略 $\alpha_{i}$ 和局中人Ⅱ选定策略 $\beta_{j}$ 后，就形成了一个局势 $\left(\alpha_{i}, \beta_{j}\right)$ ，可见这样的局势共有 $mn$ 个。对任一局势 $\left(\alpha_{i}, \beta_{j}\right)$ ，记局中人Ⅰ的赢得值为 $a_{i j}$ ，并称：
$A=\left[\begin{array}{llll}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} \\ {a_{21}} & {a_{22}} & {\cdots} & {a_{2 n}} \\ {\cdots} & {\cdots} & {\cdots} & {\cdots} \\ {a_{m 1}} & {a_{m 2}} & {\cdots} & {a_{m n}}\end{array}\right]$
为局中人Ⅰ的赢得矩阵（或为局中人Ⅱ的支付矩阵）。由于假定假定对策为零和的，故局中人Ⅱ的赢得矩阵就是 $-A$ ，一个零和对策就给定了，零和对策又可称为矩阵对策并可简记成：
$G=\left\{S_{1}, S_{2} ; A\right\}$

例2 设有一矩阵对策 $G=\left\{S_{1}, S_{2} ; A\right\}$ ，其中 $S_{1}=\left\{\alpha_{1}, \alpha_{2}, \alpha_{3}\right\}$ ， $S_{2}=\left\{\beta_{1}, \beta_{2}, \beta_{3}, \beta_{4}\right\}$
$A=\left[\begin{array}{cccc}{12} & {-6} & {30} & {-22} \\ {14} & {2} & {18} & {10} \\ {-6} & {0} & {-10} & {16}\end{array}\right]$

从 $A$ 中可以看出，若局中人Ⅰ希望获得最大盈利30，需采用策略 $\alpha_{1}$ ，但此时若局中人Ⅱ采用策略 $\beta_{4}$ ，局中人Ⅰ采取策略 $\alpha_{1}, \alpha_{2}, \alpha_{3}$
时，最坏的赢得结果分别是：
$\min \{12,-6,30,-22\}=-22$
$\min \{14,2,18,10\}=2$
$\min \{-6,0,-10,16\}=-10$
其中最好的可能为 $\max \{-22,2,-10\}=2$ 。如果局中人Ⅰ采取策略 $\alpha_{2}$ ，无论局中人Ⅱ采取什么策略，局中人Ⅰ的赢得君不悔少于2.
局中人Ⅱ采取各方案的最大损失为 $\max \{12,14,-6\}=14, \quad \max \{-6,2,0\}=2$ ， $\max \{30,18,-10\}=30$ ，和 $\max \{-22,10,16\}=16$ 。当局中人Ⅱ采取策略 $\beta_{2}$ ，其损失不会超过2。注意到在赢得矩阵矩阵，2即是所在航中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减少损失，成这样的局势为对策的一个稳定点或稳定解。

定义1 设 $f(x, y)$ 为一个定义在 $x \in A$ 及 $y \in B$ 上的实值函数，如果存在 $x^{*} \in A$ ， $y^{*} \in B$ ，使得对一切
$x \in A$ 和 $y \in B$ 有：
$f\left(x, y^{*}\right) \leq f\left(x^{*}, y^{*}\right) \leq f\left(x^{*}, y\right)$
则称 $\left(x^{*}, y^{*}\right)$ 为函数 $f$ 的一个鞍点。

定义2 设 $G=\left\{S_{1}, S_{2} ; A\right\}$ 为矩阵对策，其中 $S_{1}=\left\{\alpha_{1}, \alpha_{2}, \cdots, \alpha_{m}\right\}$ ， $S_{2}=\left\{\beta_{1}, \beta_{2}, \cdots, \beta_{n}\right\}, \quad A=\left(a_{i j}\right)_{m \times n}$ 。若等式
$\max _{i} \min _{j} a_{i j}=\min _{j} \max _{i} a_{i j}=a_{i^{*} j^{*}}（1）$
成立，记 $V_{G}=a_{i^{*} j^{*}}$ ，则称 $V_{G}$ 为对策 $G$ 的值，称使（1）式成立的纯局势 $\left(\alpha_{i^{*}}, \beta_{j^{*}}\right)$ 为对策 $G$ 的鞍点或稳定解，赢得矩阵中与 $\left(\alpha_{i}, \beta_{j^{*}}\right)$ 相对应的元素 $a_{i^{*} j^{*}}$ 称为赢得矩阵的鞍点， $\alpha_{i^{*}}$ 与 $\beta_{j}$ 分别称为局中人Ⅰ和Ⅱ的最优纯策略。

给定一个对策 $G$ ，如何判断它是否有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。

定理1 设 $G=\left\{S_{1}, S_{2} ; A\right\}$ ，记 $\mu=\max _{i} \min a_{i j}, \quad v=-\min _{j} \max a_{i j}$ ，则必有 $\mu+v \leq 0$

定理2 零和策略 $G$ 具有稳定解的充要条件是 $\mu+v=0$

2.零和定理的混合策略

具有稳定解的零和问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是
$\mu+v \neq 0$ 的情况。由于矩阵中不存在鞍点，此时在只使用纯策略的范围内，对策问题无解，下面我们引进零和对策的混合策略。

设局中人Ⅰ用概率 $x_{i}$ 选用策略 $\alpha_{i}$ ，局中人Ⅱ用概率 $\mathcal{Y}$ 选用策略 $\beta_{j}$ ， $\sum_{i=1}^{m} x_{i}=\sum_{j=1}^{n} y_{j}=1$ ，记 $x=\left(x_{1}, \cdots, x_{m}\right)^{T}, \quad y=\left(y_{1}, \cdots, y_{n}\right)^{T}$ ，则局中人Ⅰ的期望赢得为 $E(x, y)=x^{T} A y$ ，简单记：
$S_{1}^{*}=\left\{\left(x_{1}, \cdots, x_{m}\right)^{T} | x_{i} \geq 0, i=1, \cdots, m ; \sum_{i=1}^{m} x_{i}=1\right\}$
$S_{2}^{*}=\left\{\left(y_{1}, \cdots, y_{n}\right)^{T} | y_{j} \geq 0, j=1, \cdots, n ; \sum_{i=1}^{n} y_{j}=1\right\}$

定义3 若存在 $m$ 维向量 $\overline{x}$ 和 $n$ 维向量 $\overline{y}$ ，使得对一切 $m$ 维向量 $x$ 和 $n$ 维向量 $y$ 有：
$\overline{x}^{T} A \overline{y}=\max _{x} x^{T} A \overline{y}=\min _{y} \overline{x}^{T} A y$
则称 $(\overline{x}, \overline{y})$ 为混合策略对策问题的鞍点。

定理3 设 $\overline{x} \in S_{1}^{*}, \quad \overline{y} \in S_{2}^{*}$ ，则 $(\overline{x}, \overline{y})$ 为 $G=\left\{S_{1}, S_{2} ; A\right\}$ 的解的充要条件是：
$\left\{\begin{array}{ll}{\sum_{j=1}^{n} a_{i j} \overline{y}_{j} \leq \overline{x}^{T} A \overline{y},} & {i=1,2, \cdots, m} \\ {\sum_{i=1}^{m} a_{i j} \overline{x}_{i} \geq \overline{x}^{T} A \overline{y},} & {j=1,2, \cdots, n}\end{array}\right.$

定理4 任意混合策略对策问题必存在鞍点，即必存在概率向量 $\overline{x}$ 和 $\overline{y}$ ，使得：
$\overline{x}^{T} A \overline{y}=\max _{x} \min _{y} x^{T} A y=\min _{y} \max _{x} x^{T} A y$

使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策问题的特殊情况，相当于以概率 1 选取其中某一策略，以概率 0 选取其余策略。

例3 $A,B$ 为作战双方， $A$ 方拟派两架轰炸机Ⅰ和Ⅱ去轰炸 $B$ 方的指挥部，轰炸机Ⅰ在前面飞行，Ⅱ随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰炸机飞至 $B$ 方上空，受到 $B$ 方战斗机的阻击。若战斗机阻击后面的轰炸机Ⅱ，它仅受Ⅱ的射击，被击中的概率为0.3（Ⅰ来不及返回攻击它）。一旦战斗机未被击中，他将以0.6的概率击毁其选中的轰炸机。请为 $A,B$ 双方各选择一个最优策略，即，对于A方应该选择哪一架轰炸机装载炸弹？对于 $B$ 方战斗机应阻击哪一架轰炸机？

解：双方可选择的策略集分别是：
$S_{A}=\left\{\alpha_{1}, \alpha_{2}\right\}, \quad \alpha_{1} :$ 轰炸机Ⅰ装炸弹，Ⅱ护航。
$\quad \quad \quad \quad \quad\quad \quad \quad \alpha_{2}：$ 轰炸机Ⅱ装炸弹，Ⅰ护航。

赢得矩阵 $R=\left(a_{i j}\right)_{2 \times 2}$ ， $a_{i j}$ 为 $A$ 方采取策略 $\alpha_{i}$ 而 $B$ 方采取策略 $\beta_{j}$ 时，轰炸机轰炸 $B$ 方指挥部的概率，由题意可计算出：
$a_{11}=0.7+0.3(1-0.6)=0.82$
$a_{12}=1, \quad a_{21}=1$
$a_{22}=0.3+0.7(1-0.6)=0.58$
即赢得矩阵：
$R=\left[\begin{array}{cc}{0.82} & {1} \\ {1} & {0.58}\end{array}\right]$
易求得 $\mu=\max _{i} \min a_{i j}=0.82, \quad v=-\min _{i} \max _{i} a_{i j}=-1$ 。由于 $\mu+v \neq 0$ ，矩阵 $R$ 不存在鞍点，应当求最佳混合策略。

现设 $A$ 以概率 $x_{1}$ 取策略 $\alpha_{1}$ ，以概率 $x_{2}$ 取策略 $\alpha_{2}$ ； $B$ 以概率 $y_{1}$ 取策略 $\beta_{1}$ ，以概率 $y_{2}$ 取策略 $\beta_{2}$ 。

先从 $B$ 方来考虑问题。 $B$ 采用 $\beta_{1}$ 时， $A$ 方轰炸机攻击指挥部的概率期望值为 $E\left(\beta_{1}\right)=0.82 x_{1}+x_{2}$ ，而 $B$ 采用 $\beta_{2}$ 时， $A$ 方轰炸机攻击指挥部的概率的期望值为 $E\left(\beta_{2}\right)=x_{1}+0.58 x_{2}$ 。若 $E\left(\beta_{1}\right) \neq E\left(\beta_{2}\right)$ ，不妨设 $E\left(\beta_{1}\right)<E\left(\beta_{2}\right)$ ，则 $B$ 方必采用 $E\left(\beta_{1}\right)<E\left(\beta_{2}\right)$ ，则 $B$ 方必采用 $\beta_{1}$ 以减少指挥部被轰炸的概率。故对 $A$ 方选取的最佳概率 $x_{1}$ 和 $x_{2}$ ，必满足：
$\left\{\begin{array}{l}{0.82 x_{1}+x_{2}=x_{1}+0.58 x_{2}} \\ {x_{1}+x_{2}=1}\end{array}\right.$
即：
$\left\{\begin{array}{l}{a_{11} x_{1}+a_{21} x_{2}=a_{12} x_{1}+a_{22} x_{2}} \\ {x_{1}+x_{2}=1}\end{array}\right.$
由此解得 $x_{1}=0.7, \quad x_{2}=0.3$

同样，可以从 $A$ 方考虑问题，得：
$\left\{\begin{array}{l}{0.82 y_{1}+y_{2}=y_{1}+0.58 y_{2}} \\ {y_{1}+y_{2}=1}\end{array}\right.$
即：
$\left\{\begin{array}{l}{a_{11} y_{1}+a_{12} y_{2}=a_{21} y_{1}+a_{22} y_{2}} \\ {y_{1}+y_{2}=1}\end{array}\right.$
并解得 $y_{1}=0.7, \quad y_{2}=0.3$ 。 $B$ 方指挥部被轰炸的概率的期望值 $V_{G}=0.874$ 。

记零和对策 $G$ 的解集为 $T(G)$ ，下面三个定理是关于对策解集性质的主要结果：

定理4 设有两个零和对策
$G_{1}=\left\{S_{1}, S_{2} ; A_{1}\right\}, \quad G_{2}=\left\{S_{1}, S_{2} ; A_{2}\right\}$
其中 $A_{1}=\left\{a_{i j}\right\}, \quad A_{2}=\left\{a_{i j}+L\right\}, \quad L$ 为任一常数。则
（1） $V_{G_{2}}=V_{G_{1}}+L$
（2） $T\left(G_{1}\right)=T\left(G_{2}\right)$

定理5 设有两个零和对策
$G_{1}=\left\{S_{1}, S_{2} ; A\right\}, \quad G_{2}=\left\{S_{1}, S_{2} ; \alpha A\right\}$
其中 $\alpha>0$ 为任一常数。则：
（1） $V_{G_{2}}=\alpha V_{G_{1}}$
（2） $T\left(G_{1}\right)=T\left(G_{2}\right)$