第十一章二人有限零和对策第十一章二人有限零和对策

《第十一章二人有限零和对策第十一章二人有限零和对策》由会员分享，可在线阅读，更多相关《第十一章二人有限零和对策第十一章二人有限零和对策（26页珍藏版）》请在金锄头文库上搜索。

1、1 第十一章 二人有限零和对策第十一章 二人有限零和对策 二人有限零和对策是对策论(Game Theory)最基本的内容。 Game Theory也可译为博弈论，是研 究决策主体的行为发生直接相互作用时的 决策以及这种决策的均衡问题的学科。 1994年诺贝尔经济学奖授给了三位博 弈论专家：纳什、泽尔腾、海萨尼。博弈 论已经成为当代经济学的基石。 2 第一节 基本概念 一、对策现象与对策论 1. 对策现象 下棋:围棋源于我国殷代。 1- 10 10- 1 - 110 A 石头 剪子 石头 剪子 布 布 赢B 猜手:小孩A与B猜手,若规定赢 得1分，平得0分，输得 - 1分， 则 A的赢得可用右表

2、来表示。 齐王赛马：齐王与大将田忌赛马，各自的马都分为三 等，但齐王的同等马均强于田忌。孙膑给田忌出主意， 用下- - - - 上，上- - - - 中，中- - - - 下， 结果田忌胜出。 3 2 . 对策论的产生 1944年，纽曼与曼彻斯特发表了题为对策论和经 济行为。二次大战前后，由于军事需要，抽象成数学 模型。 50年代是对策论发展的鼎盛时期，纳什和夏普利等 提出了讨价还价模型和合作对策的“核”的概念。同时， 非合作对策也开始创立。纳什于1950和1951年发表了两 篇关于非合作对策的文章，图克于1950年定义了“囚徒 困境”问题。 60年代，泽尔腾（1965）引入动态分析，提出“精

3、 练纳什均衡”概念。海萨尼（1967- 1968）则把不完全信 息引入对策论的研究。 4 二 、对策问题的组成 1.局中人（参加者）：一局对策的参加者。 2.策略：局中人在一局对策中对付对手的一个完整的方案。 策略集：局中人在一局对策中所有策略的全体。记为S （分为有限和无限）问:田忌和齐王的S=? 3. 局势：在一局对策中，每个局中人都选定一策略后的各 策略总和。 0 0 零和：各局中人的得失之和为 分为 非零和：各局中人的得失之和非 4. 支付：局势给定后，局中人的得失（是局势的函数）。 如在二人对策中,设 1121 , ,1,1, mn ij SS im jn = = LL LL则局势为

4、（, ） 5 M 第二节 矩阵对策的最优纯策略 12 111 1 12 S,S A , mn n mmn ijij aa aa aa GS S A = = LLLL K MOM L 1212 设二人有限零和对策问题的局中人为 ， 策略集为，,，, 则支付可以用矩阵 表示， 其中为 的得（也是的失），的得即为- 。 故又称二人有限零和对策为矩阵对策,记为（） 一、矩阵对策 n 1 1 m L 6 二 、理智局中人的选择 在矩阵对策中，局中人将如何选取自己的策略呢？ * * max min min max ij i ji ij j ji a a 选 即 理 智 局 中 人 的 选 择 选 3 32

5、 2 323 2323 132 A432 618 aa 举例说明，若 ，都想谋取最大的赢得， 当然想出，但估计到 的心理，便出，使 反而输掉8。于是为了保险起见 出， 因为肯定不会输。即 若不存在侥幸心理（理智的），必出， 而此时必出，否则输得更多。结果，在局势（， ）下， 的得是=2，这时双方都无意见，分析的特点，是行中最小 的最大，列中最大的最小。 1 2 3 2 1 3 7 三、最优纯策略与鞍点 * * * * G 1. G, G GV iji ji jij iji j aaa a 对策 的解和值：使得的()称为 的解，与分别是 , 的最优纯策略， 称为 的值，记为 。 * * * *

6、2. maxminminmax ij ijij i j jjii ij aaa 鞍点：若局势（，）对应的 则称（，）为鞍点。 233232ij aaaa分析上例中的，它就满足 8 定理1： * , ijij G在纯策略中有解()()是鞍点 * * * * * * * * * * : minminmaxmaxminmax min,max ,1,1, (,) ijij i jij jjjiii i ji jiji j ji iji ji ji j iji ji j ij aaaa aaaa aaaaimjn aaa G = = = LL 证明 记 故 即是 的解 9 * * * * * * * *

