博弈论 Micosoft Word 文档.docVIP

对策论(Theory of Games) 第1、2讲 对策论也称博弈论，是运筹学的一个重要分支。1928年冯·诺意曼（J.von Neumann）等人由于经济问题的启发，研究了一类具有某种特性的博弈问题，这是对策论的最早期的工作。在我国古代的战国时期，“齐王与田忌赛马”就是一个非常典型的对策论的例子。对策论所研究的主要对象是带有斗争性质（或至少含有斗争成分）的现象。由于对策论研究的对象与政治、军事、工业、农业、交通、运输等领域有密切关系，处理问题的方法又有着明显的特色，所以越来越受到人们的注意。 日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为，例如下棋、打牌、体育比赛等，还如战争活动中的双方，都力图选取对自己最为有利的策略，千方百计去战胜对手，在政治方面，国际间的谈判，各种政治力量之间的斗争。各国际集团之间的斗争等无一不具有斗争的性质。经济生活中，各国之间、各公司之间的各种经济谈判，企业为争夺市场而进行的竞争等，举不胜举。 具有竞争或对抗性质的行为，称为对策行为。在这类行为中，参加斗争或竞争的各方各自具有不同的目标和利益，为了达到各自的目标和利益各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案，对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。 在我国古代，“齐王赛马”就是一个典型的对策论研究的例子。 战国时期，齐王有一天提出要与大将田忌赛马。双方约定：从各自的上中下三个等级的马中选一匹参赛。每匹马均只能参赛一次；每次比赛双方各出一匹马，负者要付给胜者千金。已经知道，在同等级的马中，田忌的马不如齐王的马，而如果田忌的马比齐王的马高一等级，则田忌的马可取胜。当时，田忌手下的一个谋士给田忌出了个主意：每次比赛时先让齐王牵出他要参赛的马，然后用下马对齐王的上马，用中马对齐王的下马，用上马对齐王的中马。比赛结果，田忌，二胜一负，可得千金，由此看来，两人各采取什么样的出马次序，对胜负是至关重要的。 还如日常生活中，儿童或喝酒中不会猜拳的用“石头—剪子—布”游戏也是带有竞争性质的现象，大家都知道游戏的规定：第一，每人每局比赛中，只能在石头、剪子、布三种出法中选一种；第二，在一局比赛中，石头对剪子认为石头赢，剪子对布认为剪子赢，布对石头认为布方赢，如果双方都是同一种，则认为没有输赢。这样一局比赛中，各方是赢是输，不仅与自己所采取的发法（亦称策略）有关，而且与对方所采取的出法有关，下面介绍对策论中的矩阵对策。 §1对策问题的三个基本要求 以下称具有对策行为的模型为对策模型或对策。对策模型的种类可以千差万别，但本质上都必须包括如下三个基本要素： (1)局中人 在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者称为局中人，通常用I表示局中人的集合，如果有n个局中人，则I={1.2……n}，一般要求一个对策中至少要有二个局中人，如在“齐王赛马”例子中，局中人是齐王与田忌。 当然，对策中关于局中人的概念是具有广义性的，局中人除了可以理解为个人外，还可以理解为某一集体。 需要补充的一点是，在对策中总是假定每一个局中人都是理智的，聪明的决策者或竞争者。 即对任一局中人来讲，不存在利用其它局中人决策的失误，来扩大自身利益的可能性或相反。 (2)策略集 一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略，参加对策的每局中人，i∈I都有自己的策略集，一般，每一局中人的策略集中至少应包括两个策略。 在“齐王赛马”例子中，如用（上、中、下）表示以上马、中马、下马依次参赛次序，这是一个完整的行动方案，即为一个策略。可见，局中人齐王与田忌各自都有六个策略：（上、中、下）、（上、下、中）、（中、上、下）、（中、下、上）、（下、中、上）、（下、上、中）。 (3)赢得函数（支付函数） 在一局对策中，当局势给定以后，就用一个数来表示得失（或输赢），显然，这种“得失”或“输赢”是局势的函数，称为支付函数。 例如，Si是i个局中人的一个策略，则n个局中人的策略组 （s1，s2 …sn） 是一个局势，全体局势的集合S可用各局人策略集的笛卡尔积表示，即 s1×s2×…×sn 当局势出现后，对策结果也就确定了，即对任一局势s∈S，局中人I可能得到一个赢得H（s）。显然Hi(s)是局势s的函数，称为第I个局中人的赢得函数（支付函数） 齐王赛马中，局中人集体I={1.2} 齐王的策略集用{α1,α2,α3,α4,α5,α6} 田忌的策略集用{β1,β2,β3,β4,β5,β6}表示 这样齐王的任一策略αi 和田忌的任一策略βj，就决定了一个局势Sij，如果α1=（上、中、下）、β1 =（上、中、下）则在局势S11下齐王的赢得值为H1（S11）=3。 田忌的赢得