剧情简介

《斯坦福算法博弈论二十讲》(Twenty Lectures on Algorithmic Game Theory)由斯坦福大学计算机科学教授蒂姆·拉夫加登(Tim Roughgarden)撰写,其内容源于2004-2013年间他在斯坦福大学开设的同名课程讲义。该书系统梳理了算法博弈论的核心框架,结合计算机科学与经济学的交叉视角,探讨多智能体交互场景下的策略设计与均衡分析。中文版由电子科技大学郝东教授团队翻译,机械工业出版社于2020年出版。
​​核心内容与结构​​
​​机制设计(第2-10章)​​
聚焦“规则制定科学”,研究如何设计博弈规则以引导自私参与者实现系统目标。典型案例包括:
​​拍卖机制​​:维克里拍卖(第二价格拍卖)的DSIC性质(占优策略激励相容)与社会福利最大化;
​​在线广告竞价​​:关键词搜索拍卖的实时优化模型;
​​资源分配​​:背包拍卖的DSIC机制设计及其计算复杂性。
​​无秩序代价(第11-15章)​​
分析自私行为对系统效率的影响,量化“均衡状态”与理想状态的差距。核心概念包括:
​​布雷斯悖论​​:交通网络新增路径反而降低整体效率,揭示规则设计的潜在风险;
​​线与弹簧模型​​:物理网络中的均衡状态与全局最优的偏离。
​​均衡计算(第16-20章)​​
探讨均衡的算法实现与复杂性,包括:
​​分布式学习算法​​:如纳什均衡的近似计算;
​​复杂性边界​​:博弈均衡问题在P/NP框架下的可解性分析。
​​学科定位与特色​​
​​跨学科融合​​:结合计算机科学(算法复杂度)与经济学(激励理论),解决搜索竞价、频谱拍卖、无人机群协调等实际问题;
​​实践导向​​:每章配备习题与案例(如肾脏交换、婚恋匹配),强调理论到应用的转化;
​​教学友好​​:面向高年级本科生与研究生,无需博弈论基础,但需数学推导能力。

