运筹学讲义 §9对策论 本章来介绍对策论( game theory) 对策是有厉害冲突的各方所分别采取的决策.对策论,亦称为博弈论,研究具有对抗、竞争、冲 突性质的问题 对策论的思想古已有之,如我国战国时期的“齐王与田忌赛马”,最早利用数学方法来研究对策 论的是数学家E. Zermelo,他于1912年发表了论文《关于集合论在象棋对策中的应用》.1944年, J. Von neumann和o. Morgenstern总结了前人关于对策论的研究成果,合著了《对策论与经济行为》 ( Theory of Games and Economic Behavior)一书,使得对策论的研究开始系统化和公理化,并具 有了深刻的经济背景.1994年,在对策论研究中作出突出贡献的Nash, Harsany i和 Selten获得诺贝 尔经济学奖 对策问题的三个要素 (1)局中人( player):参加对策的各方 规定:局中人是聪明,理智的:将厉害关系一致的参加者视为一个局中人. 局中人集合:I={1,2,…,m} (2)策略( strategy):局中人在一局对策中为争取尽量好的结果用来对付对手的行动方案 策略集合:局中人的全部策略. 局中人i的策略集合:S 局势:在一局对策中,各局中人选定的策略构成的一个策略组S 局势决定本局对策的结果(收益).在一局对策中,一但局势确定后,即得本局对策的结果 (3)收益( earning):一局对策所得结果的数量表示 收益或为赢得或为支付:收益由局势唯一确定,一但局势确定,即得收益,故收益和局势之间的 此种对应在局势集合上构成了一个函数关系 局中人i的收益函数( earning function):H1=H,(S) 显然,给定一个局势S,即可得到局中人i的收益H2(S) 综上,建立对策模型:T=(l,{S}=,{H1}=) 对策过程:每一个局中人i从其策略集合S,中选择一个策略S,得到一个局势 S=(S,S(),…,S").将S代入局中人i的收益函数H1中,即得收益H1=H,(S),本局对策结束 例1(猜硬币游戏)甲乙两人各抛掷一枚硬币,在落地以前,以手覆之.双方约定:若两枚都是 正面或反面,则甲得1分,乙得-1分:若一个正面一个反面,则甲得-1分,乙得1分:最终得分最 多者为胜
运 筹 学 讲 义 1 §9 对策论 本章来介绍对策论（game theory）. 对策是有厉害冲突的各方所分别采取的决策.对策论，亦称为博弈论，研究具有对抗、竞争、冲 突性质的问题. 对策论的思想古已有之，如我国战国时期的“齐王与田忌赛马”.最早利用数学方法来研究对策 论的是数学家 E. Zermelo，他于 1912 年发表了论文《关于集合论在象棋对策中的应用》.1944 年， J. Von Neumann 和 O. Morgenstern 总结了前人关于对策论的研究成果，合著了《对策论与经济行为》 （Theory of Games and Economic Behavior）一书，使得对策论的研究开始系统化和公理化，并具 有了深刻的经济背景.1994 年，在对策论研究中作出突出贡献的 Nash，Harsanyi 和 Selten 获得诺贝 尔经济学奖. 对策问题的三个要素： （1）局中人（player）：参加对策的各方. 规定：局中人是聪明，理智的；将厉害关系一致的参加者视为一个局中人. 局中人集合： I = {1,2, ,n}. （2）策略（strategy）：局中人在一局对策中为争取尽量好的结果用来对付对手的行动方案. 策略集合：局中人的全部策略. 局中人 i 的策略集合： i S . 局势：在一局对策中，各局中人选定的策略构成的一个策略组 S . 局势决定本局对策的结果（收益）.在一局对策中，一但局势确定后，即得本局对策的结果 （3）收益（earning）：一局对策所得结果的数量表示. 收益或为赢得或为支付；收益由局势唯一确定，一但局势确定，即得收益，故收益和局势之间的 此种对应在局势集合上构成了一个函数关系. 局中人 i 的收益函数（earning function）： H H (S) i = i . 显然，给定一个局势 S ，即可得到局中人 i 的收益 H (S) i . 综上，建立对策模型： ( ,{ } ,{ } ) Si i I Hi i I I = . 对策过程：每一个局中人 i 从其策略集合 i S 中选择一个策略 (i) S ，得到一个局势 ( , , , ) (1) (2) (n) S = S S S .将 S 代入局中人 i 的收益函数 Hi 中，即得收益 H H (S) i = i ，本局对策结束. 例 1（猜硬币游戏）甲乙两人各抛掷一枚硬币，在落地以前，以手覆之.双方约定：若两枚都是 正面或反面，则甲得 1 分，乙得-1 分；若一个正面一个反面，则甲得-1 分，乙得 1 分；最终得分最 多者为胜
运筹学讲义 显然,这是一个对策问题,其中局中人为甲(1),乙(2),局中人集合为I={1,2};局中人1 的策略可能有ax1=(出正面),a2=(出反面),局中人2的策略可能有B1=(出正面,B2=(出 反面),∴局中人1,2的策略集合分别为S1={a1,a2},S2={B1,B2} 当局中人1,2分别从其策略集合中选择一个策略后,就得到一个局势.∴∵局势集合为 S1×S2={(a1B1)(a1,B2).(a2,B)(2,B2) 由双方的约定知,局中人1,2在各局势下的收益分别为 H1(a1,B1)=1,H1(a1,B2)=-1,H1(a2,B1)=-1,H1(a2,B2)=1 H2(a1,B1)=-1,H2(a1,B2)=1,H2(a2,B1)=1,H2(a2,B2)=-1 二人有限零和对策(2- player finite zero- sum game):在一个对策问题中,有两个局中人 I={12},每个局中人的策略集合为有限集:S1={a1,a2…,an},S2={B1,B2,…,Bn} m,n<+∞.两个局中人的收益函数H1,H2满足H1+H2=0 显然,在二人有限零和对策中,局势集合为S1xS2={(a1,B,)|i=12…,m,j=1,2,…,n 且|S1×S2=m 设H1(a1,B,)=an,则由H1+H2=0知,H2(ax,B)=-an,i=12…,m,j=1,2,…,n (局中人1的)收益矩阵:A=(an)m,其中a=H1(a,B,),i=12,…,m,j 由收益矩阵的定义知,A的第i行各元素分别为局中人1出策略α,,局中人2出策略 B,B2;…,Bn时对应的局势下局中人1的收益:A的第j列各元素分别为局中人2出策略B,局中 人1出策略∝1,α2…an时对应的局势下局中人1的收益 显然,给定一个二人有限零和对策,即可确定一个支付矩阵;反之,给定一个矩阵A=(an1)m 若令|S=m|S2F=n,H1(a1,B)=an,H2(a1,B)=-an,则可确定一个二人有限零和对策 如此,二人有限零和对策和矩阵一一对应故二人有限零和对策亦称为矩阵对策( matrix game),记作: 2
运 筹 学 讲 义 2 显然，这是一个对策问题，其中局中人为甲（1），乙（2），局中人集合为 I = {1,2} ；局中人 1 的策略可能有 1 = （出正面）， 2 = （出反面），局中人 2 的策略可能有 1 = （出正面）， 2 = （出 反面）， 局中人 1，2 的策略集合分别为 { , } S1 = 1 2 ， { , } S2 = 1 2 . 当局中人 1，2 分别从其策略集合中选择一个策略后，就得到一个局势. 局势集合为 {( , ),( , ),( , ),( , )} S1 S2 = 1 1 1 2 2 1 2 2 . 由双方的约定知，局中人 1，2 在各局势下的收益分别为 H1 (1 ,1 ) =1， H1 (1 , 2 ) = −1， H1 ( 2 ,1 ) = −1， H1 ( 2 , 2 ) =1 ； H2 (1 ,1 ) = −1， H2 (1 , 2 ) =1， H2 ( 2 ,1 ) =1， H2 (2 , 2 ) = −1.▍ 二人有限零和对策（2-player finite zero-sum game）：在一个对策问题中，有两个局中人 I = {1,2} ，每个局中人的策略集合为有限集： { , , , } S1 = 1 2 m ， { , , , } S2 = 1 2 n ， m,n +.两个局中人的收益函数 1 2 H ,H 满足 H1 + H2 = 0 . 显然，在二人有限零和对策中，局势集合为 {( , ) | 1,2, , , 1,2, , } S1 S2 = i j i = m j = n ， 且 | S1 S2 |= mn. 设 H i j = aij ( , ) 1 ，则由 H1 + H2 = 0 知， H i j = −aij ( , ) 2 ，i = 1,2, ,m, j = 1,2, ,n . （局中人 1 的）收益矩阵： A = aij mn ( ) ，其中 ( , ) aij = H1 i j ，i = 1,2, ,m, j = 1,2, ,n . 由收益矩阵的定义知， A 的第 i 行各元素分别为局中人 1 出策略 i ，局中人 2 出策略 n , , , 1 2 时对应的局势下局中人 1 的收益； A 的第 j 列各元素分别为局中人 2 出策略 j ，局中 人 1 出策略 n , , , 1 2 时对应的局势下局中人 1 的收益. 显然，给定一个二人有限零和对策，即可确定一个支付矩阵；反之，给定一个矩阵 A = aij mn ( ) ， 若令 | S1 |= m,| S2 |= n ， H i j = aij ( , ) 1 ， H i j = −aij ( , ) 2 ，则可确定一个二人有限零和对策. 如此，二人有限零和对策和矩阵一一对应.故二人有限零和对策亦称为矩阵对策（matrix game），记作：
运筹学讲义 F=(S2,S2,A) 在矩阵对策中,A为局中人1的收益矩阵(贏得矩阵),-A为局中人2的收益矩阵(支付矩阵) 易见,例1猜硬币游戏即为一个矩阵对策r=(S1S2,A),其中局中人集合为/={,2},局中人 1,2的策略集合分别为S1={a1,ax2},S2={B1,B2},收益矩阵为A 例2(田忌与齐王赛马)战国时期,齐王与大将田忌赛马,分别挑选出上,中,下三个等级的马 各一匹进行比赛.齐王的马比同一等级的田忌的马强壮,而田忌的高等级的马比齐王的低等级的马强 壮.双方约定:每赛一局,胜者得千金 易见,此对策问题为一个矩阵对策r=(S1,S2,A),其中局中人为田忌(1),齐王(2),局中人 集合为Ⅰ={1,2}:局中人1的策略可能有∝x1=(上),α2=(中),a3=(下),局中人2的策略可 能有B1=(上),B2=(中),B3=(下),∴局中人1,2的策略集合分别为S1={a1a2a3}, S2=(月1,B2,B3};收益矩阵为A 【引例】给定矩阵对策r=(S1,S2,A),其中S1={a12a2a3},S2={B1,B2,B3} A=432,从收益矩阵A可见,局中人1的最大收益为6,故“聪明的”局中人1为获得 61-8 此收益,应出策略α3;但“聪明的”局中人2虑及局中人1的此种心理,会出策略β3’致使局中人 1在局势(a3,B3)下,获得收益-8:同样,局中人1也会虑及局中人2的上述心理而出策略a2,获得 收益2:同样,局中人2也会虑及局中人1的上述心理而出策略B3,获得收益-2(∵局中人1的赢得 为 2) 在上述“角逐”中,局中人1,2最终在局势(a2,B3)下分别获得了最大收益H1(a2,B3)=a23=2, H2(a2,B3)=-a23=-2.故局中人1,2的最优策略分别为a2,B3
运 筹 学 讲 义 3 ( , , ) = S1 S2 A . 在矩阵对策中， A 为局中人 1 的收益矩阵（赢得矩阵），− A 为局中人 2 的收益矩阵（支付矩阵）. 易见，例 1 猜硬币游戏即为一个矩阵对策 ( , , ) = S1 S2 A ，其中局中人集合为 I = {1,2} ，局中人 1，2 的策略集合分别为 { , } S1 = 1 2 ， { , } S2 = 1 2 ，收益矩阵为 − − = 1 1 1 1 A . 例 2（田忌与齐王赛马）战国时期，齐王与大将田忌赛马，分别挑选出上，中，下三个等级的马 各一匹进行比赛.齐王的马比同一等级的田忌的马强壮，而田忌的高等级的马比齐王的低等级的马强 壮.双方约定：每赛一局，胜者得千金. 易见，此对策问题为一个矩阵对策 ( , , ) = S1 S2 A ，其中局中人为田忌（1），齐王（2），局中人 集合为 I = {1,2} ；局中人 1 的策略可能有 ( 1 = 上 ) ， ( 2 = 中 ) ， ( 3 = 下 ) ，局中人 2 的策略可 能有 ( 1 = 上 ) ， ( 2 = 中 ) ， ( 3 = 下 ) ， 局中人 1，2 的策略集合分别为 { , , } S1 = 1 2 3 ， { , , } S2 = 1 2 3 ；收益矩阵为 − − − − − − = 1 1 1 1 1 1 1 1 1 A . 【 引 例 】 给 定 矩 阵 对 策 ( , , ) = S1 S2 A ，其中 { , , } S1 = 1 2 3 ， { , , } S2 = 1 2 3 ， − − − = 6 1 8 4 3 2 1 3 2 A ，从收益矩阵 A 可见，局中人 1 的最大收益为 6，故“聪明的”局中人 1 为获得 此收益，应出策略 3 ；但“聪明的”局中人 2 虑及局中人 1 的此种心理，会出策略 3 ，致使局中人 1 在局势 ( , ) 3 3 下，获得收益-8；同样，局中人 1 也会虑及局中人 2 的上述心理而出策略 2 ，获得 收益 2；同样，局中人 2 也会虑及局中人 1 的上述心理而出策略 3 ，获得收益-2（ 局中人 1 的赢得 为 2）. 在上述“角逐”中，局中人1，2最终在局势 ( , ) 2 3 下分别获得了最大收益 H1 ( 2 , 3 ) = a23 = 2 ， H2 ( 2 , 3 ) = −a23 = −2.故局中人 1，2 的最优策略分别为 2 3 ,
运筹学讲义 显然,上述寻找局中人的最优策略的“角逐”式方法未免过于繁琐,那么有无其它方法呢? 回忆决策论之求解不确定性决策问题的悲观主义原则:选取最小收益中的最大者对应的策略为 自己的最优策略 不妨分别利用悲观主义原则来求局中人1,2的最优策略. 先利用悲观主义原则来求局中人1的最优策略: 由max{min{-13,=2},mn{4,3,2},mn{61,-8}=max{-2,2-8}=2=a23知,局中人1的 最优策略为a2,最优收益为H1(a2,B3)=a23=2. 再利用悲观主义原则来求局中人2的最优策略: 由局中人1的收益矩阵A知,局中人2的收益矩阵为-A=-4-3-2 由max{mn{1-4.=6},min{=3,-3-1},mn(2,-28}=mx{-6-3,=2}=-2知,局中人2 的最优策略为B3,最优收益为H2(a2,B3)=-a2 事实上,亦可直接由局中人1的收益矩阵A来求局中人2的最优策略: 由mn{max{-14,6},max{3,3,1},mx{-2,2,-8}=mn{6,3,2}=2=a23知,局中人2的最优 策略为β3,最优收益为H2(2,B3)=-a23=-2 如此,在局势(a2,B3)下,局中人1获得最优收益2,局中人2获得最优收益-2,局中人1的最 优策略为a2,局中人2的最优策略为B3,且 max min{an}= min maxa}=a23 巧得很啊!当分别利用悲观主义原则求得的局中人1,2的最优收益在某一个局势下达到一致时, 即得局中人1,2的最优策略,而此最优策略竟然与利用“角逐”式方法达到的最优策略是相同的. 这里,道理在于:当两个局中人的最优收益在悲观主义原则下的同一个局势下达到一致时,即分别得 到最优策略 显然,a23作为局中人1的最优收益,满足a3≤a23≤a2y,i=1,2,3,j=1,2,3,且 mmax main=mn max(ai i=a23 Def设矩阵对策r=(S1,S2,A),若彐局势(a,B,)∈S1xS2,使得i=1,2,…,m
运 筹 学 讲 义 4 显然，上述寻找局中人的最优策略的“角逐”式方法未免过于繁琐，那么有无其它方法呢？ 回忆 决策论之求解不确定性决策问题的悲观主义原则：选取最小收益中的最大者对应的策略为 自己的最优策略. 不妨分别利用悲观主义原则来求局中人 1，2 的最优策略. 先利用悲观主义原则来求局中人 1 的最优策略： 由 2 23 max{min{ −1,3,− 2},min{ 4,3,2},min{ 6,1,−8}} = max{−2,2,−8} = = a 知，局中人 1 的 最优策略为 2 ，最优收益为 H1 ( 2 , 3 ) = a23 = 2 . 再利用悲观主义原则来求局中人 2 的最优策略： 由局中人 1 的收益矩阵 A 知，局中人 2 的收益矩阵为 − − − − − − − = 6 1 8 4 3 2 1 3 2 A . 由 max{min{ 1,−4,−6},min{ −3,−3,−1},min{ 2,− 2,8}}= max{−6,−3,− 2} = −2 知，局中人 2 的最优策略为 3 ，最优收益为 H2 ( 2 , 3 ) = −a23 = −2 . 事实上，亦可直接由局中人 1 的收益矩阵 A 来求局中人 2 的最优策略： 由 2 23 min{max{ −1,4,6},max{3,3,1},max{−2,2,−8}} = min{ 6,3,2} = = a 知，局中人 2 的最优 策略为 3 ，最优收益为 H2 ( 2 , 3 ) = −a23 = −2 . 如此，在局势 ( , ) 2 3 下，局中人 1 获得最优收益 2，局中人 2 获得最优收益-2，局中人 1 的最 优策略为 2 ，局中人 2 的最优策略为 3 ，且 23 max min{a } min max{aij} a j i ij i j = = . 巧得很啊！当分别利用悲观主义原则求得的局中人 1，2 的最优收益在某一个局势下达到一致时， 即得局中人 1，2 的最优策略，而此最优策略竟然与利用“角逐”式方法达到的最优策略是相同的. 这里，道理在于：当两个局中人的最优收益在悲观主义原则下的同一个局势下达到一致时，即分别得 到最优策略. 显然， 23 a 作为局中人 1 的 最 优 收 益 ， 满 足 ai3 a23 a2 j ,i = 1,2,3; j = 1,2,3 ， 且 23 max min{a } min max{aij} a j i ij i j = = . Def 设矩阵对策 ( , , ) = S1 S2 A ， 若 局 势 1 2 ( , ) S S i j ，使得 i = 1,2, ,m
运筹学讲义 j=12…,n,有ag≤a1≤a1,则称(a,B,)为r的策略解(鞍点),称a,B,分别为局中 人1,2的最优策略( optimal strategy),称a..为r的值( value),记作:w(T)=a Th矩阵对策r=(S1,S2,A)彐策略解分mxmm{an}= min max fa} 证明:→令 max mn(ap}=mn{an, min max{a}=max{an},则 mm{a}≤ a, <max{a2},即 max min{an}≤mmx{an}.(1) 设3策略解(a,B),则=12…mj=12,…,n,有asa 于是,mx{a,}≤a,,≤min{a,} 进而,mnmx{an} <max(a}≤a,;≤mn{a,;}≤mxmn{an}(2) 由(1),(2)得 max min{an}= min max{an} ∈设mxmn{an}= min max{an},令 max min{an}=mn{an, min max{a}=max{ab}, 则mn{an}=mx{an}令mm{n}=mx{amn}=a,则yi=1,2,…,m,j=12,…,n,有 an≤an≤a故(an,B1)是r的策略解l 注:一个直观的解释:若两个局中人无侥幸心理,仅虑及对方会设法使自己的收益最小,则应当 选取最小收益中的最大者对应的策略为自己的最优策略(悲观主义原则).当两个局中人1,2分别利 用悲观主义原则找到自己的最优策略mxmn{an}, max mn{-an}= min max a}时,若 max min{an}=mmax{an}=a,,则(α,,β,)即为矩阵对策r=(S1,S2,A)的策略解 推论若矩阵对策r=(S,S2,A)中,mxmm{}=mmmx{n}=a;,则(ar,B,)是的 最优策略,C1,B,分别为局中人1,2的最优策略,且v() 证明:Th的充分性的证明+定义.l 例3求解矩阵对策r=(S1,S2,A),其中S1={a1,a2,a3},S2={B1,B2,B3}
运 筹 学 讲 义 5 j = 1,2, , n ，有 ij i j i j a a a ，则称 ( , ) i j 为 的策略解（鞍点），称 i j , 分别为局中 人 1，2 的最优策略（optimal strategy），称 i j a 为 的值（value），记作： = i j v( ) a . Th 矩阵对策 ( , , ) = S1 S2 A 策略解 max min{ } min max{ }ij j i ij i j a = a . 证明： 令 max min{ } min{ },min max{ } max{ } 0 0 ij i ij j i i j j ij i j a = a a = a ，则 min{ } max{ } 0 0 0 0 ij i i j i j j a a a ，即 max min{ } min max{ }ij j i ij i j a a . （1） 设 策略解 ( , ) i j ，则 i = 1,2, ,m, j = 1,2, ,n ，有 ij i j i j a a a . 于是， max{ } min{ } i j j ij i j i a a a . 进而， min max{ } max{ } min{ } max min{ }ij i j i j j ij i j i ij j i a a a a a . （2） 由（1），（2）得 max min{ } min max{ }ij j i ij i j a = a . 设 max min{ } min max{ }ij j i ij i j a = a ，令 max min{ } min{ },min max{ } max{ } 0 0 ij i ij j i i j j ij i j a = a a = a ， 则 min{ } max{ } 0 0 ij i i j j a = a .令 0 0 0 0 min { } max{ } ij i j i i j j a a a = = ，则 i = 1,2, ,m, j = 1,2, ,n ，有 aij ai j ai j 0 0 0 0 .故 ( , ) 0 0 i j 是 的策略解.▍ 注：一个直观的解释：若两个局中人无侥幸心理，仅虑及对方会设法使自己的收益最小，则应当 选取最小收益中的最大者对应的策略为自己的最优策略（悲观主义原则）.当两个局中人 1，2 分别利 用悲观主义原则找到自己的最优策略 max min{ }ij i j a ， max min{ } min max{ }ij j i ij i j −a = a 时，若 = = i j ij j i ij i j max min{a } min max{a } a ，则 ( , ) i j 即为矩阵对策 ( , , ) = S1 S2 A 的策略解. 推论 若矩阵对策 ( , , ) = S1 S2 A 中， = = i j ij j i ij i j max min{a } min max{a } a ，则 ( , ) i j 是 的 最优策略， i j , 分别为局中人 1，2 的最优策略，且 = i j v( ) a . 证明：Th 的充分性的证明 + 定义.▍ 例 3 求解矩阵对策 ( , , ) = S1 S2 A ，其中 { , , } S1 = 1 2 3 ， { , , } S2 = 1 2 3