《运筹学第13章 博弈论(20141202版)课件》由会员分享，可在线阅读，更多相关《运筹学第13章 博弈论(20141202版)课件（86页珍藏版）》请在金锄头文库上搜索。
1、运筹学基础,毕德春,辽东学院信息技术学院,一个人的行为总是受到他人行为的影响。人们在追逐自己利益时，难免要与他人发生利益冲突或矛盾。如何克服和解决人们之间的利益冲突？如何才能实现一种既能让每个人都实现自己的利益，又能让每个人都不妨碍和伤害他人利益的互利互惠的和谐局面？,博弈论（game theory）为解决这些问题提供了有力工具。,要想在现代社会做一个有文化的人，你必须对博弈论有一个大致了解。,保罗.萨缪尔森,孙膑与庞涓吃饼,一天鬼谷子想试孙膑与庞涓的智力，鬼谷子拿出5个饼，放在桌上,让他们两人取去吃。鬼谷子说:每人一次最多拿两个饼，并且拿的饼全部吃完后才能再拿。鬼谷子说完后，庞涓赶忙拿了2个
2、饼，而孙膑从容地拿1个饼吃起来，庞涓未吃完两个饼，孙膑已经吃完1个饼，孙膑第二次拿了2个饼，此时桌上已经没有饼了，最后，孙膑吃了三个饼，而庞涓吃了两个饼。在这则典故当中其实隐藏着一条生存法则。,海滩选址博弈,两个竞争者Y和C销售软饮料 日光裕者均匀分布在海滩上 Y和C价格相等 消费者从较近的售点购买饮料,海滩选址博弈,在中国的大城市里，你会发现一个有意思的现象，当你在街边看到一个肯德基后，相距不太远的距离你会发现一个麦当劳,囚徒困境是图克（Tucker）1950年提出的，该博弈是博弈论最经典、著名的博弈。该博弈本身讲的是一个法律刑侦或犯罪学方面的问题，但可以扩展到许多经济问题，以及各种社会问题
3、。,商业竞争策略：广告战,两个公司互相竞争，两个公司的广告互相影响，即一公司的广告较被顾客接受则会夺取对方的部分收入。但若双方同时期发布同等数量的广告，双方收入都增加很少而成本增加。但若不提高广告数量，生意又会被对方夺走。两个公司可以有二选择：1.互相达成协议，减少广告的开支。（合作） 2.增加广告开支，压倒对方。（背叛） 在现实中，要两个互相竞争的公司达成合作协议是较为困难的，多数都会陷入囚徒困境中。,囚徒困境与苏美争霸,在苏美争霸博弈中，美国和前苏联都处于“囚徒困境”中。,智猪博弈 猪圈中有一头大猪和一头小猪，在猪圈的一端设有一个按钮，每按一下，位于猪圈另一端的食槽中就会有10单位的猪食进
4、槽，但每按一下按钮会耗去相当于2单位猪食的成本。如果大猪先到食槽，则大猪吃到9单位食物，小猪仅能吃到1单位食物；如果两猪同时到食槽，则大猪吃7单位，小猪吃3单位食物；如果小猪先到，大猪吃6单位而小猪吃4单位食物。给出这个博弈的支付矩阵。,“智猪博弈搭便车”,股市博弈 在股票市场上，大户是大猪，他们要进行技术分析，收集信息、预测股价走势，但大量散户就是小猪。他们不会花成本去进行技术分析，而是跟着大户的投资战略进行股票买卖，即所谓“散户跟大户”的现象。,为什么中小企业不会花钱去开发新产品？ 在技术创新市场上，大企业是大猪，它们投入大量资金进行技术创新，开发新产品，而中小企业是小猪，不会进行大规模技
5、术创新，而是等待大企业的新产品形成新的市场后生产模仿大企业的新产品的产品去销售。,斗鸡博弈（懦夫博弈）,独木桥,冷战期间美苏抢占地盘，一方抢占一块地盘，另一方就占另一块。 夫妻吵架，一方厉害，另一方就出去躲躲。,斗鸡博弈（懦夫博弈）,石头、剪子、布,利益与道德的博弈,有一群猴子被关在笼子里。在笼子里的上方有一条绳子，绳子拴着一个香蕉，绳子的另一头连着一个水箱。猴子们发现了香蕉，有个猴子跳上去够这个香蕉，当猴子够到时，与香蕉相连的绳子带动了水箱，于是一盆水倒进了笼子。尽管够到香蕉的猴子吃到了香蕉，但其他猴子被淋湿了。吃到香蕉的猴子是少数，而其余的大多数猴子都被淋湿。经过一段时间，有一伙猴子自觉地
6、行动起来，当有猴子去抓香蕉时，它们便揍那个猴子。久而久之，猴子们内部形成了道德约束，再也没有猴子敢去取香蕉了。,博弈论（game theory）：研究利益存在冲突的决策主体在相互依赖的条件下，如何选择适当的策略实施以获得最大利益的思想和方法。,1,2,研究对象不是客观规律，而是带有主动性的人的活动。,最优不是绝对的，而是现有主客观条件下的理想结果。,从游戏到博弈：博弈就是策略对抗，或策略有关键作用的游戏。博弈Game，博弈论Game Theory，Game即游戏、竞技。,博弈是一种普遍现象，人们总会有意、无意地运用博弈的思想。 比如企业在决策时，总是会考虑竞争对手的反应；个人与政府之间 “上有
7、政策，下有对策” ；金融监管与创新犹如“猫鼠博弈”；博弈还作为消遣游戏，让人们获得快乐。 博弈的特征表现为两个或两个以上具有利益冲突的当事人处于一种不相容状态中，一方的行动取决于对方的行动，每个当事人的收益都取决于所有当事人的行动。 当所有当事人都拿定主意作出决策时，博弈的局势便确定下来。 博弈论的目的是要研究人们之间这种不相容的行为，推广标准的一人决策理论。 博弈论关注的问题 在每个当事人的收益都依赖于其他当事人的选择的情况下，追求个人收益最大化的当事人应该如何采取行动？,参与人：博弈论中选择行动以最大化自己效用的决策主体 行动：参与人的决策变量 战略：参与人选择行动的规则 信息：参与人在博
8、弈中的知识，特别是有关其他参与人的特征和行动的知识 支付函数：参与人从博弈中获得的效用水平 结果：博弈分析真正感兴趣的要素的集合 均衡：所有参与人的最优战略的组合 参与人、行动、结果称为博弈规则；博弈分析的目的是使用博弈规则决定均衡。,参与人：博弈论中选择行动以最大化自己效用的决策主体。 可以是自然人，也可以是团体，如企业、国家甚至由若干国家组成的集团（OPEC、欧盟等）。 虚拟参与人：“自然”作为虚拟参与人 自然：指决定外生的随机变量的机制为分析方便引入，自然作为虚拟参与人没有自己的支付和目标函数（即所有结果对它是无差异的） 参与人决策的后果依赖于自然的选择。在不完全信息博弈中，自然选择参与
9、人的类型,四个核心,博弈的参加者(Player),各博弈方的策略(Strategies) 或行为(Actions),博弈的次序(Order),博弈方的得益(Payoffs),交叉分类：以上分类方式的结合，比如二人零和有限博弈。,赢钱与输钱为零和博弈；,工会与厂方达成增加工资的协议双方获得“双赢”。反之，罢工导致“两败俱伤”。,运筹学主要研究的是非合作博弈,“石头、剪刀、布”的游戏；,下棋、打牌等游戏。,战略式表述(strategic form representation)多用矩阵,扩展式表述 (extensive form representation) 多用博弈树,案例：房地产开发项目，假
10、设有A、B两家开发商，市场需求可能大，也可能小，投入需要1亿。,假定市场上有两栋楼出售：需求大时，每栋售价1.4亿；需求小时，每栋售价7千万 如果市场上有一栋楼出售：需求大时，每栋售价1.8亿；需求小时，每栋售价1.1亿,需求大的情况,需求小的情况,完全信息 博弈,B在决策时不确切地知道自然的选择；B的决策结由4个变为2个,A,开发,不开发,N,N,大,小,1/2,1/2,大,小,1/2,1/2,B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(4,4),(8,0),(-3,-3),(1,0),(0,8),(0,0),(0,1),(0,0),不完全信息 博弈,B知道自然
11、的选择，但不知道A的选择（或A、B同时决策）,A,开发,不开发,N,N,大,小,1/2,1/2,大,小,1/2,1/2,B,B,B,B,开发,不开发,开发,不开发,开发,不开发,开发,不开发,(4,4),(8,0),(-3,-3),(1,0),(0,8),(0,0),(0,1),(0,0),不完全信息 博弈,干洗店市场进入博弈的扩展式：新店知道但老店不知道自然的选择-市场需求的大小,一般来说，由于每个参与人的得益是博弈中所有参与人的策略的函数，因此每个参与人的最优策略选择依赖于所有其他参与人的策略选择。但在一些特殊的博弈中，一个参与人的最优策略可能可以不依赖于其他参与人的策略选择，就是说，不论
12、其他参与人选择什么策略，他的最优策略是唯一的，这样的最优策略被称为“占优策略”。,如果一个博弈中，某个参与人有占 优策略，那么该参与人的其他可选择策略就被称为“劣策略”。 在一个博弈里,如果所有参与人都有占优策略存在，那么占优策略均衡是可以预测到的唯一的均衡，因为没有一个理性的参与人会选择劣策略。所以在囚徒困境博弈里，坦白，坦白是占优策略均衡。,如果所有人都有（严格）占优策略存在，那么占优策略均衡就是可以预测的唯一均衡。 占优策略只要求每个参与人是理性的，而不要求每个参与人知道其他参与人是理性的（也就是说，不要求理性是共同知识）。为什么？,思路：首先找到某个参与人的劣策略（假定存在），把这个劣
13、策略剔除掉，重新构造一个不包含已剔除策略的新的博弈，然后再剔除这个新的博弈中的某个参与人的劣策略，一直重复这个过程，直到只剩下唯一的策略组合为止。这个唯一剩下的策略组合就是这个博弈的均衡解，称为“重复剔除的占优均衡”。,“智猪博弈”,4大于1 0大于-1,（R3，C3）是重复剔除的占优均衡,行：没有占优策略 列：C2严格优于C3 剔除 C3,行：C1优于R2 列：无占优策略 剔除 R2,C2优于C1,卑斯麦海之战 卑斯麦海之战发生在1943年的南太平洋上，日本海军上将木村受命将日本陆军运抵新几内亚，其间要穿越卑斯麦海。而美国上将肯尼欲对日军运输船进行轰炸，穿越卑斯麦海通往新几内亚的有两条航线，
14、木村必须从中选一条，而肯尼则必须决定将其飞机派往何处去搜索日军，如果肯尼将他的飞机派到了错误的航线上，他虽可以召回他们，但可供轰炸的天数将减少。,注意：与占优策略均衡中的占优策略和劣策略不同，这里的占优策略或劣策略可能只是相对于另一个特定策略而言。,：在下列策略式表达中，找出重复剔除的占优均衡,纳什均衡（Nash Equilibrium） “Im doing the best I can given what you are doing。Youre doing the best you can given what I am doing.” 给定你的策略，我的策略是最好的策略；给定我的策略，你
15、的策略也是你的最好的策略。即双方在给定的策略下不愿意调整自己的策略。,JOHN F.NASH 美国 (1928- ) 1994年诺贝尔经济奖得主,设想在博弈论预测的博弈结果中，给定每个参与人选定各自的战略，为使该预测是正确的，必须使参与人自愿选择理论给他推到出的战略。这样，每个参与人要选择的战略必须是针对其他参与人选择战略的最优反应，这种理论推测结果可以叫做“战略稳定”或“自动实施”的，因为没有参与人愿意独自离弃他所选定的战略，我们把这一状态就称为纳什均衡。,（R3，C3）是纳什均衡,剔除顺序：R3、C3、C2、R2，战略组合（R1，C1） 剔除顺序：C2、R2、C1、R3，战略组合（R1，C
16、3） 故一般使用严格劣战略剔除，可以看到，（R1，C3） （R1，C1）都是纳什均衡，但在这里是不可解的。,对博弈中的每个策略组合进行分析，考虑在这个策略组合下各个局中人是否能够通过单独改变自己的策略而增加支付。如果能够在对手保持策略不变的情况下，通过单独改变自己的策略选择，形成新的策略组合而增加自己的支付，那么原来的策略组合就不是博弈的具有稳定性的结果，把它排除在均衡之外，剩下没有被排除的就是博弈的纳什均衡。,企业1,企业2,参与人：企业1、企业2 战略： 选择产量 支付： 利润，利润是两个企业产量的函数,qi ：第i个企业的产量 Ci（qi）代表成本函数 P=P（q1+q2）：价格是两个企业产量的函数 第i个企业的利润函数为：,（q1*，q2*）是纳什均衡意味着：,找出纳什均衡的方法是对每个企业的利润函数求一阶导数，使其为0。,q2,q1,
