博弈论与机制设计（博弈论与机制设计）

内容简介

博弈论已涉足计算机科学和电子工程学科的很多新兴应用领域。目前已有一些关于博弈论的优秀教材，但将非合作博弈、合作博弈以及机制设计同时呈现的教材并不多见，而这正是本书的最大特色。

首先，本书主要针对工程科学领域的读者，同时也强调基于应用的计算机科学。其次，本书纳入了机制设计板块，而大多数教材着重介绍博弈论。本书分为三个部分: 非合作博弈论（第2～13章）、机制设计（第14～24章）、合作博弈论（第25～31章）。另外，下列三章相对独立：第1章是导论，第32章是结束语，第33章给出了数学知识准备。每一章都以动机和中心思想开篇，以小结和参考文献收尾。每一章的小结主要列举重要概念和知识点，参考文献主要用于指引读者进一步考察。每章结尾处都给出了一组习题，其中个别题目是编程题。

作者简介

Y.内拉哈里（Narahari）目前任教于印度科技学院计算机与自动化系。近十年来，他的研究重点是计算机科学与微观经济交叉领域的问题。他尤其关注博弈论和机制设计在拍卖、电子商务、多智能体系统以及社会网络中的应用。在这些领域以及其他领域，内拉哈里写下了大量有影响的学术论文。他的很多学生获得过最佳博士（硕士）论文奖。他是专著《网络经济学中的博弈论问题与机制设计解》（Game Theoretic Problems in Network Economics and Mechanism Design Solutions， Springer，London，2009）的第一作者。他也是《自动化制造系统的绩效模拟》（Performance Modeling of Automa- ted Manufacturing Systems，Prentice Hall， USA，1992）这本广受好评的著作的共同作者。Y.内拉哈里的工作得到了很多学会的认可，也获得了多项科研基金赞助。

章节目录

