对策理论谢家平

对策理论谢家平第1页/共41页2第10章

对策理论

理解对策模型的三大要素了解矩阵对策的基本定理

通晓纯策略和混合策略

掌握矩阵对策方程组法理解纳什定理和平衡偶掌握双矩阵对策的求解第2页/共41页3“田忌赛马”对策论（GameTheory），亦名“博弈论”

研究具有斗争或竞争性质现象的数学理论第1节对策论简介具有竞争或对抗性质的行为研究对策行为中竞争各方是否存在最合理行动方案,以及如何找到最合理行为方案的管理优化理论和方法一个决策主体,面对不确定环境下的收益最大化行为第3页/共41页4对策模型三要素局中人：在一个对策行为(或一局对策)中，有权决定自己行动方案的对策参加者。I={1,2,...,n}。理性人（有很好定义的偏好，在给定的约束下最大化偏好）策略集：指一局对策中,可供局中人选择的实际、可行、完整的行动方案，Si赢得函数：对任一局势s,局中人i可以得到一个赢得值Hi(s)。显然,Hi(s)是局势的函数,称为第个局中人的赢得函数(或支付函数)。第4页/共41页5对策问题的分类二人对策，多人对策零和对策，非零和对策合作对策，非合作对策有限对策，无限对策根据对策模型的数学特征：第5页/共41页6第2节矩阵对策一、矩阵对策的数学模型设局中人Ⅰ有个纯策略,局中人II有个纯策略,则局中人Ⅰ、Ⅱ的策略集分别为当局中人Ⅰ选定纯策略和局中人II选定纯策略后,就形成了一个纯局势。可见这样的纯局势共有个。对任一纯局势,记局中人Ⅰ的赢得值为。矩阵对策（二人有限零和对策,finitetwo-personzero-sumgame）第6页/共41页为局中人I的赢得矩阵(或为局中人II的支付矩阵)第7页/共41页其中：齐王的策略集:S1={1,2,3,4,5,6}，田忌的策略集：S2={1,2,3,4,5,6}。下面矩阵称齐王的赢得矩阵：8例10-1“田忌赛马”齐王在各局势中的益损值表（单位：千金）第8页/共41页第9页/共41页当赢得矩阵A=(ark)中等式成立时，双方才有最优纯策略并把（r,k）称为最优纯局势或对策G在纯策略下的解，又称鞍点。把其值v称之为对策G={S1，S2，A}的值。称G为有鞍点的对策。10矩阵对策的纯策略悲观准则第10页/共41页11乙甲β1β2β3min(aij)α1-71-8-8α23242α316-1-3-3α4-305-3max(aij)1625例10-2甲方“小中取大”，乙方“大中取小”=a22=2鞍点（2,2）对策G={S1，S2，A}的值v=2。第11页/共41页矩阵对策的混合策略设矩阵对策G={S1,S2,A}。当时，不存在最优纯策略。例11-412第12页/共41页对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的期望赢得最多（损失最少）--即混合策略。ⅡⅠβ1β2概率xiα136x1α254x2概率yjy1y2第13页/共41页14取,则故和分别为局中人Ⅰ和Ⅱ的最优策略,对策值(局中人Ⅰ的赢得期望值)。第14页/共41页二阶矩阵对策的通解公式乙甲β1β2甲方概率xiα1acx1α2bdx2乙方概率yjy1y2第15页/共41页16第16页/共41页二、矩阵对策的基本原理当局中人Ⅰ取纯策略时,记其相应的赢得函数为当局中人Ⅱ取纯策略时,记其相应的赢得函数为则是G的解的充要条件是：第17页/共41页则是G的解的充要条件是：存在数v,使得和分别是不等式组(Ⅰ)和(Ⅱ)的解,且。(Ⅰ)(Ⅱ)第18页/共41页矩阵对策及其解的性质定理1：对任一矩阵,一定存在混合策略意义下的解。定理2：设是矩阵对策G的解,,则：(1)若,则；（2)若,则；(3)若,则；(4)若,则。第19页/共41页第20页/共41页21记矩阵对策G的解集为T(G),关于对策解集的性质有如下三个定理：定理3：设有两个矩阵对策

其中,,L为任一常数,则有(1)(2)第21页/共41页定理4设有两个矩阵对策其中为任一常数。则(1)(2)

定理5设为一矩阵对策,且为斜对称矩阵(亦称对称对策)，则(1)(2),其中和分别为局中人Ⅰ和Ⅱ的最优策略集。第22页/共41页23矩阵对策的优超策略定义：设有矩阵对策,其中,,如果对一切都有,则称局中人Ⅰ的纯策略优超于；若对一切

