《博弈论概要》.pdf

2012 博弈论概要 邓潘亮编写 dengpanliangbupt@ 编者按：竞争与合作贯穿着人类社会生活的方方面面，博弈 论作为诠释这两种行为的理论，近年来在几乎所有门类的科 学研究探讨的重要方法论之一，本概要对应用博弈论研究科 学与工程问题所常用的定义、模型以及工具进行了总结，目 的为那些试图应用博弈论研究科学和工程问题的研究者提 供一个工具框架，本概要在最后部分还列举了博弈论应用于 认知无线电通信领域的关键文献。更为深入了解和学习请参 考博弈论专著（Fudenberg、Tirole 1991；Myerson 1991 ；）。 0? 引言 博弈论是一种研究决策主体的行为发生直接相互作用时的决策以及这种决 策之间均衡问题的数学方法。它与信息论一样在 20 世纪 40 年代到 50 年代经历 了跨越式的发展，1944 年冯诺依曼 Von Neumann 和摩根斯坦恩 Morgenstern 发 表专著《博弈论与经济行为》提出大部分的经济问题都应当用博弈的模型来分析， 引出了通用博弈理论。随后，纳什在 1950 年和 1951 年发表的两篇非合作博弈的 论文和塔克 Tucker 在 1950 年定义了“囚徒困境”奠定了现代非合作博弈的基石。 六十年代博弈论又得到很大进展，泽尔腾 Selten 1965 把纳什均衡的概念引入到 动态分析研究，提出“精炼纳什均衡”的概念，奠定了完全信息动态博弈的基础。 针对纳什均衡概念的某些不完善的地方，排除纳什均衡点的缺陷，泽尔腾将那些 包含不可置信威胁战略的纳什均衡从均衡中剔除，从而给出动态博弈结果的一个 合理的解。另一个重要的工作是海萨尼 Harsanyi 1967-1968 对不完全信息博弈的 研究，建立了不完全信息博弈的基础工作。博弈论得到了系统阐述与澄清，形成 了完整而系统的体系。同时，在合作博弈方面，纳什 Nash 1950 年 和夏普里 Shapley1953 年 研究的“讨价还价”模型，将合作博弈研究推向顶峰。博弈论 2012 作为分析和解决冲突和合作的工具，目前在生物学、经济学、国际关系、政治学、 军事战略等学科都有广泛的应用。值得注意的是近年来，随着高可靠、大容量无 线通信的需求，各个无线传输链路之间存在资源共享以及相互影响等问题，怎样 协调传输链路之间的相互作用使得系统能够获得最佳总体性能，博弈论在通信系 统设计中的应用是当前通信与信息领域学术界和工业界共同关注的热点。 博弈论作为分析不同行为主体相互作用的数学工具，其主要包含以下三个基 本要素： 1. 参与人（Player） 在博弈模型中，能够有权决定自身行为的主体成为参与人N 1,...,n 。 在博弈论中，对于参与人有一个重要的前提假设：每个参与人都是“理 性的”，也就是说，每个参与人都是以个人主体最大化为优化目标。 2. 策略集（Strategy?sets ） 博弈模型中，参与人所有可能选择的策略构成策略集Si ，i ?N 。 3. 效用函数（Utility） S 在所有博弈参与人的策略 确定后，对于第i 个参与人会产生效用函数 u : S ?R ，其中S ?? S 。 i i?N i 我们通常把上述三要素构成的博弈模型表征为G N, S , u 。 i i 1?非合作博弈 在非合作博弈论中，Nash 均衡是最基本最核心的概念。分析一个多人博弈， 通常我们需要回答三个问题：第一，这个博弈最终的结局将会如何？Nash 均衡 将会是多人非合作博弈的结果，也就说每个参与人考虑其它参与人的策略均采用 最佳策略。第二，这样的 Nash 均衡是否总是存在？Nash 证明 Nash 均衡的存在 具有普遍性。第三，存在的 Nash 均衡是否唯一？Nash 均衡的唯一性要根据具体 情况分析而定。然而，Nash 均衡只是给出了多人博弈的最终结果，并没有告诉 我们怎么才能达到 Nash 均衡。一般情况下，博弈中的每个参与人首先任意选择 其策略，随后通过某些准则更新各自的策略直到收敛到均衡状态。 2012 1.1 Nash 均衡 在博弈论中，Nash 均衡是最为常见的解，其定义如下： * * * 定义：策略博弈 G N, S , u ，策略组合s s , ?, s 如果满足以下条 i i 1 n 件： * * * ，s ?S ,i 1, ?,n ，则为纳什均衡。 u s , s 3u s , s i i -i i i -i i i 其 中 ， 对 于 每 一 个 i 1, ?, n ， s* 为 给 定 其 他 参 与 人 策 略 i * * * * * 的情况下第i