斯坦福算法博弈論二十講

出版者的話
譯者序
前言
第1章　簡(jiǎn)介和實(shí)例1
　1.1　關(guān)于規(guī)則制定的科學(xué)1
　1.2　自私的行為在什么時(shí)候是近似最優(yōu)的3
　　1.2.1　布雷斯悖論3
　　1.2.2　線與彈簧4
　1.3　策略型參與者能通過(guò)學(xué)習(xí)算出一個(gè)均衡嗎4
　總結(jié)6
　說(shuō)明6
　練習(xí)6
　問(wèn)題7
第2章　機(jī)制設(shè)計(jì)基礎(chǔ)8
　2.1　單物品拍賣8
　2.2　密封價(jià)格拍賣9
　2.3　一價(jià)拍賣9
　2.4　二價(jià)拍賣和占優(yōu)策略9
　2.5　理想化拍賣11
　2.6　經(jīng)典案例：關(guān)鍵字搜索拍賣12
　　2.6.1　背景知識(shí)12
　　2.6.2　關(guān)鍵字搜索拍賣的基本模型12
　　2.6.3　我們想要什么13
　　2.6.4　我們的設(shè)計(jì)方法13
　總結(jié)14
　說(shuō)明14
　練習(xí)14
　問(wèn)題16
第3章　邁爾森引理17
　3.1　單參數(shù)環(huán)境17
　3.2　分配規(guī)則和支付規(guī)則18
　3.3　邁爾森引理的內(nèi)容19
　3.4　邁爾森引理的證明20
　3.5　支付公式的運(yùn)用23
　總結(jié)24
　說(shuō)明25
　練習(xí)25
　問(wèn)題25
第4章　算法機(jī)制設(shè)計(jì)28
　4.1　背包拍賣28
　　4.1.1　問(wèn)題定義28
　　4.1.2　福利最大化的DSIC背包拍賣29
　　4.1.3　關(guān)鍵報(bào)價(jià)29
　　4.1.4　福利最大化的計(jì)算困難性29
　4.2　算法機(jī)制設(shè)計(jì)30
　　4.2.1　最好的情況：免費(fèi)的DSIC30
　　4.2.2　再談背包拍賣31
　4.3　顯示原理33
　　4.3.1　再談DSIC33
　　4.3.2　直接顯示的證明33
　　4.3.3　在占優(yōu)策略均衡之外34
　總結(jié)34
　說(shuō)明35
　練習(xí)35
　問(wèn)題36
第5章　收益最大化拍賣39
　5.1　收益最大化的挑戰(zhàn)39
　　5.1.1　我們被社會(huì)福利最大化“寵壞”了39
　　5.1.2　單競(jìng)拍者和單物品40
　　5.1.3　貝葉斯分析40
　　5.1.4　再談單競(jìng)拍者和單物品41
　　5.1.5　多競(jìng)拍者41
　5.2　最優(yōu)DSIC機(jī)制的性質(zhì)42
　　5.2.1　準(zhǔn)備工作42
　　5.2.2　虛擬估值42
　　5.2.3　期望收益等于期望虛擬福利43
　　5.2.4　最大化期望虛擬福利44
　　5.2.5　正則分布44
　　5.2.6　最優(yōu)單物品拍賣45
　5.3　案例分析：關(guān)鍵字搜索拍賣中的保留價(jià)格46
　5.4　引理5.1的證明47
　總結(jié)48
　說(shuō)明49
　練習(xí)49
　問(wèn)題50
第6章　簡(jiǎn)單的近似最優(yōu)拍賣52
　6.1　最優(yōu)拍賣可能很復(fù)雜52
　6.2　預(yù)知不等式53
　6.3　簡(jiǎn)單的單物品拍賣54
　6.4　先驗(yàn)獨(dú)立機(jī)制56
　總結(jié)57
　說(shuō)明58
　練習(xí)58
　問(wèn)題59
第7章　多參數(shù)機(jī)制設(shè)計(jì)61
　7.1　一般化的機(jī)制設(shè)計(jì)環(huán)境61
　7.2　VCG機(jī)制62
　7.3　實(shí)際的考量64
　總結(jié)65
　說(shuō)明65
　練習(xí)65
　問(wèn)題66
第8章　頻譜拍賣68
　8.1　非直接機(jī)制68
　8.2　分開拍賣多個(gè)物品69
　8.3　案例分析：同時(shí)升價(jià)拍賣70
　　8.3.1　兩個(gè)新手常見錯(cuò)誤70
　　8.3.2　同時(shí)升價(jià)拍賣的優(yōu)點(diǎn)71
　　8.3.3　需求縮減和披露問(wèn)題72
　　8.3.4　發(fā)送競(jìng)價(jià)信號(hào)73
　8.4　組合競(jìng)價(jià)74
　8.5　案例分析：2016年FCC激勵(lì)拍賣74
　總結(jié)77
　說(shuō)明77
　練習(xí)77
　問(wèn)題78
第9章　含支付約束的機(jī)制設(shè)計(jì)80
　9.1　預(yù)算約束80
　9.2　同一價(jià)格多單位拍賣81
　　9.2.1　多單位拍賣81
　　9.2.2　同一價(jià)格拍賣81
　　9.2.3　同一價(jià)格拍賣不是DSIC的82
　9.3　鎖定拍賣82
　9.4　不含錢機(jī)制設(shè)計(jì)85
　總結(jié)87
　說(shuō)明88
　練習(xí)88
　問(wèn)題89
第10章　腎臟交換和穩(wěn)定匹配91
　10.1　案例分析：腎臟交換91
　　10.1.1　背景91
　　10.1.2　使用TTC算法92
　　10.1.3　應(yīng)用匹配算法93
　　10.1.4　醫(yī)院方的動(dòng)機(jī)因素96
　10.2　穩(wěn)定匹配97
　　10.2.1　模型97
　　10.2.2　延遲接受算法98
　10.3　更多的性質(zhì)99
　總結(jié)101
　說(shuō)明101
　練習(xí)102
　問(wèn)題102
第11章　自私路由與無(wú)秩序代價(jià)103
　11.1　自私路由103
　　11.1.1　布雷斯悖論103
　　11.1.2　Pigou示例104
　　11.1.3　Pigou示例：非線性變種104
　11.2　主要結(jié)論：非正式的表述105
　11.3　主要結(jié)論：正式的表述106
　11.4　技術(shù)準(zhǔn)備108
　11.5　定理11.2的證明109
　總結(jié)110
　說(shuō)明110
　練習(xí)111
　問(wèn)題111
第12章　超額配置和單元自私路由113
　12.1　案例分析：網(wǎng)絡(luò)超額配置113
　　12.1.1　超額配置的動(dòng)機(jī)113
　　12.1.2　超額配置網(wǎng)絡(luò)的POA界113
　12.2　資源增廣界115
　12.3　定理12.1的證明115
　12.4　單元自私路由116
　12.5　定理12.3的證明118
　總結(jié)119
　說(shuō)明120
　練習(xí)120
　問(wèn)題121
第13章　均衡：定義、示例和存在性123
　13.1　均衡概念的層級(jí)結(jié)構(gòu)123
　　13.1.1　代價(jià)最小化博弈124
　　13.1.2　純策略納什均衡124
　　13.1.3　混合策略納什均衡124
　　13.1.4　相關(guān)均衡125
　　13.1.5　粗糙相關(guān)均衡126
　　13.1.6　示例127
　13.2　純策略納什均衡的存在性127
　　13.2.1　均衡分流的存在性127
　　13.2.2　非單元均衡分流的唯一性128
　　13.2.3　擁塞博弈129
　13.3　勢(shì)博弈129
　總結(jié)129
　說(shuō)明130
　練習(xí)130
　問(wèn)題131
第14章　平滑博弈的魯棒無(wú)秩序代價(jià)界133
　14.1　POA界四階段式處理方法133
　14.2　選址博弈134
　　14.2.1　模型134
　　14.2.2　選址博弈的性質(zhì)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
　總結(jié)141
　說(shuō)明141
　練習(xí)142
　問(wèn)題142
第15章　最好情況和強(qiáng)納什均衡144
　15.1　網(wǎng)絡(luò)代價(jià)分?jǐn)偛┺?44
　　15.1.1　外部性144
　　15.1.2　模型144
　　15.1.3　示例：VHS還是Betamax145
　　15.1.4　示例：退出博弈146
　15.2　穩(wěn)定的代價(jià)147
　15.3　強(qiáng)納什均衡的POA148
　15.4　定理15.3的證明150
　總結(jié)151
　說(shuō)明152
　練習(xí)152
　問(wèn)題152
第16章　最優(yōu)反應(yīng)動(dòng)力學(xué)154
　16.1　勢(shì)博弈中的最優(yōu)反應(yīng)動(dòng)力學(xué)154
　16.2　自私路由博弈中的近似PNE156
　16.3　定理16.3的證明157
　16.4　平滑勢(shì)博弈中的低代價(jià)結(jié)果159
　總結(jié)161
　說(shuō)明161
　練習(xí)162
　問(wèn)題162
第17章　無(wú)憾動(dòng)力學(xué)164
　17.1　在線決策164
　　17.1.1　模型164
　　17.1.2　定義和示例165
　17.2　乘性權(quán)重算法166
　17.3　定理17.6的證明168
　　17.3.1　適應(yīng)型對(duì)手與非適應(yīng)型對(duì)手168
　　17.3.2　分析168
　17.4　無(wú)憾與粗糙相關(guān)均衡170
　　17.4.1　無(wú)憾動(dòng)力學(xué)170
　　17.4.2　收斂到粗糙相關(guān)均衡171
　　17.4.3　結(jié)束語(yǔ)171
　總結(jié)172
　說(shuō)明172
　練習(xí)173
　問(wèn)題173
第18章　交換遺憾和最小最大化定理176
　18.1　交換遺憾和相關(guān)均衡176
　18.2　定理18.5的證明177
　18.3　零和博弈的最小最大化定理180
　　18.3.1　兩人零和博弈180
　　18.3.2　最小最大化定理181
　18.4　定理18.7的證明182
　總結(jié)183
　說(shuō)明183
　練習(xí)184
　問(wèn)題184
第19章　純策略納什均衡和PLS完全性186
　19.1　什么情況下均衡是計(jì)算可行的186
　　19.1.1　計(jì)算可行性回顧186
　　19.1.2　動(dòng)力學(xué)和算法187
　　19.1.3　計(jì)算困難性的結(jié)論188
　19.2　局部搜索問(wèn)題188
　　19.2.1　經(jīng)典示例：最大割問(wèn)題188
　　19.2.2　PLS：抽象局部搜索問(wèn)題190
　　19.2.3　PLS完全性192
　19.3　計(jì)算擁塞博弈的純策略納什均衡193
　　19.3.1　計(jì)算純策略納什均衡是PLS問(wèn)題193
　　19.3.2　純策略納什均衡的計(jì)算是PLS完全問(wèn)題194
　　19.3.3　對(duì)稱擁塞博弈195
　總結(jié)196
　說(shuō)明197
　練習(xí)197
　問(wèn)題198
第20章　混合策略納什均衡和PPAD完全性199
　20.1　雙矩陣博弈的混合策略納什均衡的計(jì)算199
　20.2　全NP搜索問(wèn)題200
　　20.2.1　NP搜索問(wèn)題200
　　20.2.2　具有證據(jù)的NP搜索問(wèn)題201
　　20.2.3　語(yǔ)法的復(fù)雜度集與語(yǔ)義的復(fù)雜度集202
　　20.2.4　我們?cè)撟鍪裁?03
　20.3　PPAD：TFNP的一個(gè)語(yǔ)法子集204
　20.4　經(jīng)典的PPAD問(wèn)題實(shí)例：Sperner引理205
　20.5　混合策略納什均衡和PPAD206
　　20.5.1　Sperner引理和納什定理207
　　20.5.2　Lemke-Howson算法208
　　20.5.3　結(jié)語(yǔ)208
　20.6　討論209
　總結(jié)209
　說(shuō)明209
　練習(xí)210
　問(wèn)題211
10個(gè)最重要的知識(shí)點(diǎn)213
部分練習(xí)及問(wèn)題提示215
參考文獻(xiàn)220