,都有，则称局中人Ⅱ的纯策略优超于第23页/共41页24

优超原则：设为矩阵对策,其中,,,

如果纯策略被其余纯策略中之一所优超，由G可得到一个新的矩阵对策G’,,其中：于是有：(1)(2)G’中局中人Ⅱ的最优策略就是其在G中的最优策略;(3)若G是G’中局中人Ⅰ的最优策略,则便是其在G中的最优策略。若不是为纯策略中之一所优超,而是为的某个凸线性组合所优超，定理的结论仍然成立。第24页/共41页例10-5第25页/共41页第26页/共41页27三、矩阵对策的解法方程组法例10-6：求解矩阵对策——“田忌赛马”解：已知齐王的赢得矩阵为易知,A没有鞍点,即对齐王和田忌来说都不存在最优纯策略。设齐王和田忌的最优混合策略为和，从矩阵A的元素来看,每个局中人选取每个纯策略的可能性都是存在的,故可事先假定和,于是求解线性方程组：第27页/共41页28(I)(II)得到：，故齐王和田忌的最优混合策略为双方都以1/6的概率选取每个纯策略。第28页/共41页线性规划法(Ⅰ)(Ⅱ)第29页/共41页第30页/共41页(Ⅰ)(Ⅱ)第31页/共41页32例10-7：利用线形规划方法求解赢得矩阵为A的矩阵对策

求最优解及值。第32页/共41页（P)解：此题无鞍点,设局中人Ⅰ、局中人Ⅱ的混合策略分别为：并记对策的值为V。则此问题可化为：（D)第33页/共41页解得即原问题的解为：由第34页/共41页35第3节双矩阵对策

双矩阵对策（二人有限非零和对策）的数学模型局中人I选择,局中人II选择,则对策局势为,与这个局势相应的局中人I的收入为aij,局中人II的收入不再是-aij,而是bij,记作(aij,bij)。对这种对策,通常用G={I,II;S1,S2;A,B}表示,其中A={aij},B={bij}分别是局中人I与II的支付矩阵。第35页/共41页

囚徒B

坦白抵赖

坦白囚徒A

抵赖（囚徒A，囚徒B）

-8，-80，-10-10，0-1，-1囚徒困境第36页/共41页双矩阵对策的解法平衡偶在非零和对策中,设EI=(X,Y)与EII=(X,Y)分别是局中人I与II的收入,这里X∈S1,Y∈S2为任意策略。如果存在一对策略X*∈S1,Y*∈S2使得EI=(X,Y*)≤EI=(X*,Y*),EI=(X*,Y)≤EI=(X*,Y*)对任意的X∈S1,Y∈S2均成立,则称策略(X*,Y*)为双矩阵对策G的一个平衡偶纳什定理：（美国科学家纳什,1951年）任何具有有限个纯策略的二人对策(包括零和对策与非零和对策),至少有一个平衡偶第37页/共41页38例10-8：智猪博弈笼子里面有两只猪,一只大一只小。笼子很长,一头有一个踏板,另一头是饲料的出口和食槽。每踩一下踏板,在远离踏板的猪圈一边的投食口就会落下少量的食物。如果有一只猪去踩踏板,另一只猪就有机会抢先吃到另一边落下的食物。按一下按钮会有10个单位的猪食进槽,但是谁按按钮就会首先付出2个单位的成本。若大猪先到槽边,大小猪吃到食物的比例是9∶1；若大小猪同时到槽边进食,它们吃到食物的比例是7∶3；若小猪先到槽边,它们吃到食物的比例是6∶4。如表10—2所示,那么,在两头猪都有智慧的前提下,最终结果是什么呢？智猪博弈双矩阵： 小猪按等待大猪按（5,1）（4,4）等待（9，-1）（0,0）第38页/共41页解:以智猪博弈为例,说明纯策略下的纳什均衡的求取。(1)当小猪选择按按钮时,如果大猪也选择按按钮,大猪的赢得是5；如果大猪选择等待,大猪的赢得是9,所以在第一列的9下面划线；(2)当小猪选择等待时,如果大猪选择按按钮,大猪的赢得是4；如果大猪也选择等待,大猪的赢得是0,所以在第二列的第一个分量4下面划线；(3)当大猪选择按按钮时,如果小猪选择按按钮,小猪的赢得是1；如