运筹学-博弈论.

第一章博弈论对策论在经济学上称为博弈论。1例子对策是由多个决策者分别决策，竞争场合下的决策。群决策：多个决策者协商，共同决策。对策的特点：（1）有竞争多方（2）每方有多种选择（3）对方要出的策略不知道。理性假设：各局中人以最优计算为目标，且有精确计算的能力,不会犯错误，并且也相信其它局中人不会犯错误。例1：囚徒困境甲坦白甲抵赖乙坦白-8，-80，-10乙抵赖-10，0-1，-1Nash均衡：（坦白，坦白）该模型用于解释其它问题：物价改革时：抢购与不抢购，大家都去抢购，形成抢购风。美、苏军备竞赛：造与不造，双方都选“造”，导致军备竞赛升级。人民公社，出工社员：做与偷懒。囚徒困境：博弈双方实力对称。银行挤兑的原因和预防储户甲乙存款各100万定期一年，银行用200万投资一个好项目，一年后收益共300万，付甲乙各120万，银行提前收回资金被罚款，只退140万。储户甲乙提前取款，银行必须尽可能退100万。储户乙提前取款到期取款储户甲提前取款（70，70）（100，40）到期取款（40，100）（120，120）预防：1银行资金来源多元化2良好的业绩3掌握相当比例的备用金否则银行挤兑导致银行破产。智猪博弈按铃有10单位猪食进入槽，按铃者付出“劳动”为2单位如果小猪按铃，则大猪先到，大猪可吃9单位，小猪1单位如果大猪按铃，则小猪先到，小猪可吃4单位，大猪6单位如果大小猪同时按铃，则大小猪同时到，大猪可吃7单位，小猪3单位小猪按铃等待大猪按铃（5，1）（4，4）等待（9，-1）（0，0）铃槽大猪，小猪看小猪：无论大猪是按铃或者等待，小猪最好是等待。看大猪：既然小猪最好是等待，大猪最好是按铃。例2：智猪博弈：（博弈双方实力不对称），大、小猪同在一猪圈，跑一段距离（花费成本）按动按钮，食槽才会流出部分食物，大猪吃得快，小猪吃得慢。小猪按等待大猪按5，14，4等待9，-10，0Nash均衡：（大猪按，小猪等待）买股票：大户收集信息，推动价格，监督经营，散户跟大户。广告：大企业研究新产品，打广告，小企业不打广告，不研制新产品，搞假帽伪劣。为什么大股东挑起监督经理的重任？（智猪博弈的例子）投资1亿元的大股东可能因为公司营运好，收益增加1000万，监督成本20-50万他能够承担。小股东可能因为公司营运好，收益增加2万，监督成本20-50万他能够承担吗？例3：性别战（先动优势）女足球芭蕾男足球2，10，0芭蕾0，01，2男先买票，去看足球，女先买票，去看芭蕾。在一个海滩上,均匀分布着许多日光浴旅游者,有两位卖饮料的,问他们应分布在什么位置才能使他们离所有游客最近?商店离我们最近吗?商店均匀分布吗?在解放碑,重百和新世纪都曾有两家分店.为什么银行离我们很近?因为银行业务单一,我们去银行一定是存取款,而去商店不知道买什么,需要更大的开店成本.实际上,如果全市只有一家银行,存款少不了.2．纳什均衡2．1基本概念局中人：参与人。局中人的特征：有决策权；与得失有关。*与得失无关的，如A队与B对打足球,只有不是打假球,得失与裁判无关，囚徒困境中的警察，不叫局中人。*得失利益完全一致的参加者，可视为一个局中人。策略（战略）：博弈方可选择的行为或行为组。支付（赢得）：博弈方得到或失去的效用。战略式表示：静态博弈例:房地产开发(a)高需求情况开发商B开发不开发开发开发(4000,4000)(8000,0)商A不开发(0,8000)(0,0)(b)低需求情况开发商B开发不开发开发开发(-3000,-3000)(1000,0)商A不开发(0,1000)(0,0)扩展式表示：动态博弈,参与人有多个选择阶段开金矿:乙不借(1,0)借|甲分(2,2)不分|乙不打(0,4)打|(1,0)均衡：博弈各方在理性假设下选择的结果。2.2纳什均衡设s=(s1,…,si,…,sn)为战略组合，令s-i=(s1,…,si-1,si+1…,sn)为除了第i人的战略外其它人的战略。定义：有n个参与人的博弈G=(S1,…,Sn;u1,…,un),战略组合s*=(s1,…,si…,sn)是一个纳什均衡，如果对于每一个i,是给定其他参与人的最优战略，即：ui()≧ui()siSi,i用另一种表达形式，是下述最大化问题的解：ui(…,),i=1,2,…,n**,iiss*,iiss*ismaxarg*is**1*1,...,,,niiissss,*1s用划线法求纳什均衡：044053400453353566(6,6)是纳什均衡。3纳什均衡应用举例3.1二人零和博弈纳什均衡在二人零和博弈情形，表现为极大极小均衡。minA=Max9263214321603101942381631028minA=Max926I为保险，求各的最差赢得，若出，最差得-8，或说I若出，II最多赢得8，若出，I最差得2，或说I若出，II最多赢得-2，等等。I各策略的最差赢得为：-8，2，-10，-3，最好选择是2。II各策略的最多支付为：9，2，6，最少支付是2，故2是公共选择，对应于划双线情形。Maxminaij=max{-8,2,-10,-3}=2,Minmaxaij=min{9,2,6}=2，故纳什均衡是（。32143216,60,03,310,101,19,94,42,23,38,81,16,63,310,102,28,8)2,21943年,在太平洋战场,盟军围住日军的一股部队,日军增援,盟军围点打援.日军可能走北线和南线,盟军则应决定走北线或南线进行追击轰炸.已知有效轰炸天数为三天.如果日军走北线,盟军也走北线,由于阴天影响一天轰炸,有效轰炸2天.如果日军走北线,盟军也走南线,盟军由于走错路没有遇上日军,再返回北线耽误1天,阴天掩护又耽误1天,有效轰炸1天;如果日军走南线,盟军也走北线,盟军追击耽误1天,有效轰炸2天;如果日军走南线,盟军也走南线,有效轰炸3天.问双方应如何决策?1943年，盟军轰炸日军增援部队。双方均知天气,均知对方可能的策略日军山本五十六策略走北线（阴天）走南线（晴天）盟军肯策尼略将军走北线（阴天）轰炸2天轰炸2天走南线（晴天）轰炸1天轰炸3天盟军：首先考虑每个策略至少能赢多少，然后选最有利的策略日军：首先考虑对方每个策略至多会损失多少，然后选损失最少的策略基本思路：从最坏处着想，去争取最好的结果MaxMinaij=MinMaxaij=a11=2《决策模型》之九：博弈及其应用历史事实：有效轰炸2天如果日军走北线,最多遭轰炸2天;如果走南线,最多3天;因此决定走北线.盟军走北线,最少遭轰炸2天;如果走南线,最少1天;因此决定走北线.例2：minA=Max1625Maxminaij=max{-8,2,-3,-3}=2,Minmaxaij=min{16,2,5}=2，故纳什均衡是（,a22既是所在行的最小元素，又是所在列的最大元素。321432150331164238173328)2,24．混合策略均衡：有些博弈没有纳什均衡。例：社会福利博弈，参与人：政府和流浪汉。流浪汉的战略：找工作或游荡，政府战略：救济或不救济。寻找工作游荡救济3，2-1，3不救济-1，10，0用划线法可知此博弈不存在纯策略均衡。媒体对捐助和信息传达的作用:(增大基数，愿意捐助的人很少，如1%，这就要求增加基数。只要媒体传达信息,必然有人响应。如身份证更换，一人20元，全国300亿。增大捐助比例：如在深圳关口乞讨。)西南女大学生卖生陈易卖身救母.2005年9月15日,某网站出现一张帖子:“我多么希望有好心人能救救我妈妈啊！我宁愿卖掉我自己！甘愿毕业后无条件地为他\她打工,我用我的人格和尊严担保”。报道：“女大学生为救重病母亲欲“卖自己”。引起了大家的广泛关注和讨论。回复也铺天盖地而来，质疑者有之、同情者有之、不怀好意者有之、趁火打劫者也有之。20岁的戏剧影视文学专业大三女生陈易。重庆时报、重庆晚报争相报道。社会为陈易捐助十几万善款，但陈易母亲并没有马上进行手术。深圳网民八分斋、金官人开始进行调查，指陈易存在欺骗成分，在善款的使用上存在挥霍现象。质疑一：陈易母亲是检察院的职工，她母亲的第一次手术费用30万，医保机构支付15万，同事募捐两万多。进行第二次手术，还需要30万，医保能再支付15万元。质疑二：陈易的发型是需要几百元才能做出的新潮烫发，穿的是500元一双的耐克牌运动鞋，戴的是500元的隐形眼镜。核实：陈易这样解释：“今年8月30日，一家美发屋搞宣传活动让我做模特，送的烫头。隐形眼镜和鞋是我两三年前买的”质疑三：陈易公布的是她的个人账户，所有捐款的使用和管理都只需陈易和母亲自行决定。质疑四：并非真“卖身”，是为了募集到更多钱的噱头。“4总裁向女大学生抛职位陈易坦言经历是财富”陈母为女儿仓促上手术台，死于手术中，有人指责八分斋逼死陈母。陈易捐出余款七万余元。启示:只要愿意挂个牌子说收钱,就有络绎不绝的人来交钱.收得越多越有人来.开会,每人300元,一天能收60000多元.街边乞讨:每月保底2000.把香港围起来,进来一个500元,去的人很多.钱收得越多,说明来的人越高档.街边的茶楼,就给你一杯水,一个凳子,去的人很多,收钱越多越高档.为了扩充纳什均衡的概念，引入混合策略概念：P396定义：设有矩阵对策G={S1，S2，A}，其中S1={α1，α2，…,αm-1,αm},S2={β1,β2,…,βn},A=(aij)mn,记：S={（x1,x2,…,xm）|xi0,x1+x2+…+xm=1}S={（y1,y2,…,yn）|yi0,y1+y2+…+yn=1}称S和S为局中人I和II的混合策略集，称（x1,x2,…,xm），（y1,y2,…,yn）为混合策略。S1={α1，α2，…,αm},（x1,x2,…,xm）S2={β1,β2,…,βn},（y1,y2,…,yn）*1*2*1*2例：社会福利博弈，参与人：政府和流浪汉。流浪汉的战略：找工作或游荡，政府战略：救济或不救济。寻找工作游荡救济3，2-1，3不救济-1，10，0用划线法可知此博弈不存在纯策略均衡。定义政府的混合策略为：=（θ，1-θ），定义流浪汉的混合策略为：=（γ，1-γ）政府的期望效用函数为：EG（，）=3θγ+（-1）θ（1-γ）+（-1）（1-θ）γ+0（1-θ）（1-γ）=3θγ-θ+θγ-γ+θγ=5θγ-θ-γGLGL法国人享受生活是出了名的。每年夏天，因为很多人外出度假，法国医院的床位减少，政府部门也精兵简政，甚至人去楼空。法国44岁男子提尔里·F在24年里从未工作过一天，但他却靠着政府的福利救济一直过着神仙般的滋润生活。他开一辆黑色阿尔法·罗米欧豪华跑车，在他18岁后的整个26年的成年生活中，只工作了31个月，其余24年一直靠吃政府救济生活。数年前，若斯潘搞的35小时工作制，至少是法国近十年来最大的经济失策了。一眨眼的功夫，法国的劳动力成本就增高了10%，也就是说竞争力丧失了10%！可是就业又改善了多少呢？有1%至2%吗？一切福利待遇，员工的数目也一样，都有刚性，给（雇）的时候真像坐滑梯那么容易，要想收回来（或解雇），可就难于上青天了。让资方多雇工，他们怎么可能轻易上当呢？有人说，如果没有三天两头的罢工和名目繁多的税收，法国会是世界上最美好的国家。法国是典型的高福利、高税收国家，由于企业国有化程度很高带来的效率低下，经济长期处于滞缓状态。低迷的经济要维持高福利只能靠税收，各种税加起来最高税率达64％。高税收反过来又增加了企业负担，形成恶性循环。但是法国人已经习惯了一年长达50天的付薪假期和每周35小时的工时，习惯了遭解雇可获60％工资。任何挥刀削减福利的政府都会惨遭暴风骤雨的打击，媒体将法国政府的改革遭遇归纳为“改革—争议—示威—骚乱—收回”这一模式。例:两个儿童手里各拿一枚硬币，决定要显示正面向上还是反面向上。如果两枚硬