博弈論與機制設(shè)計（博弈論與機制設(shè)計）

內(nèi)容簡介

博弈論已涉足計算機科學(xué)和電子工程學(xué)科的很多新興應(yīng)用領(lǐng)域。目前已有一些關(guān)于博弈論的優(yōu)秀教材，但將非合作博弈、合作博弈以及機制設(shè)計同時呈現(xiàn)的教材并不多見，而這正是本書的最大特色。

首先，本書主要針對工程科學(xué)領(lǐng)域的讀者，同時也強調(diào)基于應(yīng)用的計算機科學(xué)。其次，本書納入了機制設(shè)計板塊，而大多數(shù)教材著重介紹博弈論。本書分為三個部分: 非合作博弈論（第2～13章）、機制設(shè)計（第14～24章）、合作博弈論（第25～31章）。另外，下列三章相對獨立：第1章是導(dǎo)論，第32章是結(jié)束語，第33章給出了數(shù)學(xué)知識準(zhǔn)備。每一章都以動機和中心思想開篇，以小結(jié)和參考文獻(xiàn)收尾。每一章的小結(jié)主要列舉重要概念和知識點，參考文獻(xiàn)主要用于指引讀者進一步考察。每章結(jié)尾處都給出了一組習(xí)題，其中個別題目是編程題。

作者簡介

Y.內(nèi)拉哈里（Narahari）目前任教于印度科技學(xué)院計算機與自動化系。近十年來，他的研究重點是計算機科學(xué)與微觀經(jīng)濟交叉領(lǐng)域的問題。他尤其關(guān)注博弈論和機制設(shè)計在拍賣、電子商務(wù)、多智能體系統(tǒng)以及社會網(wǎng)絡(luò)中的應(yīng)用。在這些領(lǐng)域以及其他領(lǐng)域，內(nèi)拉哈里寫下了大量有影響的學(xué)術(shù)論文。他的很多學(xué)生獲得過最佳博士（碩士）論文獎。他是專著《網(wǎng)絡(luò)經(jīng)濟學(xué)中的博弈論問題與機制設(shè)計解》（Game Theoretic Problems in Network Economics and Mechanism Design Solutions， Springer，London，2009）的第一作者。他也是《自動化制造系統(tǒng)的績效模擬》（Performance Modeling of Automa- ted Manufacturing Systems，Prentice Hall， USA，1992）這本廣受好評的著作的共同作者。Y.內(nèi)拉哈里的工作得到了很多學(xué)會的認(rèn)可，也獲得了多項科研基金贊助。

章節(jié)目錄

