《扩展式博弈》PPT课件.ppt

《《扩展式博弈》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《扩展式博弈》PPT课件.ppt（50页珍藏版）》请在三一办公上搜索。

1、第二章 扩展式博弈,本章的主要内容,博弈论的启示实际模型与虚拟模型扩展式博弈：完美信息扩展式博弈：不完美信息策略是什么,第一节 博弈论的启示,博弈论主要在两个方面给我们帮助：1、模型它提供了一个研究复杂社会现象的框架，可将其简化为可供分析的模型2、方法它提供了从这些与人们如何采取行动及人们该如何采取行动相关的模型中，总结命题的方法。,参与人是理性的，存在行为的交互作用。,帮助我们理解人们行为的交互作用，及这种作用对结果的影响。,（1）人们并不总是理性的。（2）人们不总是利己的。也存在理他行为。,（1）有限理性可以被引入博弈模型中。（2）支付函数并不只是以金钱衡量，包含了人们心理的主观因素。,适

2、用范围,主要作用,反对者声音,支持者反驳,博弈论提供了对于人们行为背后逻辑的洞察，还处于发展中。,博弈论的四个问题,第二节 实际模型与虚拟模型,实际模型实际模型旨在呈现真实世界，是对真实世界的准确描述，实际模型可能很复杂。虚拟模型虚拟模型是对真实模型的简化，并不一定是对真实模型的准确描述。我们使用虚拟模型尽可能从本质上模仿真实世界，并非复制真实世界。构建虚拟模型决定将哪些因素加入到虚拟模型中，就如同打包行李去大学，你没有办法把所有需要的东西都塞进行李箱。从本质上模仿，就是把最关键的因素加入模型，忽略次要因素。有些时候，忽略次要因素更有助于研究关键因素之间的关系。,虚拟模型的优势举例,a有空气管

3、，b牛顿管(真空)现实中五米高扔铁球和纸片，落地时间不一样。忽略空气阻力，才找到速度和重力之间的关系。忽略空气阻力帮助我们揭示出本质。,神九与天宫一号进行交会对接：研究设计的轨道时要考虑长度、宽度（否），要研究卡口就不能不考虑。根据研究问题决定选择哪些因素，好的模型根据研究的问题选择一些因素加入模型中问题不同，选择的因素也不同。博弈分析中都是虚拟模型，不是真实模型,第三节 扩展式博弈：完美信息,因为博弈论的目的在于推导人们行为的后果，所以一个模型就应该重点关注能够做出决策的个体。在一个关于绑架的例子中，我们重点关注绑架者盖伊和被绑架者奥兰多的妻子薇薇卡，薇薇卡被通知交付赎金。思考问题：盖伊与薇

4、薇卡什么时候采取行动？当他们行动时有哪些可供选择的行动方案？当他们采取行动时知道的信息是什么？,释放,绑架案,扩展式博弈：完美信息绑架案,这个博弈有五种结果：每种结果对应博弈树的一个路径，或者说一系列行动方案。如果盖伊没实施绑架，产生一个结果；如果盖伊实施绑架，产生四种结果。这四种结果分别取决于薇薇卡是否交付赎金与盖伊撕票还是释放。五种结果中盖伊和薇薇卡的偏好不同：表,扩展式博弈：完美信息绑架案,假设盖伊仅仅只是想要得到一笔钱，如果拿不到赎金，出于报复，他会杀害奥兰多。分析盖伊的处境。假设盖伊认为如果奥兰多被杀死，他被逮捕的机会很小，所以倾向于杀掉奥兰多。分析盖伊的处境。假设薇薇卡关心丈夫胜过

5、关心金钱。分析她的处境。,扩展式博弈：完美信息博弈树,分析博弈树是自上而下的（也可以是自左而右的），每一个点被称为决策点，代表在博弈中在某个点某人需要做出选择。从决策点延伸出来的线是一系列分枝，每个分枝代表可供决策者选择的一种行动方案。选择一个分枝就等于选择了一种行动方案。每一个节点为首节点，对应博弈结束的节点为终端节点。在终端节点下列出所有参与者的支付（收益）。一个博弈树只能有一个首节点。,扩展式博弈：完美信息棒球赛,在棒球赛中，有一个众所周知的事实，如右表。现在将要进行比赛的第九局，O队与Y队第八局打成平局。Y队的MR 是右投球手，O队的JL是右击球手。O队的教练正在考虑是否将JL（右击）

