基础运筹学教程（第三版）- 课件 第八章 对策论.ppt

*一、非合作对策为便于理解，我们用著名的“囚徒困境”（ThePrisoner’sDilemma）例子来作一简单的分析和说明。（囚徒困境）有位富翁在家中被杀，财物被盗。警方在侦破过程中，抓到两个犯罪嫌疑人，并从其住处搜出被害人家中丢失的财物。但是，他们矢口否认杀过人，辩称是先发现富翁被杀，然后只是顺手牵羊偷了点东西。鉴于缺乏证据，警方寄希望于嫌犯自己招供，于是就将两人隔离，分别审讯，并交代政策如下：“如果你招了，另一人没招，那么就将你释放，另一人判20年；如果你不招，另一人招了，那么你得判20年，另一个人被释放；如果两人都招，则证据充分，各判10年；如果两人都不招，则因杀人罪证据不足，偷盗罪证据确凿，所以各判1年刑期。”这样，两个囚犯都面临了两个选择：或者供出他的同伙（即与警察合作，从而背叛他的同伙），或者保持沉默（也就是与他的同伙合作，而不是与警察合作）。*按照承认和不承认2种策略，可以写出两人的赢得矩阵：*从表面上看，他们应该互相合作，保持沉默，因为这样的话，两人都能得到最好的结果：各判1年。但他们不得不仔细考虑对方可能采取什么选择：对A犯而言，如果他选择沉默，他无法相信他的同伙不会向警方提供对他不利的证据，然后获得自由，让他独自坐牢；但他也意识到，他的同伙也不是傻子，也会这样来设想他。所以A犯的结论是，唯一理性的选择就是背叛同伙，把一切都告诉警方，因为如果他的同伙笨得只会保持沉默，那么他就会是那个获得自由的幸运者了，而如果他的同伙也按这个逻辑向警方交代了，那么，A犯反正也得服刑，起码他不必坐20年的牢。所以最终结果就是，这两个囚犯都得坐10年牢。*该问题最早由A.W.Tucker提出，对它的研究涉及到了数学、经济学、政治学、社会学、哲学、伦理学、心理学甚至计算机科学等广泛的领域，所展示的个体理性与集体理性之间的冲突、个人利益与社会道德的关系等，都进一步深化了人们的有关认识，非常耐人回味。就囚徒困境而言，唯一的均衡点是两人都认罪，但从赢得矩阵来看，这显然不是最有利的，最佳结果是两人都不认罪，可是在非合作条件下，这个最好的结局是难以达到的。用经济学的话语来说，就是个体理性选择的结果不符合集体理性的要求。*二、合作对策无论在自然界还是在人类社会，“合作”都是一种随处可见的现象。其意义在于，合作行动比分开行动得益要大。由于合作需要付出代价，因此就产生了交易谈判。某地区有两个蔬菜市场，由甲乙两家相互竞争的公司独自经营。由于运营模式的调整，这两个蔬菜市场在早市（早晨到中午）或者夜市（下午到晚上）轮流营业，并且这两家公司可自行选择营业时间。如果在早市营业，居民习惯在上午买菜，销售量大；如果在夜市营业，因运输成本低从而价格也低，居民也会在夜市买菜。通常情况下，一位居民一天最多购买一次蔬菜。这两家公司应如何选择营业时间？是否应该合作？双方盈利如图所示：甲乙两公司合作博弈*假设甲乙双方有合作的意愿，约定一家在早市营业，另一家在夜市营业，并且定期轮换。根据图可知，在合作的情况下，有两个均衡对策，即(20,30)和(30,20)。但如果甲乙双方有任何一方违约或者合作成本高的话，在混合对策中探索最优方案，即双方都以概率(1/10,9/10)选择在早市和夜市营业。当以1/10的概率选择在早市营业，以9/10的概率选择在夜市营业，预期收益为19.2。即在非合作的情况下，每家公司的期望收益是19.2。但在合作的情况下，每家公司的收益至少是20。*通过上述比较可知，若采用非合作对策，则每家公司的期望收益会小于合作对策下的最少收益。因此，在这种情况下，合作可以给双方带来收益。通常情况下，采用合作对策需要满足最基本条件。一是整体收益要大于每个成员单独经营收益的之和；二是每个成员都可以获得比非合作时更多的收益。**故Ⅱ应选取Y*，使支付至多为：若有：则就找到了一个对双方来说都是可接受的方案，即，Ⅰ按X*来选取策略，Ⅱ按Y*来选取策略。同理，当局中人Ⅱ取混合策略Y时，局中人Ⅰ将选用混合策略X’，使得：*对于一般混合扩充后的矩阵对策，给出如下定义。【定义4】设G*=｛S1*,S2*；E｝是G=｛S1,S2；A｝的混合扩充，若有：则混合局势(X*,Y*)称为G在混合策略意义下的解，也称为G*的鞍点；X*、Y*分别称为局中人Ⅰ和Ⅱ的最优混合策略；v称为G*的值，也称对策值。*VonNeumann和Morgenstern建立了下列矩阵对策基本定理。【定理2】矩阵对策一定存在混合策略意义下的解。即：