算法大全第07章_对策论

普大帝

你好！我是陪你一起进阶人生的普大帝！愿你成才！祝你成长！
+ Y% f7 o; C& M今日开始我会大家更新一些算法类的辅助资料，大家在想学习时，或者比赛急需时就可以按照对应的名字找到对应的算法，加以应用了。大家按照下图所示箭头处点击主题，就可以查看到其他算法类内容了，本篇为第7篇。
8 L) H6 u* Q# o3 q, X4 o
! n+ r6 b. V, {+ p9 D9 ?引言
8 p* x3 j% T; E+ A社会及经济的发展带来了人与人之间或团体之间的竞争及矛盾，应用科学的方法来解决这样的问题开始于 17 世纪的科学家，如 C.，Huygens 和 W.，Leibnitz 等。现代对策论起源于 1944 年 J.，Von Neumann 和 O.，Morgenstern 的著作《Theory of Games andEconomic Behavior》。对策论亦称竞赛论或博弈论。是研究具有斗争或竞争性质现象的数学理论和方法。一般认为，它既是现代数学的一个新分支，也是运筹学中的一个重要学科。对策论发展的历史并不长，但由于它所研究的现象与人们的政治、经济、军事活动乃至一般的日常生活等有着密切的联系，并且处理问题的方法又有明显特色。所以日益引起广泛的注意。
) @6 V2 S; e  _6 ]在日常生活中，经常看到一些具有相互之间斗争或竞争性质的行为。具有竞争或对抗性质的行为称为 对策行为。在这类行为中。参加斗争或竞争的各方各自具有不同的目标和利益。为了达到各自的目标和利益，各方必须考虑对手的各种可能的行动方案，并力图选取对自己最为有利或最为合理的方案。对策论就是研究对策行为中斗争各方是否存在着最合理的行动方案，以及如何找到这个合理的行动方案的数学理论和方法。
§2 对策问题
对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。
先考察一个实际例子。例 1（囚徒的困境） 警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以持有大量伪币罪被各判刑 18 个月；如果双方都供认伪造了钱币，将各被判刑 3 年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑 7 年。将嫌疑犯 A 、 B 被判刑的几种可能情况列于表 1。
表 1
* C7 B, w. ~% J6 S+ h$ M

& y6 ]9 r0 ]+ H- R; F表 1 中每对数字表示嫌疑犯 B A、 被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。从这一简单实例中可以看出对策现象中包含有的几个基本要素。
2.1 对策的基本要素
/ H7 D. D: p- x- ^7 p+ P4 _（i）局中人
在一个对策行为（或一局对策）中，有权决定自己行动方案的对策参加者，称为局中人。通常用 I 表示局中人的集合．如果有 n 个局中人，则 } , , 2 , 1 { n I L = 。一般要求一个对策中至少要有两个局中人。在例 1 中，局中人是 B A 、 两名疑犯。（ii）策略集一局对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个策略。参加对策的每一局中人 i ， I i∈ ，都有自己的策略集iS 。一般，每一局中人的策略集中至少应包括两个策略。（iii）赢得函数（支付函数）在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若i
s 是第 i个局中人的一个策略，则 n 个局中人的策略组) 就是一个局势。全体局势的集合 S 可用各局中人策略集的笛卡尔积表示，即

2 B5 V6 \. g1 ?9 I. ~7 E8 J当局势出现后，对策的结果也就确定了。也就是说，对任一局势， S s ∈ ，局中人i 可以得到一个赢得 ) ( s H i 。显然， ) ( s H i 是局势 s 的函数，称之为第 i 个局中人的赢得函数。这样，就得到一个向量赢得函数 本节我们只讨论有两名局中人的对策问题，其结果可以推广到一般的对策模型中去。
/ E! t9 K8 V! W8 j2.2 零和对策（矩阵对策）
& c( x; o* b8 J# E零和对策是一类特殊的对策问题。在这类对策中，只有两名局中人，每个局中人都只有有限个策略可供选择。在任一纯局势下，两个局中人的赢得之和总是等于零，即双方的利益是激烈对抗的。
2 ?5 B$ e7 D4 ]2 J& G
下载资源查看完整版内容
3 I$ p, P; d' q8 l$ N! c