博弈论耶鲁大学公开课转.doc

博弈论_耶鲁公开课_笔记及扩展1.博弈（game theory）构成要素： 参与人players：i，j 策略集strategy set:Si 策略si s-i 最优战略si* 效益（目标）payoff：Ui Ui（s1，。si。sn） 博弈game：G=S1，S2.Sn；U1，U2.Un 2.博弈论简史 理论提出：1944 冯诺依曼（计算机之父 、博弈论之父）与摩根斯坦恩合作出版博弈论与经济行为 提出了博弈概念；提出了零和博弈（Zero-sum game）；引进了合作博弈 理论发展： a.奠定非合作博弈基石： 1950 Tucker 提出了“囚徒困境” ；1950-1951 纳什：引入纳什均衡，将博弈论从零和博弈推进到非零 和博弈；定义非合作博弈并证明纳什均衡存在；1994年诺贝尔经济学奖（与selten harsanyi共同拿到） b.1965-1975 泽尔腾Selten 将纳什均衡推广到动态博弈并提出子博弈精炼均衡；发展了倒退归纳分析方法；提出颤抖手均衡 c.1967-1968 海萨尼harsanyi将纳什均衡推广到非完全信息博弈并突出贝叶斯均衡3.博弈的分类 是否合作 合作博弈cooperative ganme 非合作博弈non-operative ganme 一般说博弈指后者 后者又分一下四类 根据：是否完全信息 是否同时进行 完全信息静态博弈 （囚徒困境prisons dilemma） 纳什均衡 Nash equilibrium 完全信息动态信息 （抢劫博弈） 子博弈精炼均衡subgame perfect Nash equilibrium 非完全信息静态博弈 （密封报价拍卖模型） 贝叶斯纳什均衡Bayesian Nash equilibrium 非完全信息动态博弈 （就业市场信号 黔驴技穷） 精炼贝叶斯纳什均衡perfect Bayesian Nash equilibrium 完全信息 complete information与完美信息perfect information 完全信息指每个参与者都知道其他人的可行策略以及收益（支付函数），如果一个博弈不是完全信息，那么参与者就不可能知道自己 的行为对其他博弈者的影响 完美信息指参与者对其他参与者行动action的完全知识的状态，并随信息的出现而更新。比如下象棋中你不可能知道对手下一手棋是 为了吃马还是吃兵或者其他的什么，但是你确确实实知道对手下了一手棋 4.严格劣策略strictly dominated strategy 弱劣策略 weakly dominated strategy 重复剔除严格劣策略iterative deletion -*共同知识common knowledge的重要性 霍特林Hotelling模型1929 中间选民原理middle voters theron 漏洞：条件多维度 选民非evenly distribute model的局限性：与现实状况的差距-其他因素对model的纠正完全信息静态博弈- a.基本分析方法（适用范围由小至大）： &1 上策（占优策略Dominant strategy）均衡 ：在某个博弈中，不管其他博弈者如何选择，一博弈方的策略带来的效益永远优于选择其 他策略的效益，至少不低于（如囚徒困境中选择坦白） &2 重复剔除严格劣策略 &3 划线法 寻找自己的最优策略集 寻找其他博弈者最优策略集 寻找交集 &4 箭头法 箭头指示提高自己效益的方向 综合分析箭头的走向决定最优策略 b.纳什均衡Nash Equilibrium （NE）：给定你的策略，我的策略是最好的策略；给定我的策略，你的策略也是你最好的策略。即双方在对方 给定的策略下不愿意调整自己的策略。 *纳什定理：在一个有n个博弈方的博弈G=S1,S2，Sn;U1,U2.Un中，如果n是有限的，且Si（i=1,2.。n）都是有限集，则该博 弈至少存在一个纳什均衡，但可能包含混合策略 *纳什均衡的意义在于其一致预测性即所有人都预测到某一博弈结果会出项，那么所有人都不会背离这个结果 *纳什均衡的存在性与多重性：任何有限博弈都存在至少一个（可能有多个）纳什均衡（有限博弈：博弈有有限个参与者且每一个参与者 都存在有限个纯战略） *纳什均衡双定理： 定理一：如果用重复剔除严格劣策略剔除了除（s1*，s2*。sn*）以外的策略组合 那么剩余的这个策略组合就是唯一的纳什 均衡 定理二：如果策略组合（s1*，s2*。sn*）是博弈G的纳什均衡，那么该策略组合不会被重复剔除严格劣策略所剔除 Max Ui（si，s-i） siSi 最佳策略best response 囚徒困境：个人理性与集体理性的矛盾；应用如下：古诺Cournot双头垄断模型（产量 1838） 公共财产模型（哈丁 1968） 军备竞赛 智猪博弈：多劳者不多得；应用如下：炒股 性别战 斗鸡博弈：夫妻间吵架 市场进入阻挠 贝特兰德Bertrand双头垄断模型（价格 1883） 最后要价仲裁模型 （法伯1982） c.混合战略Mixed Stratergies：参与人以一定概率选择某种策略 纯战略pure strategy：在完全信息博弈中，如果在每个给定信息下，只能选择一种特定策略 混合战略包含纯战略，纯战略属于混合战略的特例 #帕累托上策均衡Pareto Dominant Equilibrium：在某个博弈当中可能有多个纳什均衡，但这些均衡明显具有优劣差异，所有的博弈方都 倾向于同一个纳什均衡，即其中一个纳什均衡带来的效益优于其他均衡带来的效益（例 如两国交战模型中有两个纳什均衡（战争，战争）（和平，和平）后者明显优于前者） #风险上策均衡Risk Dominant Equilibrium：如果所有博弈方在预计其他博弈方采用各种策略的概率相同时，某一策略给他带来的期望得 益最大，各博弈方都偏爱这样的策略的策略组合（如猎鹿博弈stag-hunting） #聚点均衡Focal Points Equilibrium：在多重纳什均衡博弈中，所有博弈者同时选择一个聚点构成的纳什均衡（例如在双方报时间，如 果一致则获得奖金，不一致则无的博弈中，双方可能会选择一下两个聚点：12点或者0点，而聚点 的选择也是具体问题具体分析，如性格战博弈中如果男女双方都是暴利人士，可能会选择去看拳 击比赛作为聚点，如果是文艺青年或者为了追忆以前相恋一起看电影的时光会选择电影院作为聚 点） #相关均衡Correlated Equilibrium：在多重纳什均衡博弈中，博弈者主动寻求方法，采用一种均衡选择机制，以解决多重那还是呢均衡 的选择问题。该均衡满足以下条件：在纳什均衡中找；所有纳什均衡触发条件概率相同且不会同时 触发；触发条件的设立不会影响收益（例如性别战中，用明天下雨与否决定去看电影还是看拳击） #共谋和防共谋均衡Coalition and Coalition-proof Equilibrium：在多人（大于两人）博弈中，可能存在部分博弈者追逐小团体利益而 影响纳什均衡的稳定性，与之相对防共谋均衡是指，多人博弈中，任 意n（n=1,2,3.n）人的串通都不会改变博弈的结果完全信息动态博弈- 5.动态博弈Dynamic Games（序列博弈Sequential Games 多阶段博弈Multistage Games 扩展形博弈Extensive Form Games） 阶段Stage：动态博弈中，一个博弈者选择或者几个博弈者同时行动，然后别人再行动，这个选择或者同时行动构成一个阶段 扩展形、博弈树：从起点出发，通过选择节点表达博弈各种不同结果的图形或者树。简单的动态博弈都可以用树画出来，无法用树表示的通 常用文字描述或者函数来表达 动态博弈的特点：a，参与者的决策对博弈结果有关键作用，博弈者的一次并非最优策略往往是最终取得最优策略的关键；b，非对称性，一 般来说后来者往往有更多的信息，易于处于有利位置，但也有信息多得益少的情况。 可信性问题是动态博弈的一个中心问题。如抢劫模型中威胁的可信性决定了博弈的走向。子博弈精炼那什均衡能排除该影响博弈稳定的因素 逆推归纳法Backwards Induction：从动态博弈最后一个阶段博弈方的行动开始分析，逐步倒退回上一个阶段相应博弈方的行动选择，一直 到第一个阶段的分析方法 逆推归纳法的不足：a，虽然完全信息但是数据量太大 如象棋 b，参与者足够理性并且不会发生颤抖手 Rosenthal 1981 蜈蚣博弈 子博弈：由一个动态博弈第一阶段以外的某个阶段开始的后续博弈阶段构成的，有进行博弈的全部信息，能自成一个博弈的原博弈的一部分 称为原动态博弈的子博弈 二级子博弈 三级子博弈. 子博弈精炼纳什均衡：在一个完美信息的动态博弈中，由各博弈方的策略构成的策略组合，在整个博弈及他的所有子博弈中都构成纳什均衡 完全且完美信息动态博弈： 斯塔克伯格Stacklberg模型 1934（动态寡头市场产量博弈模型） 里昂惕夫leontief 模型 1946 （有公会企业的劳资博弈） 讨价还价Bargaining模型 委托人-代理人博弈模型（店主-店员博弈模型） 挤兑银行模型 关税与国际市场的不完全竞争模型 工作竞赛模型 重复博弈Repeated Games 基本博弈（阶段博弈stage game）重复进行，重复博弈的一个阶段可能是一个静态博弈也可能是一个动态博弈。 影响重复博弈均衡结果的因素：重复博弈的次数（短期效益与长期效益的衡量）、信息的完备性（在支付函数不为人所知情况下，坏人可能 为了长期效益偶尔或者常常做好事） 有限次重复博弈：连锁店悖论chain-store paradox 1978 selten 有限次重复博弈定理一：G是阶段博弈，G（T）是G重复T次的重复博弈（T为有限）。那么如果G是有唯一的纳什均衡，G（T）的唯一子博弈 精炼均衡结果是阶段博弈G的纳什均衡重复T次。（在有限次的囚徒困境中，每一次囚徒都会选择坦白，而不会选择 对双方都有利的抵赖） 上述定理适用条件：a，重复博弈是有限的 b，阶段博弈G的纳什均衡是唯一的 多个纯策略纳什均衡博弈的有限次重复博弈：（三价博弈：市场利润因价格高中低而不同，两主动企业定价，定价相同则平分利润，不同则 由非主导企业独占利润）（两市场博弈：两企业开发两市场，一市场大，单独一家无法完全 开发，一市场小，只容得下一个企业） 触发策略Trigger Strategy：首先尝试合作，一旦发现其他人不合作即以不合作来报复。（三价博弈） 轮换策略：轮流采用原博弈两个纳什均衡策略（两市场博弈） 用wi记博弈方i在一次博弈中的最差得益，用w记各博弈方wi组成的得益数组。 个体理性得益individual rationality payoff（保留博弈 reservation payoff）：不管其他博弈方行为如何，一博弈方只要自己采取某种 特定策略，最低限度保证能获得的得益。 可实现得益feasible payoff：得益中所有纯策略组合得益的加权平均（权数非负且总和为1）数组 有限次重复博弈民间定理folk theron：设原博弈的一次性博弈有均衡得益数组优于w，那么在该博弈的多次重复中，所有不小于个体理性得 益的可实现利益，都至少有一个子博弈精炼纳什均衡的极限的平均得以来实现他们。 无限次重复博弈民间定理1971 friedman弗里德曼：设G是一个完全信息的静态博弈，用（e1，e2，.en）表示G的纳什均衡得益，用（x1， x2.xn）表示G的任意可实现得益，如果xiei对任何i都成立，而足够接近1，那么无 限次重复博弈G（，）中一定存在一个子博弈精炼纳什均衡，各博弈方的平均得益（ x1，x2.xn） 完全但不完美信息动态博弈：二手车模型不完全信息静态博弈（贝叶斯博弈）- 招标、不完全信息的古诺模型（不对称信息的古诺模型） 不完全信息静态博弈的表示： ti表示博弈方i的类型（类型指博弈方自己清楚，但其他博弈方无法知道的内部信息，如拍卖中的估价）Ti表示i的类型空间 ui（a1，a2.an，ti）表示i在策略组合（a1,a2，.an）下的得益 静态贝叶斯模型的表示为G=（A1，A2.An；T1,T2.Tn；u1，u2.un） 静态贝叶斯模型中，博弈者虽然不知道其他博弈者的类型，但却知道他们选择各种类型的概率p，那么该模型还可以表示为： G=（A1，A2.An；T1,T2.Tn；p1，p2.pn；u1，u2.un） 海萨尼转换harsanyi 1967：a，引进一个虚拟博弈方：自然nature（博弈方0）；b，自然行动，随机抽取各博弈方类型组成类型向量t=（t1 ，t2.tn）tiTi，这个自然让博弈方知道自己的类型，缺不让别人的全部或者部分知道；c，进行博弈 海萨尼转换让静态贝叶斯博弈变成一个完全但不完美的动态博弈，更方便对静态贝叶斯的分析。 在贝叶斯静态博弈G=（A1，A2.An；T1,T2.Tn；p1，p2.pn；u1，u2.un）中，博弈方i的一个策略就是对自然可能抽取的类型ti的 函数Si（ti），该函数设定，对于自然可能抽取的任意ti，博弈方i都能从行为空间Ai中选择相应的行动ai 贝叶斯纳什均衡：在静态贝叶斯博弈G=（A1，A2.An；T1,T2.Tn；p1，p2.pn；u1，u2.un）中，如果对于任意的博弈方i和他所选 择的类型ti，Si*（ti）所选择的ai都满足maxuis1*（t1），.ai.sn*（tn），ti*p（t-i|ti），则称策略组合 （s1*，s2*.sn*）为G的一个贝叶斯纳什均衡 机制设计：运用于垄断定价 最优税收 拍卖理论，分为两类：最优机制（最大化委托人拍卖者的预期收益）；效率机制（96诺贝尔经济学奖 得主的成果） 机制设计中的主体：委托人：只有一个，他的支付函数为共同知识，委托人选择机制即自己设计一个博弈规则 代理人：一个或者多个，他的支付函数只有自己知道，委托人和其他的代理人都不知道 机制设计的一般思想：委托人设计一个决策向量或者货币转移向量 委托人设计机制面临的约束：a，参与约束（个人理性约束），即代理人在该机制下的期望效用必须不小于代理人不接受此机制的最大 预期效用 b，激励相容约束，即在委托人不知道代理人类型的情况下，代理人在该机制下必须有积极选择委托人希 望他选择的行动 机制设计的特征：三阶段不完全信息博弈 a，委托人提供机制（规则，契约，分配方案等） b，代理人决定是否接受机制，若接受，进入第三阶段 c，代理人在机制中行动，即向委托人如实报告自己的类型 机制的类型：直接机制 间接机制 直接机制：a，代理人对标的估价即（类型），因为不要求诚实，所以代理人可以从Ti中选择任意ti，即使并非自己的真实类型 b，根据声明（t1，t2.tn），代理人i中标的概率