博弈与策略培训教材(PPT 49页).ppt

1、2014年11月14日,任 光,博弈与策略,二、博弈与策略,一、博弈论的相关概念,三、混合策略纳什均衡,小结,博弈与策略,四、完全信息动态博弈,五、不完全信息博弈,萨缪尔森：你要想在现代社会做一个有价值的人，就必须对博弈论有个大致的了解,一、博弈论的相关概念,没有选择就没有繁荣,有选择 就有优化,一、博弈论的相关概念,有选择 就有博弈,现代社会，时时有选择，处处有博弈,博弈就是优化,石头-剪刀-布,一、博弈论的相关概念,用简单的例子，说明博弈论的解题基本框架与要素,石头-剪刀-布,1. 局中人 2. 策略空间 3. 盈利函数,一、博弈论的相关概念,零和博弈,局中人、策略空间、盈利函数,静态分析

2、 动态分析(博弈思维的分析),A,B,1/2,肯德基很红火,例：海滩小贩,一、博弈论的相关概念,根据博弈论： 决策结果, “麦当劳”就开在肯德基 旁边,用例子，说明博弈论的思维方式,类似的例子,航空公司航班的安排,电视台节目之间的竞争,一、博弈论的相关概念,冯诺依曼和摩根斯顿1944年出版博弈论与经济行为,纳什（John Nash），海萨尼（John C. Harsanyi）泽尔滕（R. Selten）因对博弈论的卓越贡献，1994年获得诺贝尔奖,海萨尼,纳什,泽尔滕,一、博弈论的相关概念,一、博弈论的相关概念,n 人博弈的一般数学表示,局中人: N=1,2，n,策略集: S1,S2，Sn,决

3、策集: DS=S1S2Sn,盈利函数: f1, f2，fn：DR,用一个熟悉的例子，解释博弈的数学表示 田忌赛马,一、博弈论的相关概念,案例：田忌赛马,局中人: N=齐王，田忌,一、博弈论的相关概念,案例：田忌赛马,局中人: N=齐王，田忌,齐王策略集: S齐= (上中下)，(中下上)，(下上中)， (上下中)，(中上下)，(下中上),决策集: DS=S齐S田,盈利函数: f齐(上中下), (下上中)=0 f田(上中下), (下上中)=1,田忌策略集: S田=(上中下)，(中下上)，(下上中)， (上下中)，(中上下)，(下中上),囚徒困境（Prisoners Dilemma）,1.局中人 2

4、.策略空间 3.盈利函数,二、博弈与策略,囚徒困境（Prisoners Dilemma）,5, 5,交代,不交代,交代,不交代,8 , 0,0 , 8,1 , 1,囚徒 1,囚徒2,1. 考虑问题的方法：知人者智,二、博弈与策略,引进记号系统,1. 考虑问题的方法：知人者智,二、博弈与策略,在竞争对手的选择决定后，博弈方选择自己的最好的策略。如果均衡存在，就是纳什均衡。,2.纳什均衡,二、博弈与策略,猜硬币游戏,2.纳什均衡,二、博弈与策略,简单纳什均衡不存在的例子,存在混合纳什均衡,A和B各出一枚硬币,囚徒困境的得益矩阵,2. 纳什均衡,双方都选择交代，是纳什均衡,二、博弈与策略,Cost

5、to press button = 2 units,When button is pressed, food given = 10 units,智猪博弈（boxed pig game）,二、博弈与策略,2.纳什均衡,假设对方选定，选自己收益最大的策略,二、博弈与策略,对某博弈方来说，不管其他博弈方采取什么策略，他所采取的策略，能给他带来最大得益,两家厂商都选择做广告的策略。,3. 上策,二、博弈与策略,3. 上策,小猪有上策，大猪没有上策,二、博弈与策略,搭便车（Free rider），农村修路,多劳不多得，少劳不少得,囚徒困境的得益矩阵,3. 上策,双方都选择交代，也是上策均衡,4.多个纳什

6、均衡的博弈,新兴产业市场,存在两个纳什均衡,博弈双方都没有上策,在给定竞争对手的选择行为后，博弈方选择了自己的最好的策略,5.上策均衡与纳什均衡,每一个上策均衡一定是纳什均衡，但并非每一个纳什均 衡都是上策均衡。上策均衡是纳什均衡的特例。,是纳什均衡，不是上策均衡,二、博弈与策略,5.上策均衡与纳什均衡,6. 极大化极小策略,论语不患人之不己知，患不知人也。,二、博弈与策略,6. 极大化极小策略,在最小得益中求取得益的“最大化”,纳什均衡中的问题,如果博弈方2选择惩罚策略 博弈方1损失巨大,为规避风险，可选择极大化极小策略,存在纳什均衡，博弈方2有上策,6. 极大化极小策略,博弈方1和博弈方2

