第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
VG=max(min a)=min(max au,) 这里:VG=2。 这是矩阵对策在纯策略下有解的充分必要条件,是著名的求解矩阵对策的极大极小 原理。一般来说,当甲选择他的第i个纯策略时,已经考虑到最优嬴得,所以他的赢得 不可能比v再小,因此称V为对策的下值;当乙选择他的第j个纯策略和甲对局时,同 样预计了最优支付问题,这时甲的赢得是V2,不可能比V2大,因此称V为对策的上值。 所以有人把极大极小原理写成下面不等式形式 V≤vG≤V2 相应于对策值V的策略(α3和β2)称为局中人(甲、乙)的最优纯策略,记作: B 由最优纯策略组成的对策局势称为最优局势,记为: (a,B) 并且称(a,B)为矩阵对策G的“鞍点”,称V1=V2的矩阵对策为完全确定对策。 现在给出在纯策略中有解的(极大极小)定理及其证明,作为这个问题的结束语。 定理10.2-1矩阵对策G={S,S24在纯策略中有解的充要条件是,存在一个纯局 势(a2B),使得对一切P=12…,m,户=12,…,n,都有 ax≤ 证明:充分性由于一切i,j均有 < 故有: maxa,≤a,和a.≤mina 所以 maxa1≤a*x≤mna 而 min max d1≤maxa2 minai,smax min air 从而得 min max a≤a,≤ max min d 另外有: max min a s min max aIr
max(min ) min(max ) G ij i i j j V = = α αij 这里:VG = 2。 这是矩阵对策在纯策略下有解的充分必要条件,是著名的求解矩阵对策的极大极小 原理。一般来说,当甲选择他的第 i 个纯策略时,已经考虑到最优赢得,所以他的赢得 不可能比V 再小,因此称V 为对策的下值;当乙选择他的第 j 个纯策略和甲对局时,同 样预计了最优支付问题,这时甲的赢得是V ,不可能比V 大,因此称V 为对策的上值。 所以有人把极大极小原理写成下面不等式形式: 1 1 2 2 2 V V 1 2 ≤ G ≤V 相应于对策值VG 的策略(α3和β 2 )称为局中人(甲、乙)的最优纯策略,记作: * i a * β j 由最优纯策略组成的对策局势称为最优局势,记为: * * ( , ) i j a β 并且称 * * ( , ) i j a β 为矩阵对策G 的“鞍点”,称V1 =V2 的矩阵对策为完全确定对策。 现在给出在纯策略中有解的(极大极小)定理及其证明,作为这个问题的结束语。 定理 10.2-1 矩阵对策G S = { 1 2 , , S A}在纯策略中有解的充要条件是,存在一个纯局 势 * * ( , ) i j a β ,使得对一切 i=1,2,…,m,j=1,2,…,n,都有 ij* *i j* *i j a a ≤ ≤ a 证明:充分性由于一切 i,j 均有 ij* *i j* *i j a a ≤ ≤ a 故有: ma * * x ij i j i a a ≤ *和 * * mi * n i j i j j a a ≤ 所以 ma * * * x min ij i j i j i j a a a ≤ ≤ * 而 mi * n max max ij ij j i i a a ≤ mi * n max min ij ij j j i a a ≤ 从而得: mi * * n max max min ij i j ij j j i i a a ≤ ≤ a 另外有: max min min max ij ij i i j j a a ≤
于是得 maxminaj-mnmaxai=aij* 必要性:既然对策G有解,假设mnan在=时达到最大,maxa在j=广时达到 最大,即: maxmin=minaj*j min max a.=max a 而 A=maxmin-minmax ai 故有: - min max a2= max a*≥a. a,;= max min a=mna,;≤a 于是得 ag…≤a…rsar 对于一切=1,2,m,=1,2…,n成立。证毕。 10.2.3混合策略 除前面所述情况外,还会遇到无鞍点的矩阵对策。例如对策矩阵为 则甲、乙双方的可靠赢得和可靠支付如表10-4所示。 这里:V= max min a=-2 表 10-4 V2=min max a,=3 P B甲的可 靠贏得 V≠V2 显然,极大极小原理在这里不适用了, 即在纯策略情况下,这类矩阵对策没有解, 两个局中人都没有最优纯策略 乙的可靠支付3 面对这种情况,局中人应如何选择纯策略呢?通常采用被称为混合策略进行对局。 所谓混合策略,就是局中人为了预防对方识破自己的行动,按照一定概率分布随机地选 择各个纯策略。这时,局中人的赢得被称作“期望赢得”。 对本例来说,如果局中人甲以概率P选取纯策略α,以概率P选取纯策略α2;局 中人乙则以概率q选取纯策略β’以概率φ2选取纯策略β,在这里P2=1-p q2=1-q1。于是甲的期望赢得为:
于是得: ma * * x min min max ij ij i j i i j j a a = = a 必要性:既然对策G 有解,假设min 在i ij j a * = i 时达到最大,max ij 在 i a * j = j 时达到 最大,即: ma * x min min ij i j i j j a a = mi * n max max ij ij j i i a a = 而 * * max min min max i j ij ij i i j j a a = = a ≥ a ≤ a 故有: * * mi * * n max max i j ij ij ij j i i a a = = a * * ma * * x min min i j ij i j i j i j j a a = = a 于是得 ij* *i j* *i j a a ≤ ≤ a 对于一切 i=1,2,…,m,j=1,2,…,n 成立。证毕。 10.2.3 混合策略 除前面所述情况外,还会遇到无鞍点的矩阵对策。例如对策矩阵为: 3 2 4 5 − − 则甲、乙双方的可靠赢得和可靠支付如表 10-4 所示。 这里:V a 1 max min 2 ij i j = = − 表 10-4 β1 β 2 甲的可 靠赢得 α1 3 -2 -2 α2 -4 5 -4 乙的可靠支付 3 5 乙 甲 2 min max 3 ij j i V a = = V V 1 2 ≠ 显然,极大极小原理在这里不适用了, 即在纯策略情况下,这类矩阵对策没有解, 两个局中人都没有最优纯策略。 面对这种情况,局中人应如何选择纯策略呢?通常采用被称为混合策略进行对局。 所谓混合策略,就是局中人为了预防对方识破自己的行动,按照一定概率分布随机地选 择各个纯策略。这时,局中人的赢得被称作“期望赢得”。 对本例来说,如果局中人甲以概率 1 p 选取纯策略α1 ,以概率 2 p 选取纯策略α2 ;局 中人乙则以概率 q1 选取纯策略 β1 ,以概率 q2 选取纯策略 β 2 ,在这里 2 1 p = −1 p , q2 = −1 q1 。于是甲的期望赢得为:
VG =E(P, q) 3P1q1+(-2)p92-4P291+5P292 =3Pq1+(-2)P1(1-n)-4(1-P1)q1+5(1-p1)(1-P1) 14pq1-7p1-9+5 9 P1 q1 可以看出,甲的期望赢得是}。由于当甲以概率P=选取纯策略a时,其期望 赢得至少是,然而,他并不能保证超过这个赢得值,因为局中人乙可以用概率选取 纯策略β,这时甲的期望贏得值决不会超过 2 所以,该例中局中人甲的最优(混合)策略为Pn,}={1414,局中人乙的 最优(混合)策略是q={q,42}= 22,其对策值为o=2° 不难发现,对于无鞍点的矩阵对策有: 甲的混合策略为P={P,P2…,pmn} ∑p=LP≥0 乙的混合策略为q={q,q2…qn} q1=1g≥0 对策值为 G=E(pq)=∑∑aPq i=l j= 10.3矩阵对策的解法 由前所述,矩阵对策分为有鞍点对策与无鞍点对策两大类别,对于有鞍点的矩阵对 策,其解法极为简单,即应用极大极小原理,可方便的出对策值V’那么和对策值相对 应的纯策略α和β,就是局中人甲、乙的最优纯策略。所以,对于这一类对策,在此 不再讨论,这里仅讨论无鞍点矩阵对策的解法。 10.31矩阵对策的解法
1 1 1 2 2 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ( , ) 3 ( 2) 4 5 3 ( 2) (1 ) 4(1 ) 5(1 )(1 ) 14 7 9 5 9 1 1 14( )( ) 14 2 2 V E G p q p q p q p q p q p q p p p q p p q p q p q p = = + − − + = + − − − − + − − = − − + = − − + 可以看出,甲的期望赢得是 1 2 。由于当甲以概率 1 9 14 p = 选取纯策略α1 时,其期望 赢得至少是 1 2 ,然而,他并不能保证超过这个赢得值,因为局中人乙可以用 1 2 概率选取 纯策略β1,这时甲的期望赢得值决不会超过 1 2 。 所以,该例中局中人甲的最优(混合)策略为 { } 1 2 9 5 , , 14 14 p p p = = ,局中人乙的 最优(混合)策略是 { } 1 2 1 1 , 2 2 q q q = = , ,其对策值为 1 2 VG = 。 不难发现,对于无鞍点的矩阵对策有: 甲的混合策略为 p = { p p 1 2 , ,", pm } 1 1, 0 m i i i p p = ∑ = ≥ 乙的混合策略为q q = { 1 2 , , q ", qn} 1 1, 0 n j j j q q = ∑ = ≥ 对策值为 1 1 ( , ) m n G i i j V E p q a p q = = = = ∑∑ j i j 10.3 矩阵对策的解法 由前所述,矩阵对策分为有鞍点对策与无鞍点对策两大类别,对于有鞍点的矩阵对 策,其解法极为简单,即应用极大极小原理,可方便的出对策值V ,那么和对策值相对 应的纯策略 G αi 和 β j ,就是局中人甲、乙的最优纯策略。所以,对于这一类对策,在此 不再讨论,这里仅讨论无鞍点矩阵对策的解法。 10.3.1 矩阵对策的解法
假设无鞍点矩阵对策 A 其对策值VG,局中人甲、乙双方的混合策略为: P={P,P2},q={q1,42},于是有: aP,q1+anP,2+a2p2q,+a2p,2=VG P(a1q+a1292)+P2(a291+a292)=V 由于 P2>0.,n1+P2=1,a1q1+a2q2= 同理,根据q>0,q+42=1,可以得到: auP,+a2p2=VG 2P, +a22p2=VG 于是,我们可以利用以上方程组,求出甲、乙双方的最优混合策略和相应的对策值 假设,甲、乙双方的对策矩阵为 52 求解双方的最优混合策略。 解:根据对策矩阵,列出方程组: 31+5P2=G 4P+2P2=G P1+P2 7 解得 3 PI p2 由方程组: 5q+2 q2 q1+q2 解得: q2 故,局中人甲的最优混合策略P/31
假设无鞍点矩阵对策: 11 12 21 22 a a A a a = 其对策值VG ,局中人甲、乙双方的混合策略为: p = { p p 1 , 2 } , q q = { 1 , q2 } ,于是有: 11 1 1 12 1 2 21 2 1 22 2 2 G a p q a + + p q a p q a + p q = V 即 1 11 12 2 2 21 1 22 2 ( ) ( ) G p a q + + a q p a q + a q = V 由于 1 2 11 1 12 2 0, 1, i G p > + p p = a q + a q = V 21 1 22 2 G a q + a q = V 同理,根据q q j > + 0, 1 2 q = 1,可以得到: 11 1 21 2 G a p + a p = V 12 1 22 2 G a p + a p = V 于是,我们可以利用以上方程组,求出甲、乙双方的最优混合策略和相应的对策值。 假设,甲、乙双方的对策矩阵为: 3 4 5 2 求解双方的最优混合策略。 解:根据对策矩阵,列出方程组: 1 2 1 2 1 2 3 5 4 2 1 G G p p V p p V p p + = + = + = 解得 7 2 VG = , 1 3 4 p = , 2 1 4 p = 。 由方程组: 1 2 1 2 1 2 3 4 5 2 1 G G q q V q q V q q + = + = + = 解得: 1 1 2 q = , 2 1 2 q = , 故,局中人甲的最优混合策略 3 1, 4 4 p =
局中人乙的最优混合策略为q=12 对策值为:v 7 10.32矩阵对策图解法 在矩阵对策中,一个局中人只有两个纯策略者,是2×2矩阵对策以外最简单的对 策,这里仅考虑2×n对策,相似地也可以求解m×2矩阵对策。 对于第一个局中人甲来说,他所希望的是下面最小中的最大者: VG=min(,+aip,) 由p=1-P2 AU:VG=min((a2, -a,)P2+a, i 图10-1 例:甲方的赢得矩阵为 4160 首先作图。在横坐标轴上截取长度为1的线段,并在0、1处分别作横坐标的垂直 线,然后取p2=0、再取p2=1、分别画出赢得矩阵之各列数的图象,见图10-1 图中加粗的折线表示局中人甲的各最小赢得,而p点则是各最小赢得的最大值。它 是第2列和第3列图象之交点。于是根据: VG(p)=5P2+1 VG(p)=-2P2+3
局中人乙的最优混合策略为 1 1, 2 2 q = 对策值为: VG = 7 2 10.3.2 矩阵对策图解法 在矩阵对策中,一个局中人只有两个纯策略者,是 2×2 矩阵对策以外最简单的对 策,这里仅考虑 2×n 对策,相似地也可以求解 m×2 矩阵对策。 对于第一个局中人甲来说,他所希望的是下面最小中的最大者: mi 1 1 2 2 n{ } G j j V a = + p a j p 由 1 2 p = −1 p 则:V a mi 2 1 2 1 n{( ) } G j j j = − a p + j a 图 10-1 例:甲方的赢得矩阵为: 2 3 1 5 4 1 6 0 首先作图。在横坐标轴上截取长度为 1 的线段,并在 0、1 处分别作横坐标的垂直 线,然后取 p2 = 0 、再取 p2 =1、分别画出赢得矩阵之各列数的图象,见图 10-1。 图中加粗的折线表示局中人甲的各最小赢得,而 点则是各最小赢得的最大值。它 是第 2 列和第 3 列图象之交点。于是根据: p 2 ( ) 5 1 V p G = p + 2 ( ) 2 3 V p G = − + p