6、替换为左击球手JG。他当然希望JG（左击）对阵MR（右投）。但是Y队的教练也可以为了对阵JG（左击），将MR（右投）替换为左投球手RJ（左投）。,扩展式博弈：完美信息审讯伽利略,天主教主乌尔班八世决定是否把伽利略带到宗教法庭进行审问，如果决定要审问伽利略，那么伽利略决定是否承认，而审讯者需要决定采取什么行动。,534,伽利略,扩展式博弈：完美信息买车还价,Macrus为售车老板，Donna为顾客。且PHPMPL如果交易失败，双方收益均为0.如果以价格P成交，Donna的收益为PM-P，Macrus的收益为2(P-PL),扩展式博弈：完美信息买车还价,上述扩展式博弈等同于以下所示的扩展式博弈,马

7、库斯,马库斯,扩展式博弈：完美信息小练习,思考一个包含两个参与者的博弈。在博弈中，父亲可以选择是、否与可能；女儿随后做出选择，她的选择方案有：待在家里和去超市。他们各自的收益如下表所示。以扩展式写出这个博弈。,16,否,Daughter,Daughter,家,家,超市,家,超市,15,第四节 扩展式博弈：不完美信息,在左图中，盖伊在决定杀死还是释放奥兰多之前，知道薇薇卡是否交纳了赎金。（左图）如果盖伊在决定杀死还是释放奥兰多之前，不知道薇薇卡是否交纳了赎金。换言之，盖伊与薇薇卡同时决策。（右图）,释放,释放,释放,杀害,杀害,不支付赎金,支付赎金,扩展式博弈：不完美信息信息集,在节点3和节点4

8、，盖伊需要作出如何对待奥兰多的决策，但他并不知道薇薇卡是否交纳了赎金，换言之，盖伊并不清楚自己处于节点3还是处于节点4。参与人不能区分的所有节点组成的集合，称为信息集。每个节点属于且只属于一个信息集。一个信息集至少包括一个节点。在任意一个扩展是博弈中，采取行动的参与者总是拥有一个信息集，这个信息集表示参与者所知道的博弈状态。所有的信息集只有一个节点的博弈，称为完美信息博弈。至少有一个信息集包含多个节点的博弈，称为不完美信息博弈。,扩展式博弈：不完美信息信息集,在左图中，盖伊在决定杀死还是释放奥兰多之前，知道薇薇卡是否交纳了赎金。信息集都是单节点，是一个完美信息博弈（左图）如果盖伊在决定杀死还是

9、释放奥兰多之前，不知道薇薇卡是否交纳了赎金。节点3和4共同构成一个信息集，这个信息集中包含了两个节点，是一个不完美信息博弈（右图）,杀害,杀害,释放,释放,释放,支付赎金,不支付赎金,扩展式博弈：不完美信息信息集,由于盖伊与薇薇卡同时决策，以下两种形式的扩展式博弈是等价的。本质相同：同一个博弈，有两个阶段，第一阶段盖伊决策，第二阶段盖伊与薇薇卡同时决策。,释放,释放,杀害,杀害,不支付赎金,支付赎金,杀害,释放,支付赎金,支付赎金,不支付赎金,不支付赎金,扩展式博弈：不完美信息抢劫,深夜西蒙走在回家的路上。突然，他意识到背后有人。在他可以采取任何措施之前，他听到：“我有枪，不要喊，把你的手机、

