运筹学对策论

运筹学对策论2

在日常生活中，我们经常看到一些相互之间的竞争、比赛性质的现象，如下棋、打扑克、体育竞赛等。

在经济领域，各国之间的贸易谈判，各公司、企业之间的市场争夺，各公司、企业之间的加工、订货、合作谈判等等，都是竞争现象。

在政治方面，国际上政府间的各种外交谈判，各方都想在谈判中处于有利地位，争取到对自己有利的结果。各国之间或国内各集团之间的战争，是一种你死我活的斗争，双方都千方百计要战胜对方。第2页,共78页，2024年2月25日，星期天3

例：两个儿童玩的“石头—剪子—布”游戏和我国古代的“齐王赛马”就是典型的对策论研究的例子。

在这类行为中，参加斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案，对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。第3页,共78页，2024年2月25日，星期天4二、对策问题的三个基本要素

（1）局中人：在一场竞赛或斗争中，每一个有决策权的参与者(个人或集团)称为一个局中人。只有两个局中人的对策现象称为“两人对策”，而多于两个局中人的对策称为“多人对策”。

（2）策略：一个对策中，每个局中人都有供他选择的实际可行的完整的行动方案，我们把一个局中人一个可行的自始至终通盘筹划的行动方案，称为这个局中人的一个策略。如果在一个对策中，每个局中人都只有有限个策略，则称为“有限对策问题”，否则称为“无限对策问题”。第4页,共78页，2024年2月25日，星期天5

（3）赢得函数（支付函数）：一局对策结束时的结果（如收入或支出）称为得失。每个局中人在一局对策结束时的得失，不仅与该局中人自身所选择的策略有关，而且与全体局中人所取定的一组策略有关。所以，一局对策结束时每个局中人的“得失”是全体局中人所取定的一组策略的函数，通常称作赢得函数（支付函数）。把每个局中人各自所取的一个策略所组成的策略组称为“局势”，于是“得失”是“局势”的函数。第5页,共78页，2024年2月25日，星期天6第二节矩阵对策的基本定理

特点：①局中人只有两人，分别用局中人Ⅰ和局中人Ⅱ表示，双方都只有有限个策略可供选择，②局中人的“得失”相加等于零，这种对策称为“零和对策”。在两人有限零和对策中，局中人Ⅰ的所获等于局中人Ⅱ的所失。假定在局势(αi,βj)下(即局中人Ⅰ取策略αi

，局中人Ⅱ取策略βj

时所形成的局势)，局中人Ⅰ的收入或赢得是aij（“aij”是负数时，表示局中人Ⅰ是支出）。Ⅰ的策略集为：Ⅱ的策略集为：一、矩阵对策的数学模型第6页,共78页，2024年2月25日，星期天7

用矩阵表示为(称为局中人Ⅰ的赢得矩阵或局中人Ⅱ的支付矩阵):

我们称两人有限零和对策为矩阵对策，记为：G＝{Ⅰ,Ⅱ；S1,S2；A}

或G＝{S1，S2；A}。第7页,共78页，2024年2月25日，星期天8例1:设有矩阵对策，局中人Ⅱ的支付矩阵如下：

如果各局中人都不想冒险，必须考虑对方会选择策略使他得到最差的收入。因此各局中人都选择理智的决策行为。解：

α3→α3→β1→α4→β3第8页,共78页，2024年2月25日，星期天9

局中人Ⅰ的各种策略的最差收入是支付阵中各种策略所对应行的最小数。如果不存侥幸心理，他对每个策略只能期望得到最差的收入。即：

那么为了得到尽可能好的结局，只能从这些最小数之中的找最大者（最大的最小者），即选择能在最差的可能结果中得到最好结果的策略。即：－8，2，－9，－3即选择策略α2。第9页,共78页，2024年2月25日，星期天10

同样，局中人Ⅱ的各种策略的最差收入（最大支出）是支付矩阵中各列的最大数，即：局中人Ⅱ选择这些最大数中的最小者。即：16，2，5即选择策略β2。Ⅰ的最优策略为α2,Ⅱ的最优策略为β2