7、如果都采取极大化极小策略,均衡解就是（1，1）; 而（3，1）是唯一的纳什均衡。,在最小得益中求取得益的“最大化”。,假设对方选我收益最小的策略,假设对方选定，我选自己收益最大的策略,杨佳袭警案,知人者智，不知人者傻,杨佳选择啥策略？,1980年8月27日生，汉族，北京市人。中专文化程度，未婚，无正当职业。,2007年10月5日晚，杨佳骑一辆无牌无证自行车，被民警盘查,督察支队两次赴京对杨佳进行法制宣传和疏导劝解工作,6.极大化极小策略,谁更傻？为啥？,7. tit for tat（对等策略）,定价博弈 “对等策略”：,厂商1定高价，只要对方合作也会定高价 厂商1就会一直保持高价 任何一方定低

8、价，另一厂商也会跟着定低价,7. tit for tat（对等策略）,定价博弈 “对等策略”：,孟子君之视臣如手足，则臣视君如腹心；君之视臣如犬马，则臣视君如国人；君之视臣如土芥,则臣视君如寇仇,君要臣死，臣不死是为不忠；父叫子亡，子不亡则为不孝。,8. 序列博弈,一方在决策时，会考虑到另一方的反应行为，并在此基础上进行自己的当前决策,通过博弈分析，可知厂商1的最佳策略是选择生产少糖型饮料，厂商2则生产多糖型饮料。,9. 不完全信息博弈（贝叶斯均衡）,在位企业 在位企业 默 许 斗 争 默 许 斗 争 进 入 40，50 -10，0 进 入 30，100 -10，140 不进入 0，300 0

9、，300 不进入 0，400 0，400 (a)高成本情况 (b)低成本情况 市场进入博弈,上图的博弈中，在位企业属于高成本类型的企业的概率大于0.2时，潜在企业选择进入才是最优的。,潜在企业,潜在企业,在给定自己类型和对手类型的概率分布的情况下，每个参与者的期望效用达到了最大化，从而没有参与者愿意改变自己的行为或策略。,三、混合策略纳什均衡,纳什均衡回顾,猜硬币游戏,三、混合策略纳什均衡,猜硬币游戏,B 正面 反面 A 正面 -1，+1 +1，-1 r 反面 +1，-1 -1，+1 1-r q 1-q,如果q0.5,局中人A取r=1,局中人A的最佳策略RA(q),期望收益,1-2q,局中人A

10、的期望收益=-1q+1 (1-q)=1-2q,2q-1,如果q0.5,局中人A取r=0,局中人A的期望收益=+1q+(-1)(1-q)=2q-1,三、混合策略纳什均衡,猜硬币游戏,B 正面 反面 A 正面 -1，+1 +1，-1 r 反面 +1，-1 -1，+1 1-r q 1-q,如果q0.5,局中人A取r=1,如果q0.5,局中人A取r=0,局中人A的最佳策略RA(q),如果q=0.5,局中人A取0r1,期望收益,1-2q,2q-1,三、混合策略纳什均衡,猜硬币游戏,B 正面 反面 A 正面 -1，+1 +1，-1 r 反面 +1，-1 -1，+1 1-r q 1-q,如果r0.5,局中人

11、B取q=0,如果r0.5,局中人B取q=1,局中人B的最佳策略RB(r),期望收益,1-2r,2r-1,期望收益,1-2q,2q-1,局中人B的期望收益=-1r+1(1-r)=1-2r,局中人A的期望收益=+1r+(-1)(1-r)=2r-1,三、混合策略纳什均衡,猜硬币游戏,B 正面 反面 A 正面 -1，+1 +1，-1 r 反面 +1，-1 -1，+1 1-r q 1-q,如果r0.5,局中人B取q=0,如果r0.5,局中人B取q=1,局中人B的最佳策略RB(r),如果r=0.5,局中人B取0q1,期望收益,1-2r,2r-1,期望收益,1-2q,2q-1,三、混合策略纳什均衡,猜硬币游

12、戏,B 正面 反面 A 正面 -1，+1 +1，-1 r 反面 +1，-1 -1，+1 1-r q 1-q,A取r=0.5,B最佳对策也是取q=0.5,验证,展开博弈树,四、完全信息动态博弈,四、完全信息动态博弈,. 后退归纳法,市场进入阻挠博弈,姑娘恋爱，父亲干涉,五、不完全信息博弈（贝叶斯均衡）,在位企业 在位企业 默 许 斗 争 默 许 斗 争 进 入 40，50 -10，0 进 入 30，100 -10，140 不进入 0，300 0，300 不进入 0，400 0，400 (a)高成本情况 (b)低成本情况 市场进入博弈,上图的博弈中假定在位企业属于高成本类型的企业的概率大于0.2，潜在企业选择进入才是