博弈论基础wli@bjtu.edu.cn本科生:《策略博弈》2th,阿维纳什迪克西特,苏珊斯克丝《策略:博弈论导论》。乔尔沃森《博弈论基础》罗伯特吉本斯《博弈入门》马丁奥斯本研究生:《博弈论》D.弗登博格,让梯若尔《博弈论》R.迈尔森《博弈论教程》M.奥斯本,A.鲁宾斯坦参考书在所有社会,人们经常互动。有时,互动是合作,其他的时候,互动是竞争。在这两种情况下,都可以用一个术语,即相互依赖性来表示一个人的行为对另外一个人的福利造成的影响。相互依赖的情形可称为策略环境。因为人们为了确定所采取的最优行动,必须考虑他周围的其他人会怎样选择行动。1概述策略对于社会的运行来说,是非常基本的。我们要学会了解在策略环境下,人们实际上是如何采取行动的,以及他们应该怎样采取行动。相互依赖的情形可称为策略环境。因为人们为了确定所采取的最优行动,必须考虑他周围的其他人会怎样选择行动。这种系统的研究形成了应该策略互动的理论。1概述这个理论在许多方面都是有用的。首先,它提供了一种语言。其次,它提供了应该框架,能够指导我们建立策略环境模型。其三,它有助于我们追朔,对行为假设的逻辑推理过程。1概述这个理论在许多方面都是有用的。首先,它提供了一种语言。其次,它提供了应该框架,能够指导我们建立策略环境模型。其三,它有助于我们追朔,对行为假设的逻辑推理过程。1概述好几百年前,数学家就开始研究室内游戏,试图构造最优的游戏策略。在1713年,沃尔德格雷夫就某种纸牌游戏的解决方法,与他的同事德莫特和贝努利进行交流。沃尔德格雷夫的解决方法,与现代理论的结论相一致。1概述在19世纪的前10年,古诺对寡头模型的均衡进行了研究。而埃奇沃思解决了交易经济中的议价问题。1概述1913年,关于博弈的第一个定理(关于象棋游戏的结论)被泽梅罗证明。接着,博雷尔开创性地提出了“策略”的概念。1概述博弈论发展的关键事件是1944年冯诺依曼和奥斯卡摩根斯坦的著作《博弈论和经济行为》的出版。此书奠定了该领域的基石。接下去的几十年中,数学家和经济学家丰富了它的基础,逐步打造了社会科学最强大和最有影响力的工具箱之一。1概述1994年诺贝尔奖颁给了,在20世纪50-70年代对博弈论做出了重大贡献的3位经济学家:约翰·纳什,约翰·海萨尼和莱茵哈特·泽尔腾。1概述接着荣膺诺贝尔经济学奖金桂冠的经济学家有,诸如信息和合约方面的专家-威廉维克里和詹姆斯米利斯(1996年)。1概述还有2001年获奖的米歇尔斯彭斯,约瑟夫斯蒂克利茨和乔治阿克洛夫。1概述目前,博弈论被许多来自不同领域的专业人士使用,这些领域包括经济学、政治学、法律、生物、国际关系哲学以及数学。事实上,大多数情形即包含了冲突元素,也包含了合作的元素。我们对博弈的组成要有一个广义的理解。简而言之,博弈是策略环境的正式描述。因此,博弈论是研究相互依赖情形的正式的方法论。这里,“正式”是指一种以数学化的精确,以及逻辑上的一致见长的结构。利用正确的理论工具,我们可以研究各种情况下的行为,从而更好地理解经济中的相互作用。1概述1.1什么是博弈论?博弈论帮助我们理解,决策者互动的情形。Createsadoublerecordofbanktransactions.Bankreconciliation.导言MovieCricketMovie2,10,0Cricket0,01,22扩展型在数学上,有几种方法描述一个博弈:1博弈有一组参与人;2对于参与人可能采取的行动的完整描述(即它们的可行行动集);3对于参与人采取行动时,所知信息的描述;4对于参与人的行为将如何导致博弈结果的规定;5对于参与人对结果偏好的定义。2扩展型迪斯尼工作室的《虫子的一生》和梦工场的《蚂蚁》。卡曾伯格被迪斯尼的老板艾斯纳从派拉蒙招贤,以重振迪斯尼动画部。卡氏于1994年8月辞职。不久,艾斯纳接受了提议,于是《虫子的一生》进入了制作阶段。大概同时,卡氏与斯皮尔伯格等组建了梦工场。开始制作《蚂蚁》。两个工作室是在决定制作两部影片之后,才得知对方的决定的。2扩展型迪斯尼准备在1998年感恩节期间,发行《虫子的一生》。而这正是梦工场原定《埃及艳后》的上映时间。梦工场于是决定,把〉埃及艳后〉推迟到圣诞节。争取在《虫子的一生》上映之前,让《蚂蚁》上映。最后,《蚂蚁》为梦工场创造了超过0.9亿美元的利润,而《虫子的一生》确保了超过1.6亿美元的利润。2扩展型让我们用一个数学模型讲述这个故事。为了把它转化成数学的抽象语言,我们必须对故事进行适当的简化和程式化。我们的目标应该是从中分析得出一两个策略要素。这可以帮助我们从理论学者的角度,理解这个决策环境。2扩展型KEKKfghlmLSPNPNPNR’N’abcde我们可以用一个树状结构表示两个公司之间的互动。树状结构由节点和分支组成。节点表示事件的发生点,分支表示可以选择的不同的行为方案。我们用实心圆表示节点,用连接节点的箭头表示分支。这个树状结构称为扩展型表述。a称为初始点,a,b,c,d,e称为决策点。f,g,h,l,m称为终止点。表示博弈的结果。2扩展型KEKKfghlmLSPNPNPNR’N’abcde我们用信息集来定义参与人在博弈中的决策节点所拥有的信息。有一些信息集只包括一个节点,例如在节点a,b。节点c,d则包含在一个信息集中。每个信息集只能做出一个决策。而正如在故事中所说的,双方都不知道对方是否制作影片之前,决定制作自己的影片。虚线表示K知道自己处于这两个节点之一,但是不能区分自己处于c还是d。即K缺乏信息。2扩展型KKK40,11013,1200,14080,00,0LSPNPNPNR’N’abcdeE参与人对于结果的偏好性。K是否更希望博弈终止点f而不是h上结束?我们必须知道参与人关心什么,才能将终止点根据每个参与人的偏好排列。通常用数字表述参与人的偏好排序最为简便。这也称为支付(payoff),或者效用(utilities)。2扩展型KKK40,11013,1200,14080,00,0LSPNPNPNR’N’abcdeE我们引入一些数学符号来考察博弈。我们来看看一个市场博弈,两个厂商通过选择高价或者低价进行竞争。我们用参与人i表示任何一个参与人的数字代码。即在一个有n个参与人的博弈中,i=1,2,…,n。在某些博弈中,一个参与人可以在无限多个行动中进行选择。2扩展型12pyesnop,100-p0,0一个简单的讨价还价模型,即最后通牒议价。假设1希望卖一幅画。各方只有一次出价的机会。假设卖方先出价,买方2可以决定是否接受这个价格。如果画没有成交,双方均一无所获。如果成交,卖方获得等于价格的收益,买方获得自己的价值。2扩展型12pyesnop,100-p0,01.1什么是博弈论?博弈论帮助我们理解,决策者互动的情形。Createsadoublerecordofbanktransactions.Bankreconciliation.导言MovieCricketMovie2,10,0Cricket0,01,23策略策略是博弈中的一组参与人完整的相机的行动计划。这里的“完整的相机计划”是对一个参与人行为的完整描述。它包含了它的每一个决策点上的行为。因为信息集表示的是在博弈中各个参与人的决策点,所以,一个参与人的策略描述的是,在它的每个信息集中,它所做出的决策。3策略例如,在下面的博弈中,你的策略必须包括在所有的节点,即a,c-d,以及e的信息集中,所有选择的行动。即使你打算在节点a选择“留下”,你也必须对上述所有决策进行定义。3策略KKK40,11013,1200,14080,00,0LSPNPNPNR’N’abcdeE例子:该图描述了一个简单的市场博弈。两个厂商为其生产的一种相同的产品,分别选择高价或者低价进行相互竞争。3策略12HLLHH’L’1,10,22,01/2,1/2,正式地说,给定某个博弈。我们用Si来表示参与人i的策略空间。也称为策略集合。即Si包含了参与人i的每一个可能的策略集合。对前一个博弈,参与人1的策略空间S1={H,L}。而参与人2的策略空间是S2={HH’,HL’,LH’,LL’}。我们用小写字母表示单个策略(即这个集合中的一个元素),则si∈Si是博弈中参与人i的一个策略。例如,s1=L,s2=LH’。3策略一个策略组合是关于策略的向量,每一项表示一个参与人。在研究一个有n个参与人的博弈。一个典型的策略组合就是这样一个向量,s=(s1,s2,…,sn)。其中si是参与人i的策略,i=1,2,…,n。S表示策略组合的集合。在数学上表示为S=S1XS2X…XSn。X表示笛卡尔乘积。如果S1={A,B},S2={X,Y},那么,S=S1XS2={A,X),(A,Y),(B,X),(B,Y)}。3策略举个例子,我们看下图的博弈。S1={OA,OB,IA,IB},S2={O,I}请注意,在这个博弈中,参与人1的策略。不仅要定义它在开始时怎么做,还要定义在第二个信息集中,它将采取什么行动。你可能会问,如果参与人1在博弈开始时选择退出,为什么它还要在第二个信息集中,决定该怎么做?3策略211IIOOAB2,21,33,44,2原因一是,出于理性的研究,我们需要的是对于博弈中,任意一点的最优行动的明确评估。这种评估与参与人对彼此的信念有关。原因而在于,万一参与人犯了错误,它们可能会需要一个意外状况下的计划。3策略211IIOOAB2,21,33,44,2另外一个例子,在这个博弈树中,S1={U,D}S2={AC,AE,BC,BE}S3={RP,RQ,TP,TQ}3策略139,2,52,4,40,5,43,0,0UDABRTPQ22,2,21,2,26,3,2CEPQ324标准型标准型是另一种表示博弈的正式方法。在某些情况下,标准型更加简洁,可以优先使用。对于一个用扩展型表示的博弈,每一个策略组合能够告诉我们,该博弈在博弈树中所遵循的路径。同时告诉我们,在博弈结束时,终止点是哪个。与每个终止点相对应的是,各个参与人的收益向量。因此需要注意的是,每一个策略组合,给出了一个收益向量。4标准型对于每一个参与人i,我们可以定义一个函数ui=S→R(该函数的定义域是策略组合的集合,值域是实数)。对于各个参与人所选择的每一个策略组合,s∈S,ui(s)是参与人i在博弈中的收益。这个函数ui称为参与人i的收益函数。4标准型举个例子,我们看下图的博弈。S1={OA,OB,IA,IB},S2={O,I}该博弈的策略组合是S={(OA,O),(OA,I),OB,O),(OB,I),(IA,O),(IA,I)(IB,O),(IB,I)}参与人i的收益是定义在S之上的。因此,当博弈采取策略组合s时,ui(s)给出了参与人i在博弈中的收益。例如,u1=(OA,O)=2,u1(IA,I)=4,u2(IA,O)=34标准型211IIOOAB2,21,33,44,2对于各参与人具有的策略数量有限的两方博弈,表示各参与人的策略空间的一种简便方法,是画出它们的收益矩阵。矩阵的每一行对应参与人1的一个策略。而每一列对应参与人2的一个策略。4标准型1\2IOOA2,22,2OB2,22,2IA4,21,3IB3,41,3囚徒的困境。警察逮捕了两个嫌疑犯,警察拥有的证据只能证明他们犯了较轻的罪。警察分别把他们关在不同的房间。每个囚犯都被要求高发另一个囚犯。告发对应于策略D(背叛),不告发对应于策略C(指合作)。囚犯被告知,如果他们选择告发,将被免罪。他们的证据将被用于给对方定罪。如果他们都选择告发,他们都将入狱。但是他们的刑期由于合作将会较短。4标准型局中人:两个嫌疑犯。行动:每个嫌疑犯的行动集是{沉默,告密}偏好:嫌疑犯1的行动组合序列是(最好到最差):(告密,沉默),(沉默,沉默),(告密,告密),(沉默,告密);嫌疑犯2的是:(沉默,告密),(沉默,沉默),(告密,告密),(告密,沉默)4标准型嫌疑犯1\2沉默告密沉默2,20,3告密3,01,1我们研究囚徒的困境的重要性,不在于想了解囚徒的动机,而在于许多其他的情形,都具有类似的结构。每当两个局中人的