。第10页,共78页，2024年2月25日，星期天11

定义:设G＝{S1，S2；A}为矩阵对策,其中S1＝{α1,α2,…αm}，S2＝{β1,β2,…βn}。A=(aij)m×n，若满足等式：

则称纯局势(αi*，βj*)为G在纯策略下的解（或平衡局势）。记VG＝ai*j*，称VG为对策G的值,αi*，βj*分别称为局中人I、II的最优纯策略。

例1的对策G的解为（α2，β2），α2，β2分别是局中人I和II的最优纯策略，VG=2。

从例1中可以看出，矩阵的元素a22既是所在行的最小元素，又是所在列的最大元素，即：第11页,共78页，2024年2月25日，星期天12

定理1：矩阵对策A=(aij)m×n有解的充分必要条件是：存在纯局势(αi*，βj*)，使得对一切i=1,2,…,m,j=1,2,…,n均有：i=1,2,3,4；j=1,2,3

将这一事实推广到一般矩阵对策，可得如下定理：证明：先证充分性，由于对任意i，j均有：

故：第12页,共78页，2024年2月25日，星期天13另一方面，对任意i，j均有：所以：于是：所以：第13页,共78页，2024年2月25日，星期天14再证必要性，若G有解。而对于所有的i而言，必存在一个i*使：对于所有的j而言，必存在一个j*使：因为：于是：第14页,共78页，2024年2月25日，星期天15称满足条件的(αi*,βj*)为矩阵对策G的一个鞍点。但：于是有：故对一切的i,j都有：

意义：如果局中人I选择策略αi*

，局中人II不选择策略βj*

，而选择策略βj，则局中人II的支付只会增多。也就是说：策略βj*是II的最优策略。第15页,共78页，2024年2月25日，星期天16

注意：一个矩阵对策G如果存在鞍点，鞍点可能不止一个。但是在不同的鞍点处，支付值相等，都等于对策的值。（无差异性）

如果(αi,βj)以及(αk,βl)都是对策G的鞍点，则(αk,βj)与(αi,βl)也是该问题的鞍点。（可交换性）

同样，如果局中人II选择策略βj*

，局中人I不选择策略αi*

，而选择策略αi，则局中人I的所获只会减少。也就是说：策略αi*是局中人I的最优策略。第16页,共78页，2024年2月25日，星期天17G有四个鞍点：对策的值为VG＝

5。例2：给定矩阵对策G＝{S1，S2；A}，其中：第17页,共78页，2024年2月25日，星期天18二、矩阵对策的混合策略

矩阵对策G有鞍点时，就存在最优解(最优纯策略)，但是否一切矩阵对策问题中，各局中人都有上述意义的最优纯策略呢?答案是否定的。例1：石头、剪刀、布不存在上述纯策略意义下的解。第18页,共78页，2024年2月25日，星期天19

对于该例而言，直观的看：双方采用三个纯策略的频率均应为1／3：1／3：1／3。由于每个局中人在一局对策中必取某个纯策略，因此采取任何一个纯策略的概率都应是1／3。

一般地，设局中人I以概率x1,x2,…，xm来分别选取他的纯策略α1，α2，…αm

；而局中人II以概率y1,

y2,…，yn来选用自己的纯策略β1，β2，…βn

。于是：令x=(x1,x2,…，xm)T,y=(y1,y2,…，yn)T则称这样的x和y为局中人I、II的混合策略。第19页,共78页，2024年2月25日，星期天20记：

此时，当局中人I以概率

xi采用αi

时，局中人II以概率

yj采用

βj

时，支付aij

出现的概率为xi

yj

。于是局中人I收入（赢得）的期望值为：

则称G＊＝{S1＊，S2＊；E}为G＝{S1，S2；A}的混合扩充。第20页,共78页，2024年2月25日，星期天21混合策略对策矩阵可表示如下：

混合策略问题的解也是以最大最小化和最小最大化标准为根据的。第21页,共78页，2024年2月25日，星期天22

当局中人I选择某个混合策略

x

时，对于局中人II的任意选择y,

