第四讲第四讲 序贯决策博弈序贯决策博弈 .序序贯决策博弈的定义贯决策博弈的定义参与人的决策有先有后，后决策的参与人知道参与人的决策有先有后，后决策的参与人知道先决策的参与人已经做出的决策，这种决策先决策的参与人已经做出的决策，这种决策有先有后的博弈，称为序有先有后的博弈，称为序贯决策博弈，或简称为贯决策博弈，或简称为贯决策博弈，或简称为贯决策博弈，或简称为序序贯博弈贯博弈贯博弈贯博弈。先行动者的选择影响后行动者的选择空间，后行先行动者的选择影响后行动者的选择空间，后行动者可以观察到先行动者做了什么选择，因此，动者可以观察到先行动者做了什么选择，因此，为了做出最优的行动选择，每个参与人都必须这为了做出最优的行动选择，每个参与人都必须这样思考问题：如果我如此选择，对方将如何应对样思考问题：如果我如此选择，对方将如何应对？给定他的应对，什么是我的最优选择？给定他的应对，什么是我的最优选择？.例：欺负他人可以获得快乐，你会欺负例：欺负他人可以获得快乐，你会欺负他人吗？不会。欺负他人会担心他人的他人吗？不会。欺负他人会担心他人的报复，抵消了从欺负他人的行为中获得报复，抵消了从欺负他人的行为中获得快乐。快乐。先行动者在选择行动时要考虑自己的选先行动者在选择行动时要考虑自己的选择对后行动者的影响。择对后行动者的影响。.参与人集合：参与人集合： ，此外，虚拟参与人，此外，虚拟参与人“自然自然” ” ；参与人的行动顺序（参与人的行动顺序（the order of movesthe order of moves）：谁在什么时）：谁在什么时候行动；候行动；参与人的行动空间（参与人的行动空间（action setaction set）：在每次行动时，参与）：在每次行动时，参与人有些什么选择。人有些什么选择。参与人的信息集（参与人的信息集（information setinformation set）：每次行动时，参）：每次行动时，参与人知道些什么；与人知道些什么；参与人的支付函数；参与人的支付函数；扩展式表述的要素：扩展式表述的要素：序序贯贯博弈的扩展式表述博弈的扩展式表述.序序贯贯博弈的扩展式表述博弈的扩展式表述 如何用扩展式表述来描述动态博弈？如何用扩展式表述来描述动态博弈？例例1 1，解放初，美国总是寻找各种机会来侵犯我国。对此，毛主，解放初，美国总是寻找各种机会来侵犯我国。对此，毛主席提出了席提出了“人不犯我、我不犯人，人若犯我、我必犯人人不犯我、我不犯人，人若犯我、我必犯人”的的战略方针。战略方针。 该序该序贯贯贯贯博弈的战略式表述：博弈的战略式表述：参与人参与人：美国、中国：美国、中国行动空间：行动空间：美国：美国：“犯我犯我”或或“不犯我不犯我”，中国：中国：“犯人犯人”或或“不犯人不犯人”行动顺序：美国先行动，我国依美国的行动行动顺序：美国先行动，我国依美国的行动而后行动而后行动支付：这样假设支付情况：支付：这样假设支付情况： 若美国若美国“犯我犯我”，中国，中国“犯人犯人”，则支付向量为，则支付向量为(-2,-2)(-2,-2)；. n n人有限战略的扩展式表人有限战略的扩展式表述：博弈树述：博弈树 （game treegame tree）犯人犯我不犯我犯人不犯人不犯人美国我国我国(1,1)(3,-5)(2,-4)(-2,-2)若美国若美国“犯我犯我”，中国，中国“不犯人不犯人”，则支付向量为，则支付向量为(2,-4)(2,-4)； 若美国若美国“不犯我不犯我”，中国，中国“犯人犯人”，则支付向量为，则支付向量为(3,-5)(3,-5)； 若美国若美国“不犯我不犯我”，中国，中国“犯人犯人”，则支付向量为，则支付向量为(1,1)(1,1)。2 2人有限博弈的博弈人有限博弈的博弈树树: :决策结：决策结：行行动的动的时点时点枝枝终点结终点结.进入博弈进入博弈 设想一个垄断企业因为他的产品一直可以卖高设想一个垄断企业因为他的产品一直可以卖高价赚取每年价赚取每年1010亿元的利润。假定别的企业为了亿元的利润。假定别的企业为了进入这个垄断的行业，需要投资进入这个垄断的行业，需要投资4 4亿元的投资。亿元的投资。当别的企业准备进入的时候，原有企业必须决当别的企业准备进入的时候，原有企业必须决策：或者策：或者“容忍容忍”新的企业，他的利润降为新的企业，他的利润降为5 5亿元。对方的利润也将是亿元。对方的利润也将是5 5亿元，但要减去亿元，但要减去4 4亿亿元进入投资，实得元进入投资，实得1 1亿元。或者，垄断企业进亿元。或者，垄断企业进行行“抵抗抵抗”，力图将进入者挤出去，这时垄断力图将进入者挤出去，这时垄断企业的利润降到企业的利润降到2 2亿元，即使对方也得亿元，即使对方也得2 2亿元，亿元，却要投资却要投资4 4亿元，结果进入者亏损亿元，结果进入者亏损2 2个亿。个亿。. 垄断者和进入垄断者和进入 者不同的行动组合下，博弈产者不同的行动组合下，博弈产生不同的结果：生不同的结果：1 1、进入者进入，垄断者容忍；进入者进入，垄断者容忍；2 2、进入者进入，垄断者抵抗；进入者进入，垄断者抵抗；3 3、进入者不进入，垄断者容忍；进入者不进入，垄断者容忍；4 4、进入者不进入，垄断者抵抗。进入者不进入，垄断者抵抗。.容忍进入不进入容忍抵抗抵抗进入者垄断者垄断者(0,4)(0,10)(-2,2)(1,5).策略与行动策略与行动 行动是每一个决策节点上参与人的决策变量行动是每一个决策节点上参与人的决策变量或行动的具体选择。或行动的具体选择。 纯策略为一个决策规则，它能告诉这个参与人纯策略为一个决策规则，它能告诉这个参与人在每一个可能遇到的决策节点上应当采取的行在每一个可能遇到的决策节点上应当采取的行动。动。 在序贯博弈中，一个策略就是一个完整的行动在序贯博弈中，一个策略就是一个完整的行动计划。计划。.策略策略 在进入博弈中，进入者的策略：进入和不进入。在进入博弈中，进入者的策略：进入和不进入。 垄断者的策略：一、不管你怎样，我总是垄断者的策略：一、不管你怎样，我总是“容容忍忍”；二、不管你怎样，我总是二、不管你怎样，我总是“对抗对抗”；三、三、你进入我你进入我“对抗对抗”，你不进入我你不进入我“容忍容忍”；四、四、你进入我你进入我“容忍容忍”，你不进入我你不进入我“对抗对抗”；即垄即垄断者的四个纯策略：断者的四个纯策略： 容忍容忍，容忍，容忍 、 对抗对抗，对，对抗抗 、 对抗对抗，容忍，容忍 、 容忍容忍，对抗，对抗 。.n若A先行动，B在知道A的行动后行动，则A有一个决策节点，两个可选择的行动，策略空间为:(:(开发，不开发）开发，不开发）；nB有两个决策节点，2个可选择的行动，B有四个纯策略：开发策略：不论开发策略：不论A A开发不开发，我开发开发不开发，我开发 开发，开发开发，开发 追随策略：追随策略：A A开发我开发，开发我开发，A A不开发我不不开发我不开发开发 开发，不开发开发，不开发 ；对抗策略：对抗策略：A A开发我不开发，开发我不开发，A A不开发我不开发我开发开发 不开发，开发不开发，开发 ；不开发策略不开发策略: :不论不论A A开发不开发我不开发）开发不开发我不开发） 不开发，不开发不开发，不开发 ；n策略空间为：策略空间为： 开发，开发开发，开发 、 开发，开发，不开发不开发 、 不开发，开发不开发，开发 （不开发，（不开发，不开发不开发 。A开发开发不开发不开发BB开发开发不开发不开发开发开发(-3,-3)(1，0)（0，1)(0,0)不开发不开发xy什么是参与人的策略？.序序贯贯博弈纳什均衡博弈纳什均衡纳什均衡要求每个参与人的策略都是针对其它纳什均衡要求每个参与人的策略都是针对其它参与人的策略或策略组合的最佳策略选择，没参与人的策略或策略组合的最佳策略选择，没有参与人愿意单独偏离这个策略组合。有参与人愿意单独偏离这个策略组合。.足球足球芭蕾足球芭蕾芭蕾男女女(1,2)(-1,-1)(0,0)(2,1)序序贯贯情侣博弈情侣博弈.序序贯贯情侣博弈情侣博弈男的策略：足球、芭蕾男的策略：足球、芭蕾女的策略：一、追随策略：他选择什么，我就女的策略：一、追随策略：他选择什么，我就选择什么选择什么足球，芭蕾足球，芭蕾 ；二、对抗策略：二、对抗策略：他选择什么，我就偏不选什么他选择什么，我就偏不选什么芭蕾，足芭蕾，足球球 ，三、芭蕾策略：无论他选什么，我都选三、芭蕾策略：无论他选什么，我都选我喜欢的芭蕾我喜欢的芭蕾芭蕾，芭蕾芭蕾，芭蕾 ；四、足球策四、足球策略：无论他选什么，我都选他喜欢的足球略：无论他选什么，我都选他喜欢的足球 足球，足球足球，足球 .序序贯贯情侣博弈情侣博弈一共八种可能的策略组合：一共八种可能的策略组合：（足球，（足球， 足球，芭蕾足球，芭蕾 ） （芭蕾，（芭蕾， 足球，芭蕾足球，芭蕾 ）（足球，（足球， 芭蕾，足球芭蕾，足球 ） （芭蕾，（芭蕾， 芭蕾，足球芭蕾，足球 ）（足球，（足球， 芭蕾，芭蕾芭蕾，芭蕾 ） （芭蕾，（芭蕾， 芭蕾，芭蕾芭蕾，芭蕾 ）（足球，（足球， 足球，足球足球，足球 ） （芭蕾，（芭蕾， 足球，足球足球，足球 ）.序序贯贯情侣博弈情侣博弈 （2,1)（0,0）（-1，-1）（1，2）（2,1）（0,0）（-1,-1）（1,2）（2,1）（0,0）（-1，-1）（1，2）（2，1）（0，0）（-1，-1）（1，2）（足球，（足球， 足球，足球足球，足球 ） （足球，（足球， 足球，芭蕾足球，芭蕾 ） （足球，（足球， 芭蕾，足球芭蕾，足球 ） （足球，（足球， 芭蕾，芭蕾芭蕾，芭蕾 ） .序序贯贯情侣博弈情侣博弈 （2,1)（0,0）（-1，-1）（1，2）（2,1）（0,0）（-1,-1）（1,2）（2,1）（0,0）（-1，-1）（1，2）（2，1）（0，0）（-1，-1）（1，2）（芭蕾，（芭蕾， 足球，芭蕾足球，芭蕾 ） （芭蕾，（芭蕾， 足球，足球足球，足球 ） （芭蕾，（芭蕾， 芭蕾，芭蕾芭蕾，芭蕾 ） （芭蕾，（芭蕾， 芭蕾，足球芭蕾，足球 ） .纳什均衡的箭头排除确定法纳什均衡的箭头排除确定法 （2,1)（0,0）（-1，-1）（1，2）（2,1）（0,0）（-1,-1）（1,2）（2,1）（0,0）（-1，-1）（1，2）（2，1）（0，0）（-1，-1）（1，2）（足球，（足球， 足球，足球足球，足球 ） （足球，（足球， 足球，芭蕾足球，芭蕾 ） （足球，（足球， 芭蕾，足球芭蕾，足球 ） （足球，（足球， 芭蕾，芭蕾芭蕾，芭蕾 ） .纳什均衡的箭头排除确定法纳什均衡的箭头排除确定法 （2,1)（0,0）（-1，-1）（1，2）（2,1）（0,0）（-1,-1）（1,2）（2,1）（0,0）（-1，-1）（1，2）（2，1）（0，0）（-1，-1）（1，2）（芭蕾，（芭蕾， 足球，芭蕾足球，芭蕾 ） （芭蕾，（芭蕾， 足球，足球足球，足球 ） （芭蕾，（芭蕾， 芭蕾，芭蕾芭蕾，芭蕾 ） （芭蕾，（芭蕾， 芭蕾，足球芭蕾，足球 ） .均衡与结果的区别均衡与结果的区别用箭头偏离来排除不稳定的策略组合从而得到纳什均衡。用箭头偏离来排除不稳定的策略组合从而得到纳什均衡。上例中的纳什均衡：（足球，上例中的纳什均衡：（足球， 足球，足球足球，足球 ）、）、 （足球，（足球， 足球，芭蕾足球，芭蕾 ）、）、 （芭蕾，（芭蕾， 芭蕾，芭蕾芭蕾，芭蕾 ）。）。均衡策略的组合，而结果则是行动的组合。例：纳什均衡均衡策略的组合，而结果则是行动的组合。例：纳什均衡（足球，（足球， 足球，芭蕾足球，芭蕾 ）、）、是一个策略组合，表明：如果男是一个策略组合，表明：如果男方选择足球，女方就选择足球；如果男方选择芭蕾，女方就方选择足球，女方就选择足球；如果男方选择芭蕾，女方就选择芭蕾。一个均衡策略组合所导致的博弈结果是（足球，选择芭蕾。一个均衡策略组合所导致的博弈结果是（足球，足球），即按照这个纳什均衡，博弈的结果是男女双方都要足球），即按照这个纳什均衡，博弈的结果是男女双方都要去看足球。而（足球，足球）是行动的组合，而不是策略的去看足球。而（足球，足球）是行动的组合，而不是策略的组合。组合。不同的纳什均衡可以导致相同的博弈结果。例（足球，不同的纳什均衡可以导致相同的博弈结果。例（足球， 足球，足球，足球足球 ）是另外一个纳什均衡，但它的博弈结果也是（足球，是另外一个纳什均衡，但它的博弈结果也是（足球，足球）。足球）。.UUDUDDABB(5,1)(2,2)(3,1)(1,0)练习：找出策略和纳什均衡练习：找出策略和纳什均衡.策略组合策略组合一共八种可能的策略组合：一共八种可能的策略组合：（U U，UU，U U ） （U U，UU，D D ）（U U，DD，U U ） （U U，DD，D D ）（D D，UU，U U ） （D D，UU，D D ）（D D，DD，U U ） （D D，DD，D D ）.纳什均衡纳什均衡 （1,0)（3,1）（2，2）（5，1）（1,0）（3,1）（2,2）（5,1）（1,0）（3,1）（2，2）（5，1）（1，0）（3，1）（2，2）（5，1）（U U，UU，U U ） （U U，UU，D D ）纳什均衡：（纳什均衡：（U U，DD，U U ） （U U，DD，D D ）. （1,0)（3,1）（2，2）（5，1）（1,0）（3,1）（2,2）（5,1）（1,0）（3,1）（2，2）（5，1）（1，0）（3，1）（2，2）（5，1）（D D，UU，D D ）纳什均衡：（纳什均衡：（D D，UU，U U ）（D D，DD，D D ）（D D，DD，U U ）.逆向归纳法逆向归纳法( (backward induction) )逆向归纳法是从最后一个决策点开始，找出参与人逆向归纳法是从最后一个决策点开始，找出参与人的最优行动选择和路径；然后再倒回到倒数第二个的最优行动选择和路径；然后再倒回到倒数第二个决策点，找出决策者的最优决策；如此一直到初始决策点，找出决策者的最优决策；如此一直到初始决策点，所有子博弈上的最优选择就是纳什均决策点，所有子博弈上的最优选择就是纳什均衡。衡。逻辑基础：序贯博弈中先行动的理性的参与人，在逻辑基础：序贯博弈中先行动的理性的参与人，在前面阶段选择行为时必然会先考虑后行为参与人在前面阶段选择行为时必然会先考虑后行为参与人在后面阶段中将会怎样选择行为，只有在博弈的最后后面阶段中将会怎样选择行为，只有在博弈的最后一个阶段选择的，不再有后续阶段牵制的参与人，一个阶段选择的，不再有后续阶段牵制的参与人，才能直接作出明确选择。而当后面阶段参与人的选才能直接作出明确选择。而当后面阶段参与人的选择确定以后，前一阶段参与人的行为也就容易确定择确定以后，前一阶段参与人的行为也就容易确定了。了。.容忍进入不进入容忍抵抗抵抗进入者垄断者垄断者(0,4)(0,10)(-2,2)(1,5)进入博弈的纳什均衡进入博弈的纳什均衡.足球足球芭蕾足球芭蕾芭蕾男女女(1,2)(-1,-1)(0,0)(2,1)序序贯贯情侣博弈的纳什均衡情侣博弈的纳什均衡.犯人犯我不犯我犯人不犯人不犯人美国我国我国(1,1)(3,-5)(2,-4)(-2,-2)逆向归纳法找中美军事博弈的纳什均衡逆向归纳法找中美军事博弈的纳什均衡均衡为（不犯我，犯人，不犯人）练习：练习：.例2：121（2，0）（5，0）（4，2）（1，1）UDRLUD均衡为（U,U；L）.