第10章对策论 10.1基本概念 对策论也称博弈论,是研究具有竞争或斗争性质的现象,并为参加者各方提供对策 方法的数学理论,它是运筹学的一个分支。对策自古有之,只是在科学技术高度发展的 现代社会,更进一步引起越来越多人的重视和研究。 在人类社会中,人们正常生产劳动、工作、学习之余,可能去下棋、打扑克,或者 去玩各自所喜爱的乒乓球、羽毛球,或者参加其他体育比赛,或者做各种游戏等等。在 这些具有竞赛或斗争性质的活动中,人们总希望自己或自己一方最终夺得胜利,或者获 得尽可能好的结局。因此,都积极寻找有利时机,施展自己的才智,制约、干扰和破坏 对方长处或优势的发挥。 我们把这种按照不同情况、根据不同对手、采取不同对待方法,以期比赛或斗争有 利于自己的现象,称为“对策现象” 在政治领域里,国与国之间的战争,国家内部政治集团之间的斗争,更是一种你死 我活的对策现象。 在经济活动中,国家之间的贸易谈判,公司或企业之间的交往、国际或国内的市场 争夺,都明显地表现出对策的特性。 “对策现象”绝非仅此种种,但是无论何种对策,构成一个对策现象的共同特征是 具有三个基本要素 10.1.1局中人 在一场竞赛或斗争中(简称一局对策),都必须有这样的参加者,他们为了在一局 对策中力争好的结局,必须制定对付对手的行动方案,我们把这样有决策权的参加者称 为“局中人”。例如下象棋的双方。应当注意把那些利害一致的参加者看作一个局中人, 例如打桥牌的东西双方(或南北两人),因为他们得失相当,都必须齐心合力,行动一 致,如同一人。所以虽然有四人参加打牌,只能视为两个局中人。在一局对策中,即不 用决策,且结局又与之无关的人不算局中人,就像球赛的裁判、游戏的公证人等。 正是由于局中人的多少不同,才有“二人对策”和“多人对策”之分,还可以根据 局中人的合作关系分为“结盟对策”和“不结盟对策”等 10.1.2策略 参加对策的每个局中人,每行动一步都有若干个行动方案可供选择,而在整个对策 过程中,他们又必须考虑一个指导自始至终的行动方案,每个局中人的这种指导自始至 终的行动方案也有若干。我们把一个局中人的一个可行的指导自始至终的行动方案称为
第 10 章 对策论 10.1 基本概念 对策论也称博弈论，是研究具有竞争或斗争性质的现象，并为参加者各方提供对策 方法的数学理论，它是运筹学的一个分支。对策自古有之，只是在科学技术高度发展的 现代社会，更进一步引起越来越多人的重视和研究。 在人类社会中，人们正常生产劳动、工作、学习之余，可能去下棋、打扑克，或者 去玩各自所喜爱的乒乓球、羽毛球，或者参加其他体育比赛，或者做各种游戏等等。在 这些具有竞赛或斗争性质的活动中，人们总希望自己或自己一方最终夺得胜利，或者获 得尽可能好的结局。因此，都积极寻找有利时机，施展自己的才智，制约、干扰和破坏 对方长处或优势的发挥。 我们把这种按照不同情况、根据不同对手、采取不同对待方法，以期比赛或斗争有 利于自己的现象，称为“对策现象”。 在政治领域里，国与国之间的战争，国家内部政治集团之间的斗争，更是一种你死 我活的对策现象。 在经济活动中，国家之间的贸易谈判，公司或企业之间的交往、国际或国内的市场 争夺，都明显地表现出对策的特性。 “对策现象”绝非仅此种种，但是无论何种对策，构成一个对策现象的共同特征是 具有三个基本要素： 10.1.1 局中人 在一场竞赛或斗争中（简称一局对策），都必须有这样的参加者，他们为了在一局 对策中力争好的结局，必须制定对付对手的行动方案，我们把这样有决策权的参加者称 为“局中人”。例如下象棋的双方。应当注意把那些利害一致的参加者看作一个局中人， 例如打桥牌的东西双方（或南北两人），因为他们得失相当，都必须齐心合力，行动一 致，如同一人。所以虽然有四人参加打牌，只能视为两个局中人。在一局对策中，即不 用决策，且结局又与之无关的人不算局中人，就像球赛的裁判、游戏的公证人等。 正是由于局中人的多少不同，才有“二人对策”和“多人对策”之分，还可以根据 局中人的合作关系分为“结盟对策”和“不结盟对策”等。 10.1.2 策略 参加对策的每个局中人，每行动一步都有若干个行动方案可供选择，而在整个对策 过程中，他们又必须考虑一个指导自始至终的行动方案，每个局中人的这种指导自始至 终的行动方案也有若干。我们把一个局中人的一个可行的指导自始至终的行动方案称为
这个局中人的一个策略,而把这个局中人的策略全体,叫做这个局中人的策略集合。 个局中人的策略集合中至少有两个策略或者多个策略,甚至无穷个策略。据此,可以把 对策分为“有限对策”或“无限对策”。 1013赢得(支付)函数 一局对策结束时,对每个局中人来说,结果总是肯定的。可能以胜利或失败的形式 反映,也可能表示为比赛名次的前后,还可表现为实物收入的多少等等。我们称这样的 结果为“得”,也可称为“支付”。 局对策结束时,每个局中人的“赢得”和全体局中人各选取的策略所组成的策略 组有关,即是该策略组的函数,通常称为“赢得函数”(“支付函数”)。 根据一局对策结束后每个局中人的“赢得”相加之和等于零与否,我们把对策分为 零和对策”或“非零和对策” 10.2矩阵对策 矩阵对策就是有限零和二人对策,指的是参加对策的局中人只有两方(或二人), 每一方局中人的可供选择策略数是有限多个,而且每一局对策结束时,一方的收入(或 赢得)等于另一方的支出(或称输出),换句话说,二方得失之和总是等于零。这类对 策比较简单,理论上也比较成熟,在实践中应用的也极为广泛。由于矩阵对策的理论奠 定了研究“对策现象”的基本思路,所以它是对策论中必须掌握的内容 1021矩阵对策的数学模型 对于矩阵对策,我们用甲、乙表示两个局中人,假设甲有m个策略(又称纯策略), 分别以a,a2…an表示,乙有n个策略,分别以尻,B2…Bn表示。根据对策规定,若 甲选用第i个策略,乙选用第j个策略,则称(a,)为一个纯局势,那么,甲的赢得可 以用a表示(若a是负数时,表示甲是支出而不是收入)。于是,甲的支付可以列成表 10-1。 甲的支付表 表10-1 甲的支付<的策略 B 甲的策略 BI B B 21 22
这个局中人的一个策略，而把这个局中人的策略全体，叫做这个局中人的策略集合。一 个局中人的策略集合中至少有两个策略或者多个策略，甚至无穷个策略。据此，可以把 对策分为“有限对策”或“无限对策”。 10.1.3 赢得（支付）函数 一局对策结束时，对每个局中人来说，结果总是肯定的。可能以胜利或失败的形式 反映，也可能表示为比赛名次的前后，还可表现为实物收入的多少等等。我们称这样的 结果为“赢得”，也可称为“支付”。 一局对策结束时，每个局中人的“赢得”和全体局中人各选取的策略所组成的策略 组有关，即是该策略组的函数，通常称为“赢得函数”（“支付函数” ）。 根据一局对策结束后每个局中人的“赢得”相加之和等于零与否，我们把对策分为 “零和对策”或“非零和对策” 。 10.2 矩阵对策 矩阵对策就是有限零和二人对策，指的是参加对策的局中人只有两方（或二人）， 每一方局中人的可供选择策略数是有限多个，而且每一局对策结束时，一方的收入（或 赢得）等于另一方的支出（或称输出），换句话说，二方得失之和总是等于零。这类对 策比较简单，理论上也比较成熟，在实践中应用的也极为广泛。由于矩阵对策的理论奠 定了研究“对策现象”的基本思路，所以它是对策论中必须掌握的内容。 10.2.1 矩阵对策的数学模型 对于矩阵对策，我们用甲、乙表示两个局中人，假设甲有 m 个策略（又称纯策略）， 分别以 1 2 , , , α α " α m 表示，乙有 n 个策略，分别以 1 2 , , , β β " n )j β 表示。根据对策规定，若 甲选用第 i 个策略，乙选用第 j 个策略，则称( ,i a β 为一个纯局势，那么，甲的赢得可 以用αij 表示(若αij 是负数时，表示甲是支出而不是收入)。于是，甲的支付可以列成表 10-1。 甲的支付表 表 10-1 β1 β2 ┅ βj ┅ βn α1 α11 α12 ┅ α1j ┅ α1n α2 α21 α22 ┅ α2j ┅ α2n ┇ ┇ ┇ ┇ ┇ αi αi1 αi2 ┅ αij ┅ αin ┇ ┇ ┇ ┇ ┇ αm αm1 αm2 ┅ αmj ┅ αmn 甲的支付 甲的策略 乙的策略
由于讨论的是有限零和二人对策,所以甲的收入就是乙的支出。那么,乙的支出表 可在甲的支付表中每个a之前加一个负号得到 如果仅考虑支付表中的数值an,便可以得到一个矩阵A,称为甲的支付矩阵(或叫 赢得矩阵) 一般可写成 或 乙的支付矩阵为 a1-012 B a 或 B=(-ai)mxn 若用S表示甲的策略集合,即 以S2表示乙的策略集合: S2={A,B2…Bn} 则甲、乙的有限零和二人对策可表示成: G={S2,S2,4 例如,甲乙两个小孩做猜拳游戏,分别以拳头、两个指头、伸直五指的手掌代表石 头、剪刀、布,并规定石头砸(赢)剪刀,剪刀剪(赢)布,布包(嬴)石头,且赢者 得1,输者得-1,于是小孩甲的支付表如表10-2所示
由于讨论的是有限零和二人对策，所以甲的收入就是乙的支出。那么，乙的支出表 可在甲的支付表中每个αij 之前加一个负号得到。 如果仅考虑支付表中的数值αij ，便可以得到一个矩阵 A，称为甲的支付矩阵（或叫 赢得矩阵）： 11 12 1 1 21 22 2 2 1 2 1 2 j n j n i i ij in m m mj mn A α α α α α ααα α α α α α α α = " " " " # # # # " " # # # # " " α 一般可写成 ( ) A = αij m×n 或 乙的支付矩阵为： 11 12 1 1 21 22 2 2 1 2 1 2 j n j n i i ij i m m mj mn B α α α α α ααα α α α α α α α α − − − − − −−− = − − − − − − − − " " " " # # # # " " # # # # " " n 或 ( ) B = −αij m×n 若用S1表示甲的策略集合，即 S1 1 = {α , , α2 ",α m} 以S2 表示乙的策略集合： S2 1 = {β , , β β 2 ", n} 则甲、乙的有限零和二人对策可表示成： G S = { 1 2 , , S A} 例如，甲乙两个小孩做猜拳游戏，分别以拳头、两个指头、伸直五指的手掌代表石 头、剪刀、布，并规定石头砸（赢）剪刀，剪刀剪（赢）布，布包（赢）石头，且赢者 得 1，输者得-1，于是小孩甲的支付表如表 10-2 所示
表10-2 甲的支付<的策略 石头 布 甲的策略 剪刀 石头 剪刀 甲乙两个小孩的猜拳游戏(对策)可表示成: 其中S=S2={剪刀、石头、布 01 A=-101 1-10 10.2.2最优纯策略和极大极小原理 设有矩阵对策G={S,S24 其中: S2={A,B,B} 80-5 423 就局中人甲来说,对于他的四个纯策略,希望嬴得分别是8,2,4,2,即他的希望赢得, 都是他的各纯策略中的最大值,而甲最希望赢得是8。对于局中人乙来说,他拿出三个 纯策略回答进行对策时,希望支付分别是-3,-1,-5,即乙希望他的支付都是各策略中 的最小值,其中-5是乙最希望的支付。 但是,每个局中人选择策略的行动都要受到对方的干扰或制约。当甲希望嬴得8而 选择纯策略α1时,乙会考虑到甲的这种心理状态,所以乙可能采取他的纯策略β3,使 甲得不到8而失去5(即得到-5)。不过这仅仅是推测,究竟对方要采用哪个纯策略进行 对策活动,双方都不知道,在这种情况下,决定自己的策略结果是赢还是输难以估计。 因此,甲乙双方都必然要考虑,选择自己的哪一个纯策略才是可靠的?显而易见,甲的 纯策略α1的可靠贏得(即最小贏得)是-5,不可能再小,甲的纯策略α2,α3,α4的可 靠贏得分别是-3,2,-3;类似的道理,乙的纯策略β’尻,β得可靠支付(即最大支
表 10-2 石头 剪刀 布 石头 0 1 -1 剪刀 -1 0 1 布 1 -1 0 乙的策略 甲的支付 甲的策略 甲乙两个小孩的猜拳游戏（对策）可表示成： G S = { 1 2 , , S A} 其中 = ={剪刀、石头、布} 1 S 2 S 0 1 1 1 0 1 1 1 0 A − = − − 10.2.2 最优纯策略和极大极小原理 设有矩阵对策G S = { 1 2 , , S A} 其中： S1 1 = {α , , α α2 3 ,α4} S2 1 = {β , , β β2 3} 8 0 5 3 1 2 4 2 3 3 1 2 A − − = − − 就局中人甲来说，对于他的四个纯策略，希望赢得分别是 8，2，4，2，即他的希望赢得， 都是他的各纯策略中的最大值，而甲最希望赢得是 8。对于局中人乙来说，他拿出三个 纯策略回答进行对策时，希望支付分别是-3，-1，-5，即乙希望他的支付都是各策略中 的最小值，其中-5 是乙最希望的支付。 但是，每个局中人选择策略的行动都要受到对方的干扰或制约。当甲希望赢得 8 而 选择纯策略α1 时，乙会考虑到甲的这种心理状态，所以乙可能采取他的纯策略 β3，使 甲得不到 8 而失去 5（即得到-5）。不过这仅仅是推测，究竟对方要采用哪个纯策略进行 对策活动，双方都不知道，在这种情况下，决定自己的策略结果是赢还是输难以估计。 因此，甲乙双方都必然要考虑，选择自己的哪一个纯策略才是可靠的？显而易见，甲的 纯策略α1 的可靠赢得（即最小赢得）是-5，不可能再小，甲的纯策略α2 ，α3，α4 的可 靠赢得分别是-3，2，-3；类似的道理，乙的纯策略β1，β 2 ，β3得可靠支付（即最大支
付)分别是8,2,3,不可能超过这些数值。甲乙双方进行对策时,分别赢得或支付的 结果见表10-3 表10-3 甲的支付<的策略 甲的甲的 甲的 甲的策 ..希望得可靠得最优得 8 2 2 4 2 4 2 2 3 2 2 乙的希望赢得 乙的可靠赢得 8 2 3 最优纯策略(a3,B2) 乙的最优赢得 局中人在分析了可靠赢得(或支付)之后,符合逻辑地都会想到最优赢得(或最优 支付)问题。可以看出,甲的可靠赢得数值中最大者为2,成为他的最优赢得值;而乙 的最优支付值则是他的可靠支付值中最小者2。 可以看出,任何一方局中人都在集中精力关心一件事,即在对方采取的策略对自己 来说是最不利时,可能发生最坏的事态,这时要采取措施,从最坏的事态中寻找最好的 结果 很显然,在有把握的对策情况下,甲选择策略的原则是,首先在每个纯策略(行) 中找出最小值(可靠赢得),即 min ay (i=1 然后在这些最小值中找到最大值(最优赢得), 即: max(mina,)=maxa =V 在本对策G中,V=2 局中人乙则和甲相反,他的原则首先是在各纯策略(列)中找出最大值(可靠支付): (j=1,2,…,m) 然后再找出各最大值中的最小值(最优支付) min(max ai)=mina,=V2 这里V2 我们把甲的最优嬴得和乙的最优支付的这个公共值,称为矩阵对策的值,记作V 即
付）分别是 8，2，3，不可能超过这些数值。甲乙双方进行对策时，分别赢得或支付的 结果见表 10-3。 表 10-3 β1 β2 β3 甲的 希望赢得 甲的 可靠赢得 甲的 最优赢得 α1 8 -1 -5 8 -5 α2 -3 1 2 2 -3 α3 4 2 3 4 2 2 α4 -3 -1 2 2 -3 乙的希望赢得 -3 -1 -5 乙的可靠赢得 8 2 3 乙的最优赢得 2 最优纯策略（α3，β2） 乙的策略 甲的支付 甲的策略 局中人在分析了可靠赢得（或支付）之后，符合逻辑地都会想到最优赢得（或最优 支付）问题。可以看出，甲的可靠赢得数值中最大者为 2，成为他的最优赢得值；而乙 的最优支付值则是他的可靠支付值中最小者 2。 可以看出，任何一方局中人都在集中精力关心一件事，即在对方采取的策略对自己 来说是最不利时，可能发生最坏的事态，这时要采取措施，从最坏的事态中寻找最好的 结果。 很显然，在有把握的对策情况下，甲选择策略的原则是，首先在每个纯策略（行） 中找出最小值（可靠赢得），即 min * ij ij j α =α (i m =1,2,", ) 然后在这些最小值中找到最大值（最优赢得）， 即： ma * 1 x(min ) max ij ij i i j α α = =V 在本对策G 中，V1 = 2 局中人乙则和甲相反，他的原则首先是在各纯策略（列）中找出最大值（可靠支付）： max * ij i j i α =α ( j =1,2,",m ) 然后再找出各最大值中的最小值（最优支付） mi * 2 n(max ) min ij i j j j i α α = =V 这里V2 = 2 我们把甲的最优赢得和乙的最优支付的这个公共值，称为矩阵对策的值，记作V ， 即： G