完全信息静态博弈基础理论PPT课件

1、1.1.A 基础理论:博弈的标准式和纳什均衡 1.1.A 博弈的标准式表述 在博弈的标准式表述中，每一参与者同时选择一个战略，所有参与者选择战略的组合决定了每个参与者的收益。 我们借一个经典的例子说明博弈的标准式囚徒困境。第1页/共48页囚徒困境： 两个犯罪嫌疑人被捕并受到指控，但除非至少一个人招认犯罪，警方并无充足证据将其按罪判刑。警方把他们关入不同牢室，并对他们说明不同行动带来的后果。如果两人都不坦白，将均被判为轻度犯罪，入狱一个月;如果双方都坦白招认，都将被判入狱6个月;最后，如果一人招认而另一人拒不坦白，招认的一方将马上获释，而另一人将判入狱9个月所犯罪行6个月，干扰司法加判3个月。第

2、2页/共48页 囚徒面临的问题可用下图所示的双变量矩阵表来描述。 “双变量”指的是在两个参与者的博弈中，每一单元格有两个数字，分别表示两个参与者的收益。第3页/共48页 在此博弈中，每一囚徒有两种战略可供选择:坦白(或招认)、不坦白(或沉默). 在一组特定的战略组合被选定后，两人的收益由上图双变量矩阵中相应单元的数据所表示。 习惯上，横行代表的参与者(此例中为囚徒1)的收益在两个数字中放前面，列代表的参与者(此例为囚徒2)的收益置于其后。第4页/共48页博弈的要素： 现在我们回到一般情况。 博弈的标准式表述包括: （1）博弈的参与者； （2）每一参与者可供选择的战略集； （3）针对所有参与者可

3、能选择的战略组合，每一个参与者获得的收益。第5页/共48页 考虑n个参与者的博弈： （1）参与者从1到n排序; （2）设其中任一参与者的序号为i，令Si代表参与者i可以选择的战略集合(称为i的战略空间)，其中任意一个特定的战略用si表示(有时我们写成，siSi表示战略si是战略集Si中的要素); （3）令(s1,.,sn)表示每个参与者选定一个战略形成的战略组合，ui表示第i个参与者的收益函数，ui (si,.,sn)即为参与者选择战略(s1,.,sn)时第i个参与者的收益。第6页/共48页博弈的标准式表述 将上述内容综合起来，我们得到: 定义 在一个n人博弈的标准式表述中，参与者的战略空间为

4、S1,Sn，收益函数为u1,un，我们用G=S1,Sn; u1,un表示此博弈。第7页/共48页同时选择战略的含义： 尽管我们曾提到,在博弈的标准式中，参与者是同时选择战略的，但这并不意味着各方的行动也必须是同时的。只要是每一参与者在选择行动时不知道其他参与者的选择就足够了。像上例中牢里分开关押的囚徒，可以在任何时间作出他们的选择。 更进一步，尽管在本章中博弈的标准式只用来表示参与者行动时不清楚他人选择的静态博弈，但标准式也可用来表示序贯行动的博弈，只不过另一种变通的方式博弈的扩展式表述更为常用，它在分析动态问题时也更为方便。第8页/共48页1.1.B 重复剔除严格劣战略 下面开始介绍如何着手

5、分析一个博弈论问题。 我们从囚徒的困境这个例子开始，因为它较为简单，只需用到理性的参与者不会选择严格劣战略这一原则。第9页/共48页严格劣战略的定义： 定义 在标准式的博弈G=S1,Sn; u1,un中，令si和si”代表参与者i的两个可行战略(即si和si”是Si中的元素)。如果对其他参与者每一个可能的战略组合，i选择si的收益都小于其选择si”的收益，则称战略si相对于战略si”是严格劣战略: ui(s1,si-1,si,si+1,sn)ui(s1,si-1,si”,si+1,sn)对其他参与者在其战略空间S1, Si-1,Si+1, Sn中每一组可能的战略（s1,si-1,si+1,sn