7、 * 1,1, maxmin minmaxmaxminmaxmin A,maxminminmax minmaxmaxmin (,) iji ji j iji ji j ji ijij iji ji j jjjiii ijij jjii ijij i j jjii ij aaa imjn aaa aaaaa aa aaa = = QLL 但对于任意有 只有 即是鞍点 证毕 10 7883 例1 - 2 2 - 2 7 4 3 8 5 8 - 6 2 - 1 2 6 3 * G 22 V3 (,)(,) ij = = 例2 022 543 234 2 4 3 425 minmax2 maxmin2

8、 , ij ji ij ji a a = = 鞍点不存在 即在纯策略意义下无解 11 例3 6 5 6 5 1 4 2 - 1 8 5 7 5 0 2 6 2 5578 5 5 - 1 0 * G 1214 3234 V5 (,)(,),(,), (,),(,) ij = = 鞍点不唯一,但值唯一。 1122 1122 1122 1221 1. (,), (,), 2 . (,), (,)G, (,), (,)G ijij i jij ijij ijij G aa = 例 3直 观 地 证 明 了 最 优 解 的 两 个 性 质 : 无 差 别 性 是的 两 个 解 则 可 交 换 性是的 两

9、 个 解 则也 是的 解 。 12 第三节 矩阵对策的混合策略与混合扩充 一、基本概念 T 4. (X , Y ),E (X , Y )XAY = 对 于 一 个 混 合 局 势用 表 示收 益局 中 人 的期 望 值 。 1: .局 中 人，。 * 11 1 * 21 1 2. S() |1,0 S() |1,0 m mii i n mii i Xxxxx Yyyyy = = = = LL LL 混合策略集 混合 的 的策略集 3. XYXY, (X,Y) 为 的混合策略,为的混合策略,选定和 则称为一个混合局势。 * 1212 5. (S ,S ,E)(S ,S ,A)= * 用表示的混合

10、扩充。 13 6.混合扩充的解与值 * * * * * * (,)(,)(, ) * (,): (,). G E X YE XYE XY VE XY XYG =的值满足 的解也称 在混合策略意义下的解 式 分析*式： * * * 1111 * 1 * 1 (,)(,)(, ) (,) () T n m mmn n E X YE XYE XY E XYXAY yaa xx aa y = = LLMOMM L 14 分析左式： * 11 * 1 * * 1 1 * (,)() () T m m n m m Ay E X YX AYxx A y AY xx A Y = = LLMM LLM 也可以写

11、成： 111 1 n mmn aa aa K MOM L * n y * 1 y m x 1 x M L * 11 * mm x AY x A Y M * XY 已固定， 将在 中选，使得收益最大 * 11 xAY M * mm xA Y M 15 进一步： * 11 * mm x AY x A Y M * * i G AYV中必有每个 *0 * * 0 L L因为若有某个 ，则 出即取 （） 此时矛盾。 0 i 16 性质1： * 11 1 i T j G mn ij ij AYV VVVX AV xy = = = 二、性质 性质2：松紧定理 * * ()0 ()0 T T XVAY VXA

12、 Y = = V V V = M其中 17 例4：猜手游戏 011 101 110 A = 该对策问题无纯策略最优， 在混合策略下求解： 解： 由性质1 T A YV XAV 可假设X，Y的所有分量均 为非零，则左式等号成立 2323 1313 1212 11 ii yyVxxV yyVxxV yyVxxV yx =+= += =+= = - 且 * 1 1 1 ( )0 3 3 3 XYV=解得 ， 18 ,1 ,1 ijkjik ik ijiljl jl Ai kaajn Alaa im = = L f L f 定义： 若 中第行有 称优超于 。 记 若 中第j 列有 称优超于 。 记 性

13、质3： 1212 1122 G(, )(,) ik k S SAGS SA SSSSAAk =f若中，构造新的 其中 是 去掉， ， 是 中去掉 行，则： * 111 * 111 () (0) G G kkm kkm VV yyXxxxx Xxxxx + + = = = LL LL 若， 则， ， 19 例5：用优超原理求解下列对策 1 0 3 4 - 1 4 0 1 2 2 2 3 0 4 1 1 A = 1 0 3 4 - 1 4 0 1 2 2 2 3 0 4 1 1 13 f 14 f 1 0 - 1 4 2 2 0 4 31 f 32 f 22 04 12 f 2 0 34 f 2（ ） A= * 31 * A minmaxmaxmin2, (0,0,1,0),(1,0,0,0),2 ijijG jjii G aaV YV = = * 对于即对策解是（）2。 根据性质3，则X 20 性质4： 21 112121221 212 (,),(,),(), () ij ijGG GS SAGS SAAa AadGGVVd = =+=+则：，同解，并且 21 112121221 212 (,),(,),(), () ij ijGG GS SAGS SAAa