运筹学：第十二章 博弈论

第十二章博弈论第一节博弈论的基本概念 第二节纯策略矩阵博弈第三节混合策略矩阵博弈第四节其它类型博弈简介博弈论------实际上就是多人决策！运筹学前面所介绍的优化管理方法，基本上是一个决策主体针对不同的实际内部条件和外部环境在做决策！其中内部条件的变化及外部环境的改变都是客观进行的，并非有意识地针对决策者！而博弈论是多人决策，决策的一方在选择自己的方案或策略时，其他人也在选择，并且会想方设法地让自己选择策略所获得的好处大于对方获得的好处！这样自己做决策时就必然要猜测考虑对方的行为！

第一节博弈论的基本概念一、博弈现象的三个基本要素局中人策略支付函数见如下例子：

我国古代的“齐王赛马”就是一个典型的博弈例子:战国时期，齐国国王与大将田忌进行赛马比赛。

双方约定：从各自的上、中、下三个等级的马匹中各选一匹参加比赛，分三场进行；每匹马只能参加一次；每一场比赛中的负者付给胜者一千金。已知:田忌的三匹马都略逊于齐威王相应的三匹马，但其上马、中马分别优于齐威王的中马和下马。田忌的一个谋士孙膑给田忌出了个主意：用下马对齐王的上马，中马对齐王的下马，上马对齐王的中马。这样田忌虽然输掉了一场比赛，但却赢得了另两场比赛，结果是赢得了一千金。1、局中人博弈中的决策者或参与者，用I表示局中人集合，如I={1,2,…,n}表示有n个局中人。局中人至少要有两个，个人和集体都可以作为局中人，如“齐王赛马”中的齐王和田忌。参与人的目的是通过选择行动或战略(策略)以最大化自己的支付(效用)水平。一、博弈现象的三要素2、策略局中人在整个决策过程中一系列行动的一个方案。如用（上、中、下）表示出场参赛的三匹马依此为上马、中马和下马，这就是局中人的一个策略。每个局中人

i的策略集合记为Si，如田忌和齐王的策略各有6个可供选择：上中下（先出上等马，再出中等马，最后出下等马）、上下中、中上下、中下上、下上中、下中上。每个局中人所出的一个策略形成的一个策略组为一个局势。设si是局中人i的一个策略，则n个局中人的策略形成的策略组s=(s1,s2,…,sn)就是一个局势。记S为全部局势的集合，即S=S1×S2×…×Sn。3、赢得函数当一个局势s出现后，每个局中人有一个赢得值Hi(s)。显然，Hi(s)是定义在S上的一个函数，称为局中人i的赢得函数。如“齐王赛马”中，国王选择了上中下，而田忌选择了下上中，则田忌将赢得这场比赛。田忌为何能赢这场？田忌一直能赢吗？田忌的赢率是多少？如下为“田忌赛马”游戏的支付矩阵。

齐王田忌上中下上下中中上下中下上下上中下中上上中下－3－1－11－1－1上下中－1－31－1－1－1中上下－1－1－3－1－11中下上－1－1－1－31－1下上中1－1－1－1－3－1下中上－11－1－1－1－3若双方同时选择策略，田忌的胜率只有1/6！当局中人和策略是有限时，把赢利数字写成矩阵形式，叫博弈矩阵的表示，其矩阵叫做博弈的支付矩阵。例如:“锤子、剪刀、布”游戏中，“锤子、剪刀、布”游戏，锤子击败剪刀，剪刀胜布，布胜锤子。参与双方各有三种方案：方案1代表出锤子，方案2代表出剪刀，方案3代表出布。假定胜者得1分，负者得-1分，两个局中人博弈的整个结果可用一个矩阵表示，该矩阵为局中人1的支付矩阵，见表12-1。参与者2参与者1锤子剪刀布锤子01-1剪刀-101布1-10博弈问题中还有一个很重要的概念:博弈问题的解。

经济学习惯把市场力量对持的结局称为市场均衡。

如供不应求将使价格上升；供大于求将使价格下降，供求力量对持的结果，会在一个价格水平达到市场供求均衡。