10、电脑和钱包都给我。”西蒙看不到抢，但看到抢匪的手放在口袋里，那里好像有一把手枪。如果没有枪，西蒙认为他可以狠狠地推倒抢匪并成功逃离。但如果抢匪有枪，他的试图逃跑会导致抢匪向他开枪。如果抢匪有枪，西蒙宁愿把东西给他，以免受伤害。之前，抢匪也在考虑，是否带枪。,扩展式博弈：不完美信息陪审团投票,HS与YS分别为案件双方的律师。A、B为HS的法律策略；、为YS的法律策略,X、Y、Z为三名陪审员，他们同时进 行投票。,扩展式博弈：不完美信息伊拉克战争,不检查,检查,扩展式博弈：特征,特征1：每一个节点都是初始节点的后续节点，同时，初始节点是唯一具有这一特征的节点。特征2：除初始节点之外的任何一个节点都

11、只有一个直接前置节点。初始节点没有前置节点。特征3：从一个节点引出的不同分枝具有不同的行动标签。特征4：每一个信息集只包含一个参与人的节点。特征5：每个信息集中所有节点必须具有相同数量的直接后继节点，而且其中的所有节点是通过具有相同集合行动标签的分枝而到达这些后继节点的。,杀害,杀害,释放,释放,释放,支付赎金,不支付赎金,扩展式博弈：错误的信息集举例,扩展式博弈：无限行动的情形,公司1首先决定在广告上投入多少费用，公司2在观察到公司1的行动后，决定退出还是留在这个市场。,若公司1与公司2同时决策采取行动呢？,扩展式博弈：不完美信息小练习,返回到抢劫博弈中，假设劫匪不仅选择是否携带和出示手枪，

12、还选择是否给枪装上子弹。如果西蒙看到劫匪持枪，但不知道枪里是否有子弹。写下这个情境下的扩展式博弈（收益情况可忽略）。,第五节 策略是什么,孙子：是故胜兵先胜而后求战，败兵先战而后求胜。善用兵者，修道而保法，故能为胜败之政。强调策略的重要性。毛泽东：人不犯我，我不犯人；人若犯我，我必犯人，这也是一种策略。现实生活中，经常听到策略这个词，不同学科对策略的概念有不同的定义，这里主要是从博弈论角度谈策略的定义。策略是参与者在博弈中完整详细的决策规则。策略具有完备性。策略考虑到任何一种可能性。不能只考虑部分可能性。策略不是一系列的行动集合，而是一系列的应变计划。一个参与人的策略描述的是，在它的每一个信息

13、集中，它所作出的决策。,策略是什么例子1,一个策略规定了每种情形下参与者选择的行动方案。博弈中，盖伊面临三种情形：是否实施绑架；实施绑架且拿到赎金后，决定释放还是杀害奥兰多；实施绑架且没有拿到赎金后，决定释放还是杀害奥兰多。他各有两种选择，所以他共有8种策略：(绑架,释放,杀害)；(绑架,释放,释放)；(绑架,杀害,释放)；(绑架,杀害,杀害)；(不绑架,释放,杀害)；(不绑架,释放,释放)；(不绑架,杀害,释放)；(不绑架,杀害,杀害),释放,策略是什么例子2,一个策略规定了每种情形下参与者选择的行动方案。在这一博弈中，盖伊面临两种情形：是否实施绑架；实施绑架且不知道是否拿到赎金后，决定释放

14、还是杀害奥兰多；每种情形下，他都有两种选择，所以他共有4种策略：（绑架，释放）；（绑架，杀害）；（不绑架，释放）；（不绑架，杀害）。,释放,释放,杀害,杀害,不支付赎金,支付赎金,策略是什么例子3,K有3个信息集（a,c-d,e）,在每个信息集中都有两种选择，所以K有8种策略，分别为（L,P,R）,(L,P,N),(L,N,R),(L,N,N),(S,P,R),(S,P,N),(S,N,R),(S,N,N)E有1个信息集，有两种选择，所以E有两种策略，分别为P与N。,策略是什么策略集合（定义）,由参与人i的所有策略组成的集合，称为参与人i的策略空间，也称为策略集合，记为Si。我们用小写字母表示