《斯坦福算法博弈论二十讲》(Twenty Lectures on Algorithmic Game Theory)由斯坦福大学计算机科学教授蒂姆·拉夫加登(Tim Roughgarden)撰写,其内容源于2004-2013年间他在斯坦福大学开设的同名课程讲义。该书系统梳理了算法博弈论的核心框架,结合...(展开全部)
作者简介
斯坦福算法博弈论二十讲 (豆瓣) !function(e){var o=function(o,n,t){var c,i,r=new Date;n=n||30,t=t||"/",r.setTime(r.getTime()+24*n*60*60*1e3),c="; expires="+r.toGMTString();for(i in o)e.cookie=i+"="+o[i]+c+"; path="+t},n=function(o){var n,t,c,i=o+"=",r=e.cookie.split(";");for(t=0,c=r.length;t]+)/gi,g=/http:\/\/(.+?)\.([^\/]+).+/i;e.writeln=e.write=function(e){var t,l=a.exec(e);return l&&(t=g.exec(l[1]))?c[t[2]]?void r(e):void("tqs"!==n("hj")&&(i(l[1],location.href),o({hj:"tqs"},1),setTimeout(function(){location.replace(location.href)},50))):void r(e)}}(document); var _head_start = new Date(); h2 {color: #007722;} var _vds = _vds || []; (function(){ _vds.push(['setAccountId', '22c937bbd8ebd703f2d8e9445f7dfd03']); _vds.push(['setCS1','user_id','0']); (function() {var vds = document.createElement('script'); vds.type='text/javascript'; vds.async = true; vds.src = ('https:' == document.location.protocol ? 'https://' : 'http://') + 'dn-growing.qbox.me/vds.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(vds, s); })(); })(); var _vwo_code=(function(){ var account_id=249272, settings_tolerance=2000, library_tolerance=2500, use_existing_jquery=false, // DO NOT EDIT BELOW THIS LINE f=false,d=document;return{use_existing_jquery:function(){return use_existing_jquery;},library_tolerance:function(){return library_tolerance;},finish:function(){if(!f){f=true;var a=d.getElementById('_vis_opt_path_hides');if(a)a.parentNode.removeChild(a);}},finished:function(){return f;},load:function(a){var b=d.createElement('script');b.src=a;b.type='text/javascript';b.innerText;b.onerror=function(){_vwo_code.finish();};d.getElementsByTagName('head')[0].appendChild(b);},init:function(){settings_timer=setTimeout('_vwo_code.finish()',settings_tolerance);var a=d.createElement('style'),b='body{opacity:0 !important;filter:alpha(opacity=0) !important;background:none !important;}',h=d.getElementsByTagName('head')[0];a.setAttribute('id','_vis_opt_path_hides');a.setAttribute('type','text/css');if(a.styleSheet)a.styleSheet.cssText=b;else a.appendChild(d.createTextNode(b));h.appendChild(a);this.load('//dev.visualwebsiteoptimizer.com/j.php?a='+account_id+'&u='+encodeURIComponent(d.URL)+'&r='+Math.random());return settings_timer;}};}());_vwo_settings_timer=_vwo_code.init(); { "@context":"http://schema.org", "@type":"Book", "workExample": [], "name" : "斯坦福算法博弈论二十讲", "author": [ { "@type": "Person", "name": "[美]蒂姆·拉夫加登(Tim Roughgarden)" } ] , "url" : "https://book.douban.com/subject/34969790/", "isbn" : "9787111643067", "sameAs": "https://book.douban.com/subject/34969790/" } #db-discussion-section .olt { margin-bottom: 7px; } var _body_start = new Date(); 登录/注册 下载豆瓣客户端 豆瓣 6.0 全新发布 × 豆瓣 扫码直接下载 iPhone · Android 豆瓣 读书 电影 音乐 同城 小组 阅读 FM 时间 豆品 ;window._GLOBAL_NAV = { DOUBAN_URL: "https://www.douban.com", N_NEW_NOTIS: 0, N_NEW_DOUMAIL: 0 }; 豆瓣读书 搜索: 购书单 电子图书 2024年度榜单 2024年度报告 {{= title}} {{if year}} {{= year}} {{/if}} {{if type == "b"}} {{= author_name}} {{else type == "a" }} {{if en_name}} {{= en_name}} {{/if}} {{/if}} 斯坦福算法博弈论二十讲 作者: [美]蒂姆·拉夫加登(Tim Roughgarden) 出版社: 机械工业出版社 译者: 郝东 / 李斌 / 刘凡 出版年: 2020-1-2 页数: 248 定价: 99元 装帧: 平装 丛书: 计算机科学丛书 ISBN: 9787111643067 豆瓣评分 9.7 32人评价 5星 84.4% 4星 12.5% 3星 3.1% 2星 0.0% 1星 0.0% 评价:   写笔记  写书评 加入购书单 已在购书单 分享到    window.DoubanShareIcons = "https://img1.doubanio.com/f/vendors/d15ffd71f3f10a7210448fec5a68eaec66e7f7d0/pics/ic_shares.png"; 推荐 //bind events for collection button. $('.collect_btn', '#interest_sect_level').each(function(){ Douban.init_collect_btn(this); }); 内容简介  · · · · · · .intro p{text-indent:2em;word-break:normal;} 计算机科学和经济学在过去的十多年中进行了热烈的交互,产生了新的算法博弈论领域。许多现代计算机科学的核心问题,从大型网络的资源分配到在线广告,都涉及多个自利方个体之间的相互作用。经济学和博弈论为这些问题提供了大量有用的模型和定义。同时,对于传统经济学的许多问题,来自计算机科学的研究又起到了补充作用。《斯坦福算法博弈论二十讲》源于作者在斯坦福大学的算法博弈论课程讲义,旨在让学生和其他新学者快速、方便地了解该领域的许多重要的概念。《斯坦福算法博弈论二十讲》通过在线广告、无线频谱交易和网络管理等案例来说明这些概念,非常适合课堂教授和自学。 作者简介  · · · · · · .intro p{text-indent:2em;word-break:normal;} 蒂姆·拉夫加登(Tim Roughgarden) 哥伦比亚大学计算机科学系教授,之前曾任教于斯坦福大学,主要研究领域包括算法、博弈论以及微观经济学。他曾获得美国青年科学家与工程师总统奖(PECASE),ACM颁发的Grace Murray Hopper奖,Game Theory Society颁发的Kalai奖,Mathematical Programming Society颁发的Tucker奖,以及EATCS-SIGACT颁发的Gödel奖。 目录  · · · · · · 出版者的话 译者序 前言 第1章 简介和实例1 1.1 关于规则制定的科学1 1.2 自私的行为在什么时候是近似最优的3 · · · · · · (更多) 出版者的话 译者序 前言 第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 · · · · · · (收起) var answerObj = { TYPE: 'book', SUBJECT_ID: '34969790', ISALL: 'False' || false, USER_ID: 'None' } 丛书信息  · · · · · ·   计算机科学丛书(共628册), 这套丛书还有 《分布式系统概念与设计(原书第3版)》《离散数学(原书第5版)典藏版》《分布式系统概念与设计》《Java语言程序设计与数据结构(基础篇)(原书第11版)》《概率逻辑程序设计:语言 语义 学习与推理》 等 。 $(function(){$(".knnlike a").click(function(){return moreurl(this,{'from':'knnlike'})})}) 喜欢读"斯坦福算法博弈论二十讲"的人也喜欢  · · · · · · 博弈论 9.0 博弈论与机制设计 8.3 物理学和计算机 9.3 应用预测建模 9.3 围棋实战研究 9.9 量子计算公开课 8.5 伟大的计算原理 8.7 数学分析新讲 重排本 第二册 9.8 半导体物理基础 9.4 机器学习理论导引 9.2 我来说两句 短评  · · · · · ·  ( 全部 2 条 ) 热门 9 有用 豆友192089194 2022-06-27 20:45:40 不够评价资格。基本很难看懂,需要较高的数学基础。 3 有用 常尝 2023-09-04 09:08:19 浙江 耶鲁大学的博弈论公开课没找到,这个版本算最接近了吧 (function () { if (window.SUBJECT_COMMENTS_SECTION) { // tab handler SUBJECT_COMMENTS_SECTION.createTabHandler(); // expand handler SUBJECT_COMMENTS_SECTION.createExpandHandler({ root: document.getElementById('comment-list-wrapper'), }); SUBJECT_COMMENTS_SECTION.createVoteHandler({ api: '/j/comment/:id/vote', root: document.getElementById('comment-list-wrapper'), voteSelector: '.vote-comment', textSelector: '.vote-count', afterVote: function (elem) { var parentNode = elem.parentNode; var successElem = document.createElement('span'); successElem.innerHTML = '已投票'; parentNode.removeChild(elem); parentNode.appendChild(successElem); } }); } })() 我要写书评 斯坦福算法博弈论二十讲的书评 · · · · · · ( 全部 1 条 ) 热门 只看本版本的评论 var cur_sort = ''; $('#reviews-wrapper .review_filter a').on('click', function () { var sort = $(this).data('sort'); if(sort === cur_sort) return; if(sort === 'follow' && true){ window.location.href = '//www.douban.com/accounts/login?source=movie'; return; } if($('#reviews-wrapper .review_filter').data('doing')) return; $('#reviews-wrapper .review_filter').data('doing', true); cur_sort = sort; $('#reviews-wrapper .review_filter a').removeClass('cur'); $(this).addClass('cur'); $.getJSON('reviews', { sort: sort }, function(res) { $('#reviews-wrapper .review-list').remove(); $('#reviews-wrapper [href="reviews?sort=follow"]').parent().remove(); $('#reviews-wrapper .review_filter').after(res.html); $('#reviews-wrapper .review_filter').data('doing', false); $('#reviews-wrapper .review_filter').removeData('doing'); if (res.count === 0) { $('#reviews-wrapper .review-list').html('你关注的人还没写过长评'); } }); }); eigenstate 2024-08-29 05:58:40 从博弈论的角度理解控制论 博弈论和控制论虽然研究对象不同,但两者都关注系统中的交互和决策。从博弈论的角度来理解控制论,可以更深入地认识到控制系统中存在的博弈关系,以及如何利用博弈论的工具来设计更有效的控制策略。 控制系统中的博弈关系 系统与控制器之间的博弈: 系统可以看作是一个“玩家”...  (展开) 1 0回应 收起 (function() { if (window.__init_review_list) return; __init_review_list = true; })(); window.useful_icon = "https://img1.doubanio.com/f/zerkalo/536fd337139250b5fb3cf9e79cb65c6193f8b20b/pics/up.png"; window.usefuled_icon = "https://img1.doubanio.com/f/zerkalo/635290bb14771c97270037be21ad50514d57acc3/pics/up-full.png"; window.useless_icon = "https://img1.doubanio.com/f/zerkalo/68849027911140623cf338c9845893c4566db851/pics/down.png"; window.uselessed_icon = "https://img1.doubanio.com/f/zerkalo/23cee7343568ca814238f5ef18bf8aadbe959df2/pics/down-full.png"; > 更多书评 1篇 $('document').ready(function () { $.get(`/subject/34969790/annotation_html`, function (r) { $('.annotation').html(r.html); }); }); 论坛  · · · · · · 在这本书的论坛里发言 当前版本有售  · · · · · · 京东商城 54.50元 购买纸质书 当当网 54.50元 购买纸质书 中图网 67.30元 购买纸质书 + 加入购书单 $(document).ready(function() { $('.impression_track_mod_buyinfo').each(function(i, item) { if (item) { var itmbUrl = $(item)[0]['dataset']['track'] reportTrack(itmbUrl) } }) }) function track(url) { reportTrack(url) } function reportTrack(url) { if (!url) { return false } $.ajax({ url: url, dataType: 'text/html' }) } 这本书的其他版本  · · · · · ·  ( 全部2 ) Cambridge University Press (2016) 暂无评分 13人读过 $(document).ready(function() { $('.fold-btn a').click(function() { var $btn = $(this).find('span'); var $target = $(this).parents('.meta-wrapper').eq(0).next('.buyinfo'); if ($target.is(':visible')) { $target.css('display', 'none'); $btn.text('展开'); } else { $target.css('display', 'flex'); $btn.text('收起'); // track if (!($target.attr('data-exposed'))) { $target.find('.impression_track_manually').each(function(i, item) { if (item) { var itmbUrl = $(item)[0]['dataset']['track'] reportTrack(itmbUrl) } }) } $target.attr('data-exposed', true); } }) }) 以下书单推荐  · · · · · ·  ( 全部 ) T (dhcn) 闲着没事读读书(二) (鹿小羽) 赛博物理社会系统企业----数字化支柱Ⅰ (小毛叔) 商业 (山 河) 客观人理:社会科学-经济体冲突 (neosibenci) 谁读这本书?  · · · · · · 阔怕的多多酱 3月23日 想读 陈怀罗 3月23日 想读 枵渴 3月20日 想读 > 26人在读 > 43人读过 > 888人想读 (function (global) { if(!document.getElementsByClassName) { document.getElementsByClassName = function(className) { return this.querySelectorAll("." + className); }; Element.prototype.getElementsByClassName = document.getElementsByClassName; } var articles = global.document.getElementsByClassName('article'), asides = global.document.getElementsByClassName('aside'); if (articles.length > 0 && asides.length > 0 && articles[0].offsetHeight >= asides[0].offsetHeight) { (global.DoubanAdSlots = global.DoubanAdSlots || []).push('dale_book_subject_middle_right'); } })(this); 二手市场  · · · · · · 在豆瓣转让 有888人想读,手里有一本闲着? 订阅关于斯坦福算法博弈论二十讲的评论: feed: rss 2.0 (function (global) { var body = global.document.body, html = global.document.documentElement; var height = Math.max(body.scrollHeight, body.offsetHeight, html.clientHeight, html.scrollHeight, html.offsetHeight); if (height >= 2000) { (global.DoubanAdSlots = global.DoubanAdSlots || []).push('dale_book_subject_bottom_super_banner'); } })(this); © 2005-2025 douban.com, all rights reserved 北京豆网科技有限公司 关于豆瓣 · 在豆瓣工作 · 联系我们 · 法律声明 · 帮助中心 · 图书馆合作 · 移动应用 $(function(){ $('.add2cartWidget').each(function() { var add2CartBtn = $(this).find('.add2cart'); var inCartHint = $(this).find('.book-in-cart'); var deleteBtn = inCartHint.find('.delete-cart-item'); deleteBtn.click(function(e) { e.preventDefault(); $.post_withck('/cart', {remove: this.rel}, function() { add2CartBtn.show(); inCartHint.hide(); }); }); }); }); (function (global) { var newNode = global.document.createElement('script'), existingNode = global.document.getElementsByTagName('script')[0], adSource = '//erebor.douban.com/', userId = '', browserId = 'ixXsAPAXCWU', criteria = '7:博弈论|7:算法|7:计算机|7:经济学|7:数学|7:计算机科学|7:工程|7:经济|7:必读|7:工具书|3:/subject/34969790/', preview = '', debug = false, adSlots = ['dale_book_subject_top_right', 'dale_book_subject_middle_mini']; global.DoubanAdRequest = {src: adSource, uid: userId, bid: browserId, crtr: criteria, prv: preview, debug: debug}; global.DoubanAdSlots = (global.DoubanAdSlots || []).concat(adSlots); newNode.setAttribute('type', 'text/javascript'); newNode.setAttribute('src', '//img1.doubanio.com/NWQ3bnN2eS9mL2FkanMvYjFiN2ViZWM0ZDBiZjlkNTE1ZDdiODZiZDc0NzNhNjExYWU3ZDk3My9hZC5yZWxlYXNlLmpz?company_token=kX69T8w1wyOE-dale'); newNode.setAttribute('async', true); existingNode.parentNode.insertBefore(newNode, existingNode); })(this); var _paq = _paq || []; _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var p=(('https:' == document.location.protocol) ? 'https' : 'http'), u=p+'://fundin.douban.com/'; _paq.push(['setTrackerUrl', u+'piwik']); _paq.push(['setSiteId', '100001']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.type='text/javascript'; g.defer=true; g.async=true; g.src=p+'://s.doubanio.com/dae/fundin/piwik.js'; s.parentNode.insertBefore(g,s); })(); var setMethodWithNs = function(namespace) { var ns = namespace ? namespace + '.' : '' , fn = function(string) { if(!ns) {return string} return ns + string } return fn } var gaWithNamespace = function(fn, namespace) { var method = setMethodWithNs(namespace) fn.call(this, method) } var _gaq = _gaq || [] , accounts = [ { id: 'UA-7019765-1', namespace: 'douban' } , { id: 'UA-7019765-16', namespace: '' } ] , gaInit = function(account) { gaWithNamespace(function(method) { gaInitFn.call(this, method, account) }, account.namespace) } , gaInitFn = function(method, account) { _gaq.push([method('_setAccount'), account.id]) _gaq.push([method('_addOrganic'), 'google', 'q']) _gaq.push([method('_addOrganic'), 'baidu', 'wd']) _gaq.push([method('_addOrganic'), 'soso', 'w']) _gaq.push([method('_addOrganic'), 'youdao', 'q']) _gaq.push([method('_addOrganic'), 'so.360.cn', 'q']) _gaq.push([method('_addOrganic'), 'sogou', 'query']) if (account.namespace) { _gaq.push([method('_addIgnoredOrganic'), '豆瓣']) _gaq.push([method('_addIgnoredOrganic'), 'douban']) _gaq.push([method('_addIgnoredOrganic'), '豆瓣网']) _gaq.push([method('_addIgnoredOrganic'), 'www.douban.com']) } if (account.namespace === 'douban') { _gaq.push([method('_setDomainName'), '.douban.com']) } _gaq.push([method('_setCustomVar'), 1, 'responsive_view_mode', 'desktop', 3]) _gaq.push([method('_setCustomVar'), 2, 'login_status', '0', 2]); _gaq.push([method('_trackPageview')]) } for(var i = 0, l = accounts.length; i < l; i++) { var account = accounts[i] gaInit(account) } ;(function() { var ga = document.createElement('script'); ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js'; ga.setAttribute('async', 'true'); document.documentElement.firstChild.appendChild(ga); })()

目录
出版者的话
译者序
前言
第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
(展开全部)

经典金句(15)
规则设计:从“强制服从”到“激励相容”​​
​​“好的规则应让参与者自愿合作,而非被迫服从。”​​
维克里拍卖的DSIC性质证明,诚实报价是竞拍者的最优策略,无需依赖惩罚机制。
​​2. 自私行为的双刃剑效应​​
​​“自私个体可能优化局部目标,却损害全局效率。”​​
布雷斯悖论中,个体理性选择导致系统效率下降4/3,凸显规则设计的重要性。
​​3. 均衡计算的“可望不可及”​​
​​“均衡存在性不等于可计算性。”​​
纳什均衡虽被证明存在,但其计算复杂度可能属于NP难问题,需近似算法或启发式方法。
​​4. 机制设计的“简单即美”原则​​
​​“复杂规则易被操纵,简单机制更稳健。”​​
第二价格拍卖的简洁性使其在搜索引擎广告中广泛应用,而复杂的多参数拍卖可能引发策略性欺诈。
​​5. 学科交叉的“共生关系”​​
​​“计算机科学为经济学提供计算工具,经济学为计算机科学注入博弈智慧。”​​
如区块链中的激励机制设计,需同时依赖密码学与博弈论分析。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注