斯坦福算法博弈论二十讲 (美)蒂姆·拉夫加登(Tim Roughgarden) 著 郝东,李斌,刘凡 译 大中专 文轩网

出版者的话
译者序
前言
第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.2VCG机制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.2Pigou示例104
11.1.3Pigou示例：非线性变种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.1POA界四阶段式处理方法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.1PNE的POA界139
14.4.2CCE的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.2PLS：抽象局部搜索问题190
19.2.3PLS接近性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.1NP搜索问题200
20.2.2具有证据的NP搜索问题201
20.2.3语法的复杂度集与语义的复杂度集202
20.2.4我们该做什么203
20.3PPAD：TFNP的一个语法子集204
20.4经典的PPAD问题实例：Sperner引理205
20.5混合策略纳什均衡和PPAD206
20.5.1Sperner引理和纳什定理207
20.5.2Lemke-Howson算法208
20.5.3结语208
20.6讨论209
总结209
说明209
练习210
问题211
10个最重要的知识点213
部分练习及问题提示215
参考文献220