I的期望所获至少是：

于是局中人I希望选择x，使上式最大，保证局中人I的期望所获不小于：

这就是局中人I的最大最小化标准。

同理：当局中人II选择某个混合策略y

时，对于I的任意选择x，II的期望支付至多是：

于是局中人II希望选择

y，使上式最小，保证局中人II的期望支付不多于：这就是局中人II的最小最大化标准。第22页,共78页，2024年2月25日，星期天23例1：求解矩阵对策G＝{S1，S2；A}

，其中：如果令：则得问题的最优解。解：设X=(x,1－x)T,Y=(y,1－y)T

且对策的值为：第23页,共78页，2024年2月25日，星期天24另解：

（用微分求极值的方法）且对策的值为：第24页,共78页，2024年2月25日，星期天25

定义

:

G＊＝{S1＊,S2＊；E}为矩阵对策G＝{S1,S2；A}的混合扩充，若存在(x*,y*)满足等式：则称(x*,y*)为G在混合策略下的解。称VG＝E(x*,y*)

为对策G的值,x*,y*分别称为I、II的最优混合策略。

定理2：混合策略x*和y*是G的解的充分必要条件是：对一切混合策略x,y有：称(x*,y*)是对策问题在混合策略意义下的鞍点。第25页,共78页，2024年2月25日，星期天26当局中人I

取纯策略αi时，记其赢得函数为于是三、矩阵对策的基本定理当局中人II取纯策略βj时，记其赢得函数为于是第26页,共78页，2024年2月25日，星期天27则有：

定理3：混合策略x*和y*是G的解的充分必要条件是：对任意的i,j有：第27页,共78页，2024年2月25日，星期天28则证明：必要性显然，只需证充分性，若对任意i,j均有：即：所以x*和y*是G的解。第28页,共78页，2024年2月25日，星期天29注意到：可以写成：于是定理3可以改述为：

定理4：矩阵对策G＝{S1,S2；A}有解的充要条件是存在数v，使得x,y

分别是下述两个不等式组的解：第29页,共78页，2024年2月25日，星期天30

定理5：（对策基本定理）任何矩阵对策G在混合策略下一定有解。证明：由定理3，只需证明存在混合策略x*和y*，使得（3）式成立，为此考虑如下两个线性规划：第30页,共78页，2024年2月25日，星期天31容易验证（P）和（D）是互为对偶规划，而且

是（P）的一个可行解，是(D)的一个可行解，由线性规划对偶理论可知，(P)和(D)是都存在最优解(x*，w*)

和(y*,v*)，且最优值w*=v*，即:i=1，2,…,m,j=1，2,…,n.第31页,共78页，2024年2月25日，星期天32又由：可得：

定理5的证明是构造性的证明，同时给出了求解方法。第32页,共78页，2024年2月25日，星期天33

定理6：设（x*，y*）是矩阵对策G解，v=VG，则第33页,共78页，2024年2月25日，星期天34矩阵对策G＝{S1，S2；A}。（1）若（即A中第k行的每个元素≥A中第l行的每个元素）称局中人I的策略αk优超于策略αl

；则可在A中去掉第l行，矩阵对策G的解不变。（2）如果：（即A中第k列的每个元素≤A中第l列的每个元素）称局中人II的策略βk

优超于策略βl

。则可在A中去掉第第l列，矩阵对策G的解不变。优超定理：第34页,共78页，2024年2月25日，星期天35第三节矩阵对策的求解一、2×2对策的方程法则称G为2×2对策。

若G没有纯策略下的解，则G的最优混合策略x*=(x1,

x2

)T,y*

=(y1,y2

)T满足下列方程组：且其中v=VG

.第35页,共78页，2024年2月25日，星期天36例1：求解求解矩阵对策G＝{S1，S2；A}

，其中：解：在A中由于：第3行≥第2行，第4行≥第1行，因此从A中划去1，2两行，得：第36页,共78页，2024年2月25日，星期天37在A1中由于：第1列≤第3列，第2列≤第4列，因此从A1中划去3，4两列，得：在A2中由于：第1行≥第3行，因此从A2中划去第3行，得：在A3中由于：第2列≤第3列，因此从A3中划去第3列，得：第37页,共78页，2024年2月25日，星期天38分别求解方程组得：得x3=1/3,x4

