矩阵对策.ppt

二人有限零和对策,,,,,§2 纯策略对策,一、纯策略与混合策略纯策略是指确定的选择某策略；而混合策略则指以某一概率分布选择各策略二、纯策略对策的解,1. 引例,,前提： 对策双方均理智,结论： 最不利中选最有利,解：可用下述表格表示上述寻找最优纯策略过程:,,2. 纯策略分析,（1）局中人甲对每个策略si的评价值为,,故局中人甲选择策略模型为：,,（2）局中人乙对每个策略dj的评价值为,,故局中人乙选择策略模型为：,,,3. 纯策略对策模型的解,(1) 鞍点与解,,,,称为对策G 之值例 上例中,对策值V=1,,局中人甲的最优策略为s1 ,,局中人乙的最优策略为d2，,(2) 多鞍点与无鞍点对策,例 设有一矩阵对策如下，求它的解此对策有多个解例： 矩阵对策赢得矩阵如下，试求它的解例：齐王赛马为无鞍点对策,4、优超原理,例：,,例： 用优超原理求解下列对策,,,,,§3 混合策略对策,一、混合策略对策的基本概念,无鞍点对策的求解方法是采用混合策略，混合策略就是局中人考虑以某种概率分布来选择他的各个策略m维概率向量,1．混合策略,,称为局中人甲的一个混合策略，即局中人甲选择策略si的概率为xi 。

同理可定义乙的混合策略例： “剪刀、石头、布” 游戏，若B的混合策略（0.4，0.3，0.3）,则A选“石头”的期望赢得为：,0×0.4 + 1 ×0.3 + (-1)×0.3=0,则A选“剪子”的期望赢得为：,(-1)×0.4 + 0 ×0.3 + 1 ×0.3= - 0.1,则A选“石头”的期望赢得为：,1×0.4 + (-1) ×0.3 + 0×0.3=0.1,若又已知A的混合策略（0.5，0.2，0.3），则A的期望赢得为：,0×0.5 + (-0.1) ×0.2 + 0.1×0.3= 0.01,（同理，B的期望赢得为-0.01）,3．混合局势,当局中人甲选择混合策略x；局中人乙选择混合策略y，称(x,y)为一个混合局势2．混合策略集合,称集合,,为甲的混合策略集合；,,为乙的混合策略集合；,对于一个混合局势(x,y)，用,,表示局中人甲在混合局势(x,y)时的收益期望值4．收益期望函数,,,二、混合策略对策的解,1．混合策略分析,,对于混合策略对策,局中人甲的策略决策模型为：,,,局中人乙的策略决策模型为：,2．混合策略矩阵对策的线性规划解法,若所有aij>0（否则，可取一充分大M>0，使得aij +M>0）， 则可用下述两规划 来求解混合策略：,,（Ⅰ）,（Ⅱ）,例： “剪刀、石头、布” 游戏，,,同理，,第三部分 二人有限非零和对策,一、非零和对策的一般表达,1、局中人集合：i = 1, 2 ,…，n,2、每个局中人的策略集：Si (i = 1,…,n),3、每个局中人的赢得函数：ui (s1, …, s i , … sn),对策的一般表达：G={S1, … Sn ; u1, … un },二、纳什均衡,均衡（Equilibrium）是所有局中人的最优策略的组合，一般记为：,其中，,是第i个局中人在均衡情况下的最优战略，即,（,表示除 i 之外,所有局中人的策略组成的向量。

),占优策略均衡,均衡的层次：,,重复剔除的占优均衡,,（纯策略）纳什均衡,,混合策略纳什均衡,,条件,强,弱,1. 占优策略均衡,考虑“囚犯困境”问题：,不论同伙选择什么策略，每个囚徒的最优策略是“坦白”定义：如果对应所有的,是i的严格最优选择，即,则称,是i的占优策略(Dominant strategy)2. 重复剔除的占优均衡,,考虑智猪博弈问题：,“等待”是小猪的占优战略，而大猪无占优战略劣策略,例：,,,可按如下思路寻找均衡解： 首先找出某个局中人的劣策略（如果存在），剔除该劣策略，得到新的博弈；再剔除该新博弈中的某个中人的劣策略重复进行，直至只剩下唯一的策略组合为止，这个剩下的策略称为重复剔除的占优均衡（Iterated dominance equilibrium）前提假设：“理性”是所有局中人的共同知识 （Common Knowledge）,,,,例：求下面博弈的重复剔除的占优均衡解,,,（均衡解）,,,例：智猪博弈问题：,,,（均衡解）,3. 纳什均衡,例：（夫妇之争）夫妇俩商量晚上去哪里消遣丈夫喜欢看足球比赛，而妻子喜欢去看芭蕾舞表演，夫妇都希望二人同往，不愿分开问题：既不存在占优策略均衡，也不存在重复剔除的占优均衡。