这个均衡就称为博弈的解。表12-1二、博弈问题举例及分类1.博弈问题举例“囚徒困境”是一个经典的博弈模型:警察抓住两个合伙犯罪的犯人，但却缺乏足够的证据指证他们所犯的罪行。如果只要其中一人供任犯罪，就能确认罪名成立。为了得到有用的口供，警察将两人分别关押以防止他们串供结成攻守同盟，并给他们选择的机会:如果两人都拒绝认罪，则他们将会被轻判各判1年；如果两人中有一个认罪，则认罪者从轻处理，立即释放，而另一人则重判8年；如果两人同时坦白认罪，则他们将各判5年监禁。囚徒一囚徒二坦白不坦白坦白不坦白囚徒一的支付矩阵1年5年释放8年如果分别用-1、-5、-8表示罪犯被判1年、5年和8年的支付，用0表示立即释放的支付，则囚徒1和囚徒2的支付矩阵分别表示为：囚徒2坦白不坦白囚徒1坦白-50不坦白-8-1囚徒2坦白不坦白囚徒1坦白-5-8不坦白0-1表12-2（b）囚徒2的收益矩阵表12-2(a)囚徒1的收益矩阵囚徒2坦白不坦白囚徒1坦白-5，-50，-8不坦白-8，0-1，-1第1个数字表示囚徒1的支付，第2数字表示囚徒2的支付。这个支付矩阵也称为双支付矩阵。表12-3

－5，－50，－8－8，0－1，－1因为“囚徒困境”模型中，囚徒1的所得不等于囚徒2的所失，所以不是零和博弈，要用下面的双支付博弈矩阵来表示囚徒1坦白不坦白囚徒2

坦白不坦白两个囚徒在选择自己的策略时，都是想让自己效用最大化，但最终作出的选择却是对己对人都无好处！这就是所谓的囚徒困境！囚徒困境应用1：搭便车分析假设：学生A和B同处一室，各有财产300元；夏季对风扇的福利评价分别为100元（即风扇给各自带来的效用是100元），风扇价格为160元，合伙买风扇的收益为200-160=40元（各享受20）。学生B

买风扇不买风扇买风扇320，320240，400

学生A

不买风扇400，240300，300

囚徒困境应用2：

广告博弈－－高成本的纳什均衡：纳什均衡：两烟草企业选择（做广告，做广告）做广告的成本很高，可能要降低原有的利润！烟草企业1烟草企业2囚徒困境应用3——产品定价策略：

例、两个生产相同产品的企业A、B，在决定自己产品的价格时，有高价、中价、低价三个策略。如A、B都选择高价（中价、低价），则AB分别收益6、5、4元；如AB选择不一致，则定价高的将会失去市场，如下表：低价高价低价6，60，100，810，00，88，08，04，4A企业B企业高价中价中价5，5求Nash均衡的方法（划线法）-----推荐方法C1C2C3R1R2R3100，1000，050，10150，01，160，00，3000，0200，200用政策或法律解决“囚徒困境”举例：治理污染不治理污染治理污染不治理污染10，103，1212，35，5某地有甲乙两个企业，生产中都会污染环境，治理污染需要花费资金，若大家都治理，环境好了，对双方、对整个社会都有利，但若只有一家治理，花了钱，环境也不能变好，自己的利润将会下降。数据如上表：甲企业乙企业治理污染不治理污染治理污染不治理污染10，103，88，35，5甲企业乙企业很显然上面的博弈甲乙两个企业陷入了囚徒困境，其结果对两企业自身、对整个社会都没有好处。设X＝4>12-10，可表示为政府对污染企业的罚款。上表中企业不治理污染，利润将在12的基础上减4。存在两个纳什均衡。通常，若存在多个纳什均衡，理性的决策者都会选择对己对人都好的那个均衡！猎手博弈：每个局中人的策略空间为（猎鹿，猎兔）猎人2

猎鹿猎兔猎鹿5，50，3

猎人1

猎兔3，03，3

在该猎手博弈中，有两个Nash均衡（猎鹿，猎鹿），（猎兔，猎兔），到底应该出现哪个呢？（猎鹿，猎鹿）是帕累托优势均衡，总效用最大!

（猎兔，猎兔）是风险上策均衡，期望效用（得益）最大，无风险！因每个猎手选择猎鹿的期望效用为2.5，选择猎兔的期望效用（实际效用）为3。

例、考试作弊（官员贪污）博弈9，99，99，90，30，8－10，33，08，03，－102，27，72，2甲作弊（贪污）不作弊（不贪污）乙

作弊（贪污）不作弊（不贪污）最常见2.博弈分类 第二节纯策略矩阵博弈一、纯策略意义下的解二、纯策略意义下解的存在性一、纯策略意义下的解

假设：1）局中人充分了解相互的得失；2）局中人是理性的；3）局中人间不允许存在任何协议。用I和II分别表示即两个局中人。 局中人I有m个策略，S1={

1,

2,…,

m}；局中人II有n个策略，S2={

1,

2,…,

n}。 当局中人I选策略

i，局中人II选策略

j，就形成了一个局势(

i,

j)——纯局势。两人有限博弈称为矩阵对策。两人：局中人为两个，即n=2。有限：每个局中人的策略有限，即S1和S2为有限集。零和：在任一局势下，两个局中人的赢得值之和为零，即

