斯坦福算法博弈论二十讲

本书特色

[

本书源于斯坦福大学“算法博弈论”课程讲义，面向计算机科学、经济学、电子工程和数学等不同专业的高年级本科生和研究生。第1章概述相关知识和实例。第2~10章讨论关于规则制定的理论，即“机制设计”，包括在线广告、无线频谱拍卖和肾脏交换等实例。第11~15章介绍“无秩序代价”理论，围绕实际博弈中均衡的近似保证展开讨论。第16~20章介绍关于均衡计算的一些结论，基于分布式学习算法和以计算效率为核心的算法对均衡进行分析和计算，包括积极结论和消极结论。此外，每章都有颇具挑战性的习题，部分习题配有解答提示。

]

内容简介

[

计算机科学与经济学的交互产生了“算法博弈论”这一新的研究领域。对于计算机科学中的诸多核心问题，其本质上都涉及多个自私个体之间的交互，经济学和博弈论为这样的问题提供了丰富的推理模型和定义系统。而对于传统经济学中的问题，计算机科学也起到了补充作用，例如关于计算复杂性、近似边界以及贝叶斯或平均情况分析的研究。
本书源于斯坦福大学“算法博弈论”课程讲义，通过具有代表性的模型和结论，帮助读者快速了解这一领域的重要概念。书中首先讨论关于规则制定的理论，即“机制设计”，包括在线广告、无线频谱拍卖和肾脏交换等实例，目标是设计一个由多个策略型参与者组成的系统，并保证其具有良好的性能。接下来介绍“无秩序代价”理论，围绕实际博弈中均衡的近似保证展开讨论，目标是了解在什么情况下自私的行为是良性的。*后介绍关于均衡计算的一些结论，基于分布式学习算法和以计算效率为核心的算法对均衡进行分析和计算，目标是研究如何使策略型参与者达到博弈均衡，以及达到均衡后的情形。

]

作者简介

[

—作者简介—
蒂姆·拉夫加登（Tim Roughgarden） 哥伦比亚大学计算机科学系教授，之前曾任教于斯坦福大学，主要研究领域包括算法、博弈论以及微观经济学。他曾获得美国青年科学家与工程师总统奖（PECASE），ACM颁发的Grace Murray Hopper奖，Game Theory Society颁发的Kalai奖，Mathematical Programming Society颁发的Tucker奖，以及EATCS-SIGACT颁发的Gödel奖。

—译者简介—
郝东 电子科技大学副教授，研究领域为算法博弈论、*优决策、多智能体系统。

]

目录