定义：对于博弈 G={S1, … Sn ; u1, … un }，策略组合,如果对于每一个i，,是给,定其它局中人选择,的情况下第i个局中人的最优策略，即,则称该策略组合为一个纳什均衡例：斗鸡博弈（Chicken Game）两个人举着火棍从独木桥的两端走向中央进行火拼每个人都有两种策略：继续前进，或退下阵来若两人都继续前进，则两败俱伤；若一方前进另一方退下来，前进者取得胜利，退下来的丢了面子；若两人都退下来，两人都丢面子赢得矩阵如下表所示Nash均衡：一进一退,,,纳什均衡的哲学意义,表示n个局中人达成的,一个协议，当这个协议可以自动实施（Self-enforcing）时，即没有任何局中人有积极性破坏这个协议，那么这个协议就构成纳什均衡否则，若至少存在某些局中人有积极性偏离这个协议，就构不成纳什均衡例：智猪博弈问题：,例：囚犯困境问题：,,,,例：（夫妇之争）夫妇俩商量晚上去哪里消遣丈夫喜欢看足球比赛，而妻子喜欢去看芭蕾舞表演，夫妇都希望二人同往，不愿分开纳什均衡解： （足球，足球）或（芭蕾，芭蕾）,,解纳什均衡的划线法,设有两个局中人：A和B Step 1: 考虑A，给定B的每一个策略，找出A的最优策略，并在其对应的赢得下面画一横线。

Step 2: 用类似的方法，找出B的最优策略 Step 3: 都画横线的单元格即为纳什均衡例：求纳什均衡,,,,,,,纳什均衡,总结:对矩阵A，按列求最大；对矩阵B，按行求最大零和博弈的鞍点对应于Nash均衡,，,例 考虑零和博弈,，其赢得矩阵为：,，其中,,鞍点,Nash均衡,纳什均衡在经济中的应用举例,公共地的悲剧（Tragedy of the commons） 如果一种资源没有排他性的所有权，就会导致对这种资源的过渡使用 考虑一个有n个农民的村庄共同拥有一片草地，每个农民都有在草地上放牧的自由每年春天，每个农民要决定自己杨多少只羊用gi表示第i个农民饲养的数量，表示总数量；v代表每只羊的平均价值v是G的,因为每只羊至少要一定数量的草才,不至于饿死，有一个最大可存活的数量Gmax : 当,函数：,G0； 当G≥Gmax时，v(G)=0当草地上的羊很少时，增加一只羊也许不会对其它羊的价值有太大的不利影响，但随着饲养量的不断增加，每只羊的价值会急剧下降，因此：,在该博弈中，每个农民的问题是选择gi以最大化自己的利润设购买每只羊的价格为c，则利润函数为：,最优化的条件为：,上述n个优化函数的交叉点就是纳什均衡。

可以证明，纳什均衡的总饲养量大于社会最优的饲养量具体示例：设n=3，设每只羊的利润函数为,，设c =4,则3个农民的利润函数分别为：,,带入利润函数得,结论: (1)Nash均衡条件下，养羊总数24×3= 72，总利润 576×3=1728；（2）总利益最大条件下：养羊总数48，总利润 23044. 混合策略的纳什均衡,问题的提出——纯策略意义下，有可能不存在纳什均衡,例：小偷与守卫的博弈（泽尔腾，1996） 一小偷欲偷窃有一守卫看守的仓库，如果小偷去偷窃时守卫在睡觉，则小偷就能得手，否则要被抓住假设小偷得手可偷得价值为V 的赃物，若被抓住坐牢，负效用 -P再设守卫睡觉而未被偷则有S 的正效用，睡觉遭偷则要被解雇，负效用-D若小偷不偷，则无得无失，守卫不睡则出一份力争一份工资，无得无失无纳什均衡,Ⅰ的混合策略集:,Ⅱ的混合策略集:,混合策略的纳什均衡,纳什均衡的存在性定理：（纳什，1950）,每一个有限博弈至少存在一个纳什均衡（纯策略的或混合策略的）,2×2双矩阵博弈的解法,当A和B均为2×2阶时，相应的双矩阵博弈可表示为:,I,II,（1）,（2）,,,,,,,,,,,,,,,,,图示,解,条件,条件序号,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,总结2×2双矩阵博弈的求解步骤,（1）由 计算,（2）根据Ai和Bi的符号,得到I和II的解,其公共点即博弈的解。

例：（夫妇之争）夫妇俩商量晚上去哪里消遣丈夫喜欢看足球比赛，而妻子喜欢去看芭蕾舞表演，夫妇都希望二人同往，不愿分开纳什均衡解（纯策略）：（足球，足球）或（芭蕾，芭蕾）,考虑混合策略：,,,,,,,,,,,,,,,,,,,案例分析——“非典”疫情扩散和防治 背景： 2003年4月，流行性非典型肺炎从广东省通过输入性病例的传播进入北京在华北地区“非典”疫情爆发初期，由于没有有效地进行预防和控制，疫情迅速扩散和蔓延，很快就开始在更广泛的区域内传播这种局面的出现，和SARS具有极强的传染性有关，也与防治工作不力有关由于政府的监管力度不够，少数医生逃避责任，医院之间也产生一种互相推诿病人的博弈关系随着疫情的发展，中央政府采取果断措施，加强了领导和监管力度，逐步扭转了这种不利的局面疫情爆发初期的情况： 在北京爆发SARS的初期，重症患者出现死亡，给医护人员带来巨大恐慌，个别医院怕自己的医护人员感染和影响单位经济效益，拒收患者当时情况下，由于对“非典”缺乏科学认识，政府对其严重性也认识不足，政府对医院没有建立严格有效的监管体制医院面对的局面是一种“囚徒困境”式的博弈问题结果：疫情扩散，影响到人民健康和社会稳定,疫情防治： 在疫情发展过程中，随着对SARS的逐步了解，政府及时总结经验教训，迅速出台一系列措施和规定来扭转当时的不利局面，如实行首诊负责制，对拒收发热病人的医院严惩不贷。

如果医院不收治非典病人和疑似病人，将受到严厉的惩罚和面临强大的舆论压力此时两个医院之间的博弈为：,结果：疫情得到控制,。