运筹学 其他对策模型

其他对策模型姓名专业7.1阵地对策7.1阵地对策阵地对策

对策论中所谓局中人的一个策略是指局中人的一个完整地行动方案，例如赛马的例子中，出赛马的一个次序是一个完整地行动方案。但是有的对策现象中完整地行动方案是不容易说清楚的，例如下象棋，要走很多步，每步又有很多可供选择的走法，那么一个由始至终的行动方案怎么说得清楚呢？但是这种类型的对策现象有它的特点，即它规定了各步该谁走，而走的局中人又有多少种走法可选择，另外走的局中人走时是否能知道别的局中人在他此步之前是怎么走的信息等等。因此根据此类对策现象的特点来形成数学模型也是对策论的工作之一，由于这类对策现象是一步一步走的，所以给它起个名字叫“阵地对策”。7.1阵地对策特点

假如给局中人编上号码1,2,…,n则每步上都规定了是哪个局中人的步，对于不是局中人的步而是机遇步，我们规定这种步是局中人”0”的步，那么每一步都有一个数与之对应。而每一步上都是可供选择的路（即走法）的集合。每一步都指出能知道什么信息。最后在各路的终点（即无择路可走出去的点）上规定了各局中人的“得失”。所以这样的对策可用树状图来表达。即：（1）一棵定向的树，树根表示第一步，其后各分叉点表示后继各步。

（2）每个分叉点上所有枝条的个数，即为该步择路的个数。

（3）树的各个分叉点上都给定0,1,…,n中一个数。即规定在这点上是哪个局中人的步（带数“0”的步即为机遇步）。

（4）带数”0”的分叉点上，如果它有k个枝条，则在这个枝条上规定了一个概率分布，即给出k个数

7.1阵地对策特点（5）诸分叉点全体组成的点集有一个划分，它把一切分叉点完全无遗地分在互斥的子集（称为信息集）内。这些子集满足下列假设：

（i）属于同一信息集的一切分叉点都是属于同一个局中人的步。（ii）同一信息集的各个分叉点有相同数目的择路。（iii）带数“0”的分叉点所在的信息集只能有这一个分叉点。（6）这棵树的每一个树梢上都定义有n个实数F1,F2,……,Fn分别表示局中人1,2,……,n的“得失”。7.1阵地对策例14猜数对策局中人甲秘密地选定1,2,3三个数之一。局中人乙猜甲所选的数，并且说出他所猜的是什么数，每一次局中人乙说出他所猜的数后，甲按照实际情况回答“太高”，“太低”或“正确”。对策继续进行到乙回答出为止。甲的支付数等于乙回答出正确答案所需要的次数。显然局中人甲的策略是选择数1,2,或3。局中人乙的策略可以用一组数（G;H,L）来表示。其中G是第一次猜的数，H是局中人乙听到甲回答“太高”后第二次猜的数。L是局中人乙听到甲回答“太低”后第二次猜的数。很清楚，最多猜两次对策就结束了。因此局中人乙有五个策略（1;0,2）,（1;0,3）,（2;1,3）,（3;1,0）,（3;2,0）其中0表示这种情况不存在。局中人甲得到的支付数，是局中人乙直到听局中人甲说“正确”时共回答的次数。支付矩阵列出如下：7.1阵地对策猜数对策也是一个阵地对策，可用图4-1的树状图来描写：7.2连续对策7.2连续对策在一个有限对策里，每个局中人的策略集是有限的，即策略的总数可以很大，但毕竟是一个有限数。可是许多军事和经济的对策往往涉及无穷多个策略的问题。例如在一海域里潜行的潜水艇，为躲过敌方飞机的侦察，该如何选择出水换气的地点的对策问题。其策略数目就是无穷多个。具有无穷多个策略的对策称为无限对策。最简单的一种是被称为连续对策。连续对策在其最简单的形式下可描述如下：局中人甲在[0,1]闭区间中选择一个点X，同时局中人乙在[0,1]闭区间中选择一个点Y，而在局势

之下，局中人甲得到支付为。假定对策是零和的，则局中人乙得到的支付为

。并且假设支付函数

对于每个存在，而对于每个

也存在，所以对局中人甲来说，存在一个策略，使他至少得到。同样对局中人乙来说，存在一个策略使他至少得到