出版者的话译者序前言第1章　简介和实例1　1.1　关于规则制定的科学1　1.2　自私的行为在什么时候是近似*优的3　　1.2.1　布雷斯悖论3　　1.2.2　线与弹簧4　1.3　策略型参与者能通过学习算出一个均衡吗4　总结6　说明6　练习6　问题7第2章　机制设计基础8　2.1　单物品拍卖8　2.2　密封价格拍卖9　2.3　一价拍卖9　2.4　二价拍卖和占优策略9　2.5　理想化拍卖11　2.6　经典案例：关键字搜索拍卖12　　2.6.1　背景知识12　　2.6.2　关键字搜索拍卖的基本模型12　　2.6.3　我们想要什么13　　2.6.4　我们的设计方法13　总结14　说明14　练习14　问题16第3章　迈尔森引理17　3.1　单参数环境17　3.2　分配规则和支付规则18　3.3　迈尔森引理的内容19　��3.4　迈尔森引理的证明20　3.5　支付公式的运用23　总结24　说明25　练习25　问题25第4章　算法机制设计28　4.1　背包拍卖28　　4.1.1　问题定义28　　4.1.2　福利*大化的DSIC背包拍卖29　　4.1.3　关键报价29　　4.1.4　福利*大化的计算困难性29　4.2　算法机制设计30　　4.2.1　*好的情况：免费的DSIC30　　4.2.2　再谈背包拍卖31　4.3　显示原理33　　4.3.1　再谈DSIC33　　4.3.2　直接显示的证明33　　4.3.3　在占优策略均衡之外34　总结34　说明35　练习35　问题36第5章　收益*大化拍卖39　5.1　收益*大化的挑战39　　5.1.1　我们被社会福利*大化“宠坏”了39　　5.1.2　单竞拍者和单物品40　　5.1.3　贝叶斯分析40　　5.1.4　再谈单竞拍者和单物品41　　5.1.5　多竞拍者41　5.2　*优DSIC机制的性质42　　5.2.1　准备工作42　　5.2.2　虚拟估值42　　5.2.3　期望收益等于期望虚拟福利43　　5.2.4　*大化期望虚拟福利44　　5.2.5　正则分布44　　5.2.6　*优单物品拍卖45　5.3　案例分析：关键字搜索拍卖中的保留价格46　��5.4　引理5.1的证明47　总结48　说明49　练习49　问题50第6章　简单的近似*优拍卖52　6.1　*优拍卖可能很复杂52　6.2　预知不等式53　6.3　简单的单物品拍卖54　6.4　先验独立机制56　总结57　说明58　练习58　问题59第7章　多参数机制设计61　7.1　一般化的机制设计环境61　7.2　VCG机制62　7.3　实际的考量64　总结65　说明65　练习65　问题66第8章　频谱拍卖68　8.1　非直接机制68　8.2　分开拍卖多个物品69　8.3　案例分析：同时升价拍卖70　　8.3.1　两个新手常见错误70　　8.3.2　同时升价拍卖的优点71　　8.3.3　需求缩减和披露问题72　　8.3.4　发送竞价信号73　8.4　组合竞价74　8.5　案例分析：2016年FCC激励拍卖74　总结77　说明77　练习77　问题78第9章　含支付约束的机制设计80　9.1　预算约束80　9.2　同一价格多单位拍卖81　　9.2.1　多单位拍卖81　　9.2.2　同一价格拍卖81　　9.2.3　同一价格拍卖不是DSIC的82　��9.3　锁定拍卖82　9.4　不含钱机制设计85　总结87　说明88　练习88　问题89第10章　肾脏交换和稳定匹配91　10.1　案例分析：肾脏交换91　　10.1.1　背景91　　10.1.2　使用TTC算法92　　10.1.3　应用匹配算法93　　10.1.4　医院方的动机因素96　10.2　稳定匹配97　　10.2.1　模型97　　10.2.2　延迟接受算法98　��10.3　更多的性质99　总结101　说明101　练习102　问题102第11章　自私路由与无秩序代价103　11.1　自私路由103　　11.1.1　布雷斯悖论103　　11.1.2　Pigou示例104　　11.1.3　Pigou示例：非线性变种104　11.2　主要结论：非正式的表述105　11.3　主要结论：正式的表述106　11.4　技术准备108　��11.5　定理11.2的证明109　总结110　说明110　练习111　问题111第12章　超额配置和单元自私路由113　12.1　案例分析：网络超额配置113　　12.1.1　超额配置的动机113　　12.1.2　超额配置网络的POA界113　12.2　资源增广界115　��12.3　定理12.1的证明115　12.4　单元自私路由116　��12.5　定理12.3的证明118　总结119　说明120　练习120　问题121第13章　均衡：定义、示例和存在性123　13.1　均衡概念的层级结构123　　13.1.1　代价*小化博弈124　　13.1.2　纯策略纳什均衡124　　13.1.3　混合策略纳什均衡124　　13.1.4　相关均衡125　　13.1.5　粗糙相关均衡126　　13.1.6　示例127　13.2　纯策略纳什均衡的存在性127　　13.2.1　均衡分流的存在性127　　13.2.2　非单元均衡分流的唯一性128　　13.2.3　拥塞博弈129　13.3　势博弈129　总结129　说明130　练习130　问题131第14章　平滑博弈的鲁棒无秩序代价界133　��14.1　POA界四阶段式处理方法133　��14.2　选址博弈134　　14.2.1　模型134　　14.2.2　选址博弈的性质136　　14.2.3　定理14.1的证明137　��14.3　平滑博弈138　��

封面

书名:斯坦福算法博弈论二十讲

作者:蒂姆·拉夫加登

页数:248

定价:¥99.0

出版社:机械工业出版社

出版日期:2020-01-01

ISBN:9787111643067

PDF电子书大小:80MB 高清扫描完整版