=2/3,y1=1/2,y2

=1/2,v=5.由此对于原问题A而言，最优解为：第38页,共78页，2024年2月25日，星期天39二、2×n和m×2对策的图解法解：设局中人I

的混合策略为(x,1－x)T,局中人I

的最少得益为如下图中由局中人II

选择β1,β2,β3

时所确定的三条直线2x

＋7(1－x)＝v，3x

＋5(1－x)＝v，11x

＋2(1－x)＝v在x处纵坐标的最小者，即如图中折线B1BB2B3。例2：求解求解矩阵对策G＝{S1，S2；A}

，其中：第39页,共78页，2024年2月25日，星期天40012511237xVVβ3β1β2B1BB2B3A

所以对局中人I来说，他的策略就是确定x使他的得益达到最大。按最大最小原则应选择x＝OA，而AB即为对策的值。为求出x和对策的值VG

，可联立过B点的两条直线β2和β3所确定的方程。第40页,共78页，2024年2月25日，星期天41解得：x

＝3/11，VG=49/11。此外从图中可看出，局中人II的最优策略只由β2和β3组成（不选β1），可由方程组所确定：解得：y2=9/11，y3=2/11。所以最优解为：第41页,共78页，2024年2月25日，星期天42例3：求解矩阵对策G＝{S1，S2；A}，其中：

解：设局中人II

的混合策略为(y,1－y)T,局中人II的最大支付为如下图中由局中人I选择α1,α2,α3

时所确定的三条直线2y＋7(1－y)＝v，9y＋6(1－y)＝v，11y＋2(1－y)＝v在y处纵坐标的最小者，即如图中折线上的B点。第42页,共78页，2024年2月25日，星期天43012611297yVVBAα1α2α3

对局中人II来说，他的策略就是确定y使他的支付达到最小。按最小最大原则应选择y＝OA，为求出y和对策的值VG，可联立过B

点的两条直线α1和α2所确定的方程。第43页,共78页，2024年2月25日，星期天44解得：y＝1/8，VG=51/8。

此外从图中可看出，局中人II的最优策略只由α1和α2组成（不选α3），可由方程组所确定：解得：x1=3/8，x2=5/8。所以最优解为：第44页,共78页，2024年2月25日，星期天45三、线性规划法由前面定理可知，对策G的解满足下列线性规划：作变量替换：第45页,共78页，2024年2月25日，星期天46则于是上述线性规划等价于下面的线性规划问题。

由此求解一个对策问题，就相当于求解上面的对偶问题：第46页,共78页，2024年2月25日，星期天47例4：利用线性规划法求解矩阵对策G＝{S1,S2；A}.【注】如果aij不满足非负性，则存在一个正数k，使得aij+k≥0

令B=(bij)=(aij+k)，求解对策问题

{S1，S2；B}

，可以证明：问题{S1，S2；B}与问题{S1，S2；A}的最优策略相同，且有：其中：第47页,共78页，2024年2月25日，星期天48解：建立相应的线性规划模型及用单纯形法求解后一个问题，先标准化为：第48页,共78页，2024年2月25日，星期天49用单纯形表求解如下：第49页,共78页，2024年2月25日，星期天50第50页,共78页，2024年2月25日，星期天51由此最优解为：第51页,共78页，2024年2月25日，星期天52第四节两人有限非零和对策

例1：“囚徒困境”甲乙是同案囚犯，被隔离审讯。如果两个都抵赖，因为证据不充分，两人都只能判1年。如果只有一方坦白，则无罪释放；而另一方则属抗拒从严，判10年。但如果两人都坦白，则各判5年。

下表给出了“囚徒困境”博弈问题的战略式表述，为了实现各自的效用最大化，双方格采取何种策略呢?

坦白β1抵赖β2坦白α1(－5,－5

)(0,－10

)抵赖α2(－10，0

)(－1,－1

)第52页,共78页，2024年2月25日，星期天53

