《运筹学》课程教学讲义（Operations Research）第九章对策论.doc_大学文库

运筹学讲义 §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 分；最终得分最多者为胜

运筹学讲义 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 mn ( ) ，其中 ( , ) 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 mn ( ) ，若令 | S1 |= m,| S2 |= n ， H i j = aij ( , ) 1   ， H i j = −aij ( , ) 2   ，则可确定一个二人有限零和对策. 如此，二人有限零和对策和矩阵一一对应.故二人有限零和对策亦称为矩阵对策（matrix game），记作：

运筹学讲义 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  , 

运筹学讲义 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

运筹学讲义 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

《运筹学》课程教学讲义（Operations Research）第九章 对策论

《运筹学》课程教学讲义（Operations Research）第九章对策论