第1章 引言与概览 1 　　1.1 博弈论：策略互动科学 1 　　1.2 当前趋势和现代应用 6 　　1.3 本书结构 11 　　第1部分 非合作博弈论 　　第2章 博弈论中的重要概念 17 　　2.1 策略型博弈 17 　　2.2 偏好 18 　　2.3 效用 19 　　2.4 理性 19 　　2.5 智能 21 　　2.6 博弈分类 23 　　2.7 小结与参考文献 24 　　第3章 展开型博弈 27 　　3.1 例子 27 　　3.2 展开型博弈：定义 29 　　3.3 将展开型博弈转换为策略型博弈 32 　　3.4 小结与参考文献 34 　　3.5 习题 35 　　第4章 策略型博弈 37 　　4.1 基本知识 37 　　4.2 同时行动情形下的硬币配对 38 　　4.3 石头剪刀布 39 　　4.4 BOS博弈 39 　　4.5 协作博弈 40 　　4.6 囚徒困境博弈 40 　　4.7 公司两难博弈 41 　　4.8 公司两难博弈：非对称版本 42 　　4.9 双寡头定价博弈 42 　　4.10 公地悲剧 43 　　4.11 带宽共享博弈 43 　　4.12 密封拍卖 44 　　4.13 庇古网络博弈 44 　　4.14 布雷斯悖论博弈 46 　　4.15 小结与参考文献 47 　　4.16 习题 49 　　第5章 优势策略均衡 50 　　5.1 强优（劣）势 50 　　5.2 弱优（劣）势 51 　　5.3 极弱优（劣）势 52 　　5.4 优势策略均衡的例子 52 　　5.5 小结与参考文献 55 　　5.6 习题 56 　　第6章 纯策略纳什均衡 57 　　6.1 纳什均衡概念 57 　　6.2 纯策略纳什均衡的例子 60 　　6.3 不存在纯策略纳什均衡的博弈 63 　　6.4 纳什均衡的解释 65 　　6.5 存在多个纳什均衡的情形 67 　　6.6 最大最小值和最小最大值 68 　　6.7 展开型博弈的均衡 71 　　6.8 小结与参考文献 73 　　6.9 习题 75 　　第7章 混合策略与混合策略纳什均衡 79 　　7.1 混合策略 79 　　7.2 混合策略纳什均衡 81 　　7.3 混合策略的性质 82 　　7.4 策略组成为混合策略纳什均衡的必要充分条件 84 　　7.5 混合策略中的最大最小值与最小最大值 89 　　7.6 混合策略中的优（劣）势 90 　　7.7 小结与参考文献 93 　　7.8 习题 95 　　第8章 效用理论 99 　　8.1 为何需要效用理论 99 　　8.2 冯·诺依曼-摩根斯坦效用理论公理 101 　　8.3 冯·诺依曼-摩根斯坦定理 104 　　8.4 仿射变换 106 　　8.5 计算冯·诺依曼-摩根斯坦效用 107 　　8.6 参与人的风险态度 108 　　8.7 小结与参考文献 110 　　8.8 习题 111 　　第9章 矩阵博弈 112 　　9.1 矩阵博弈的例子 113 　　9.2 矩阵博弈中的纯策略 114 　　9.3 鞍点与纯策略纳什均衡 115 　　9.4 矩阵博弈中的混合策略 117 　　9.5 最小最大定理 122 　　9.6 小结与参考文献 124 　　9.7 习题 125 　　第10章 纳什均衡的存在性 128 　　10.1 对应以及不动点定理 129 　　10.2 纳什均衡是不动点 130 　　10.3 纯策略纳什均衡存在性的充分条件 131 　　10.4 纳什定理 133 　　10.5 施佩纳引理 134 　　10.6 从施佩纳引理到布劳威尔不动点定理 138 　　10.7 使用布劳威尔不动点定理证明纳什定理 141 　　10.8 无限博弈的纳什均衡存在性 143 　　10.9 小结与参考文献 144 　　10.10 习题 145 　　第11章 纳什均衡的计算 147 　　11.1 支撑与纳什均衡 147 　　11.2 有限策略型博弈纳什均衡的一般算法 148 　　11.3 计算纳什均衡：一个例子 150 　　11.4 小结与参考文献 154 　　11.5 习题 156 　　第12章 纳什均衡计算的复杂性 158 　　12.1 纳什问题与布劳威尔问题 158 　　12.2 PPAD类 159 　　12.3 纳什问题是PPAD-complete问题 161 　　12.4 一些观察 162 　　12.5 小结与参考文献 163 　　第13章 贝叶斯博弈 165 　　13.1 伴随不完全信息的博弈 165 　　13.2 贝叶斯博弈的例子 168 　　13.3 类型代理表示法与泽尔腾博弈 169 　　13.4 贝叶斯纳什均衡 172 　　13.5 优势策略均衡 173 　　13.6 小结与参考文献 175 　　13.7 习题 175 　　第2部分 机制设计 　　第14章 机制设计导论 179 　　14.1 机制设计：常见例子与历史 179 　　14.2 机制设计环境 183 　　14.3 直接机制与间接机制 185 　　14.4 社会选择函数的例子 186 　　14.5 小结与参考文献 192 　　14.6 习题 193 　　第15章 通过机制实施社会选择函数 194 　　15.1 通过直接机制实施社会选择函数 194 　　15.2 通过间接机制实施社会选择函数 198 　　15.3 机制诱导出的贝叶斯博弈 201 　　15.4 通过机制实施社会选择函数 202 　　15.5 小结与参考文献 204 　　15.6 习题 205 　　第16章 激励相容与显示原理 206 　　16.1 激励相容 206 　　16.2 优势策略均衡的显示原理 208 　　16.3 贝叶斯纳什均衡的显示原理 209 　　16.4 社会选择函数的性质 210 　　16.5 小结与参考文献 212 　　16.6 习题 213 　　第17章 吉伯德-萨特思韦特不可能性定理 216 　　17.1 引言 216 　　17.2 吉伯德-萨特思韦特定理 218 　　17.3 吉伯德-萨特思韦特定理 221 　　17.4 阿罗不可能定理 225 　　17.5 小结与参考文献 229 　　第18章 维克瑞-克拉克-格罗夫斯机制 231 　　18.1 拟线性环境 231 　　18.2 格罗夫斯机制 237 　　18.3 克拉克机制（关键人机制） 240 　　18.4 VCG机制的例子 240 　　18.5 小结与参考文献 244 　　18.6 习题 245 　　第19章 拟线性环境中的机制设计空间 247 　　19.1 格罗夫斯机制与严格预算平衡 247 　　19.2 克拉克机制与弱预算平衡 248 　　19.3 个体理性 250 　　19.4 VCG机制与个体理性 251 　　19.5 dAGVA机制 253 　　19.6 拟线性环境中的机制设计空间 257 　　19.7 线性环境 258 　　19.8 小结与参考文献 259 　　19.9 习题 260 　　第20章 拍卖 262 　　20.1 拍卖类型与合意性质 262 　　20.2 经典机制：一件不可分割的商品的拍卖 264 　　20.3 第一价格密封拍卖和第二价格密封拍卖的收入等价性 266 　　20.4 收入等价定理 268 　　20.5 组合拍卖 271 　　20.6 小结与参考文献 273 　　20.7 习题 274 　　第21章 最优机制与迈尔森拍卖 276 　　21.1 最优机制 276 　　21.2 迈尔森最优拍卖 277 　　21.3 有效率的最优拍卖 282 　　21.4 小结与参考文献 283 　　21.5 习题 284 　　第22章 赞助搜索拍卖的机制设计 285 　　22.1 赞助搜索拍卖 285 　　22.2 作为机制设计问题的赞助搜索拍卖 286 　　22.3 广义第一价格（GFP）机制 289 　　22.4 广义第二价格（GSP）机制 289 　　22.5 维克瑞克拉克格罗夫斯（VCG）机制 290 　　22.6 最优（OPT）机制 292 　　22.7 小结与参考文献 298 　　22.8 习题 299 　　第23章 在事后纳什均衡中实施社会选择函数 300 　　23.1 社会选择函数的实施：多个均衡的情形 300 　　23.2 在纳什均衡中实施社会选择函数 301 　　23.3 社会选择函数的可实施性：完全信息环境 304 　　23.4 小结与参考文献 306 　　第24章 机制设计的其他议题 308 　　24.1 优势策略激励相容的特征 308 　　24.2 BIC规则的优势策略实施 309 　　24.3 相互依赖的价值 309 　　24.4 其他形式的实施 310 　　24.5 当前重要议题 310 　　24.6 机制设计中的计算议题 311 　　24.7 小结与参考文献 311 　　第3部分 合作博弈论 　　第25章 相关策略与相关均衡 317 　　25.1 伴随合同的博弈 318 　　25.2 相关策略 319 　　25.3 伴随沟通的博弈 322 　　25.4 相关均衡 325 　　25.5 小结与参考文献 327 　　25.6 习题 328 　　第26章 两人议价问题 331 　　26.1 纳什规划 331 　　26.2 两人议价问题 332 　　26.3 纳什公理 334 　　26.4 纳什议价解 336 　　26.5 纳什议价定理的证明 338 　　26.6 平等主义解和效用主义解 342 　　26.7 小结与参考文献 344 　　26.8 习题 345 　　第27章 伴随可转移效用的联盟博弈 347 　　27.1 多人合作博弈 347 　　27.2 伴随可转移效用的博弈 350 　　27.3 伴随特殊结构的TU博弈 354 　　27.4 成本博弈 358 　　27.5 小结与参考文献 358 　　27.6 习题 359 　　第28章 联盟博弈的核 361 　　28.1 核：定义与例子 361 　　28.2 博弈何时有非空的核 366 　　28.3 凸博弈的核 369 　　28.4 成本博弈的核 370 　　28.5 小结与参考文献 370 　　28.6 习题 372 　　第29章 夏普利值 374 　　29.1 夏普利公理 375 　　29.2 夏普利定理与例子 377 　　29.3 夏普利定理的证明 380 　　29.4 夏普利值的其他发展方法 383 　　29.5 凸博弈的夏普利值 384 　　29.6 夏普利舒比克权力指数 385 　　29.7 班茨哈夫指数 386 　　29.8 小结与参考文献 387 　　29.9 习题 388 　　第30章 合作博弈论中的其他解概念 391 　　30.1 稳定集 391 　　30.2 议价集 393 　　30.3 内核 396 　　30.4 核仁 397 　　30.5 盖特利点 398 　　30.6 小结与参考文献 399 　　30.7 习题 401 　　第31章 稳定匹配 402 　　31.1 匹配问题 402 　　31.2 匹配算法 403 　　31.3 市场匹配 407 　　31.4 小结与参考文献 408 　　31.5 习题 408 　　第32章 结束语 　　410 32.1 本书目的 410 　　32.2 进一步探索 411 　　32.3 小结与参考文献 412 　　第33章 数学知识准备 414 　　33.1 概率论 414 　　33.2 线性代数 416 3 　　3.3 线性规划与对偶 417 　　33.4 数学分析 419 　　33.5 计算复杂类 422 　　33.6 小结与参考文献 424 　　索引 426