H1(s)+H2(s)=0,

s

S非零和：在任一局势下，两个局中人的赢得值之和不为零，即

H1(s)+H2(s)≠0,

s

S 对任一局势(

i,

j)，用aij记局中人I的赢得值，称矩阵 为局中人I的赢得矩阵。对于零和对策，局中人II的赢得矩阵为-A。

设G={S1,S2;A}为一个矩阵对策，其中S1={

1,

2,…,

n}，S2={

1,

2,…,

n}，A=(aij)m×n。若 则称该值为对策G的值，记为VG；使上式成立的纯局势(

i*,

j*)称为对策G在纯策略意义下的解；

i*和

j*，分别为局中人I和II的最优纯策略。例12.1设局中人1的策略为：；局中人2的策略为：；局中人1的支付矩阵为：求该矩阵博弈的鞍点及最优策略。局中人I局中人III的最优策略（行）II的最优策略（列）如果局中人1选择策略A1，则他至少可得：

如果局中人2选择策略B1，则他至多失去：

如果双方都不想冒险，则都会从坏的打算出发，然后得到最好的结果。……

所以，如果局中人1选择策略Ai，则他至少可以得到支付因此局中人1可以选择i，使他得到的支付不小于

同理，如果局中人2选择策略Bj，则他至多失去因此，局中人2可以选择Bj，使他失去的不大于

二、纯策略意义下解的存在性

定理12.1矩阵对策G={S1,S2;A}在纯策略意义下有解的充要条件是：存在纯局势(

i*,

j*)，使得对任意i和j，有当局中人1偏离策略(

i*,

j*)时，他的赢得变小，当局中人2偏离策略(

i*,

j*)时，他的付出变大。证明:已知必要条件：已知另一方面：

充分条件：定理12.2.

如果和都是矩阵博弈:的鞍点，则和也是它的鞍点，且在鞍点处的值相等，

第三节混合策略矩阵博弈一、混合策略意义下的解二、混合策略意义下解的存在性三、均衡解的计算一、混合策略意义下的解 定义12.2

设G={S1,S2;A}为一个矩阵对策，其中S1={

1,

2,…,

m}，S2={

1,

2,…,

n}，A=(aij)m×n。

记S1*={x

Em|xi

0,i=1,2,…,m;

ixi=1}

S2*={y

En|yj

0,j=1,2,…,n;

jyj=1} 分别称S1*和S2*为局中人I和II的混合策略集合；x

S1*和y

S2*称为混合策略，(x,y)称为混合局势。纯策略是混合策略的特例。定义12.3

对任意的x*

S1*和y*

S2*，如果存在x

S1*和y

S2*，使则称是矩阵博弈混合策略意义下的一个鞍点（或均衡）。如果存在，使，则混合局势称为该矩阵博弈的最优解。和分别称为局中人1和局中人2的最优混合策略。v为该矩阵博弈的均衡值。二、混合策略意义下解的存在性定理12.3

矩阵博弈一定存在混合策略意义下的解。该定理是纳什定理的特殊情况，纳什定理是说：每一个有限博弈都至少存在一个混合策略纳什均衡。有关纳什均衡这里不在详细讨论，请读者参考有关书籍。由混合策略意义下均衡的定义21.3，很容易得到如下定理。

定理12.4

设x*

S1*和y*

S2*，则(x*,y*)为对策G的解的充要条件是：存在数v，使得x*和y*分别是下列不等式组的解，且v=VG。定理12.5

设有两个矩阵博弈G={S1,S2;A}和G={S1,S2;A}，其中A=(aij)m×n

，A=(aij+L)m×n，L为任意常数，则(1)vG

=vG+L；(2)G和G有相同的解集定理12.6

设有矩阵博弈G={S1,S2；A}和G={S1,S2；A}，其中A=(aij)m×n

，A=(

aij)m×n，

为任意正常数，则（1）vG=

vG；（2）G和G有相同的解集。三、均衡解的计算例12.2：设G={S1,S2;A}为一个矩阵对策，其中S1={

1,

2}，S2={

1,

2,

3}， 设局中人I的混合策略为(x,1-x)T，x

[0,1]。（一）作图法 横坐标表示局中人I混合策略的x，纵坐标表示局中人I的赢得值v。 根据定理3，对任意i=1,2,…,m和j=1,2,…,n， 得到

在直线的下方，找最大的v则本题的3条直线分别如下，其围成的公共区域见图12-1到图12-4:

即x=3/11，v=49/11。111257230x*

1

2

3xI(v)II(v)