容易证明下式成立：

7.2连续对策

如果上式的等号成立，那么设策略X0，Y0使

对于一切Y成立

对于一切X成立。则称X0是局中人甲的最优纯策略，Y0是局中人乙的最优纯策略。（X0,Y0）称为此连续对策的鞍点。如果上式的等号不成立。就没有最优纯策略。于是和有限两人零和对策中引入混合策略（即是有限集上的概率分布函数）的概念一样，我们引无限集上的概率分布函数为无限对策中的混合策略。即连续对策的混合策略是一个从[0,1]闭区间中选择一个不大于X的数的随机过程。当甲取混合策略即某个分布函数F(x)，而乙取混合策略G(y)时，甲的期望支付是斯蒂尔杰积分：

类似于矩阵对策当

及

7.2连续对策

都存在且相等（其中D是[0,1]上的分布函数的全体组成的集合），则在混合策略中有平衡局势。也就是存在甲的混合策略F0(X)，乙的混合策略G0(Y)使对任何的X,Y有：7.3多人对策7.3多人对策当局中人是两个以上时，这样的对策称为多人对策。一般多人对策中不可避免会出现合作的情况，例如两人有默契，合起来对付第三个，使第三个必败。所以讨论多人对策时，对局中人之间可能有怎样的合作必需进行研究。所谓正规型不结盟多人对策是指三元体

其中I是局中人集合，Si是局中人I的策略集，Hi是局中人I的得失函数。现在我们对这种多人对策来讨论其中局中人之间可能有怎样的合作。下面引入特征函数的概念。当我们把I的一个子集合R看成是一个联盟，而把I中除去R后剩下元素全体记作I/R看成是另一个联盟，然后构造一个两零和对策：

7.3对人对策

如果对策有值则把

看成是联盟R的“得失”。假定对于任何子集而言，对策

的值都存在，记为

。然后我们假定（其中表示空集）。这样我们就在

的一切子集上定义了一个函数，这个函数称为对策P的特征函数。它必有如下的性质：(1)(2)(3)

由性质（3）可推得

特别有

光从特征函数来讨论可能成立什么联盟还为时过早，因为虽然结盟会增加共同赢得，但如果制定的分配共同赢得的方案不合适，也会引起联盟的破裂。所以又引入了分配的概念。7.3对人对策在零和对策中，局中人如何结盟呢？这主要取决于分配对局中人的影响，所谓分配乃是指满足下列条件的n个实数d=(a1,a2,……,an).对于一个分配a=(a1,a2……,an)而言，要使某个联盟有可能形成，必须要这个条件如果满足，则称联盟R对分配a有效。设为两个分配，如果存在联盟，R对分配a有效，且使得对一切

而言，ai>bi

那么说分配α优于分配β，记为α>β。显然当α>β时，联盟R必至少包含有两个局中人。因为若R只包含一个局中人i，那么由

但β乃是一个分配，所以bi>U(i)必成立。从而ai>U(i)，但已假设R对分配a有效，即必须成立，从而矛盾。7.3对人对策

引入这些概念之后，有人给出如下的解的概念。定义：命W是某些分配组成的集合，如果（1）对于任何

,α>β和β>α都不成立（2）对任何，必存在

使得

成立。

那么W就叫做对策P的一个解。下面举一个多人对策的例子。此多人对策的树状图为7.3对人对策这是一个全信息多人阵地对策。如果1,2合作，则上面阵地对策等价于如下的阵地对策（见图4-3）（-1,1）（1,0）由于最后一步都是③的步；因此在这步上③一定选择对他有利的择路，也即绝不会选使他一无所得的择路。但第一，二步是①、②联盟的步，他们也一定选择使他们总收入最大的择路。现在分析一下如果第一步选了右边的择路，最后肯定①、②只得到1而③可得到3.那么如果第一步选了左边的择路，而第二步分两种情况：（1）如果选右边的择路，则①②可得1，而③只可得0。（2）如果选左边的择路，则①②可得-1，而③可得1。因此①②为了自己多得，也为了不让③有所得，他们必须是第一步选左边的择路。所以①②联盟时①②的总收入是1记作U(1,2)，而③的收入是0，记作U(3)。也即

