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