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