资源描述：
《算法大全第07章_对策论.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章对策论§1引言社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来解决这样的问题开始于17世纪的科学家，如C.，Huygens和W.，Leibnitz等。现代对策论起源于1944年J.，VonNeumann和O.，Morgenstern的著作《TheoryofGamesandEconomicBehavior》。对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一
2、般的日常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。§2对策问题对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方
3、所采取的策略的综合结果。先考察一个实际例子。例1（囚徒的困境）警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑18个月；如果双方都供认伪造了钱币，将各被判刑3年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑7年。将嫌疑犯A、B被判刑的几种可能情况列于表1。表1嫌疑犯B供认不供认供认（3，3）（0，7）嫌疑犯A不供认（7，0）（1.5，1.5）表1中每对数字表示嫌疑犯A、B被判刑的年数
4、。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。从这一简单实例中可以看出对策现象中包含有的几个基本要素。2.1对策的基本要素（i）局中人在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局中人。通常用I表示局中人的集合．如果有n个局中人，则I={1,2,L,n}。一般要求一个对策中至少要有两个局中人。在例1中，局中人是A、B两名疑犯。（ii）策略集一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人i，i∈I，都有自己的策略集S。一般，每一局中人的策略集中
5、i至少应包括两个策略。-154-（iii）赢得函数（支付函数）在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若s是第ii个局中人的一个策略，则n个局中人的策略组s=(s,s,L,s)12n就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔积表示，即S=S×S×L×S12n当局势出现后，对策的结果也就确定了。也就是说，对任一局势，s∈S，局中人i可以得到一个赢得H(s)。显然，H(s)是局势s的函数，称之为第i个局中人的赢ii得函数。这样，就得到一个向量赢得函数H(s)=(H(s),L,H(s))。1n本节我们只讨论有两名局中人
6、的对策问题，其结果可以推广到一般的对策模型中去。2.2零和对策（矩阵对策）零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。设局中人Ⅰ、Ⅱ的策略集分别为S={α,L,α}，S={β,L,β}11m21n当局中人Ⅰ选定策略α和局中人Ⅱ选定策略β后，就形成了一个局势(α,β)，可见ijij这样的局势共有mn个。对任一局势(α,β)，记局中人Ⅰ的赢得值为a，并称ijij⎡a11a12La1n⎤⎢⎥aaLaA=⎢21222n⎥⎢LLLL⎥
7、⎢⎥aaLa⎣m1m2mn⎦为局中人Ⅰ的赢得矩阵（或为局中人Ⅱ的支付矩阵）。由于假定对策为零和的，故局中人Ⅱ的赢得矩阵就是−A。当局中人Ⅰ、Ⅱ和策略集S、S及局中人Ⅰ的赢得矩阵A确定后，一个零和对策12就给定了，零和对策又可称为矩阵对策并可简记成G={S,S;A}。12例2设有一矩阵对策G={S,S;A}，其中S={α,α,α}，121123S={β,β,β,β}，21234⎡12−630−22⎤⎢⎥A=1421810⎢⎥⎢⎣−60−1016⎥⎦从A中可以看出，若局中人Ⅰ希望获得最大赢利30，需采取策略α，但此时若局1中人Ⅱ采取策略β，局中人Ⅰ非但
8、得不到30，反而会失去22。为了稳妥，双方都应考4虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果，局中人Ⅰ采
