[醉染正版]斯坦福算法博弈论二十讲 计算机科学丛书 蒂姆 拉夫加登 经济学的跨学科研究 经济与计算科学 计算机科学理论与

               店铺公告

为保障消费者合理购买需求及公平交易机会，避免因非生活消费目的的购买货囤积商品，抬价转售等违法行为发生，店铺有权对异常订单不发货且不进行赔付。异常订单：包括但不限于相同用户ID批量下单，同一用户（指不同用户ID，存在相同/临近/虚构收货地址，或相同联系号码，收件人，同账户付款人等情形的）批量下单（一次性大于5本），以及其他非消费目的的交易订单。

温馨提示：请务必当着快递员面开箱验货，如发现破损，请立即拍照拒收，如验货有问题请及时联系在线客服处理，（如开箱验货时发现破损，所产生运费由我司承担，一经签收即为货物完好，如果您未开箱验货，一切损失就需要由买家承担，所以请买家一定要仔细验货），

关于退货运费：对于下单后且物流已发货货品在途的状态下，原则上均不接受退货申请，如顾客原因退货需要承担来回运费，如因产品质量问题（非破损问题）可在签收后，联系在线客服。

A8 

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

作者: 蒂姆·拉夫加登

作者地区: 美国

定价: 99.00元

ISBN编号: 9787111643067

是否是套装: 否

出版社名称: 机械工业出版社

出版时间: 2020-01

计算机科学和经济学在过去的十多年中进行了热烈的交互，产生了新的算法博弈论领域。许多现代计算机科学的核心问题，从大型网络的资源分配到在线广告，都涉及多个自利方个体之间的相互作用。经济学和博弈论为这些问题提供了大量有用的模型和定义。同时，对于传统经济学的许多问题，来自计算机科学的研究又起到了补充作用。本书源于作者在斯坦福大学的算法博弈论课程讲义，旨在让学生和其他新学者快速、方便地了解该领域的许多重要的概念。本书通过在线广告、无线频谱交易和网络管理等案例来说明这些概念，非常适合课堂教授和自学。

出版者的话
译者序
前言
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
14.4 平滑博弈的鲁棒POA界139
14.4.1 PNE的POA界139
14.4.2 CCE的POA界139
14.4.3 近似PNE的POA界140
总结141
说明141
练习142
问题142
15章好情况和强纳什均衡144
15.1 网络代价分摊博弈144
15.1.1 外部性144
15.1.2 模型144
15.1.3 示例：VHS还是Betamax145
15.1.4 示例：出博弈146
15.2 稳定的代价147
15.3 强纳什均衡的POA148
15.4 定理15.3的证明150
总结151
说明152
练习152
问题152
16章优反应动力学154
16.1 势博弈中的优反应动力学154
16.2 自私路由博弈中的近似PNE156
16.3 定理16.3的证明157
16.4 平滑势博弈中的低代价结果159
总结161
说明161
练习162
问题162
17章 无憾动力学164
17.1 在线决策164
17.1.1 模型164
17.1.2 定义和示例165
17.2 乘性权重算法166
17.3 定理17.6的证明168
17.3.1 适应型对手与非适应型对手168
17.3.2 分析168
17.4 无憾与粗糙相关均衡170
17.4.1 无憾动力学170
17.4.2 收敛到粗糙相关均衡171
17.4.3 结束语171
总结172
说明172
练习173
问题173
18章 交换遗憾和小大化定理176
18.1 交换遗憾和相关均衡176
18.2 定理18.5的证明177
18.3 零和博弈的小大化定理180
18.3.1 两人零和博弈180
18.3.2小大化定理181
18.4 定理18.7的证明182
总结183
说明183
练习184
问题184
19章 纯策略纳什均衡和PLS完全性186
19.1 什么情况下均衡是计算可行的186
19.1.1 计算可行性回顾186
19.1.2 动力学和算法187
19.1.3 计算困难性的结论188
19.2 局部搜索问题188
19.2.1 经典示例：大割问题188
19.2.2 PLS：抽象局部搜索问题190
19.2.3 PLS完全性192
19.3 计算拥塞博弈的纯策略纳什均衡193
19.3.1 计算纯策略纳什均衡是PLS问题193
19.3.2 纯策略纳什均衡的计算是PLS完全问题194
19.3.3 对称拥塞博弈195
总结196
说明197
练习197
问题198
20章 混合策略纳什均衡和PPAD完全性199
20.1 双矩阵博弈的混合策略纳什均衡的计算199
20.2 全NP搜索问题200
20.2.1 NP搜索问题200
20.2.2 具有证据的NP搜索问题201
20.2.3 语法的复杂度集与语义的复杂度集202
20.2.4 我们该做什么203
20.3 PPAD：TFNP的一个语法子集204
20.4 经典的PPAD问题实例：Sperner引理205
20.5 混合策略纳什均衡和PPAD206
20.5.1 Sperner引理和纳什定理207
20.5.2 Lemke-Howson算法208
20.5.3 结语208
20.6 讨论209
总结209
说明209
练习210
问题211
10个重要的知识点213
部分练习及问题提示215
参考文献220

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