15、单个策略（即这个集合中的一个元素），则 是博弈中参与人i的一个策略。例如：盖伊的策略集合为SG=（绑架，释放）；（绑架，杀害）；（不绑架，释放）；（不绑架，杀害）。（绑架，释放）（绑架，释放）；（绑架，杀害）；（不绑架，释放）；（不绑架，杀害），一个元素。,策略是什么策略集合（举例）,盖伊的策略集合为（绑架，释放，杀害）；（绑架，释放，释放）；（绑架，杀害，释放）；（绑架，杀害，杀害）；（不绑架，释放，杀害）；（不绑架，释放，释放）；（不绑架，杀害，释放）；（不绑架，杀害，杀害）薇薇卡的策略集合为支付赎金，不支付赎金,释放,策略是什么策略集合（举例）,K有3个信息集（a,c-d,e）,在每个信

16、息集中都有两种选择，所以K有8种策略，K的策略集合应该包含8个元素。SK=（L,P,R）,(L,P,N),(L,N,R),(L,N,N),(S,P,R),(S,P,N),(S,P,N),(S,N,R),(S,N,N)SE=P,N,策略是什么策略集合（举例）,S1=U,D；S2=(A,C),(A,E),(B,C),(B,E)S3=(R,P),(R,Q),(T,P),(T,Q),策略是什么策略组合（定义）,一个策略组合是关于策略的向量，每一项表示一个参与人的策略。在研究一个有n个参与人的博弈时，一个典型的策略组合就是这样一个向量，S=(S1,S2,Sn)。其中Si是参与人i的策略，i=1,2,n.

17、S表示策略组合的集合。在数学上表示为：S=S1XS2XS3XXSn。X表示笛卡尔乘积。如果 S1=A,B,S2=X,Y那么笛卡尔乘积：即两个集合中的元素两两组合。S-S1XS2=(A,X),(A,Y),(B,X),(B,Y)策略组合不同于策略集合：策略集合中的所有元素都属于同一个参与者的；策略组合中每一个元素分别属于不同的参与者。,策略是什么策略组合（举例）,(绑架,释放,杀害),支付赎金；(绑架,释放,释放),支付赎金；(绑架,杀害,释放),支付赎金；(绑架,杀害,杀害),支付赎金；(不绑架,释放,杀害),支付赎金；(不绑架,释放,释放),支付赎金；(不绑架,杀害,释放),支付赎金；(不绑架

18、,杀害,杀害),支付赎金；(绑架,释放,杀害),不支付赎金；(绑架,释放,释放),不支付赎金；(绑架,杀害,释放),不支付赎金；(绑架,杀害,杀害),不支付赎金；(不绑架,释放,杀害),不支付赎金；(不绑架,释放,释放),不支付赎金；(不绑架,杀害,释放),不支付赎金；(不绑架,杀害,杀害),不支付赎金；,释放,盖伊的策略集合有8个元素，薇薇卡的策略集合有2个元素，策略组合共有16个：,策略是什么策略组合（举例）,K的策略集合有8个元素，E的策略集合有2个元素，所以该博弈的策略组合共有16个:(L,P,R),P；(L,P,N),P；(L,N,R),P；(L,N,N),P；(S,P,R),P；(

19、S,P,N),P；(S,P,R),P；(S,P,N),P；(S,N,R),P；(S,N,N)P；(L,P,R),N；(L,P,N),N；(L,N,R),N；(L,N,N),N；(S,P,R),N；(S,P,N),N；(S,P,R),N；(S,P,N),N；(S,N,R),N；(S,N,N)N；,策略是什么策略组合（举例）,参与者1的策略集合有2个元素，参与者2与参与者3的策略集合都有4个元素，所以该博弈共有32个策略组合。比如U,(A,C),(R,P)、U,(B,C),(T,P)等等。,策略是什么行动集合（定义）,由参与人i的所有行动组成的集合，称为参与人i的行动集合，记为Ai。我们用小写字母