6、 ）都成立。第10页/共48页重复剔除严格劣战略均衡： 理性的参与者不会选择严格劣战略，因为他对其他人选择的战略)无法作出这样的推断，使这一战略成为他的最优反应。 这样，在囚徒的困境中，一个理性的参与人会选择招认，于是（招认，招认）就成为两个理性参与者的结果，尽管(招认，招认)带给双方的福利都比(沉默，沉默)要低。第11页/共48页第12页/共48页现在，我们来看理性参与者不选择严格劣战略这一原则是否能解决其他博弈问题。 考虑图1.1.1所示抽象博弈的例子：第13页/共48页重复剔除严格劣战略均衡的缺陷： 上面的过程可称为 “重复剔除严格劣战略”。 尽管此过程建立在理性参与人不会选择严格劣战略

7、这一合情近理的原则之上，它仍有两个缺陷: 第一，每一步剔除都需要假定，参与者间相互了解。 如果我们要把这一过程应用到任意多步，就需要假定“参与者是理性的”是共同知识。 这意味着，我们不仅需要假定所有参与人是理性的，还要假定所有参与人都知道所有参与人是理性的，还需要假定所有参与人都知道所有参与人都知道所有参与人是理性的，如此等等，以至无穷。第14页/共48页 第二个缺陷在于这一方法对博弈结果的预测经常是不精确的。例如，在下图1.1.4中的博弈中，就没有可以剔除的严格劣战略。既然所有战略都经得住对严格劣战略的重复剔除，该方法对分析博弈将出现什么结果毫无帮助。第15页/共48页1.1.C 纳什均衡的

8、导出和定义 下面我们介绍纳什均衡，它是一种博弈的解的概念，可以对非常广泛类型的博弈作出严格得多的预测。 导出纳什均衡的途径之一，是证明： 如果博弈论可以为博弈问题提供一个惟一解，此解一定是纳什均衡。 原因如下：第16页/共48页 设想在博弈论预测的博弈结果中给每个参与者选定各自的战略。为使该预测是正确的，必须使参与者自愿选择理论给他推导出的战略。这样，每一参与者要选择的战略必须是针对其他参与者选择战略的最优反应。 这种理论推测结果可以叫做“战略稳定”或“自动实施”的，因为没有参与人愿意独自离弃他所选定的战略。 我们把这一状态称为纳什均衡。第17页/共48页纳什均衡的定义： 定义 在n个参与者标

9、准式博弈G=S1,Sn; u1,un中，如果战略组合s*1,s*n满足对每一参与者i，si*是(至少不劣于)他针对其他n-1个参与者所选战略s*1,s*i-1,s*i+1,s*n 的最优反应战略，则称战略组合s*1,s*n 是该博弈的一个纳什均衡。即: ui(s*1,s*i-1,s*i,s*i+1,s*n) ui(s*1,s*i-1,si,s*i+1,s*n) 对所有Si中的si都成立，亦即s*i是以下最优化问题的解:第18页/共48页纳什均衡与协议的理念 和纳什均衡推导密切相关的是协议的理念:对给定的博弈，如果参与者之间要商定一个协议决定博弈如何进行，那么一个有效的协议中的战略组合必须是纳什

10、均衡的战略组合，否则，至少有一个参与人会不遵守该协议。 为更准确地理解纳什均衡这一概念，下面求解几个例题。第19页/共48页寻找纳什均衡的方法：划线法 一个最直接办法就是：简单查看每一个可能的战略组合是否符合定义中不等式的条件。 在两人博弈中，这一方法开始的程序如下:对每一个参与者，并且对该参与者每一个可选战略，确定另一参与者相应的最优战略。 图1.1.5中，就把图1.1.4所示博弈作了上述处理，对参与者i的每一个可选战略，在参与者j使用最优反应战略时的收益下面划了横线。 如果在一对战略中，每一参与人的战略都是对方战略的最优反应战略，则双变量矩阵相应单元的两个收益值下面都被划了横线)。第20页

