
本书是关于博弈论的一本基础教材,主要介绍了博弈论的概貌与脉络、棋类游戏的博弈分析、基本的数学工具、二人博弈的纯粹策略解和混合策略解、多人博弈的纯粹纳什均衡和混合纳什均衡、合作博弈的模型与解概念、解概念之核心、解概念之沙普利值及博弈论进阶学习。本书概念清晰、逻辑严密、写作规范,用最少的数学语言阐述博弈论的核心内容,可作为高等学校数学、管理、控制、智能等专业的本科生相关课程的教材或参考用书。
前言 博弈论是刻画竞争与合作环境下交互式决策的系统性科学理论,是数学的一个重要分支,主要研究交互决策的模型、解概念、性质、计算和应用等。博弈论涉及的要素包括参与人、行动策略、盈利函数、信息、顺序结构、认知逻辑等。 按照参与人是否合作,经典的博弈论粗略划分为非合作博弈与合作博弈。按照信息的完备程度和决策的顺序结构,非合作博弈又划分为完全信息静态博弈、完全信息动态博弈、不完全信息静态博弈和不完全信息动态博弈四种类型,对应的解概念包括纳什均衡、颤抖手均衡、子博弈完美均衡、序贯均衡、贝叶斯均衡、完美贝叶斯均衡等,后五者都是对纳什均衡的精炼和筛选。按照效用是否可以转移,合作博弈又划分为可转移效用合作博弈和不可转移效用合作博弈,对应的解概念包括稳定集、核心、沙普利值、谈判集等,合作博弈解概念都是基于公平、稳定分配的原则来设计的。 经典博弈论的性质研究主要聚焦多类型解概念的存在性、唯一性和复杂度,一般而言,存在性是可以保证的,但是唯一性往往不可兼得,解概念的复杂度都很高,给计算求解带来了很多困难,也催生了新型的复杂度概念。 经典的博弈模型与不同的数学结构融合,产生了新型的博弈论分支:与网络科学相结合产生了网络博弈论,与控制科学相结合产生了微分博弈论,与随机过程相结合产生了随机博弈论,与模糊理论相结合产生了模糊博弈论,与灰色理论相结合产生了灰色博弈论,与扩散方程相结合产生了平均场博弈论,与算法复杂度相结合产生了算法博弈论等。经典的博弈论在不同的场景应用中产生了新型的博弈论应用分支:在经济领域称之为经济博弈论,在社会领域称之为社会博弈论,在政治领域称之为政治博弈论,在管理领域称之为管理博弈论,在生态领域称之为进化博弈论,在智能领域称之为智能博弈论,在军事领域称之为军事博弈论等。 博弈论备受诺贝尔经济学奖的青睐,从1994 年的纳什、泽尔腾和海萨尼开始,至今陆续已有二十余位与博弈论研究密切相关的学者获得此奖;博弈论也颇受图灵奖的重视,数位研究博弈论解概念复杂度的理论计算机专家获得此奖。博弈论在人工智能中发挥了重要作用,是典型的人工智能系统(如Alpha Go、Liberatus、Alpha Star 等)背后的重要数学机理。 本书是写给本科生的一本关于博弈论的基础教材,主要介绍博弈论的概貌与脉络、棋类游戏的博弈分析、基本的数学工具、二人博弈的纯粹策略解和混合策略解、多人博弈的纯粹纳什均衡和混合纳什均衡、合作博弈的模型与解概念、解概念之核心、解概念之沙普利值及博弈论进阶学习。 全书分为11 章,各章的主要内容和作用如下。 第1章通过典型例子引出博弈论的基本模型,随后介绍了博弈论的基本定义、基本要素、基本分类,梳理了博弈论的历史脉络,介绍了博弈论著名学者的生平事迹。 棋类游戏是典型的博弈问题,第2章介绍了棋类游戏的博弈论建模和让人比较迷惑的三择一定理,这也是典型智能系统产生的基础。 博弈论是一门数学理论,具体来说是运筹学的一个分支,为了支撑博弈论模型的构建,需要底层的数学理论作为工具。在本书介绍的博弈论范围之内,双变量函数的鞍点定理、有限集合上的概率分布、优化模型与线性对偶理论、盈利函数形成的线性空间是所需要的数学工具。第3章详细介绍了这些基本的数学工具。 博弈论发展早期最成功的当属二人有限零和博弈。第4章和第5章介绍了二人有限零和博弈的理论,特别是冯.诺依曼的极小极大定理,该定理于1928 年提出,时至今日在智能时代仍然发挥着重要作用。 二人零和博弈是重要的博弈模型,但是也有其局限性。第6章、第7章一方面突破了参与人数量的限制,另一方面突破了盈利函数零和的限制。第6章介绍了多人策略型博弈(完全信息静态博弈)的纯粹策略解概念,包括支配均衡、安全均衡和纳什均衡及多类均衡之间的关系,特别是利用不动点定理在一定条件下证明了纳什均衡的存在性。有限完全信息静态博弈的纳什均衡不一定存在,为了解决这个问题,第7 章介绍了混合扩张方法,包括混合策略的定义和混合纳什均衡的存在性,此外还介绍了混合策略的颤抖手均衡和相关均衡。 除非合作博弈外,合作博弈也是博弈论的一个重要分支。第8章介绍了合作博弈的模型与解概念;第9章和第10章分别介绍了合作博弈的解概念之核心和沙普利值,并论证了它们的性质,在这个过程中,线性优化及其对偶理论扮演了重要角色。 作为一本高等学校本科生相关课程的教材,自然不能太厚、内容太多,只能择其精要简述。对于大多数只需要初步了解博弈论的学生而言,这已经足够,但是对于其有浓厚科研兴趣的学生而言,这就远远不够了,所以第11 章给出了有关博弈论进阶学习的建议。 本书的最大特色是公理化写作,采用了简单清晰的纯数学风格,学生只要掌握了初步的微积分、线性代数和概率论知识,就可以在博弈论课程的学习中游刃有余。 鉴于作者水平有限,书中难免有不足之处,请各位读者批评指正。 编者 2023 年1 月于长沙
目录 第1 章博弈论的概貌与脉络. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 案例:田忌赛马. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 案例:囚徒困境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 案例:金币的分配. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 博弈论的科学内涵. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 博弈论的主要概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 博弈论的内容体系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.7 博弈论的历史脉络. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.8 博弈论的著名学者. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 第2 章棋类游戏的博弈分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 棋类游戏的形式化描述. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15 2.2 棋类游戏的博弈论建模. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 2.3 棋类游戏的三择一定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 2.4 阅读材料:其他棋类. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1 六子棋博弈. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.2 围棋博弈. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.3 点格棋博弈. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5 人物故事:策梅洛. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.1 人物简历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.2 学术贡献一:集合论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.3 学术贡献二:博弈论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 第3 章基本的数学工具. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 双变量函数的鞍点定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29 3.2 有限集合上的概率分布. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 3.3 优化模型与线性对偶定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.1 数学优化模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.2 拉格朗日对偶理论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.3.3 线性优化对偶模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 盈利函数形成的线性空间. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 第4 章二人博弈的纯粹策略解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1 案例:俾斯麦海战. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 二人有限零和博弈的模型要素. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3 二人有限零和博弈的值与解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.4 二人有限零和博弈的解的刻画. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.5 俾斯麦海战案例的求解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65 第5 章二人博弈的混合策略解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.1 案例:猜硬币游戏. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2 二人零和博弈的混合模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3 二人有限零和博弈的混合值与解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4 二人有限零和博弈的混合解的刻画. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.5 二人有限零和博弈的混合解的存在性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.6 猜硬币游戏的计算. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.7 人物故事:冯·诺依曼. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83 5.7.1 人物简历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.7.2 学术贡献一:数学公理化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.7.3 学术贡献二:纯粹数学. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.7.4 学术贡献三:应用数学. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.7.5 学术贡献四:博弈论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.7.6 学术贡献五:计算机. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.7.7 著作与荣誉等身. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.7.8 有趣的轶事. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 第6 章多人博弈的纯粹纳什均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.1 案例:囚徒困境. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.2 纯粹策略的基本模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.3 纯粹策略的支配均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.4 纯粹策略的安全均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.5 纯粹策略的纳什均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.6 多类均衡之间的关系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.7 囚徒困境问题的计算. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 第7 章多人博弈的混合纳什均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.1 混合策略的基本模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 7.2 混合策略的支配均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.3 混合策略的安全均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 7.4 混合策略的纳什均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 7.5 混合策略的颤抖手均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.6 混合策略的相关均衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 7.7 多类均衡之间的关系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.8 猎鹿问题的计算. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.9 人物故事:纳什. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7.9.1 人物简历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7.9.2 学术贡献与荣誉. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 7.9.3 艺术形象. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.10 人物故事:吴文俊. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.10.1 人物简历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.10.2 学术贡献一:拓扑学. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.10.3 学术贡献二:人工智能. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 7.10.4 学术贡献三:数学史. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 7.10.5 学术贡献四:博弈论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 第8 章合作博弈的模型与解概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 8.1 合作博弈的基本模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 8.2 合作博弈的等价表示. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.3 合作博弈的解概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 第9 章解概念之核心. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 9.1 核心的定义和性质. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 9.2 核心的非空性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 9.2.1 平衡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 9.2.2 非空性定理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 9.3 平衡与全平衡覆盖. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 9.4 核心的一致性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 9.5 市场博弈的核心. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 9.6 可加博弈的核心. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 9.7 凸博弈的核心. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 9.8 一般联盟的核心. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 9.8.1 一般联盟核心的定义. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 9.8.2 一般联盟核心的性质. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 第10 章解概念之沙普利值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 10.1 数值解的公理体系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 10.2 满足部分公理的解. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 10.3 沙普利值经典刻画. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 10.4 沙普利值的边际刻画. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208 10.5 凸博弈的沙普利值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 10.6 沙普利值的一致性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 10.7 一般联盟沙普利值. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 10.7.1 一般联盟沙普利值的公理体系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 10.7.2 一般联盟沙普利值的定义性质. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 10.8 沙普利-舒比克权力指数. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .236 10.9 人物故事:沙普利. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 10.9.1 人物简历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 10.9.2 学术贡献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 10.9.3 中国情结. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 第11 章博弈论进阶学习. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 11.1 不确定博弈论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 11.2 博弈学习理论. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 11.3 博弈论与智能. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246