1、第二部分非合作博弈理论 第二章第二章 策略型博弈策略型博弈第三章第三章 扩展型博弈扩展型博弈第四章第四章 贝叶斯博弈贝叶斯博弈第五章第五章 动态贝叶斯博弈动态贝叶斯博弈 第一节第一节 策略型博弈的表示策略型博弈的表示第二节第二节 重复剔除严格劣策略均衡重复剔除严格劣策略均衡第三节第三节 纳什均衡纳什均衡第四节第四节 混合策略纳什均衡混合策略纳什均衡第五节第五节 纳什均衡的存在性纳什均衡的存在性 策略型策略型(标准型）表述标准型）表述 适合表示静态博弈适合表示静态博弈扩展型表述扩展型表述 适合表示动态博弈适合表示动态博弈 一、策略型博弈的含义一、策略型博弈的含义 完全信息静态博弈又称为策略型博弈
2、完全信息静态博弈又称为策略型博弈。完全信息完全信息是指是指局中人对自己与其他局中人的所有与博弈有关的事前信息局中人对自己与其他局中人的所有与博弈有关的事前信息（策略空间、支付函数等）有充分的了解（策略空间、支付函数等）有充分的了解(局中人的支付函局中人的支付函数是共同知识数是共同知识)。静态博弈静态博弈是指在博弈中，局中人同时采取是指在博弈中，局中人同时采取行动，或者局中人的行动有先有后，但后行动者不能知道行动，或者局中人的行动有先有后，但后行动者不能知道先行动者的行动选择。先行动者的行动选择。二、策略型博弈的三个要素：二、策略型博弈的三个要素：1 1、局中人（、局中人（Players):1,
3、2,nPlayers):1,2,n；2 2、策略（、策略（Strategies):Strategies):;3 3、支付函数、支付函数 （Payoff Payoff functions)functions)表示为：表示为：niSsii,.,2,1,.,;,.,11nnuuSSG 1 1、有限博弈：、有限博弈：(1)(1)博弈中局中人人数有限博弈中局中人人数有限;(2)(2)每个局中人只有有限个策略。每个局中人只有有限个策略。2 2、零和博弈：、零和博弈：博弈中局中人所获支付之和为零，即一方博弈中局中人所获支付之和为零，即一方所得为另一方所失。所得为另一方所失。1 1、局中人、局中人：甲，乙：甲
4、，乙2 2、策、策 略略：坦白坦白,不坦白不坦白 3 3、支付函数、支付函数支付矩阵支付矩阵（双人有限博弈）（双人有限博弈）每个位置上第一个数字表示局中人每个位置上第一个数字表示局中人1 1在对应的策略组在对应的策略组合中得到的支付，第二个数字表示局中人合中得到的支付，第二个数字表示局中人2 2的相应所的相应所获支付。获支付。乙甲SS 乙乙 甲甲坦白坦白不坦白不坦白坦白坦白-6-6，-6-6-1-1，-8-8不坦白不坦白-8-8，-1-1-2-2，-2-2 乙乙 甲甲石头石头剪刀剪刀布布石头石头0 0，0 01 1，-1-1-1-1，1 1剪刀剪刀-1-1，1 10 0，0 01 1，-1-1
5、布布1 1，-1-1-1-1，1 10 0，1 1 田忌田忌 齐王齐王上中下上中下上下中上下中中上下中上下中下上中下上下上中下上中下中上下中上上中下上中下3 3，-3-31 1，-1-11 1，-1-11 1，-1-1-1-1，1 11 1，-1-1上下中上下中1 1，-1-13 3，-3-31 1，-1-11 1，-1-11 1，-1-1-1-1，1 1中上下中上下1 1，-1-1-1-1，1 13 3，-3-31 1，-1-11 1，-1-11 1，-1-1中下上中下上-1-1，1 11 1，-1-11 1，-1-13 3，-3-31 1，-1-11 1，-1-1下上中下上中1 1，-1-
6、11 1，-1-11 1，-1-1-1-1，1 13 3，-3-31 1，-1-1下中上下中上1 1，-1-11 1，-1-1-1-1，1 11 1，-1-11 1，-1-13 3，-3-3 局中人局中人：男，女：男，女 策策 略略：男：看足球，看芭蕾：男：看足球，看芭蕾 女：看足球，看芭蕾女：看足球，看芭蕾 支付矩阵支付矩阵：见下一页：见下一页 女女 男男足球足球芭蕾芭蕾足球足球3 3，2 21 1，1 1芭蕾芭蕾-1-1，-1-12 2，3 3一、基本思想：一、基本思想：如果一个局中人在任何情况下从某种策略中得到的支付如果一个局中人在任何情况下从某种策略中得到的支付均小于从另一种策略中得到
7、的支付，那么显然对他而言，前均小于从另一种策略中得到的支付，那么显然对他而言，前一种策略劣于后一种策略。一种策略劣于后一种策略。从个人利益出发，被剔除的策略不会被局中人采用。从从个人利益出发，被剔除的策略不会被局中人采用。从而可以利用剔除严格劣策略的概念来简化博弈局势，可能会而可以利用剔除严格劣策略的概念来简化博弈局势，可能会得到博弈的解。得到博弈的解。,如果存在如果存在 ，对于所有的，对于所有的都有都有 且其中至少有一个为严格不等式且其中至少有一个为严格不等式 ，则称，则称 是第是第i i个个局中人的一个局中人的一个严格劣策略严格劣策略。iiSs iiSs ),.,.(),.,.(11111
8、1niiiniiiSSSSSsssss),(),(iiiiiissussu is 1 1、根据、根据理性的局中人不会选择严格劣策略理性的局中人不会选择严格劣策略这一原则，可这一原则，可以通过重复剔除严格劣策略的方法对博弈进行求解。以通过重复剔除严格劣策略的方法对博弈进行求解。2 2、其方法是其方法是：对每个局中人寻找严格劣策略，由于它不：对每个局中人寻找严格劣策略，由于它不会被局中人选择实施，所以找到一种后就可以将其从博弈会被局中人选择实施，所以找到一种后就可以将其从博弈局势中剔除，从而得到一种新的缩减后的博弈局势，对这局势中剔除，从而得到一种新的缩减后的博弈局势，对这种新局势重复上述过程，直
9、到无法找到新的严格劣策略为种新局势重复上述过程，直到无法找到新的严格劣策略为止止。对局中人甲而言，无论局中人乙采取何种策略，对局中人甲而言，无论局中人乙采取何种策略，采用采用“不坦白不坦白”策略得到的支付都小于采用策略得到的支付都小于采用“坦坦白白”策略。局中人甲的策略。局中人甲的“不坦白不坦白”策略严格劣于策略严格劣于“坦白坦白”策略策略.“不坦白不坦白”策略都是一种严格劣策略，从而可策略都是一种严格劣策略，从而可以剔除。博弈中局中人各自从自身利益出发的理以剔除。博弈中局中人各自从自身利益出发的理性选择（博弈均衡解）就是性选择（博弈均衡解）就是（坦白，坦白）（坦白，坦白）。乙乙 甲甲坦白坦白
10、不坦白不坦白坦白坦白-6-6，-6-6-1-1，-8-8不坦白不坦白-8-8，-1-1-2-2，-2-2 乙乙 甲甲坦白坦白不坦白不坦白坦白坦白-6-6，-6-6-1-1，-8-8 乙乙 甲甲坦白坦白坦白坦白-6-6，-6-6 乙乙 甲甲左左中中右右上上1 1，0 01 1，2 20 0，1 1下下0 0，3 30 0，1 12 2，0 0 乙乙 甲甲左左中中右右上上1 1，0 01 1，2 20 0，1 1下下0 0，3 30 0，1 12 2，0 0 乙乙 甲甲左左中中上上1 1，0 01 1，2 2下下0 0，3 30 0，1 1 乙乙 甲甲左左中中上上1 1，0 01 1，2 2 乙乙
11、 甲甲中中上上1 1，2 21 1、每一步剔除需要局中人间相互了解的更进一步假定，、每一步剔除需要局中人间相互了解的更进一步假定，如果我们把这一过程应用到任意多步，需要假定如果我们把这一过程应用到任意多步，需要假定“局中人局中人是理性的是理性的”是共同知识。是共同知识。2 2、这一方法对博弈结果的预测经常是不准确的、这一方法对博弈结果的预测经常是不准确的.乙乙 甲甲石头石头剪刀剪刀布布石头石头0 0，0 01 1，-1-1-1-1，1 1剪刀剪刀-1-1，1 10 0，0 01 1，-1-1布布1 1，-1-1-1-1，1 10 0，1 1 乙乙 甲甲左左中中右右上上0 0，4 44 4，0
12、05 5，3 3中中4 4，0 00 0，4 45 5，3 3下下3 3，5 53 3，5 56 6，6 6F大多数的博弈局势中使用剔除严格劣策略的大多数的博弈局势中使用剔除严格劣策略的方法能够对博弈局势进行简化，但可能得不方法能够对博弈局势进行简化，但可能得不到博弈的均衡解。到博弈的均衡解。F需要引入非合作博弈理论中的核心概念需要引入非合作博弈理论中的核心概念 纳什均衡纳什均衡 (Nash EquilibriumNash Equilibrium)。一、纳什均衡的思想一、纳什均衡的思想 “双赢双赢”或或“多赢多赢”它是关于博弈结局的一致性预测它是关于博弈结局的一致性预测 如果所有局中人预测一个
13、特定的纳什均衡会出如果所有局中人预测一个特定的纳什均衡会出现，那么这种均衡就会出现。现，那么这种均衡就会出现。只有纳什均衡才能使每个局中人均认可这种结只有纳什均衡才能使每个局中人均认可这种结局，而且他们均知道其他局中人也认可这种结局。局，而且他们均知道其他局中人也认可这种结局。1 1、博弈的纳什均衡博弈的纳什均衡是这样一种最优策略组合，是这样一种最优策略组合，是一种你好、我好大家都好的理性结局，其中每是一种你好、我好大家都好的理性结局，其中每一个局中人均不能也不想单方面改变自己的策略一个局中人均不能也不想单方面改变自己的策略而增加收益，每个局中人选择的策略是对其他局而增加收益，每个局中人选择的
14、策略是对其他局中人所选策略的最佳反应。中人所选策略的最佳反应。2 2、数学定义：、数学定义：在策略型博弈在策略型博弈 中，如果对于每个局中，如果对于每个局中人中人i i，存在，存在 ，都有，都有 或或 则称策略组合则称策略组合 是此博弈是此博弈G G的一个的一个纳什均衡纳什均衡。iiSs iiiiiiiiSsssussu),(),(),.,(1nss,.,;,.,11nnuuSSG nissusiiiSsiii,.,2,1,),(maxarg1 1、双人有限博弈：双划线法、双人有限博弈：双划线法 首先对局中人首先对局中人2 2的每一个策略，局中人的每一个策略，局中人1 1寻找支付最大寻找支付最
15、大的策略，在其对应支付下划线；的策略，在其对应支付下划线；然后对局中人然后对局中人1 1进行相应的步骤；进行相应的步骤；最后，凡是两个局中人支付下均被划线的结局就是纳最后，凡是两个局中人支付下均被划线的结局就是纳什均衡。什均衡。用双划线法可以求出纳什均衡用双划线法可以求出纳什均衡：（坦白，坦白），（坦白，坦白），（-6-6，-6-6）意义：揭示个人理性与集体理性之间的意义：揭示个人理性与集体理性之间的矛盾矛盾。乙乙 甲甲坦白坦白不坦白不坦白坦白坦白-6-6，-6-6-1-1，-8-8不坦白不坦白-8-8，-1-1-2-2，-2-2 乙乙 甲甲坦白坦白不坦白不坦白坦白坦白-6-6，-6-6-1-
16、1，-8-8不坦白不坦白-8-8，-1-1-2-2，-2-2 乙乙 甲甲坦白坦白不坦白不坦白坦白坦白-6-6，-6-6-1-1，-8-8不坦白不坦白-8-8，-1-1-2-2，-2-2 局中人：大猪，小猪局中人：大猪，小猪 策策 略：大猪：按，等待略：大猪：按，等待 小猪：按，等待小猪：按，等待 支付矩阵：见下一页支付矩阵：见下一页 纳什均衡：纳什均衡：（按，等待）（按，等待）小猪小猪 大猪大猪按按等待等待按按5 5，1 14 4，4 4等待等待9 9，-1-10 0，0 0 小猪小猪 大猪大猪按按等待等待按按5 5，1 14 4，4 4等待等待9 9，-1-10 0，0 0 小猪小猪 大猪大
17、猪按按等待等待按按5 5，1 14 4，4 4等待等待9 9，-1-10 0，0 0 女女 男男足球足球芭蕾芭蕾足球足球3 3，2 21 1，1 1芭蕾芭蕾-1-1，-1-12 2，3 3 女女 男男足球足球芭蕾芭蕾足球足球3 3，2 21 1，1 1芭蕾芭蕾-1-1，-1-12 2，3 3 女女 男男足球足球芭蕾芭蕾足球足球3 3，2 21 1，1 1芭蕾芭蕾-1-1，-1-12 2，3 3 局中人局中人：甲，乙：甲，乙 策策 略略：甲：放左手，放右手：甲：放左手，放右手 乙：猜左手，猜右手乙：猜左手，猜右手 支付矩阵支付矩阵：见下一页：见下一页 没有纳什均衡没有纳什均衡 乙乙 甲甲猜左手猜
18、左手猜右手猜右手放左手放左手-1-1，1 11 1，-1-1放右手放右手1 1，-1-1-1-1，1 1 乙乙 甲甲猜左手猜左手猜右手猜右手放左手放左手-1-1，1 11 1，-1-1放右手放右手1 1，-1-1-1-1，1 1 乙乙 甲甲猜左手猜左手猜右手猜右手放左手放左手-1-1，1 11 1，-1-1放右手放右手1 1，-1-1-1-1，1 12 2、连续性博弈纳什均衡的求法、连续性博弈纳什均衡的求法 首先求出每个局中人对其他局中人策略组合的首先求出每个局中人对其他局中人策略组合的反应函数反应函数即在其他局中人策略组合给定时极即在其他局中人策略组合给定时极大化自己的支付，得到的最佳反应策
19、略表现为其大化自己的支付，得到的最佳反应策略表现为其他局中人策略组合的函数；他局中人策略组合的函数；然后将这些反应函数联立求解即得到博弈的纳然后将这些反应函数联立求解即得到博弈的纳什均衡解。什均衡解。局中人：局中人：厂商厂商1 1，厂商，厂商2 2 策策 略：略：厂商厂商1 1：选择产量：选择产量 厂商厂商2 2：选择产量：选择产量 假假 设：设：价格价格 支付函数支付函数 (利润函数利润函数)：1q2q)(21qqap)(),(211211cqqaqqq)(),(212212cqqaqqq )(),(max2112111cqqaqqqq)(),(max2122122cqqaqqqq02)1(
20、)(),(2*1*12*11211cqqaqcqqaqqq02)1()(),(*11*2*212212cqqaqcqqaqqq 反应函数反应函数:纳什均衡：纳什均衡：)(2121cqaq)(2112cqaq)(31),(31),(21cacaqq221)(91ca 假设两寡头可以串谋，共同确定产量假设两寡头可以串谋，共同确定产量Q Q使总利润最大化，使总利润最大化，利润函数为：利润函数为：(Q)=Q(a-Q-c)(Q)=Q(a-Q-c)总利润最大的产量为：总利润最大的产量为：称为称为契约曲线契约曲线 总利润为：总利润为：比较及含义：比较及含义：)(21caQm)(2121caQQQm2)(41
21、cam221)(92cam)(3221caqqQm Q1 厂商厂商2 2的反应曲线的反应曲线 纳什均衡纳什均衡 契约曲线契约曲线 厂商厂商1 1的反应曲线的反应曲线 O Q2 )(21ca)(21ca)(31ca)(31ca局中人局中人：厂商：厂商1 1，厂商，厂商2 2 策策 略略：厂商：厂商1 1选择价格选择价格 ；厂商；厂商2 2选择价格选择价格假假 设设:两寡头固定成本都为两寡头固定成本都为0 0，边际成本为常数，边际成本为常数c,c,消费者对厂商消费者对厂商1 1和和2 2生产产品的需求量分别为：生产产品的需求量分别为：;1p2p21211),(bppappq12212),(bppa
22、ppq支付（利润）函数：支付（利润）函数：最优化的一阶条件是最优化的一阶条件是:)(),(121211cpbppapp)(),(212212cpbppapp02)()(1(),(2*12*1*11211cbppabppacpppp02)()(1(),(1*21*2*22212cbppabppacpppp 反应函数：反应函数：纳什均衡价格：纳什均衡价格：bcabcapp2,2),(21)(2121cbpap)(2112cbpap 在在n n个局中人的策略型博弈中，个局中人的策略型博弈中，1 1、如果重复剔除严格劣策略剔除掉除策略组合、如果重复剔除严格劣策略剔除掉除策略组合s s以外的以外的所有策
23、略，则这一策略组合所有策略，则这一策略组合s s为该博弈的唯一的纳什均衡。为该博弈的唯一的纳什均衡。2 2、如果策略组合、如果策略组合s s是一个纳什均衡，那么它就不会被重是一个纳什均衡，那么它就不会被重复剔除严格劣策略所剔除。复剔除严格劣策略所剔除。纳什均衡是比重复剔除严格劣策略更强的解概念。纳什均衡是比重复剔除严格劣策略更强的解概念。一、举例说明混合策略纳什均衡一、举例说明混合策略纳什均衡 例例2.82.8 猜左右手游戏猜左右手游戏 乙乙 甲甲（q q）猜左手猜左手（1-q1-q）猜右手猜右手（p p）放左手放左手-1,-1,1 11,1,-1-1（1-p1-p）放右手放右手1,1,-1-
24、1-1,-1,1 1 在甲选在甲选 ，乙选，乙选 这种策略时，这种策略时，他们的期望效用分别为：他们的期望效用分别为：(,1)pp甲(,1)qq乙,)(1)(1)1(1)1(1)(1)(1)4221Eupqpqp qpqpqpq 甲甲乙（,)1(1)(1)(1)(1)(1)(1)14221Eupqpqp qpqpqpq 乙甲乙（甲和乙的目标是甲和乙的目标是:最优化的一阶条件是最优化的一阶条件是:1224),(maxqppqpEup乙甲甲1224),(maxqppqpEuq乙甲乙024),(qppEu乙甲甲024),(pqpEu乙甲乙 混合策略纳什均衡为：混合策略纳什均衡为：2121,2121)
25、,(，乙甲21p21q1 1、混合策略、混合策略（mixed Strategy)局中人局中人 i i 的一个混合策略的一个混合策略 是在其纯策略空是在其纯策略空间间 上的一个概率分布，其中上的一个概率分布，其中 是是 i i 选择策选择策略略 的概率。局中人的概率。局中人 i i的混合策略空间的混合策略空间 是他的所有混合策略是他的所有混合策略构成的集合。构成的集合。纯策略可以理解为混合策略的特例。如纯策略可以理解为混合策略的特例。如 等价于等价于 ),.,(1ikii),.,(1ikiissS)(ijiijsijsi1is)0,.,0,1(i 在混合策略组合在混合策略组合 下，局中人下，局中
26、人 i i的期望效用的期望效用函数为：函数为：其中其中),.,()(),(11),.,(1nijjnjssiiissusEun),(ii),.,.,(111nnni 在策略型博弈在策略型博弈 中，如果对于每中，如果对于每个局中人个局中人 i i，存在，存在 ，都有，都有 或或 则称则称 是博弈是博弈G G的一个的一个混合策略纳什均衡混合策略纳什均衡。iiiiiiiiiiEuEu),(),(),.,(1n,.,;,.,11nnuuSSG niEuiiiiii,.,2,1,),(maxarg 奇数定理奇数定理 (Wilson 1971)(Wilson 1971)：几乎所有的有限博弈：几乎所有的有限
27、博弈都有奇数个纳什均衡。都有奇数个纳什均衡。例例2.112.11 社会保障博弈社会保障博弈 局中人局中人：政府和下岗工人：政府和下岗工人 策策 略略：政：政 府：救济，不救济府：救济，不救济 下岗工人：找工作，不找工作下岗工人：找工作，不找工作 支付矩阵支付矩阵为：为：工人工人 政府政府找工作找工作不找不找救济救济3 3，2 2-1-1，3 3不救济不救济-1-1，1 10 0，0 0 女女 男男足球足球芭蕾芭蕾足球足球3 3，2 21 1，1 1芭蕾芭蕾-1-1，-1-1 定理定理1 1：（Nash,Nash,19501950）每个有限策略型博弈至少）每个有限策略型博弈至少存在一个纳什均衡（
28、纯策略的或混合策略的）。存在一个纳什均衡（纯策略的或混合策略的）。BrouwerBrouwer不动点定理不动点定理：如果：如果X X是非空的有界闭凸集，是非空的有界闭凸集，f(x)f(x)是是X X到自身的连续映射，那么至少存在一个到自身的连续映射，那么至少存在一个x xX X，使得，使得 f(xf(x)=x)=x，x x 称为不动点。称为不动点。KakutaniKakutani不动点定理不动点定理：设设f(X)f(X)是点集是点集X X上的一个集值映射，上的一个集值映射，如果如果X X是非空的有界闭凸集，并且对于所有的是非空的有界闭凸集，并且对于所有的x x X X，f(x)f(x)是非空是
29、非空的、凸的且上半连续的，那么至少存在一个的、凸的且上半连续的，那么至少存在一个x xX X，使得，使得 x xf(xf(x)，x x 称为不动点。称为不动点。1 1、集值映射集值映射：对于集合：对于集合X X上的任何一个点上的任何一个点x x，如果，如果f(x)f(x)给给出唯一的一个点出唯一的一个点y y Y Y，则，则f(x)f(x)称为从称为从X X到到Y Y的映射；如果的映射；如果f(x)f(x)给出给出一个集合一个集合f(x)f(x)Y Y，则，则f(x)f(x)称为从称为从X X到到Y Y的的集值映射集值映射。映射是集值映射的特例。映射是集值映射的特例。2 2、上半连续上半连续：
30、设：设f(x)f(x)是是X X到自身的一个到自身的一个集值映射，如果对集值映射，如果对于所有的于所有的x xX X和包含和包含f(xf(x)的开集的开集V V，都存在，都存在x x 的一个邻域的一个邻域U U，使得对于所有的使得对于所有的x x U U，有，有f(x)f(x)V V，则称，则称f(x)f(x)是上半连续的是上半连续的。定理定理2 2：(Debreu,(Debreu,19521952 ;Glicksberg,1952;Glicksberg,1952 ;Fan,;Fan,1952)1952)在在n n人策人策略型博弈中，如果每个局中人的纯策略空间略型博弈中，如果每个局中人的纯策略
31、空间S Si i是欧氏空间中的一是欧氏空间中的一个非空的有界闭凸集，支付函数个非空的有界闭凸集，支付函数u ui i(s)s)是连续的且对是连续的且对s si i是拟凹的，是拟凹的，那么该博弈存在一个纯策略纳什均衡。那么该博弈存在一个纯策略纳什均衡。定理定理3 3：(Glicksberg,1952)(Glicksberg,1952)在在n n人策略型博弈中，如果每个局人策略型博弈中，如果每个局中人的纯策略空间中人的纯策略空间S Si i是欧氏空间中的一个非空的有界闭凸集，支是欧氏空间中的一个非空的有界闭凸集，支付函数付函数u ui i(s)(s)是连续的，那么该博弈存在一个混合策略纳什均衡。是连续的，那么该博弈存在一个混合策略纳什均衡。
