运筹学 Operations Research §9对策论 对策是有厉害冲突的各方所分别采取的决策 对策论,亦称为博弈论,研究具有对抗、竞争、冲突性质的 问题 最早利用数学方法来研究对策论的是数学家E. Zermelo,他于 1912年发表了论文《关于集合论在象棋对策中的应用》.1944 年,J. Von neumann和O. Morgenstern总结了前人关于对策论 的研究成果,合著了《对策论与经济行为》( Theory of Games and economic behavior)一书,使得对策论的研究开 始系统化和公理化,并具有了深刻的经济背景.1994年,在对 策论研究中作出突出贡献的Nash, Harsanyi和 Selten获得诺贝 尔经济学奖 2021/2/20
2021/2/20 1 运 筹 学 Operations Research §9 对策论 对策是有厉害冲突的各方所分别采取的决策. 对策论，亦称为博弈论，研究具有对抗、竞争、冲突性质的 问题. 最早利用数学方法来研究对策论的是数学家E. Zermelo，他于 1912年发表了论文《关于集合论在象棋对策中的应用》.1944 年，J. Von Neumann和O. Morgenstern总结了前人关于对策论 的研究成果，合著了《对策论与经济行为》（Theory of Games and Economic Behavior）一书，使得对策论的研究开 始系统化和公理化，并具有了深刻的经济背景.1994年，在对 策论研究中作出突出贡献的Nash，Harsanyi和Selten获得诺贝 尔经济学奖
运筹学 Operations Research 对策问题的三个要素: (1)局中人( player):参加对策的各方 规定:局中人是聪明,理智的;将厉害关系一致的参加者视 为一个局中人 局中人集合: (2)策略( strategy):局中人在一局对策中为争取尽量好 的结果用来对付对手的行动方案 策略集合:局中人的全部策略. 局中人的策略集合:S 局势:在一局对策中,各局中人选定的策略构成的一个策 略组S 局势决定本局对策的结果. 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research 对策问题的三个要素： （1）局中人（player）：参加对策的各方. 规定：局中人是聪明，理智的；将厉害关系一致的参加者视 为一个局中人. 局中人集合： （2）策略（strategy）：局中人在一局对策中为争取尽量好 的结果用来对付对手的行动方案. 策略集合：局中人的全部策略. 局中人的策略集合： 局势：在一局对策中，各局中人选定的策略构成的一个策 略组S. 局势决定本局对策的结果. I = {1,2, ,n} i S
运筹学 Operations Research (3)收益( earning):一局对策所得结果的数量表示 收益或为赢得或为支付;收益由局势唯一确定,一但局 势确定,即得收益,故收益和局势之间的此种对应在局势集 合上构成了一个函数关系 局中人i的收益函数( earning function):H=H(S) 综上,建立对策模型:=(l,{S1}a,{H1}/er 对策过程: 每一个局中人i从其策略集合S中选择一个策略S,得到一个局势 S=(S,S2)…S)将S代入局中人的收益函数H中,即得收益 H=H(S),本局对策结束 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research （3）收益（earning）：一局对策所得结果的数量表示. 收益或为赢得或为支付；收益由局势唯一确定，一但局 势确定，即得收益，故收益和局势之间的此种对应在局势集 合上构成了一个函数关系. 局中人i的收益函数（earning function）： 综上，建立对策模型： 对策过程： H H (S) i = i ( ,{ } ,{ } ) Si i I Hi i I I = ( ) . ( , , , ). (1) (2) ( ) ( ) ，本局对策结束 将 代入局中人 的收益函数 中，即得收益 每一个局中人 从其策略集合 中选择一个策略 ，得到一个局势 H H S S S S S S i H i S S i i i n i i = =
运筹学 Operations research 例1(猜硬币游戏)甲乙两人各抛掷一枚硬币,在落地以前, 以手覆之.双方约定:若两枚都是正面或反面,则甲得1分, 乙得-1分;若一个正面一个反面,则甲得-1分,乙得1分;最 终得分最多者为胜 这是一个对策问题 局中人为甲(1),乙(2),局中人集合为Ⅰ=12} 局中人1的策略可能有α1={正面,α2={反面 局中人2的策略可能有B1=出正面},B2={出反面} 局中人1,2的策略集合分别为S={a1,a2},S2={B1,B2} 局势集合为S1×S2={(∝1,B1)(1,B2)2(a2,B1),(a2,B2)} 局中人1,2在各局势下的收益分别为 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research 例1（猜硬币游戏）甲乙两人各抛掷一枚硬币，在落地以前， 以手覆之.双方约定：若两枚都是正面或反面，则甲得1分， 乙得-1分；若一个正面一个反面，则甲得-1分，乙得1分；最 终得分最多者为胜. 这是一个对策问题. 局中人为甲（1），乙（2），局中人集合为 局中人1的策略可能有 局中人2的策略可能有 局中人1，2的策略集合分别为 局势集合为 局中人1，2在各局势下的收益分别为 I = {1,2} { } { } 1 = 出正面 ，2 = 出反面 { } { } 1 = 出正面 ，2 = 出反面 { , }, S1 = 1 2 { , } S2 = 1 2 {( , ),( , ),( , ),( , )} S1 S2 = 1 1 1 2 2 1 2 2
运筹学 Operations Research H1(a1,B)=1H1(1,B2)=-1H1(a2,B1) H1(a2,B2)=1 H2(12B1)=-1H2(x12B2)=1H2(a2,B1)=1H2(a2,B2)=-1 二人有限零和对策(2- player finite zero- sum game) ={12} t1,2,… S2={B1,B2;…,Bn}mn<+∞ H1+H,=0 设H1(a,B1)=an,则H2(a,B)=-an (局中人1的)收益矩阵:A=(a1)mn,其中an=H1(a,B,) 2021/2/20
2021/2/20 5 运 筹 学 Operations Research 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 H1 + H2 = 0 m,n + ( , ) ( , ) . 设H1 i j = ai j，则H2 i j =－ai j （局中人1的）收益矩阵： ( ) , A = aij mn ( , ). 其中aij = H1 i j
运筹学 Operations Research 二人有限零和对策和矩阵一一对应.故二人有限零和对策亦 称为矩阵对策( matrix game),记作:r=(S,S2,A) 猜硬币游戏即为一个矩阵对策=(S1,S2,A) 其中局中人集合为Ⅰ={2} 局中人1,2的策略集合分别为S={ana2},S2={B,B2} 收益矩阵为 例2(田忌与齐王赛马)战国时期,齐王与大将田忌赛马, 分别挑选出上,中,下三个等级的马各一匹进行比赛.齐王 的马比同一等级的田忌的马强壮,而田忌的高等级的马比齐 王的低等级的马强壮.双方约定:每赛一局,胜者得千金 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research 二人有限零和对策和矩阵一一对应.故二人有限零和对策亦 称为矩阵对策（matrix game），记作： 猜硬币游戏即为一个矩阵对策 其中局中人集合为 局中人1，2的策略集合分别为 收益矩阵为 ( , , ) = S1 S2 A ( , , ) = S1 S2 A I = {1,2} { , }, S1 = 1 2 { , } S2 = 1 2 − − = 1 1 1 1 A 例2（田忌与齐王赛马）战国时期，齐王与大将田忌赛马， 分别挑选出上，中，下三个等级的马各一匹进行比赛.齐王 的马比同一等级的田忌的马强壮，而田忌的高等级的马比齐 王的低等级的马强壮.双方约定：每赛一局，胜者得千金
运筹学 Operations Research 此对策问题为一个矩阵对策r=(S2S2,A 其中局中人为田忌(1),齐王(2) S={a1,a2ax3}:a1={上},a2={中},a3={下} =(B1,B2B3}:B={上;,B2={},B3={下} 收益矩阵为 A 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research 此对策问题为一个矩阵对策 其中局中人为田忌（1），齐王（2） 收益矩阵为 ( , , ) = S1 S2 A { , , }: { } { } { } { , , }: { } { } { } 2 1 2 3 1 2 3 1 1 2 3 1 2 3 上 ， 中 ， 下 上 ， 中 ， 下 = = = = = = = = S S − − − − − − = 1 1 1 1 1 1 1 1 1 A
运筹学 Operations Research R 【引例】给定矩阵对策T=(S,S2A,其中S={a1a2a3}, S2={B1,B2,B3} 收益矩阵为 A=432 在“角逐”中,局中人1,2最终在局势(α2,B3)下分别获得 最大收益H1(α2,B3)=a23=2故局中人,2的最优策略分别 为a2,月3 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research 【引例】给定矩阵对策 其中 收益矩阵为 ( , , ), = S1 S2 A { , , }, S1 = 1 2 3 { , , }, S2 = 1 2 3 − − − = 6 1 8 4 3 2 1 3 2 A , . ( , ) 2. 1 2 1 2 ( , ) ...... 2 3 1 2 3 2 3 2 3 为 最大收益 故局中人 ，的最优策略分别 在“角逐”中，局中人 ，最终在局势 下分别获得 H = a =
运筹学 Operations Research 分别利用悲观主义原则来求局中人1,2的最优策略: 局中人1: max{min{-13,-2},min{4,32},mn{6,1,-8}=max{-2,2,-8}=2=a23 局中人最优策略为a2,最优收益为H1(a2,3)=a2=2 局中人2: 6 331 max{min{1-4,=6},mn{-3,=3,-1},min{2,-28}=max{-6,-3,-2}=-2 局中人的最优策略为β,最优收益为H2(α2,B3)=-q23=-2. 2021/2/20
2021/2/20 9 运 筹 学 Operations Research 分别利用悲观主义原则来求局中人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. 局中人 的最优策略为 2，最优收益为H1 2 3 = a23 = 局中人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 1 ( , ) 2. 局中人 的最优策略为3，最优收益为H2 2 3 = −a2 3 = −
运筹学 Operations Research 注: (1)巧得很啊!当分别利用悲观主义原则求得的局中人1,2的 最优收益在某一个局势下达到一致时,即得局中人1,2的最 优策略,而此最优策略竟然与利用“角逐”式方法达到的最 优策略是相同的 (2)max miai Lai=min max a,=a23 J Th(1)矩阵对策r=(S,S2A)存在最优策略台 max min ia min max fail 2)当 max min a}= min max{an}=a,时,a,月,)即为的 最优策略 2021/2/20 10
2021/2/20 10 运 筹 学 Operations Research 注： (1)巧得很啊！当分别利用悲观主义原则求得的局中人1，2的 最优收益在某一个局势下达到一致时，即得局中人1，2的最 优策略，而此最优策略竟然与利用“角逐”式方法达到的最 优策略是相同的. (2) 23 max min{a } min max{aij} a j i ij i j = = . (2) max min { } min max{ } ( , ) max min { } min max{ } . h(1) ( , , ) 1 2 最优策略 当 时， 即为 的 矩阵对策 存在最优策略 = = = = i j i j i j j i i j i j i j j i i j i j a a a a a T S S A