数学建模对策论

《数学建模对策论》由会员分享，可在线阅读，更多相关《数学建模对策论（97页珍藏版）》请在金锄头文库上搜索。

1、GAME THEORY 对 策 论第11章*111 矩阵对策6.1 引言6.2 对策论的基本概念6.3 矩阵对策的概念及模型6.4 矩阵对策的纯策略解（鞍点解）6.5 矩阵对策的混合策略解（mixed strategic solution）6.6 矩阵对策的解法Date2Operations Research6.1.1 何谓对策论（Game Theory）？6.1.2 对策的例子6.1.3 对策论的诞生与发展简况6.1 引 言Date3Operations Research6.1.1 何谓对策论(Game Theory)？( 定义：对策论亦称竞赛论或博弈论，是研 究具有斗争或竞争性质现象的数学

2、理论和方 法。 囚徒困境 局中人2 坦白不坦白 局中人1坦白(-6,-6)(-1,-8)不坦白(-8,-1)(-2,-2)Date4Operations Research(齐王赛马 (决斗问题：神雕侠侣中武林盟主大会6.1.2 对策的例子朱子柳霍 都 郭 靖达尔巴 郝大通金轮法王Date5Operations Research6.1.3 对策论的诞生与发展简况早期工作 F1912年E.Zermelo 关于集合论在象棋 对策中的应用 F 1921年E.Borel 引入最优策略 F 1928年J.V.Neumann证明了一些猜想Date6Operations Research6.1.3 对策论的诞

3、生与发展简况产生标志1944年J.V.Neumann和O.Morgenstern” 对策论与经济行为” （Theory of Games and Economic Behavior） 发展成熟Nash均衡、经济博奕论、信息不对称 对策和广义对策Date7Operations Research6.2 对策论的基本概念(6.2.1 局中人（Player） (6.2.2 策略（Strategy） (6.2.3 支付与支付函数Date8Operations Research6.2.1 局中人（Player）1、局中人：在一场竞争或斗争中的决策者 称为该局对策的局中人通常，一局对策具有两个或两个以上-

4、决策者，一般用I表示局中人集合：Date9Operations Research6.2.1 局中人（Player）2、对策分类：依据局中人的数量，可将对 策分为有限对策无限对策(n2)对策无限零和对策无限非零和对策有限零和对策有限非零和对策Date10Operations Research6.2.2 策略（Strategy）1、 策略与策略集 F局中人指导自己自始至终如何行动的一 个方案，称为策略(Strategy) F由所有策略构成的集合，称为策略集 (Strategy Set)Date11Operations Research6.2.2 策略（Strategy）2、策略集的元素：对于局中人

5、i,iI，都有自己的 策略集Si,通常每一局中人的策略集中至少应包括 两个策略对于例4的包、剪、锤游戏。假设有两个局中人 I=甲，乙，甲的策略集为S甲=(包)、(剪)、(锤 )=a1、a2、a3;乙的策略集为S乙=(包)、(剪)、( 锤) =b1、b2、b3;Date12Operations Research6.2.3 支付与支付函数1、局势：各局中人所选定的策略形成的策略组 2、策略组若si是第i个局中人的一个策略，则n个局中人的策 略组 s=(s1,s2,sn)就是一个局势。Date13Operations Research6.2.3 支付与支付函数例如，对于包、剪、锤游戏。假设有两个局中

6、人 I=甲，乙，甲的策略集为S甲=(包)、(剪)、(锤 )=(a1)、(a2)、(a3);乙的策略集为S乙=(包)、(剪) 、(锤) =(b1)、(b2)、(b3);则甲的一个策略ai，和乙的一个策略bj就构成一 个局势sij.Date14Operations Research6.2.3 支付与支付函数3、赢得（支付）：当每个局中人所采取的策 略确定后，他们就会得到相应的收益或损失，称 为局中人的支付（Payoff）。若甲的一个策略a3(锤)，乙的一个策略b2(剪) ，则构成一个局势s32 。在局势s32下，甲的支付为 ：乙的支付Date15Operations Research6.2.3 支

7、付与支付函数4、支付（赢得）函数： 不同的策略会导致不同的支付，因此，支付是策略 (准确的说应该是局势)的函数，称为支付函数 (payoff function)。 对于例4，两人的支付函数分别记为： 和例如，对于策略a3, b1Date16Operations Research6.2.3 支付与支付函数5、零和对策和非零和对策根据各局中人支付的代数和是否为0，将对策 分为零和对策和非零和对策(non-zero-sum games)。若在任一局对策中，全体局中人支付的总和为 0，则该对策称为零和对策，否则称为非零和对策 (non-zero-sum games)。对于前例，显然为零和对策，因为Da

8、te17Operations Research6.2.3 支付与支付函数6、对策分类根据局中人的数目和支付函数代数和有限对策n人对策(n2)对策合作对策非合作对策Date18Operations Research6.3 矩阵对策的概念及模型1、定义：两个人零和对策称为矩阵对策例，“包、剪、锤”游戏中，甲、乙双方各有三种 不同的策略，分别为：Date19Operations Research6.3 矩阵对策的概念及模型甲的支付情况如下表 1 (包)2(剪)3(锤)1 (包)0-11 2 (剪)10-1 3(锤)-110乙的策略甲的支付甲的策略表6.1Date20Operations Resear

9、ch6.3 矩阵对策的概念及模型齐王赛马 1234561 (上中下)31111-1 2 (上下中)1311-11 3(中上下)1-13111 4(中下上)-111311 5(下中上)11-1131 6(下上中)111-113田忌策略齐王赢得齐王策略上中下上下中中上下中下上下中上下上中Date21Operations Research6.3 矩阵对策的概念及模型表6.1中的数字用矩阵的形式表示A称为甲的支付矩阵。显然，乙的支付矩阵为-A。 因此，该对策可记为： Date22Operations Research6.3 矩阵对策的概念及模型(2、矩阵对策的模型 F一般地，若局中人 ，的策略集分别

10、为：F为了与后面的概念区分开来，我们称i为 的纯策略， j为的纯策略，对于纯策略i, j构成的策略偶(i, j)称为纯局势。 Date23Operations Research6.3 矩阵对策的概念及模型(若的支付矩阵为： ij表示局势(i,j)下，局中人的支付,则矩 阵对策可记为G=S1,S2,A：即矩阵对策模型 。 Date24Operations Research6.4 矩阵对策的纯策略解6.4.1 矩阵对策的纯策略解例解过程 6.4.2 矩阵对策的纯策略解理论基础 6.4.3 矩阵对策的纯策略解性质Date25Operations Research例5 设二人零和对策 G=S1, S2

11、, A，其中 6.4.1 矩阵对策的纯策略解例解过程而且局中的支付矩阵为： 两位局中人都想自己的支付最大化。Date26Operations Research6.4.1 矩阵对策的纯策略解例解过程这里我们认为局中人都是理智的，从矩阵A进 行逻辑推理可知：如果局中人采取3作策略，虽有可能获得最 大支付18，但是,局中人分析到的这种心理， 就会采取3策略，使不仅得不到最大值18，反而 取得很坏的结果-8；同样，局中人为了得到最大支付+12(即局中 人的支付-12)，会采取 2作为策略,但局中人 也会猜到的这种心理,而采取 2作策略，这样局 中人只能得到-3。Date27Operations Res

12、earch6.4.1 矩阵对策的纯策略解例解过程从以上的分析可以看出，局中人选取最优策略 时应该考虑到也是十分理智与精明的，的策 略是要以支付最少为目的，所以不能存在任何 侥幸心理。局中人也应作同样的考虑。对于局中人来说，应该是从最坏处着想 向最好处努力。Date28Operations Research6.4.1 矩阵对策的纯策略解例解过程对局中人来讲，各策略的最坏结果分别为： min-6,2,-7=-7 min5,3,6=3 min18,0,-8=-8 min-2,-12,7=-12 这些最坏的情况中，最好的结果是： max-7,3,-8,-12=3Date29Operations Res

13、earch6.4.1 矩阵对策的纯策略解例解过程同样，对局中人而言，各策略的最坏的结 果分别为： max-6,5,18,-2=18 max2,3,0,-12=3 max-7,6,-18,7=7 在这些最坏的情况中，最好的结果（损失最 小）是 min18,3,7=3Date30Operations Research6.4.1 矩阵对策的纯策略解例解过程1231-62-7-7 25363 3180-8-8 4-2-127-12 1837Date31Operations Research6.4.1 矩阵对策的纯策略解例解过程课堂练习:求解对策 G=S1,S2,A 已知：Date32Operation

14、s Research定义1 对于矩阵对策G=S1,S2,A,如果存在纯局势 6.4.2 矩阵对策的纯策略解理论基础则称局势 为对策G在纯策略中的解。亦 称其为G的鞍点(saddle point): (列中最大，行中最小)使得对任意j=1, ，n,及任意i=1, m有： Date33Operations Research6.4.2 矩阵对策的纯策略解理论基础分别称为局中人，的最优纯策略 。 称 为对策G的值(value)，记为Date34Operations Research6.4.2 矩阵对策的纯策略解理论基础(定理1 矩阵对策G=S1,S2,A存在最优纯 策略的充分必要条件为：Date35O

15、perations Research6.4.2 矩阵对策的纯策略解理论基础求对G的解和值。例6 已知 G=S1,S2,A，其中, Date36Operations Research6.4.2 矩阵对策的纯策略解理论基础1234186866 2134-3-3 396766 4-31103-3 961066解：根据A可得Date37Operations Research6.4.2 矩阵对策的纯策略解理论基础由于： 四个局势均为G的鞍点，且 故知： Date38Operations Research6.4.3 矩阵对策的纯策略解性质从上例可知，对策的解可以是不唯一的，但对策 的值是唯一的。对策解不唯一时，应满足下面两 条性质：1. 无差别性：若 与 是矩阵对策G的两个解，则即对策值相等，它们在矩阵中的元素相同。Date39Operations Research6.4.3 矩阵对策的纯策略解性质2. 可交换性：若 与 是矩阵对策G的两个解,则 与 也是对策的解。 Date40Operations Research6.4.3 矩阵对策的纯策略解性质是不是每一个矩阵对策都有纯策略解（鞍点）？12310-11-1 210-1-1 3-110-1 1