假设该博弈是一次性的，对于囚犯甲而言，不管乙选择坦白还是抵赖，他选择坦白都比选择抵赖更好。这种不管对方选择何种策略，局中人的最优选择总是不变的那个策略被称为该局中人的优超策略。此例中坦白为甲的优超策略，同样道理坦白也是乙的优超策略。结果是，两个囚徒争先恐后地都选择坦白，各判刑5年。从而(坦白，坦白)也就构成了该博弈的优超策略均衡（称为纳什均衡）。第53页,共78页，2024年2月25日，星期天54

囚犯困境反映了一个深刻的问题，这就是个人理性与集体理性的矛盾，如果两个人都抵赖，对局中人组成的集体而言，可谓帕累托最优，但是这并不满足个人理性导致的纳什均衡(坦白，坦白)，因而，这个帕累托改进在静态博弈中办不到。囚徒困境说明纳什均衡并不一定导致帕累托最优，从而动摇了传统经济学中个人效用最大化行为必然导致社会福利最优的基本命题。

对囚犯困境问题作进一步分析，不难发现，尽管甲与乙各自的最佳选择都是坦白，如果双方均选择抵赖，各判刑1年，显然比双方均坦白时答判刑5年的结局要好，因此，其最佳选择与最优结局并不一致。出现所谓的“囚徒困境”。第54页,共78页，2024年2月25日，星期天55

设对策G的局中人Ⅰ和Ⅱ，双方都只有有限个策略，其中

在局势(αi,βj)下(即局中人Ⅰ取策略α，局中人Ⅱ取策略βj

时所形成的策略组合)，局中人Ⅰ的赢得值是aij，局中人Ⅱ的赢得值是bij。分别用矩阵表示为A和B。Ⅰ的策略集为：Ⅱ的策略集为：非合作两人对策第55页,共78页，2024年2月25日，星期天56

定义：对于非合作两人对策G，如果αi*是局中人Ⅰ对Ⅱ的策略βj*的最优策略，βj*是局中人Ⅱ对Ⅰ的策略αi*的最优策略，则称局势(αi*，βj*)是该问题的一个纳什均衡（即谁都不愿单独改变策略）

。第56页,共78页，2024年2月25日，星期天57

本博弈的纳什均衡为(大猪按，小猪等待)。

例2：“智猪博弈”猪圈有一头大猪、一头小猪，按一下按钮会有10个单位的饲料，但按按钮需要2个单位成本。

按β1等待β2按α1(5，1

)(4，4

)等待α2（9，－1）(0，0

)第57页,共78页，2024年2月25日，星期天58

例3：“夫妻博弈”丈夫喜欢看球赛，妻子喜欢逛商场。他们都宁愿在一起，也不愿分开行动。

本例有两个纳什均衡结果会出现，要么一起去看球赛，要么一起去逛商场，但在一次博弈中究竟会出现哪一种？

看球赛β1逛商场β2看球赛α1(2，1

)(0，0

)逛商场α2(0，0

)(1，3)第58页,共78页，2024年2月25日，星期天59

这个博弈也有两个纳什均衡，一个是(进攻，退却)，另一个是(退却，进攻)。

进攻β1退却β2进攻α1(-3，-3

)(2，0

)退却α2(0，2

)(0，0)

例4：“斗鸡博弈”有两个斗鸡A、B，它们各有两个策略：进攻或退却。第59页,共78页，2024年2月25日，星期天60(0，300

)(0，300

)不进入α2(－10,0

)(40,50

)进入α1阻挠β2默许β1

进入者在位者

这个博弈也有两个纳什均衡，一个是(进入，默许)，另一个是(不进入，斗争)，而(不进入，默许)却不是一个纳什均衡。

例5:

“市场进入壁垒”

设想一个垄断企业已占领市场(称为“在位者”)，另一个企业很想进入市场(称为“进入者”)，在位者想保持其垄断地位，就要阻挠进入者进入．假定双方在各种策赂组合下的赢得短阵如表所示：第60页,共78页，2024年2月25日，星期天61非合作两人对策的解法

