数学建模算法对策论.doc

数学建模算法对策论.doc第七章对策论
§1 引言
社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾,应用科学的方法来解决这样的问题开始于17世纪的科学家,如C.,Huygens和W.,Leibnitz等。现代对策论起源于1944年J.,Von Neumann和O.,Morgenstern的著作《Theory of Games and Economic Behavior》。
对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为,它既是现代数学的一个新分支,也是运筹学中的一个重要学科。对策论发展的历史并不长,但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系,并且处理问题的方法又有明显特色。所以日益引起广泛的注意。
在日常生活中,经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益,各方必须考虑对手的各种可能的行动方案,并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案,以及如何找到这个合理的行动方案的数学理论和方法。
§2 对策问题
对策问题的特征是参与者为利益相互冲突的各方,其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。
先考察一个实际例子。
例1 警察同时逮捕了两人并分开关押,逮捕的原因是他们持有大量伪币,警方怀疑他们伪造钱币,但没有找到充分证据,希望他们能自己供认,这两个人都知道:如果他们双方都不供认,将被以持有大量伪币罪被各判刑18个月;如果双方都供认伪造了钱币,将各被判刑3年;如果一方供认另一方不供认,则供认方将被从宽处理而免刑,但另一方面将被判刑7年。将嫌疑犯、被判刑的几种可能情况列表如下:
嫌疑犯
供认不供认
嫌疑犯供认(3,3) (0,7)
不供认(7,0) (,)
表中每对数字表示嫌疑犯被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚,最保险的办法自然是承认制造了伪币。
从这一简单实例中可以看出对策现象中包含有的几个基本要素。
对策的基本要素
(i)局中人
在一个对策行为(或一局对策)中,有权决定自己行动方案的对策参加者,称为局中人。,则。一般要求一个对策中至少要有两个局中人。在例1中,局中人是两名疑犯。
(ii)策略集
一局对策中,可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人,,都有自己的策略集。一般,每一局中人的策略集中至少应包括两个策略。
(iii)赢得函数(支付函数)
在一局对策中,各局中人所选定的策略形成的策略组称为一个局势,即若是第个局中人的一个策略,则个局中人的策略组

就是一个局势。全体局势的集合S可用各局中人策略集的笛卡尔积表示,即

当局势出现后,对策的结果也就确定了。也就是说,对任一局势,,局中人可以得到一个赢得。显然,是局势的函数,称之为第个局中人的赢得函数。这样,就得到一个向量赢得函数。
本节我们只讨论有两名局中人的对策问题,其结果可以推广到一般的对策模型中去。
零和对策(矩阵对策)
零和对策是一类特殊的对策问题。在这类对策中,只有两名局中人,每个局中人都只有有限个策略可供选择。在任一纯局势下,两个局中人的赢得之和总是等于零,即双方的利益是激烈对抗的。
设局中人Ⅰ、Ⅱ的策略集分别为
,
当局中人Ⅰ选定策略和局中人Ⅱ选定策略后,就形成了一个局势,可见这样的局势共有个。对任一局势,记局中人Ⅰ的赢得值为,并称
为局中人Ⅰ的赢得矩阵(或为局中人Ⅱ的支付矩阵)。由于假定对策为零和的,故局中人Ⅱ的赢得矩阵就是。
当局中人Ⅰ、Ⅱ和策略集、及局中人Ⅰ的赢得矩阵确定后,一个零和对策就给定了,零和对策又可称为矩阵对策并可简记成
。
例2 设有一矩阵对策,其中,,
从中可以看出,若局中人Ⅰ希望获得最大赢利30,需采取策略,但此时若局中人Ⅱ采取策略,局中人Ⅰ非但得不到30,反而会失去22。为了稳妥,双方都应考虑到对方有使自己损失最大的动机,在最坏的可能中争取最好的结果,局中人Ⅰ采取策略时,最坏的赢得结果分别为
其中最好的可能为。如果局中人Ⅰ采取策略,无论局中人Ⅱ采取什么策略,局中人Ⅰ的赢得均不会少于2。
局中人Ⅱ采取各方案的最大损失为,,,和。当局中人Ⅱ采取策略时,其损失不会超过2。注意到在赢得矩阵中,2既是所在行中的最小元素又是所在列中的最大元素。此时,只要对方不改变策略,任一局中人都不可能通过变换策略来增大赢得或减少损失,称这样的局势为对策的一个稳定点或稳定解。
定义1 设为一个定义