《运筹学教学资料》ch14 对策论.ppt

第十四章 对策论 引言 对策行为的三要素 对策的分类 二元对策模型 二元对策的纯策略 二元对策的混合策略 最优策略 二元对策的基本定理 二元对策的解法 引 言 齐王赛马 战国时代，齐王有一天要和他的大将军田忌赛马。比赛三场，每场各自选上中下三个等级的马一匹进行比赛，并规定每个等级的马只能赛一场，三赛二胜者为赢。已知在同等级的马中，齐王的马都比田忌的马强；在不同等级中，齐王的马要比田忌的高一个等级的马弱。 对局策略 田忌为取得比赛的胜利，接受了孙膑的建议：每场比赛时先让齐王牵出要比赛的马 (名为恭敬实有对策)，然后用自己的下马对齐王的上马，中马对齐王的下马，上马对齐王的中马。比赛结果，田忌获胜。 在这个故事里，田忌并没有设法去得到更好的马，而只是在比赛中运用了较好的策略而获胜. 囚徒困境问题 甲和乙两个小偷联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数据列出，如下： 囚徒困境博弈 博弈结果： 尽管甲不知道乙是否招供，但他认为自己选“招”最好，因而甲会选择“招”，乙也同样会选择“招”，结果各判8年； 但若两人都不招，结果是每人只被判1年，但在“人是理性的，即人人都会在约束条件下最大化自身的利益”的基本假设下，这种结果是不会出现的. 甲和乙是参与博弈的人，称为“局中人”. 表中每一个小方格内的数字被称为局中人的支付，其中左边的数字代表甲的支付，右边的是乙的支付. 表中的双变量矩阵称为博弈支付矩阵. 局中人所选择的战略构成的组合（招,招）被称为博弈均衡.这个组合中前后两个战略分别表示甲和乙所选择的战略. 如果甲和乙在决策时抛掉谨慎，加入一定的“疯狂”，不约而同地采取“不招”的策略，其结果是每人只被判1年. 显然，这对甲、乙二人来说，比他们采取理性策略的结果“好”. 商家价格战 出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱. 当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来. 博弈论有三个基本假设： 参与人是理性的； 他们有这些理性的共同知识； 他们知道博弈规则. 任何一个博弈问题都包含如下三个要素：局中人、策略和支付函数. 二、对策行为的三要素 （1）局中人（player) （2）策略集（strategy set） “齐王赛马”中，αi 和βj构成一个局势 sij . 在局势 s11下，齐王赢得 H1(s11)= 3， 田忌赢得 H2(s11)= - 3. 齐王应取得的支付值3,田忌得到的支付值是-3； 或者说齐王赢得3，田忌输掉3。 如此类推，可得到“齐王赛马”的支付矩阵. “齐王赛马”支付矩阵 例 1 有三个位于某河流同侧的城市,从上游到下游依次为A,B,C，这三个城市的污水必须经处理后才能排入河中.A与B距离为20km, B与C距离38km，如图.设Q为污水流量 (单位： ),L为管道长度(km).建污水厂费用的经验公式为 (单位：万元), 而建管道费用的经验公式为 (单位：万元).已知三城市的污水流量分别为 ，问应该怎样处理(单独设厂还是联合设厂)，才可使总开支最少？又每一城镇负担的费用应各为多少? §14.1 二元对策模型 在支付矩阵A中 a ij 既是局中人Ⅰ的赢得值，又是局中人Ⅱ的损失值。 局中人Ⅰ希望赢得值 a ij 越大越好， 而局中人Ⅱ则希望损失值 a ij 越小越好。 因此，矩阵对策完全是对抗性的。 例1 矩阵对策 G={ S1，S2；A } 局中人Ⅰ希望a ij 越大越好，因此他可以选择使上式为最大的策略，从而他的赢得不少于 由于局中人Ⅰ所得不会超过局中人Ⅱ的所失, 故 可见 都是A的鞍点，并且对策G的值是2。 二、二元对策的混合策略 如果对策G={ S1，S2；A }不是均衡对策，即A无鞍点，从而 例 3 两个小学生玩“锤子、剪刀、布”游戏。约束规则是：锤子胜剪刀，剪刀胜布，布胜锤子。双方各有三个策略αi与βj（i=1，2，3），分别表示锤子、剪刀和布，假定胜者得1分，负者得-1分， 则