第8章-重复博弈

第二部分：完全信息动态博弈第八章重复博弈主要内容：一、有限重复博弈二、无限重复博弈三、讨价还价博弈ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng第八章重复博弈主要内容：一、有限重复博弈二、无限重复博弈三、讨价还价博弈ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng一、有限重复博弈重复博弈所关心的议题：将来可信的威胁或承诺如何影响到当前的行动ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng考察下列博弈1,15,00,54,4UDLR12ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng上述博弈存在唯一的Nash均衡。将上述博弈重复两次，其中第二次博弈开始时，第一次博弈的结果已知。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng两次重复博弈的博弈树121ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng上述重复博弈只存在唯一的Nash均衡：在每次博弈中，参与人1都选择U，参与人2都选择L，即((U,U,U,U,U),(L,L,L,L,L))可以证明：该均衡为精炼Nash均衡。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng1,15,00,54,4UDLR121,15,00,54,4UDLR121+1,1+15+1,0+10+1,5+14+1,4+1UDLR12ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng前面的分析说明：在两次重复博弈中，合作仍无法到达。同样可证明：在n阶段重复博弈(即博弈重复n次且每次博弈开始时，前面博弈的结果都已知)中，合作同样无法到达。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng重复博弈定义对于给定的阶段博弈G，令G(T)表示G重复进行T次的有限重复博弈，并且在下一此博弈开始前，所有以前博弈的进程都可被观测到,G(T)的收益为T次阶段博弈收益的简单相加。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng在重复博弈中，当全部博弈进行到任何一个阶段，到此为止的进行过程就成为参与各方的共同知识，而其后尚未开始进行的部分就是一个子博弈。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng定理：如果阶段博弈G有唯一的Nash均衡，则对任意有限的T，重复博弈G(T)有唯一的子博弈精炼解，即G的Nash均衡结果在每一个阶段重复进行。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng考察下列博弈1,15,00,00,54,40,00,00,03,3121L2L1M1R2M2RControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng上述博弈存在两个Nash均衡：(L1,L2)和(R1,R2)将上述博弈重复两次。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng1)战略：每个局中人都有个战略；(1+9)3=59049ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng2)战略组合：一共存在个战略组合；5904959049=3,486,784,401ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng3)均衡：可以根据以下原则构造均衡：由第一阶段的结果，预测第二阶段的均衡。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng例如：若第一阶段出现(M1,M2)(即出现合作)，则第二阶段为(R1,R2)(即“好的均衡”)；若第一阶段没有出现(M1,M2),则第二阶段为(L1,L2)(即“差的均衡”)。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng根据上述原则，可构造如下策略：S1：第一阶段选择M1；如第一阶段结果为(M1，M2)，则下一阶段选R1；否则选择L1。S2：第一阶段选择M2；如第一阶段结果为(M1，M2)，则下一阶段选R2；否则选择L2。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng在上述策略下，博弈可表示为：这意味着：合作可以在第一阶段达到1+1,1+15+1,0+10+1,0+10+1,5+14+3,4+30+1,0+10+1,0+10+1,0+13+1,3+1121L2L1M1R2M2RControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng定理：如果G=T,(Ai),(ui)是一个有多个Nash均衡的完全信息静态博弈，则G(T)可以存在子博弈精炼解，其中对每一tT,t阶段的结果都不是G的Nash均衡。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng上述结论说明：对将来行动所作的可信威胁或承诺可以影响到当前的行动。考察下列博弈。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng1,15,00,00,00,00,54,40,00,00,00,00,03,30,00,00,00,00,04,1/20,00,00,00,00,01/2,4121X1Y1Z1P1Q2X2Y2Z2P2QControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng如果第一阶段出现(Y1,Y2),则第二阶段(Z1,Z2);如果第一阶段出现(Y1,w),其中(wY2),则第二阶段为(P1,P2)；ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng如果第一阶段出现(w,Y2),其中(wY1),则第二阶段(Q1,Q2);如果第一阶段出现(w1,w2),其中(w1Y1,w2Y2),则第二阶段为(Z1,Z2)。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng1+3,1+35+1/2,0+40+3,0+30+3,0+30+3,0+30+4,5+1/24+3,4+30+4,0+1/20+4,0+1/20+4,0+1/20+3,0+30+1/2,0+43+3,3+30+3,0+30+3,0+30+3,0+30+1/2,0+40+3,0+34+3,1/2+30+3,0+30+3,0+30+1/2,0+40+3,0+30+3,0+31/2+3,4+3121X1Y1Z1P1Q2X2Y2Z2P2QControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng显然，上述策略构成博弈的Nash均衡，且为子博弈精炼Nash均衡。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng第八章重复博弈主要内容：一、有限重复博弈二、无限重复博弈三、讨价还价博弈ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng二、无限重复博弈•定义(无线重复博弈)给定一阶段博弈G，令表示相应的无限重复博弈，其中G将无限次低重复进行，且参与人的贴现率为。对每个t，之前t-1次阶段博弈的结果在t阶段开始进行前都可以被观测到，每个参与人在中的收益都是该参与人在无限次的阶段博弈中所得受益的现值。(,)G(,)GControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng在有限重复博弈G(T)中，由第t+1阶段开始的一个子博弈为G进行T-t次的重复博弈，可表示为G(T-t)。由第t+1阶段开始有许多子博弈，到t阶段为止的每一可能的进行过程之后都是不同的子博弈。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng在无限重复博弈中，由t+1阶段开始的每个子博弈都等同于初始博弈，和在有限情况下相似，博弈到t阶段为止有多少不同的可能进行过程，就有多少从t+1阶段开始的子博弈。(,)G(,)G(,)GControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng对于无限重复博弈，参与人在博弈的每一时点，都不必考虑过去的得失，也就是说，无限重复博弈中，参与人过去的得失并不重要，可以看成是沉没成本(或收入)。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng下列博弈重复无限次。1,15,00,54,4UDLR12ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng对于阶段博弈为上述博弈的有限重复博弈，合作不可能形成。但对于无限重复博弈，在一定的贴现率下，合作有可能形成。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng构造如下触发策略：S1：第i阶段选择D；如第i阶段结果为(D，R)，则下一阶段选D；否则以后一直选择U。S2：第i阶段选择R；如第i阶段结果为(D，R)，则下一阶段选R；否则以后一直选择L。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng可用证明：在一定的贴现率下，上述触发策略构成Nash均衡。ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng贴现率的求解2245+1+1+4+414所以ControlScienceandEngineering,HUSTAllRightsReserved,2007,LuoYunfeng可行收益一组收益为阶段博弈G的可行收益，如果它们是G的纯战略收益的凸组合(即纯战略收益的加权平均，权重非负且和为1)。前述阶段博弈的可行收益集合如下图所示。12(