1、第三章 对策论（Game Theory）,本章主要内容： 基本概念 二人有限零和对策 二人有限非零和对策,又称博弈论，是研究决策主体的行为发生直接相互作用时的决策以及这种决策的均衡问题的学科。 是研究具有竞争、对抗、冲突性质的现象的数学理论和方法。,1 基本概念,一、对策论的定义,1 基本概念,一、对策论的定义二、对策理论的历史三、对策问题举例四、对策的分类,二、对策理论的历史 我国春秋战国时期的“孙子兵法” ； 围棋，发明于我国殷代； 对策作为一种数学理论开始于1944年。 由美国数学家冯诺依曼(Von. Neumann)和经济学家摩根斯坦(Morgenstern)发表了题为“博弈论与经济行
2、为”的著作 1950年，纳什完成博士论文“非合作博弈”， 纳什的两篇论文和Tucker定义的囚徒困境，奠定了现代非合作博弈论的基石。,1994年诺贝尔经济学奖获得者，纳什在普林斯顿读博士时刚刚20岁出头，他的一篇关于非合作对策的博士论文和其他两篇相关文章确立了他博奕论大师的地位。到上世纪50年代末，他已是闻名世界的大牌科学家了。,然而，正当他的事业如日中天的时候，天妒英才，他得了严重的精神分裂症。多亏前妻艾莉西亚的爱心呵护和普林斯顿大学诸多朋友和同事无私的帮助才没有使他流落街头，并最终把他推上诺贝尔经济学奖宝座（1994年获奖）。,他的故事被好莱坞拍成了电影美丽心灵，该影片获得了2002年奥斯
3、卡金像奖的四项大奖,纳什简介,合作博弈和非合作博弈的主要区别：当事人能否达成一个具有约束力的协议（binding agreement）。 另外，合作博弈强调的是集体理性，强调效率、公平、公正；非合作博弈强调的是个体理性。 现代博弈论主要指非合作博弈理论。非合作博弈更受重视的原因：主导人们行为的主要还是个体理性，而非集体理性；即，竞争是一切社会、经济关系的根本基础，不合作是基本的，合作是有条件和暂时的。,九十年代以来博弈理论在金融、管理和经济领域中得到广泛应用,合作博弈和非合作博弈,九十年代以来对策理论在金融、管理和经济领域中得到广泛应用,博弈论和诺贝尔经济奖,1994：非合作博弈：纳什(Nas
4、h)、泽尔腾（Selten） 、海萨尼（Harsanyi）1996：不对称信息激励理论：莫里斯（Mirrlees）和维克瑞（Vickrey）2001：不完全信息市场博弈：阿克罗夫（Akerlof）（商品市场）、斯潘塞（Spence）（教育市场）、斯蒂格里兹（Stiglitze）（保险市场）2005: 授予罗伯特奥曼与托马斯谢林，以表彰他们通过博弈理论的分析增强世人对合作与冲突的理解。2007年，授予赫维茨（Leonid Hurwicz）、马斯金(Eric S. Maskin）以及迈尔森(Roger B. Myerson）。三者的研究为机制设计理论奠定了基础。2012年，授予罗斯（Alvin E
5、. Roth）与沙普利（Lloyd S. Shapley）。他们创建“稳定分配”的理论，并进行“市场设计”的实践。,1 基本概念,一、对策论的定义二、对策理论的历史三、对策问题举例四、对策的分类,三、对策问题举例1. 囚犯困境（Prisoners dilemma）,囚犯困境是图克（Tucker）1950年提出的；该对策是博奕论最经典、著名的对策；该对策本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题，可以揭示市场经济的根本缺陷。,三、对策问题举例1. 囚犯困境（Prisoners dilemma） 两名囚犯I和II因涉嫌抢劫被捕。警方 因证据不足先将二人分关
6、二室，并宣布： 若二人均不坦白，则只能因藏有枪支而被判刑1年； 若有一人坦白而另一个不坦白，则坦白者无罪释放，不坦白者 被判刑10年； 若二人都坦白了，则同判9年。 此二人确系抢劫犯，请分析他们的抉择。,对策分析的基本假设,（1）个人理性 假设当事人在决策时能够充分考虑他所面临的局势，并能做出合乎理性的选择。,（2）最大化自己的收益 假设当事人在决策时通常选择使自己收益最大化的策略。,相关概念介绍,对策问题的基本要素（1）局中人（Players） 参与对抗的各方；不一定指自然人（2）策略集（Strategies） 局中人选择对付其它局中人的行动方案称为策略; 某局中人的所有可能策略全体称为策略
7、集；,对策双方的策略集一般记为：,例：囚犯困境中，每个囚犯均有2个策略： 坦白，抵赖,（3）局势,局中人采用某局势时的收益值。,例:当局中人甲选择策略si ，局中人乙选策略dj 时，局中人甲的赢得值可用 表示。,当每个局中人从各自策略集合中选择一策略而组成的策略组成为一个局势，用 来表示。,（4）赢得（支付）,启示：个人理性和集体理性的矛盾 当一个社会中的每个个体都为自身的利益打算时，即使大家都遵守社会规则，个体的行为不一定能实现个体的最佳利益。结论：政府在社会经济活动中的组织协调工作是必需的，放任自流不是导致全社会最大福利的最佳政策。,继续讨论“囚犯困境”问题：,囚犯困境问题在经济、政治、军
8、事等领域的应用举例,例：寡头垄断企业定价的对策,卡特尔价格不是纳什均衡，最终结果：每个企业按照纳什均衡的价格进行定价，其利润小于卡特尔价格条件下的利润。,例：军备竞赛,冷战期间，美苏两国的军备竞赛，使得两国的社会福利都变得更糟。,案例分析： 生活中的“囚徒困境”例子, 商家价格战 出售同类产品的商家之间本来可以通过共同将价格维持在高位而获利，但实际上却是相互杀价，结果都赚不到钱。 当一些商家共谋将价格抬高，消费者实际上不用着急，因为商家联合维持高价的垄断行为一般不会持久，可以等待垄断的自身崩溃，价格就会掉下来。,譬如，2000年我国几家生产彩电的大厂商合谋将彩电价格维持高位，他们搞了一个“彩电
9、厂家价格自律联盟”，并在深圳举行了由多家彩电厂商首脑参加的“彩电厂商自律联盟高峰会议”。当时，国家有关部门还未出台相关的反垄断法律，对于这种在发达国家明显属于违法行为的所谓“自律联盟”，国家在法律上暂时还是无能为力的。寡头厂商在光天化日之下进行价格合谋，并且还通过媒体大肆炒作，这在发达国家是不可思议的。,但是，尽管政府当时无力制止这种事情，公众也不必担心彩电价格会上涨。这是因为，“彩电厂商自律联盟”只不过是一种“囚徒困境”，彩电价格不会上涨。在高峰会议之后不到二周，国内彩电价格不是上涨而是一路下跌。这是因为厂商们都有这样一种心态：无论其他厂商是否降价，我自己降价是有利于自己的市场份额扩大的。问
10、题：明确该对策问题的各要素：局中人、策略集、赢得矩阵,2、智猪博弈,猪圈里有两头猪：一头大猪、一头小猪，猪圈的一头有一个猪食槽，另一头安装一个按钮，控制着猪食的供应。按一下按钮就会有10个单位的猪食进槽，但谁按按钮谁就需要付2个单位的成本。若大猪先到，大猪吃到9个单位，小猪只能吃1个单位；若同时到，大猪吃到7个单位，小猪吃3个单位；若小猪先到，大猪吃到6个单位，小猪吃4个单位；,智猪博弈的应用举例,例：大、小股东的职责,股份公司中，股东承担着监督经理的职能。监督需要成本，大股东从监督中获得的好处要多于小股东。Nash均衡：大股东担当起搜集信息、监督经理的责任，小股东“搭便车”。,例：股票市场中
11、的大户、小户,例：市场中的大企业、小企业 进行研究开发、为新产品做广告，对大企业是值得的，对小企业则得不偿失。 所以，一种可能的情况是，小企业把精力花在模仿上，或等待大企业用广告打开市场后出售廉价产品。,例：公共产品的提供 村里住两户人家，一户富，一户穷，有一条路年久失修。这时候，富户一般会承担起修路的责任，穷户则很少这样干，因为富户常常高朋满座，路用得更多。穷户对于修路无所谓。,3.中国的游戏“剪刀、石头、布”,小孩A与B猜手,若规定赢得1分，平得0分，输得 -1分，则 A的赢得可用下表来表示。,分析：无确定最优解，可用“混合策略”求解。,4.齐王赛马 战国时期，齐国国王有一天提出要与大将军
12、田忌赛马。田忌答应后，双方约定：1)每人从上中下三个等级中各出一匹马，共出三匹；2) 一共比赛三次，每一次比赛各出一匹马；3) 每匹被选中的马都得参加比赛，而且只能参加一次；4) 每次比赛后输者要付给胜者一千金。 当时在三个不同等级中，齐王的马要比田忌的强些，看来田忌要输三千金了，但由于田忌采用了谋士的意见，最终反败为胜。谋士的主意是：1) 每次比赛前先让齐王说出他要出哪匹马；2) 让田忌用下马对齐王上马；3) 用中马对齐王下马；4) 用上马对齐王中马。,“齐王赛马”齐王在各局势的赢得表（单位：千金）,1 基本概念,一、对策论的定义二、对策理论的历史三、对策问题举例四、对策的分类,四、对策的分
13、类,非合作博弈： 更一般意义的分类及其对应均衡,推荐书目,张维迎, 博弈论与信息经济学 ,上海三联书店,上海人民出版社谢识予, 经济博弈论 ,复旦大学出版社,局中人为2； 对策双方的策略均有限； 对策双方的赢得值之和为零。,G = S, D, A 甲的策略集 甲的赢得矩阵 乙的策略集,特点：,例：“齐王赛马”即是一个矩阵策略。,记矩阵对策为:,2 二人有限零和对策（矩阵对策）,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对策三、混合策略对策,一、纯策略与混合策略 纯策略是指确定的选择某策略；而混合策略则指以某一概率分布选择各策略。,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对
14、策,三、混合策略对策,引例纯策略分析纯策略对策模型的解优超原理,二、纯策略对策,1. 引例,前提：对策双方均理智,结论：最不利中选最有利,解：可用下述表格表示上述寻找最优纯策略过程:,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对策,三、混合策略对策,引例纯策略分析纯策略对策模型的解优超原理,2. 纯策略分析,（1）局中人甲对每个策略si的评价值为,故局中人甲选择策略模型为：,（2）局中人乙对每个策略dj的评价值为,故局中人乙选择策略模型为：,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对策,三、混合策略对策,引例纯策略分析纯策略对策模型的解优超原理,3. 纯策略对策模型的解,
15、(1) 鞍点与解,称为对策G 之值。,例 上例中,对策值V=1,局中人甲的最优策略为s1 ,局中人乙的最优策略为d2，,(2) 多鞍点与无鞍点对策,例 设有一矩阵对策如下，求它的解。,此对策有多个解。,例： 矩阵对策赢得矩阵如下，试求它的解。,例：齐王赛马为无鞍点对策,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对策,三、混合策略对策,引例纯策略分析纯策略对策模型的解优超原理,4、优超原理,例：,优超原理,降阶求解，且两个对策具有相同的值。,可,例： 用优超原理求解下列对策,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对策三、混合策略对策,基本概念混合策略对策的解,三、 混合策
16、略对策,1. 基本概念,无鞍点对策的求解方法是采用混合策略，混合策略就是局中人考虑以某种概率分布来选择他的各个策略。,同理可定义乙的混合策略。,（1） 混合策略,例： “剪刀、石头、布” 游戏，若B的混合策略（0.4，0.3，0.3）,则A选“石头”的期望赢得为：,00.4 + 1 0.3 + (-1)0.3=0,则A选“剪子”的期望赢得为：,(-1)0.4 + 0 0.3 + 1 0.3= - 0.1,则A选“布”的期望赢得为：,10.4 + (-1) 0.3 + 00.3=0.1,若又已知A的混合策略（0.5，0.2，0.3），则A的期望赢得为：,00.5 + (-0.1) 0.2 + 0
17、.10.3= 0.01,（同理，B的期望赢得为-0.01）,（3）混合局势,当局中人甲选择混合策略x；局中人乙选择混合策略y，称(x,y)为一个混合局势。,（2）混合策略集合,称集合,为甲的混合策略集合；,为乙的混合策略集合；,对于一个混合局势(x,y)，用,表示局中人甲在混合局势(x,y)时的收益期望值。,（4）收益期望函数,2 二人有限零和对策,一、纯策略与混合策略二、纯策略对策三、混合策略对策,基本概念混合策略对策的解,2. 混合策略对策的解,（1）混合策略分析,对于混合策略对策,局中人甲的策略决策模型为：,局中人乙的策略决策模型为：,（2）混合策略矩阵对策的线性规划解法,若所有aij0
18、（否则，可取一充分大M0，使得aij +M0），则可用下述两规划 来求解混合策略：,（）,（）,例： “剪刀、石头、布” 游戏，,同理，,例：,先应用优超原理化简A,22矩阵可以直接按公式计算：,3 非零和博弈,一、非零和博弈的一般表达,1、局中人集合：i = 1, 2 ,，n,2、每个局中人的策略集：Si (i = 1,n),3、每个局中人的赢得函数：ui (s1, , s i , sn),博弈的一般表达：G=S1, Sn ; u1, un ,二、纳什均衡,均衡（Equilibrium）是所有局中人的最优策略的组合，一般记为：,其中，,是第i个局中人在均衡情况下的最优策略，即,（,表示除 i
19、 之外,所有局中人的策略组成的向量。),占优策略均衡,均衡的层次：,重复剔除的占优均衡,（纯策略）纳什均衡,混合策略纳什均衡,条件,强,弱,1. 占优策略均衡,考虑“囚犯困境”问题：,不论同伙选择什么策略，每个囚徒的最优策略是“坦白”。,定义：如果对应所有的,是i的严格最优选择，即,则称,是i的占优策略(Dominant strategy)。,2. 重复剔除的占优均衡,考虑智猪博弈问题：,“等待”是小猪的占优战略，而大猪无占优战略。,劣策略,例：,可按如下思路寻找均衡解：首先找出某个局中人的劣策略（如果存在），剔除该劣策略，得到新的博弈；再剔除该新博弈中的某个中人的劣策略。重复进行，直至只剩下
20、唯一的策略组合为止，这个剩下的策略称为重复剔除的占优均衡（Iterated dominance equilibrium）。,前提假设：“理性”是所有局中人的共同知识 （Common Knowledge）,例：求下面博弈的重复剔除的占优均衡解,（均衡解）,例：智猪博弈问题：,（均衡解）,3. 纳什均衡,例：（夫妇之争）夫妇俩商量晚上去哪里消遣。丈夫喜欢看足球比赛，而妻子喜欢去看芭蕾舞表演，夫妇都希望二人同往，不愿分开。,问题：既不存在占优策略均衡，也不存在重复剔除的占优均衡。,定义：对于博弈 G=S1, Sn ; u1, un ，策略组合,。如果对于每一个i，,是给,定其它局中人选择,的情况下第
21、i个局中人的最优策略，即,则称该策略组合为一个纳什均衡。,或表示为：,是下述最大化问题的解：,纳什均衡的哲学意义,表示n个局中人达成的,一个协议，当这个协议可以自动实施（Self-enforcing）时，即没有任何局中人有积极性破坏这个协议，那么这个协议就构成纳什均衡。 否则，若至少存在某些局中人有积极性偏离这个协议，就构不成纳什均衡。,例：智猪博弈问题：,例：囚犯困境问题：,例：（夫妇之争）夫妇俩商量晚上去哪里消遣。丈夫喜欢看足球比赛，而妻子喜欢去看芭蕾舞表演，夫妇都希望二人同往，不愿分开。,纳什均衡解： （足球，足球）或（芭蕾，芭蕾）,解纳什均衡的划线法,设有两个局中人：A和BStep 1
22、: 考虑A，给定B的每一个策略，找出A的最优策略，并在其对应的赢得下面画一横线。Step 2: 用类似的方法，找出B的最优策略。Step 3: 都画横线的单元格即为纳什均衡。,例：求纳什均衡,纳什均衡,总结:对矩阵A，按列求最大；对矩阵B，按行求最大。,Nash均衡,零和博弈的鞍点对应于Nash均衡,，,例 考虑零和博弈,，其赢得矩阵为：,，其中,鞍点,例：斗鸡博弈（Chicken Game） 两个人举着火棍从独木桥的两端走向中央进行火拼。每个人都有两种策略：继续前进，或退下阵来。若两人都继续前进，则两败俱伤；若一方前进另一方退下来，前进者取得胜利，退下来的丢了面子；若两人都退下来，两人都丢面
23、子。赢得矩阵如下表所示。,Nash均衡：一进一退,斗鸡博弈的应用,冷战期间，美苏在世界各地抢占地盘，如果一方已经抢占了一块地盘，另一方就设法占另一块地盘，而不是与对手竞争同一块地盘。,警察与游行队伍。,夫妻吵架。一般来说，吵得厉害了，不是妻子回娘家躲一躲，就是丈夫到院子里抽支烟。,斗鸡博弈的问题：谁退？两败俱伤亦有可能。,纳什均衡在经济中的应用举例之例一,公共地的悲剧（Tragedy of the commons）如果一种资源没有排他性的所有权，就会导致对这种资源的过渡使用。考虑一个有n个农民的村庄共同拥有一片草地，每个农民都有在草地上放牧的自由。每年春天，每个农民要决定自己养多少只羊。用gi
24、表示第i个农民饲养的数量， 表示总数量；v代表每只羊的平均价值。v是G的,。因为每只羊至少要一定数量的草才,不至于饿死，有一个最大可存活的数量Gmax : 当,函数：,G0； 当GGmax时，v(G)=0。,当草地上的羊很少时，增加一只羊也许不会对其它羊的价值有太大的不利影响，但随着饲养量的不断增加，每只羊的价值会急剧下降，因此：,在该博弈中，每个农民的问题是选择gi以最大化自己的利润。设购买每只羊的价格为c，则利润函数为：,最优化的条件为：,上述n个优化函数的交叉点就是纳什均衡。可以证明，纳什均衡的总饲养量大于社会最优的饲养量。,具体示例：设n=3，设每只羊的利润函数为,，设c =4,则3个
25、农民的利润函数分别为：,带入利润函数得,结论: (1)Nash均衡条件下，养羊总数243= 72，总利润 5763=1728； （2）总利益最大条件下：养羊总数48，总利润 2304。,反应函数：局中人i的最优策略是其他所有局中人策略的函数。,例如上例中，,结论：无限策略博弈分析，所有反应函数的交点即为Nash均衡。,4. 混合策略的纳什均衡,问题的提出纯策略意义下，有可能不存在纳什均衡,例：小偷与守卫的博弈（泽尔腾，1996）一小偷欲偷窃有一守卫看守的仓库，如果小偷去偷窃时守卫在睡觉，则小偷就能得手，否则要被抓住。假设小偷得手可偷得价值为V 的赃物，若被抓住坐牢，负效用 -P。再设守卫睡觉而
26、未被偷则有S 的正效用，睡觉遭偷则要被解雇，负效用-D。若小偷不偷，则无得无失，守卫不睡则出一份力争一份工资，无得无失。,无纳什均衡,的混合策略集:,的混合策略集:,混合策略的纳什均衡,纳什均衡的存在性定理：（纳什，1950）,每一个有限博弈至少存在一个纳什均衡（纯策略的或混合策略的）,22双矩阵博弈的解法,当A和B均为22阶时，相应的双矩阵博弈可表示为:,I,II,（1）,（2）,图示,解,条件,条件序号,总结22双矩阵博弈的求解步骤,（1）由 计算,（2）根据Ai和Bi的符号,得到I和II的解,其公共点即博弈的解。,例：（夫妇之争）夫妇俩商量晚上去哪里消遣。丈夫喜欢看足球比赛，而妻子喜欢去看芭蕾舞表演，夫妇都希望二人同往，不愿分开。,纳什均衡解（纯策略）： （足球，足球）或（芭蕾，芭蕾）,考虑混合策略：,