11、/共48页第21页/共48页第22页/共48页猪圈里一头大猪和一头小猪。圏的一头有一槽，另一头一按钮，控制食量。按一下进食10单位，但支付2单位成本。如大猪先到，大猪吃到9单位，小猪1单位；如小猪先到，大猪吃6单位，小猪4单位；如同时到，大猪6单位，小猪4单位。智猪博弈1：多劳不多得（张维迎，P010） 5 1 4 4 9 1 0 0 小猪按 等 按大猪 等第23页/共48页猪圈里一头大猪和一头小猪。圏的一头有一槽，另一头一按钮，控制食量。按一下进食8单位，但支付2单位成本。如大猪先到，大猪吃到7单位，小猪1单位；如小猪先到，各吃4单位；如同时到，大猪5单位，小猪3单位。智猪博弈2：多劳少得（

12、张维迎，P034035） 3 1 2 4 7 1 0 0 小猪按 等 按大猪 等第24页/共48页猪圈里一头大猪和一头小猪。圏的一头有一槽，另一头一按钮，控制食量。按一下进食仅4单位，但支付2单位成本。如大猪先到，大猪吃到4单位，小猪0单位；如小猪先到，吃4单位；如同时到，大猪3单位，小猪1单位。智猪博弈3：劳而不得！ 1 -2 -2 4 4 -2 0 0 小猪按 等 按大猪 等第25页/共48页作业 请设计一个多劳多得的智猪博弈。第26页/共48页纳什均衡和重复剔除严格劣战略均衡的关系 如果用重复剔除严格劣战略把除战略组合s*1,s*n外所有的战略组合都剔除掉，则该所存战略组合就是此博弈惟一

13、的纳什均衡。 不过，由于重复剔除严格劣战略并不经常会只剩下惟一的战略组合，纳什均衡作为比重复剔除严格劣战略更强的解的概念，自然受到更多关注，理由如下: 如果战略组合s*1,s*n是一个纳什均衡，它一定不会被重复剔除严格劣战略所剔除，但也可能有重复剔除严格劣战略无法剔除的战略组合，其本身却和纳什均衡一点儿关系都没有。第27页/共48页纳什均衡的存在性 证明了纳什均衡是一个比重复剔除严格劣战略条件更强的解的概念之后，我们还必须解决一个问题，就是纳什均衡作为博弈解的概念，条件是否太强了，即我们能否确定纳什均衡一定是存在的? 纳什(1950)证明了在任何有限博弈(即参与者n和战略集S1，Sn都是有限的

14、博弈)中，都存在至少一个纳什均衡(这一均衡可能包含了混合战略，我们将在后面讨论)。第28页/共48页 古诺（1838）在双头垄断模型这一特定的环境中提出了同样的均衡概念，并通过构造的方法证明了模型中均衡的存在性。 在以后的每一个应用分析中，我们都将沿袭古诺的思路:即将通过构造一个纳什均衡(或条件更强的均衡)的方法，证明均衡本身的存在性。第29页/共48页纳什均衡的局限性： 我们用另一经典例子作为本节小结性别战博弈。关于这一博弈的传统表述(这一博弈从20世纪50年代就开始使用了)，是一男一女试图决定安排一个晚上的娱乐内容，我们分析这一博弈的中性版本。 不在同一地方工作的帕特（男）和克里斯（女）必