U(1,2)=1;U(3)=0

同样的方法分析后可得

U(1,3)=3;U(2)=1U(2,3)=2;U(1)=07.3对人对策

如果①，②，③结成联盟时，等价于一人对策

显然此时第一步必走右边的择路，最后总收入是4，记作U(1,2,3)=4。然后令U(V)=0。如此得到了定义在局中人集合I的一切子集上的一个函数（但与前述特征函数不太一样，因为此时对策不是零和的）。从此函数可以看到任何局中人不结盟总是一无所得的，但是哪样的结盟会实现呢，这就与结盟时商定的总收入如何在盟员之间分配的协定有关了。例如三个人一起合作时，总收入4该如何分配呢，如果照树梢上写的支付函数分配，肯定有一人没收入因而不满意而退出联盟。所以讨论多人对策中的结盟问题，必须要涉及结盟后如何分配（也即有所谓“边支付”）的问题。07.4微分对策7.4微分对策在追踪对策中追赶双方是在空间或地面运动的。这里逃的一方有时不是单纯逃，而是企图在被追到以前达到某种目的。而追的一方就要在逃方达到目的之前追到他。

设想有一只老鼠在园形的湖边碰上了猫，它想回洞已来不及，只好跳入湖中企图逃走。但猫在岸上跑的速度比鼠在湖中游的速度快得多，例如是鼠速的4倍。粗看起来，老鼠没有好办法，只有束手就擒。但是，仔细研究一下，老鼠还是可以跑掉的。我们将老鼠所跑路线的奥妙介绍如下：

图4-5中大圆表示圆湖其半径设为R，取1/4R为半径作一同心小圆K于是老鼠跳入湖中后，先游到小圆K内，然后转圈游，猫在岸上按固定的路线跟着老鼠；但用同样的时间，老鼠在圆k内转圈所转过的角度比猫沿湖岸转圈转过的角度要大。所以老鼠可以游到和猫不在同一半径，而在同一直径的圆K的边界点*的位置上去，然后沿此直径游向湖岸。因为*点到湖岸的最短距离是3/4R，设鼠的速度为V,则鼠由*点到湖岸所需的时间是3R/4V，由于猫的位置同*点不在同一半径上，所以猫的到达同一地点的路程正好是半圆周，即。那么，猫的速度是鼠的4倍（即4V），但猫所需时间是

所以鼠先上岸，且有时间迅速跑入附近的鼠洞而溜掉。猫鼠猫鼠猫鼠7.4微分对策

追踪问题也存在对策现象所共有的根本要素：1.局中人此时局中人就是迫者与逃者，例如在空战中一方的歼击机和另一方的轰炸机，在空防中是攻方的轰炸机和守方的高射炮，在导弹战中是一方的导弹和另一方的反导弹等等。2．策略追逃双方都有自己的可选择的行动方案，例如轰炸机可选择飞行路线和投弹方式等，歼击机可选择攻击时间，飞行路线和攻击方式等，高射炮可选择发射角度等等。不过在追踪问题中局中人的完整的行动方案(所谓策略)比以前介绍的矩阵对策中的完整的行动方案要复杂得多了。因为在追踪问题中，局中人例如歼击机必须每时每刻都掌握对方相对位置和某些情况以便跟踪追击。同时轰炸机也得每时每刻都能掌握双方的相对位置和某些情况以便躲过攻击，飞达轰炸目标。所以用数学描述追踪对策中的策略，也必须要反映出这种连续动态的决策过程，这就得借助微分方程的理论。因此这类对策理论称为微分对策。在微分对策中，通常用向量X(t)表示时刻t时各方为继续进行对策所必须知道的双方的状况变量。例如空战中双方飞机的相对位置和机头所指方向等等，因此X(t)也被称为状况变量。7.4微分对策同时，各局中人都有控制自己运动路线的手段，例如飞机驾驶员可以做改变机速和使机头拐弯等操作，于是机速和机头拐弯的曲率半径等是属于局中人直接可控制的量，这些量的改变就能引起前述状况变量的改变，并且这些量将怎么变，对方是不知道的，所以这些向量称做控制量。于是局中人的一个策略就是决定一个连续控制的规律，即对任意状况