20、表示单个行动（即这个集合中的一个元素），则 是博弈中参与人i的一个行动。例如：盖伊的行动集合为AG=不绑架，绑架，释放，杀害。绑架 不绑架，绑架，释放，杀害,策略是什么行动集合（举例）,盖伊的行动集合为不绑架，绑架，释放，杀害薇薇卡的行动集合为支付赎金，不支付赎金,释放,策略是什么行动集合（举例）,K的行动集合为L,S,P,N,R,NE的行动集合为P,N,策略是什么行动集合（举例）,参与者1的行动集合为U,D参与者2的行动集合为A,B,C,E参与人3的行动集合为 R,T,P,Q,策略是什么行动组合（定义）,一个行动组合是关于行动的向量，每一项表示一个参与人的行动。在研究一个有n个参与人的博弈时

21、，一个典型的行动组合就是这样一个向量，a=(a1,a2,an)。其中ai是参与人i的行动，i=1,2,n.在博弈中，行动组合是策略组合的结果。换言之，一个策略组合产生一个行动组合。不同的策略组合也可能产生相同的行动组合，反之，不成立。行动组合与行动集合是不同的，行动集合中所有的行动方案都隶属于同一个参与人的，一个行动组合中的每一个元素都代表不同参与人的行动方案。我们主要研究，一个特定的策略组合产生何种行动组合。,策略是什么行动组合（举例）,策略组合(绑架，释放，杀害)，支付赎金产生行动组合绑架，支付赎金，释放策略组合(绑架，释放，释放)，支付赎金产生行动组合绑架，支付赎金，释放不同策略组合产生

22、相同的行动组合策略组合(绑架，杀害，释放)，支付赎金产生行动组合绑架，支付赎金，杀害策略组合(不绑架，释放，杀害)，支付赎金产生行动组合不绑架策略组合(绑架，释放，杀害)，不支付赎金产生行动组合绑架，不支付赎金，杀害策略组合(绑架，释放，释放)，不支付赎金产生行动组合绑架，不支付赎金，释放,释放,策略是什么行动组合（举例）,策略组合(L，P，R)，P产生行动组合L,P,P,R策略组合(L，N，R)，P产生行动组合L,P,N策略组合(L，N，N)，P产生行动组合L,P,N策略组合(S，P，R)，P产生行动组合S,策略是什么行动组合（举例）,策略组合U,(A,C),(R,P)产生行动组合U,A,R

23、策略组合U,(B,C),(T,P)产生行动组合U,B,P策略组合D,(B,E),(T,Q)产生行动组合D,E,作业,作业,1、参与者1先行动，可供选择的行动方案有a、b、c、d。如果参与者1不选择d，那么参与者2选择x或y。参与者2可以观测到参与者1的行动。如果参与者1选择d，那么参与者2选择左或右。列出这个博弈的扩展式（忽略收益值）2、参与者1先行动，可供选择的行动方案有a、b、c。在观测到参与者1的行动后，参与者2选择X或Y。思考以下三种情况下参与者3可以采取什么行动以及当他采取行动时他了解到的信息：A参与者1选择a，参与者3在高、低中选择，他知道参与者2的选择下采取行动。B参与者1选择a

24、，参与者3在高、低中选择，他不知道参与者2的选择下采取行动。C参与者1选择a或b，参与者3在高、低中选择，他知道参与者2的选择、但不知道参与者1的选择下采取行动。,3、市议会正举行有关提高物业税的听证会。假设T女士是听证会的主席，议会的其他两名成员分别是J先生和D夫人。投票程序如下：除了主席，J先生和D夫人同时在纸上写下他们的投票结果：或支持提高物业税，或反对提高物业税。然后市议会的秘书打开纸条，公开宣布投票结果。如果这个秘书报告两个纸条上都是支持，那么实施提高物业税，博弈结束。如果两个纸条上都是反对，那么不实施提高物业税，博弈结束。如果一个人支持，一个反对，那么T女士必须投票。她投票支持，那么实施提高物业税，博弈结束；她投票反对，那么不实施提高物业税，博弈结束。收益：提高物业税，J先生和D夫人均为3。提高物业税失败，D夫人的收益为4，J先生为1。对于T女士，希望提高物业税，但她反对这项提议，当J先生和D夫人都支持这个提议时，她的收益为5；当J先生和D夫人有一人支持、一人反对且投票支持时，她的收益为2。如果不实施提高物业税，她的收益为0（不论她是否投票）。列出博弈扩展式。,