对其他局中人的任一策略组合，找出局中人i的最佳策略，并在其得益值下划线。若存在一个策略组合，使得所有局中人的得益值下都划了线，则该策略组合就是一个纳什均衡。求纳什均衡的方法如下:第61页,共78页，2024年2月25日，星期天62例1：囚犯困境(－1，－1

)(－10，0

)抵赖α2(0,－10

)(－5,－5

)坦白α1抵赖β2坦白β1

甲乙因此(坦白，坦白)

构成了该博弈的纳什均衡。第62页,共78页，2024年2月25日，星期天63例3：夫妻博弈

看球赛β1逛商场β2看球赛α1(2，1

)(0，0

)逛商场α2(0，0

)(1，3)

这个博弈有两个纳什均衡，一个是(看球赛，看球赛)，另一个是(逛商场，逛商场)。第63页,共78页，2024年2月25日，星期天64(0，300

)(0，300

)不进入α2(－10,0

)(40,50

)进入α1阻挠β2默许β1

进入者在位者例5:市场进入壁垒

因此(进入，默许)和(不进入，阻挠)是该问题的两个钠什均衡。第64页,共78页，2024年2月25日，星期天65混合策略纳什均衡

上面介绍了在纯策略意义下非合作两人对策纳什均衡的概念及求解方法，但有些对策不存在纯策略意义下的纳什均衡，考虑下面的例子。第65页,共78页，2024年2月25日，星期天66(0，0)(－1，1

)不救济α2(－1,3

)(3,2)救济α1游荡β2寻找工作β1

政府流浪汉

例6：局中人是政府和一个流浪汉，流浪汉有两个策略：寻找工作或游荡；政府也有两个策略：救济或不救济。政府帮助流浪汉的前提是后者必须试图寻找工作；否则，政府不予以帮助；而流浪汉只在得不到救济时才会寻找工作，如表给出了对策的赢得双矩阵：第66页,共78页，2024年2月25日，星期天67

同样局中人可以考虑按照一定的随机方式来确定一个策略组合的混合策略。每个局中人作出决策时，不是只选用一个纯策略，而是按照预先确定的一组概率来选取他们所有可能采用的策略。

容易理解：当流浪汉选择寻找工作时，政府的最优策略是救济；当流浪者选择游荡时，政府的最优策略是不救济；当政府策略为不救济时，流浪汉的最优策略是寻找工作；当政府选择救济时，流浪汉的最优策略是游荡。总之，在纯策略下，没有一个策略组合构成纳什均衡。第67页,共78页，2024年2月25日，星期天68

局中人I以概率x1,x2,…,xm来分别选取纯策略α1,α2

…,αm

；而局中人II以概率y1,y2,…，yn来选用自己的纯策略β1,β2,…,βn。于是：

称x=(x1,x2,…，xm)T,y=(y1,y2,…，yn)T分别为I和II的混合策略。

设A，B分别为局中人I和II的赢得矩阵，且都是为m×n矩阵。第68页,共78页，2024年2月25日，星期天69则局中人I和II的混合策略集为：

当局中人I和II的混合策略分别为x和y时，局中人I和II的期望赢得值分别为：第69页,共78页，2024年2月25日，星期天70如果一个混合策略组合(x*,y*)同时满足：且

则称策略组合(x*,y*)

是一个混合策赂纳什均衡，其中(x,y)分别是局中人I和II的任意混合策略。

例6中假定政府以概率x选择救济．概率1－x选择不救济，即政府的混合策略为(x,1－x)；流浪汉以概率y选择寻找工作，以概率1－y选择游荡，即流浪汉的混合策略为(y,1－y)。那么政府的期望赢得函数为：第70页,共78页，2024年2月25日，星期天71同样，流浪汉的期望赢得函数为：令得令得第71页,共78页，2024年2月25日，星期天72

这就是说，在混合策略均衡中，流浪汉在对付政府给定的混合策略下，最优策略是以1／5的概率选择寻找工作,而以4／5的概率选择