第1章 引言與概覽 1 　　1.1 博弈論：策略互動科學(xué) 1 　　1.2 當(dāng)前趨勢和現(xiàn)代應(yīng)用 6 　　1.3 本書結(jié)構(gòu) 11 　　第1部分 非合作博弈論 　　第2章 博弈論中的重要概念 17 　　2.1 策略型博弈 17 　　2.2 偏好 18 　　2.3 效用 19 　　2.4 理性 19 　　2.5 智能 21 　　2.6 博弈分類 23 　　2.7 小結(jié)與參考文獻(xiàn) 24 　　第3章 展開型博弈 27 　　3.1 例子 27 　　3.2 展開型博弈：定義 29 　　3.3 將展開型博弈轉(zhuǎn)換為策略型博弈 32 　　3.4 小結(jié)與參考文獻(xiàn) 34 　　3.5 習(xí)題 35 　　第4章 策略型博弈 37 　　4.1 基本知識 37 　　4.2 同時行動情形下的硬幣配對 38 　　4.3 石頭剪刀布 39 　　4.4 BOS博弈 39 　　4.5 協(xié)作博弈 40 　　4.6 囚徒困境博弈 40 　　4.7 公司兩難博弈 41 　　4.8 公司兩難博弈：非對稱版本 42 　　4.9 雙寡頭定價博弈 42 　　4.10 公地悲劇 43 　　4.11 帶寬共享博弈 43 　　4.12 密封拍賣 44 　　4.13 庇古網(wǎng)絡(luò)博弈 44 　　4.14 布雷斯悖論博弈 46 　　4.15 小結(jié)與參考文獻(xiàn) 47 　　4.16 習(xí)題 49 　　第5章 優(yōu)勢策略均衡 50 　　5.1 強優(yōu)（劣）勢 50 　　5.2 弱優(yōu)（劣）勢 51 　　5.3 極弱優(yōu)（劣）勢 52 　　5.4 優(yōu)勢策略均衡的例子 52 　　5.5 小結(jié)與參考文獻(xiàn) 55 　　5.6 習(xí)題 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 小結(jié)與參考文獻(xiàn) 73 　　6.9 習(xí)題 75 　　第7章 混合策略與混合策略納什均衡 79 　　7.1 混合策略 79 　　7.2 混合策略納什均衡 81 　　7.3 混合策略的性質(zhì) 82 　　7.4 策略組成為混合策略納什均衡的必要充分條件 84 　　7.5 混合策略中的最大最小值與最小最大值 89 　　7.6 混合策略中的優(yōu)（劣）勢 90 　　7.7 小結(jié)與參考文獻(xiàn) 93 　　7.8 習(xí)題 95 　　第8章 效用理論 99 　　8.1 為何需要效用理論 99 　　8.2 馮·諾依曼-摩根斯坦效用理論公理 101 　　8.3 馮·諾依曼-摩根斯坦定理 104 　　8.4 仿射變換 106 　　8.5 計算馮·諾依曼-摩根斯坦效用 107 　　8.6 參與人的風(fēng)險態(tài)度 108 　　8.7 小結(jié)與參考文獻(xiàn) 110 　　8.8 習(xí)題 111 　　第9章 矩陣博弈 112 　　9.1 矩陣博弈的例子 113 　　9.2 矩陣博弈中的純策略 114 　　9.3 鞍點與純策略納什均衡 115 　　9.4 矩陣博弈中的混合策略 117 　　9.5 最小最大定理 122 　　9.6 小結(jié)與參考文獻(xiàn) 124 　　9.7 習(xí)題 125 　　第10章 納什均衡的存在性 128 　　10.1 對應(yīng)以及不動點定理 129 　　10.2 納什均衡是不動點 130 　　10.3 純策略納什均衡存在性的充分條件 131 　　10.4 納什定理 133 　　10.5 施佩納引理 134 　　10.6 從施佩納引理到布勞威爾不動點定理 138 　　10.7 使用布勞威爾不動點定理證明納什定理 141 　　10.8 無限博弈的納什均衡存在性 143 　　10.9 小結(jié)與參考文獻(xiàn) 144 　　10.10 習(xí)題 145 　　第11章 納什均衡的計算 147 　　11.1 支撐與納什均衡 147 　　11.2 有限策略型博弈納什均衡的一般算法 148 　　11.3 計算納什均衡：一個例子 150 　　11.4 小結(jié)與參考文獻(xiàn) 154 　　11.5 習(xí)題 156 　　第12章 納什均衡計算的復(fù)雜性 158 　　12.1 納什問題與布勞威爾問題 158 　　12.2 PPAD類 159 　　12.3 納什問題是PPAD-complete問題 161 　　12.4 一些觀察 162 　　12.5 小結(jié)與參考文獻(xiàn) 163 　　第13章 貝葉斯博弈 165 　　13.1 伴隨不完全信息的博弈 165 　　13.2 貝葉斯博弈的例子 168 　　13.3 類型代理表示法與澤爾騰博弈 169 　　13.4 貝葉斯納什均衡 172 　　13.5 優(yōu)勢策略均衡 173 　　13.6 小結(jié)與參考文獻(xiàn) 175 　　13.7 習(xí)題 175 　　第2部分 機制設(shè)計 　　第14章 機制設(shè)計導(dǎo)論 179 　　14.1 機制設(shè)計：常見例子與歷史 179 　　14.2 機制設(shè)計環(huán)境 183 　　14.3 直接機制與間接機制 185 　　14.4 社會選擇函數(shù)的例子 186 　　14.5 小結(jié)與參考文獻(xiàn) 192 　　14.6 習(xí)題 193 　　第15章 通過機制實施社會選擇函數(shù) 194 　　15.1 通過直接機制實施社會選擇函數(shù) 194 　　15.2 通過間接機制實施社會選擇函數(shù) 198 　　15.3 機制誘導(dǎo)出的貝葉斯博弈 201 　　15.4 通過機制實施社會選擇函數(shù) 202 　　15.5 小結(jié)與參考文獻(xiàn) 204 　　15.6 習(xí)題 205 　　第16章 激勵相容與顯示原理 206 　　16.1 激勵相容 206 　　16.2 優(yōu)勢策略均衡的顯示原理 208 　　16.3 貝葉斯納什均衡的顯示原理 209 　　16.4 社會選擇函數(shù)的性質(zhì) 210 　　16.5 小結(jié)與參考文獻(xiàn) 212 　　16.6 習(xí)題 213 　　第17章 吉伯德-薩特思韋特不可能性定理 216 　　17.1 引言 216 　　17.2 吉伯德-薩特思韋特定理 218 　　17.3 吉伯德-薩特思韋特定理 221 　　17.4 阿羅不可能定理 225 　　17.5 小結(jié)與參考文獻(xiàn) 229 　　第18章 維克瑞-克拉克-格羅夫斯機制 231 　　18.1 擬線性環(huán)境 231 　　18.2 格羅夫斯機制 237 　　18.3 克拉克機制（關(guān)鍵人機制） 240 　　18.4 VCG機制的例子 240 　　18.5 小結(jié)與參考文獻(xiàn) 244 　　18.6 習(xí)題 245 　　第19章 擬線性環(huán)境中的機制設(shè)計空間 247 　　19.1 格羅夫斯機制與嚴(yán)格預(yù)算平衡 247 　　19.2 克拉克機制與弱預(yù)算平衡 248 　　19.3 個體理性 250 　　19.4 VCG機制與個體理性 251 　　19.5 dAGVA機制 253 　　19.6 擬線性環(huán)境中的機制設(shè)計空間 257 　　19.7 線性環(huán)境 258 　　19.8 小結(jié)與參考文獻(xiàn) 259 　　19.9 習(xí)題 260 　　第20章 拍賣 262 　　20.1 拍賣類型與合意性質(zhì) 262 　　20.2 經(jīng)典機制：一件不可分割的商品的拍賣 264 　　20.3 第一價格密封拍賣和第二價格密封拍賣的收入等價性 266 　　20.4 收入等價定理 268 　　20.5 組合拍賣 271 　　20.6 小結(jié)與參考文獻(xiàn) 273 　　20.7 習(xí)題 274 　　第21章 最優(yōu)機制與邁爾森拍賣 276 　　21.1 最優(yōu)機制 276 　　21.2 邁爾森最優(yōu)拍賣 277 　　21.3 有效率的最優(yōu)拍賣 282 　　21.4 小結(jié)與參考文獻(xiàn) 283 　　21.5 習(xí)題 284 　　第22章 贊助搜索拍賣的機制設(shè)計 285 　　22.1 贊助搜索拍賣 285 　　22.2 作為機制設(shè)計問題的贊助搜索拍賣 286 　　22.3 廣義第一價格（GFP）機制 289 　　22.4 廣義第二價格（GSP）機制 289 　　22.5 維克瑞克拉克格羅夫斯（VCG）機制 290 　　22.6 最優(yōu)（OPT）機制 292 　　22.7 小結(jié)與參考文獻(xiàn) 298 　　22.8 習(xí)題 299 　　第23章 在事后納什均衡中實施社會選擇函數(shù) 300 　　23.1 社會選擇函數(shù)的實施：多個均衡的情形 300 　　23.2 在納什均衡中實施社會選擇函數(shù) 301 　　23.3 社會選擇函數(shù)的可實施性：完全信息環(huán)境 304 　　23.4 小結(jié)與參考文獻(xiàn) 306 　　第24章 機制設(shè)計的其他議題 308 　　24.1 優(yōu)勢策略激勵相容的特征 308 　　24.2 BIC規(guī)則的優(yōu)勢策略實施 309 　　24.3 相互依賴的價值 309 　　24.4 其他形式的實施 310 　　24.5 當(dāng)前重要議題 310 　　24.6 機制設(shè)計中的計算議題 311 　　24.7 小結(jié)與參考文獻(xiàn) 311 　　第3部分 合作博弈論 　　第25章 相關(guān)策略與相關(guān)均衡 317 　　25.1 伴隨合同的博弈 318 　　25.2 相關(guān)策略 319 　　25.3 伴隨溝通的博弈 322 　　25.4 相關(guān)均衡 325 　　25.5 小結(jié)與參考文獻(xiàn) 327 　　25.6 習(xí)題 328 　　第26章 兩人議價問題 331 　　26.1 納什規(guī)劃 331 　　26.2 兩人議價問題 332 　　26.3 納什公理 334 　　26.4 納什議價解 336 　　26.5 納什議價定理的證明 338 　　26.6 平等主義解和效用主義解 342 　　26.7 小結(jié)與參考文獻(xiàn) 344 　　26.8 習(xí)題 345 　　第27章 伴隨可轉(zhuǎn)移效用的聯(lián)盟博弈 347 　　27.1 多人合作博弈 347 　　27.2 伴隨可轉(zhuǎn)移效用的博弈 350 　　27.3 伴隨特殊結(jié)構(gòu)的TU博弈 354 　　27.4 成本博弈 358 　　27.5 小結(jié)與參考文獻(xiàn) 358 　　27.6 習(xí)題 359 　　第28章 聯(lián)盟博弈的核 361 　　28.1 核：定義與例子 361 　　28.2 博弈何時有非空的核 366 　　28.3 凸博弈的核 369 　　28.4 成本博弈的核 370 　　28.5 小結(jié)與參考文獻(xiàn) 370 　　28.6 習(xí)題 372 　　第29章 夏普利值 374 　　29.1 夏普利公理 375 　　29.2 夏普利定理與例子 377 　　29.3 夏普利定理的證明 380 　　29.4 夏普利值的其他發(fā)展方法 383 　　29.5 凸博弈的夏普利值 384 　　29.6 夏普利舒比克權(quán)力指數(shù) 385 　　29.7 班茨哈夫指數(shù) 386 　　29.8 小結(jié)與參考文獻(xiàn) 387 　　29.9 習(xí)題 388 　　第30章 合作博弈論中的其他解概念 391 　　30.1 穩(wěn)定集 391 　　30.2 議價集 393 　　30.3 內(nèi)核 396 　　30.4 核仁 397 　　30.5 蓋特利點 398 　　30.6 小結(jié)與參考文獻(xiàn) 399 　　30.7 習(xí)題 401 　　第31章 穩(wěn)定匹配 402 　　31.1 匹配問題 402 　　31.2 匹配算法 403 　　31.3 市場匹配 407 　　31.4 小結(jié)與參考文獻(xiàn) 408 　　31.5 習(xí)題 408 　　第32章 結(jié)束語 　　410 32.1 本書目的 410 　　32.2 進一步探索 411 　　32.3 小結(jié)與參考文獻(xiàn) 412 　　第33章 數(shù)學(xué)知識準(zhǔn)備 414 　　33.1 概率論 414 　　33.2 線性代數(shù) 416 3 　　3.3 線性規(guī)劃與對偶 417 　　33.4 數(shù)學(xué)分析 419 　　33.5 計算復(fù)雜類 422 　　33.6 小結(jié)與參考文獻(xiàn) 424 　　索引 426