局中人I最优混合策略(x*,1-x*)T=(3/11,8/11)T，赢得值VG=49/11。根据定理12.6得到局中人II最优混合策略(y1*,y2*,y3*)T=(0,9/11,2/11)T

定义12.4:设矩阵对策G={S1;S2;A}，其中S1={α1,…,αm},S2={β1,…,βn}，A=(aij)(——局中人I的支付矩阵），若对一切j=1,…,n有：

ai0,j≥ak0,j即矩阵A的第i0行元素均不小于第k0行的对应元素，则称局中人I的纯策略αi0优超于αk0。同理，若对一切

i=1,…,m有ai,j0≤ai,k0

则称局中人II的纯策略βj0优于βk0。行删小，列删大。（二）优超法定理12.7:设矩阵对策G={S1;S2;A}，其中S1={α1,…,αm},S2={β1,…,βn}，A=(aij)，若纯策略α1被其余纯策略α2,…,αm中之一所优超，由G可得到一个新的矩阵对策G={S`1;S`2;A`}，其中S`1={α2,…,αm},S2={β2,…,βn}，A`=(a`ij)，则有：（1）V`G=VG；（2）G`中局中人II的最优策略就是G中的最优策略（3）若(x2,x3,…,xm)是局中人I的最优策略，则x=(0,x2,…,xm)是G的最优策略。例12.3：设赢得矩阵为：求其均衡点例、如下是甲乙两人的博弈矩阵。

双方选择策略的宗旨：从最坏处着眼，寻找最好的结果！是否所有的二人有限零和博弈矩阵都有鞍点？回答是否定的，见如下的矩阵：局中人A、B各有4个策略，矩阵中的数值是A的所得或B的所失。a1a2a3a4b1b2b3b4AB12003487该博弈矩阵没有鞍点！即没有纯策略解，只能求混合策略解是否所有的二人有限零和博弈矩阵都有鞍点？为了求出混合策略解，需要先化简博弈矩阵采用优势原则（汰劣法或优超法）a1a2a3a4b1b2b3b4AB比较矩阵的1，3，4行，发现c1j≧c3j，c1j≧c4j，因此可以划去3，4行(a3,a4是A的劣势策略）同理，可以划去3，4列（b3，b4是B的劣势策略）

原来的博弈矩阵就简化为2×2博弈矩阵，而对于这样的矩阵，有多种方法可以求出其混合策略解（反应函数法，线性规划法，综合求解法）下面介绍一种综合求解法：a1a2b1b2X—局中人A采用a1的概率1－x—A采用a2的概率y1－y—B采用b2的概率B采用b1的概率令E（x，y）表示局中人A的期望赢得值

解得x＝1/4，y=1/2，A的赢得值（均衡值）为5/2（三）反应函数法例12.4．局中人1、2玩扑克牌游戏，如果同时出红色或黑色，则局中人1得-1分，局中人2得1分；如果同时出的颜色不同，则则局中人1得1分，局中人2得-1分。现在设局中人1的混合策略是以的概率出红牌和以的概率出黑牌；局中人2的混合策略是以的概率出红牌和以的概率出黑牌。支付矩阵如下：计算在局中人1、2的混合策略分别是和时的最优混合策略和期望支付是多少。红黑红黑局中人2局中人1-1，11，-1

1，-1-1，1局中人1的期望支付为：因为，局中人1只能选择p不能选择q，所以当时，局中人1把p选的越大越好，即:p=1当时，局中人1把p选的越小越好，即:p=0当时，局中人1可任意选择p。所以，如果局中人2的混合策略是（q,1-q），局中人1的最佳反应函数是：同理，局中人2的期望支付为：局中人2的最佳反应函数是：以p为纵轴、以q为横轴，把局中人1、2的反应函数画在Opq直角坐标系中，两个反应函数交点，就得到混合策略的鞍点。所以，。故局中人１和局中人２的最优混合策略均为：；在处的期望支付为：。（四）线性规划法首先，选取一个适当的常数c加到支付矩阵A的每个元素上，使得到的新矩阵的所有元素都是正数，即然后，转化为线性规划问题，即求解下列规划：设最优解是最优函数值是。则局中人１最优混合策略均衡值是

同理，求下列线性规划：设最优解是最优函数值是局中人２的最优混合策略均衡值是例12.5．用线性规划法计算例12.4。

解：最优混合策略是

求其对偶问题的解得局中人2的最优策略：首先，取，则：

变为第四节其它类型博弈简介一、多人非合作博弈二、非零和博弈一、多人非合作博弈定理12.8：每一个n人非合作博弈必存在纳什均衡点。例12.6．求“囚徒困境”博弈模型(见表12-5)的Nash均衡。

解：由表12-5可得均衡点。其结果见表