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

作者: 热爱学习的高老板 | 来源:发表于2019-08-20 11:47 被阅读0次

【数学建模算法】(21)对策论（上）
【数学建模算法】(22)对策论（下）
数学建模算法总结
【数学建模算法】(31)方差分析（上）
机器学习之各类型算法简介&初识SVM
【数学建模算法】（番外1）解决整数规划问题的Matlab函数in
【数学建模算法】(9)树
数学建模算法学习
数学建模最常用的数学算法
7月17日2018年。暑假日志。

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

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

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)$

定理6 设 $G=\left\{S_{1}, S_{2} ; A\right\}$ 为一零和对策，且 $A=-A^{T}$ 为反对称矩阵（亦称这种对策为对称对策）。则
（1） $V_{G}=0$
（2） $T_{1}(G)=T_{2}(G)$

以上三个定理中 $T_{1}(G)$ 和 $T_{2}(G)$ 为局中人Ⅰ和Ⅱ的最佳策略集。

以上定理说明，把矩阵 $A$ 加一个常数，倍乘，反对称变换，最佳策略集不变。

【数学建模算法】(21)对策论（上）
对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是...
【数学建模算法】(22)对策论（下）
4.零和对策的线性规划解法当且时，通常采用线性规划方法求解零和对策问题。局中人Ⅰ选择混合策略的目的是使得：其中...
数学建模算法总结
无总结反省则无进步写这篇文章，一是为了总结之前为了准备美赛而学的算法，而是将算法罗列并有几句话解释方便以后自己需...
【数学建模算法】(31)方差分析（上）
我们已经作过两个总体均值的假设检验，如两台机床生产的零件尺寸是否相等，病人和正常人的某个生理指标是否一样。如果把这...
机器学习之各类型算法简介&初识SVM
最近学习数学建模，其中有一种分类（Classification）算法，叫做 Support Vector Mach...
【数学建模算法】（番外1）解决整数规划问题的Matlab函数in
我们在数学建模算法（2）中了解了一种用于解决指派问题的算法——匈牙利算法，当时我在网上苦苦找寻算法实现代码，但是今...
【数学建模算法】(9)树
1.基本概念联通的无圈图叫做树，记做为T。若图满足，则称是的生成树。图联通的充分必要条件为有生成树。一个连通数的...
数学建模算法学习
->点击访问个人博客，相互交流学习<- 相关模型解决的问题数据分析类算法一览100个经典动态规划方程优化问题线...
数学建模最常用的数学算法
1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的...
7月17日2018年。暑假日志。
1.现在做数学建模还是有一点儿用处的，找到了济南大学的建模论文，然后看了看遗传算法，准备把遗传算法给用进去。虽然他...

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

1.对策问题

1.1.对策的基本要素

1.1.1.局中人

1.1.2.策略集

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

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

2.零和定理的混合策略

相关文章

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

【数学建模算法】(22)对策论（下）

数学建模算法总结

【数学建模算法】(31)方差分析（上）

机器学习之各类型算法简介&初识SVM

【数学建模算法】（番外1）解决整数规划问题的Matlab函数in

【数学建模算法】(9)树

数学建模算法学习

数学建模最常用的数学算法

7月17日2018年。暑假日志。

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读