15、须就去听歌剧和看职业拳击赛选择其一，帕特和克里斯都希望两人能在一起渡过一个夜晚，而不愿分开，但帕特更希望能一起看拳击比赛，克里斯则希望能在一起欣赏歌剧，如下面双变量矩阵所示:第30页/共48页 (歌剧，歌剧和(拳击，拳击)都是纳什均衡。第31页/共48页 可见：如果博弈论可以为一个博弈提供惟一解，此解一定是一个纳什均衡。这一命题没有提及博弈论不能提供惟一解的可能情况。 同时还论证了如果参与者之间能就如何进行给定的博弈达成一个协议，该协议也一定是一个纳什均衡。但这一命题同样没有考虑不能达成协议的可能情况。第32页/共48页 在一些有多个纳什均衡的博弈中，有一个均衡比其他均衡明细占优后面各章的主要

16、理论内容就是找出不同类型博弈的这种占优均衡)，这时，多个纳什均衡的存在本身也不会引出其他问题。 不过，在上面讲的性别战博弈中，歌剧，歌剧)和(拳击，拳击)又难分优劣。 这说明博弈论对有些博弈并不能提供惟一解，参与者间也不能就该博弈的进行达成协议。 在这样的博弈中，纳什均衡用于预测博弈将如何进行的作用就大大减弱了。第33页/共48页1、多重性： 许多博弈往往存在不止一个纳什均衡，而且相互之间有时没有明显的优劣关系。 即使相互之间有明显的优劣关系，我们也不能保证，博弈方一定会选择较优的纳什均衡。 因此需要根据对手的情况适时作出反应，将原则的坚定性和策略的灵活性有机结合。多重纳什均衡博弈的分析第34

17、页/共48页 2、几个常用的甄别标准 （1）帕累托优势标准 适用于多个纳什均衡之间存在明显的优劣关系，博弈的某个纳什均衡给所有局中人带来的收益，都大于其他纳什均衡带来的收益。这种按支付大小筛选出来的纳什均衡，比其他纳什均衡具有帕累托优势。第35页/共48页 猎鹿博弈2 20 11 0 1 1 局中人2坚守 擅离 坚守局中人1 擅离第36页/共48页 战争与和平 （谢识予，P93）5 5 8 1010 ，8 10 ，10 战争 国家1 和平 国家2战争 和平第37页/共48页 （2）风险优势标准 考虑不同纳什均衡之间的风险状况，风险小的优先。 测定风险的方法有二： 第一是期望支付法；第二是偏离损

18、失比较法。第38页/共48页 期望支付法：寻找占优战略 （王则柯，P125126） 9 ， 9 0 ， 8 8 ， 0 7 ， 7 上 局中人1 下 局中人2上 下v这种方法通过假设概率情况来计算期望支付，从而测定风险。这容易引起混淆，有很不严密的地方。第39页/共48页 偏离损失乘积比较法： 比较 甲偏离均衡A的损失乙偏离均衡A的损失 甲偏离均衡B的损失乙偏离均衡B的损失 乘积大的风险大，具有风险优势 （王则柯，P126127） 6 ， 6 0 ， 5 5 ， 0 4 ， 4 上 甲 下 乙左 右 第40页/共48页 （3）聚点均衡 在现实生活中，局中人可能会使用某些被博弈模型抽象掉的信息来

19、达成一个共识，从而达到一个均衡。这些信息往往跟社会文化习惯、局中人过去博弈的历史和经历有关。这就是聚点均衡概念的基本思想。第41页/共48页 案例： 假定你和你热恋中的恋人正在打电话，突然，连接中断。这时候，你将如何行动？聚点是什么？ 0 ， 0 3 ，2 2 ， 3 0 ， 0 重打 男 不打 女重打 不打第42页/共48页 （4）颤抖手精练均衡 泽尔滕在1975年的一篇论文，提出了颤抖手精练均衡（trembling-hand perfect equilibrium），进一步精练纳什均衡。基本思想是：在任何一个博弈中，每一个局中人都有一定的犯错误的可能性。局中人所选择的一个策略组合，只有当它在允许每个局中人都可能犯小小的错误时仍是所有局中人的最优策略组合时，才是一个足够稳定的均衡。（正式的定义，见：王则