博弈論與機制設計

博弈論已涉足計算機科學和電子工程學科的很多新興應用領域。目前已有一些關於博弈論的優秀教材，但將非合作博弈、合作博弈以及機制設計同時呈現的教材並不多見，而這正是本書的最大特色。

首先，本書主要針對工程科學領域的讀者，同時也強調基於應用的計算機科學。其次，本書納入了機制設計板塊，而大多數教材著重介紹博弈論。本書分為三個部分: 非合作博弈論（第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