重庆工商大学数学模型与数学实验课件07对策与决策模型

对策与决策模型第八章对策与决策模型对策与决策是人们生活和工作中经常会遇到的择优活动。人们在处理一个问题时，往往会面临几种情况，同时又存在几种可行方案可供选择，要求根据自己的行动目的选定一种方案，以期获得最佳的结果。有时，人们面临的问题具有竞争性质，如商业上的竞争、体育中的比赛和军事行动、政治派别的斗争等等。这时竞争双方或各方都要发挥自己的优势，使己方获得最好结果。因而双方或各方都要根据不同情况、不同对手做出自己的决择，此时的决策称为对策。在有些情况下，如果我们把可能出现的若干种情况也看作是竞争对手可采取的几种策略，那么也可以把决策问题当作对策问题来求解。§8.1对策问题对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。先考察几个实际例子。例8.1（田忌赛马）田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。例8.2（石头—剪子—布）这是一个大多数人小时候都玩过的游戏。游戏双方只能选石头、剪子、布中的一种，石头赢剪子，剪子赢布，而布又赢石头，赢者得一分，输者失一分，双方相同时不得分，见下表。表8.1石头剪子布石头01－1剪子－101布1－10例8.3（囚犯的困惑）警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将各被判刑3年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列表如下：表8.2嫌疑犯B供认不供认嫌疑犯A供认不供认（3，3）（0，7）（7，0）（1.5，1.5）表中每对数字表示嫌疑犯A、B被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。一、对策的基本要素（1）局中人。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例8.3中，局中人是A、B两名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他们各自采取的态度，警方不能为他们做出选择。从这些简单实例中可以看出对策现象中包含的几个基本要素。（2）策略集合。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。记局中人i的策略集合为Si。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量S表示，称之为一个纯局势（简称局势）。例如，若一对策中包含A、B两名局中人，其策略集合分别为SA={1,…,m}，SB={1,…,n}。若A选择策略i而B选策略j，则（i,j）就构成此对策的一个纯局势。显然，SA与SB一共可构成m×n个纯局势，它们构成表8.3。对策问题的全体纯局势构成的集合S称为此对策问题的局势集合。(m,n)…(m,j)…(m,2)(m,1)m…………………(i,n)…(i,j)…(i,2)(i,1)i…………………(2,n)…(2,j)…(2,2)(2,1)2(1,n)…(1,j)…(1,2)(1,1)1A的策略n…J…21B的策略（3）赢得函数（或称支付函数）。对策的结果用矢量表示，称之为赢得函数。赢得函数F为定义在局势集合S上的矢值函数，对于S中的每一纯局势S，F（S）指出了每一局中人在此对策结果下应赢得（或支付）的值。综上所述，一个对策模型由局中人、策略集合和赢得函数三部分组成。记局中人集合为I={1,…,k}，对每一i∈I，有一策略集合Si，当I中每一局中人i选定策略后得一个局势s；将s代入赢得函数F，即得一矢量F(s)=(F1(s),…,Fk(s))，其中Fi(s)为在局势s下局中人i的赢得（或支付）。本节讨论只有两名局中人的对策问题，即两人对策，其结果可以推广到一般的对策模型中去。对于只有两名局中人的对策问题，其局势集合和赢得函数均可用表格表示。例如，表8.2就给出了例8.3的局势集合和赢得函数。二、零和对策存在一类特殊的对策问题。在这类对策中，当纯局势确定后，A之所得恰为B之所失，或者A之所失恰为B之所得，即双方所得之和总为零。在零和对策中，因F1(s)=－F2(s)，只需指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若A有m种策略，B有n种策略，赢得矩阵111212122212nnmnmmmnaaaaaaRaaa表示若A选取策略i而B选取策略j，则A之所得为aij（当aij0时为支付）。在有些两人对策的赢得表中，A之所得并非明显为B之所失，但双方赢得数之和为一常数。例如在表8.4中，无论A、B怎样选取策略，双方赢得总和均为10，此时，若将各人赢得数减去两人的平均赢得数，即可将赢得表化为零和赢得表。表8.4中的对策在转化为零和对策后，具有赢得矩阵表8.4局中人B123局中人A1(8,2)(1,9)(7,3)2(4,6)(9,1)(3,7)3(2,8)(6,4)(8,2)4(6,4)(4,6)(6,4)342142313111R给定一个两人对策只需给出局中人A、B的策略集合SA、SB及表示双方赢得值的赢得矩阵R。综上所述，当遇到零和对策或可转化为零和对策的问题时，R可用通常意义下的矩阵表示，否则R的元素为一两维矢量。故两人对策G又可称为矩阵对策并可简记成G={SA,SB,R}例8.4给定G={SA,SB,R}，其中SA={1,2,3}，SB={1,2,3,4}123412312630221421810601016R从R中可以看出，若A希望获得最大赢利30，需采取策略1，但此时若B采取策略4，A非但得不到30，反而会失去22。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人A采取策略1、2、3时，最坏的赢得结果分别为min{12,－6,30,－22}=－22min{14,2,18,10}=2min{－6,0,－10,16}=－10其中最好的可能为max{－22,2,－10}=2。如果A采取策略2，无论B采取什么策略，A的赢得均不会少于2.B采取各方案的最大损失为max{12,14,－6}=14，max{－6,2,0}=2，max{30,18,－10}=30和max{－22,10,16}=16。当B采取策略2时，其损失不会超过2。注意到在赢得矩阵中，2既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定解，（注：也被称为鞍点）定义8.1对于两人对策G={SA,SB,R}，若有，则称G具有稳定解，并称VG为对策G的值。若纯局势（）使得，则称（）为对策G的鞍点或稳定解，赢得矩阵中与（）相对应的元素称为赢得矩阵的鞍点，与分别称为局中人A与B的最优策略。maxminminmaxijijGjjiiaaV**,ij**minmaxijijGjjaaV**,ij**,ij**ija*i*j对（8.1）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定一个对策G，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。定理8.1设G={SA,SB,R}，记，则必有μ+ν≤0maxminminmaxijijjjiiaa，证明:，maxmin(ijija)易见μ为A的最小赢得，ν为B的最小赢得，由于G是零和对策，故μ+ν≤0必成立。定理8.2零和对策G具有稳定解的充要条件为μ+ν=0。证明：（充分性）由μ和ν的定义可知，存在一行（例如p行）μ为p行中的最小元素且存在一列（例如q列），－ν为q列中的最大元素。故有apq≥μ且apq≤－ν又因μ+ν=0，所以μ=－ν，从而得出apq=μ，apq为赢得矩阵的鞍点，（p,q）为G的稳定解。（必要性）若G具有稳定解（p,q），则apq为赢得矩阵的鞍点。故有maxminminijpjpqjjiaaaminmaxmaxijiqpqjiiaaa从而可得μ+ν≥0，但根据定理8.1，μ+ν≤0必成立，故必有μ+ν=0。上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若12345123494311010115185182641513R则易见，（2,2），（2,4），（4,2），（4,4）均为此对策问题的解。一般又可以证明。定理8.3对策问题的解具有下列性质：（1）无差别性。若（,）与（,）同为对策G的解，则必有。1i1i2i2i1122ijijaa（2）可交换性。若（,j1）、（,j2）均为对策G的解，则（,j2）和（,j1）也必为G的解。1i2i1i2i定理8.3的证明非常容易，作为习题留给读者自己去完成。具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是μ+ν≠0的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（8.1）中的赢得矩阵R。若双方都采取保守的maxmin原则，将会出现纯局势（4,1）或（4,3）。但如果局中人A适当改换策略，他可以增加收入。例如，如果B采用策略1，而A改换策略1，则A可收益3。但此时若B改换策略2，又会使A输掉4，……。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。设A方用概率xi选用策略i，B方用概率yj选用策略j，，且双方每次选用什么策略是随机的，不能让对方看出规律，111mnijij记X=(x1,…,xm)T，Y=(y1,…,yn)T，则A的期望赢得为E(X,Y)=XTRY其中，R为A方的赢得矩阵。记SA:策略α1,…,αmSB:策略β1,…,βn概率x1,…,xm概率y1,…,yn分别称SA与SB为A方和B方的混合策略。对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。定义8.2若存在m维概率向量和n维概率向量，使得对一切m维概率向量X和n维概率向量y有则称（,）为混合策略对策问题的鞍点。maxm