数学模型 第十一章博弈模型 111进攻与撒退的抉择 112让报童订购更多的报纸 13“一口价”的战略 11.4不患寡而患不均 115效益的合理分配 11.6加权投票中权力的度量
第十一章 博弈模型 11.1 进攻与撤退的抉择 11.2 让报童订购更多的报纸 11.3 “一口价”的战略 11.4 不患寡而患不均 11.5 效益的合理分配 11.6 加权投票中权力的度量
数学模型) 决策问题( Decision problem) 单一决策主体 决策变量 目标函数优化模型 要素 约束条件 (Optimization 多个决策主体决策主体的决策 博弈模型 行为发生直接相 互作用(相互影响)( Game Theory) 博弈模型 合作博弈非合作博弈 静态、动态 信息完全、不完全 军事、政治、经济、企业管理和社会科学中应用广泛
单一决策主体 决策变量 目标函数 约束条件 决策主体的决策 行为发生直接相 互作用 (相互影响) 博弈模型 合作博弈 非合作博弈 三要素 博弈模型 (Game Theory) 多个决策主体 优化模型 (Optimization) 决策问题（Decision Problem） 静态、动态 信息完全、不完全 军事、政治、经济、企业管理和社会科学中应用广泛
数学模型 111进攻与撤退的抉择 背·1944年6月初,盟军在诺曼底登陆成功 景·到8月初的形势: 盟军(加 盟军(英) 盟军(美一) 德军→撒退 盟军化>毽攻 (预备队) 东盟军 (美三) 原地 持命 双方应该如何决策?
• 1944年6月初，盟军在诺曼底登陆成功. • 到8月初的形势： 背 景 11.1 进攻与撤退的抉择 双方应该如何决策 ？ 强 化 盟军 缺口 (预备队) 撤退 进攻 德军 盟军(加) 盟军(英) 盟军(美一) 盟 军 (美三) 东进 原地 待命
数学模型 模型假设 博弈参与者为两方(盟军和德军) 盟军有3种使用其预备队的行动:强化缺口,原地 待命,东进;德军有2种行动:向西进攻或向东撤退 博弈双方完全理性,目的都是使战斗中己方获得 的净胜场次(胜利场次减去失败场次)尽可能多 盟军德军向西进攻向东撤退 强化缺口盟军胜1场无战斗 原地待命盟军胜2场无战斗 东进盟军败2场」盟军胜1场 双方同时做出决策 完全信息 共同知识(以上信息双方共有) 静态博弈
模型假设 • 博弈参与者为两方（盟军和德军） • 盟军有3种使用其预备队的行动：强化缺口，原地 待命，东进；德军有2种行动：向西进攻或向东撤退. • 博弈双方完全理性，目的都是使战斗中己方获得 的净胜场次（胜利场次减去失败场次）尽可能多. 东进 盟军败2场 盟军胜1场 原地待命 盟军胜2场 无战斗 强化缺口 盟军胜1场 无战斗 盟军 德军 向西进攻 向东撤退 完全信息 • 共同知识(以上信息双方共有) 静态博弈 • 双方同时做出决策
数学模型 博弈模型 博弈参与者集合N={1,2}(为盟军,2为德军) 盟军行动a1∈A1={12,3}(强化缺口原地待命/东进); 德军行动a2∈A2={1,2}(进攻/撒退)。(行动:即纯战略) 用u1a1,a2)表示对盟军产生的结果,即净胜场次, 称为盟军的效用函数 盟军德军向西进攻向东撤退 20 强化缺口盟军胜1场无战斗 M={mn3×2 原地待命盟军胜2场无战斗支付矩阵 东进盟军败2场盟军胜1场( Payoff matrix) 完全竞争零和博弈(常数和博弈)2(a1,a2)对应M
博弈模型 • 博弈参与者集合N={1,2}(1为盟军，2为德军) • 用u1 (a1，a2 )表示对盟军产生的结果，即净胜场次， 称为盟军的效用函数. 东进 盟军败2场 盟军胜1场 原地待命 盟军胜2场 无战斗 强化缺口 盟军胜1场 无战斗 盟军 德军 向西进攻 向东撤退 − = = 2 1 2 0 1 0 { } M mij 3 2 • 盟军行动a1 A1={1,2,3}(强化缺口/原地待命/东进)； 德军行动a2 A2={1,2}(进攻/撤退)。 (行动：即纯战略) 支付矩阵 （Payoff Matrix） 完全竞争: 零和博弈 (常数和博弈) u2 (a1，a2 )对应 -M
(数学模型 博弈的解的概念:纳什均衡(NE: Nash equilibrium) Nash:1994年获诺贝尔经济学奖 NE:单向改变战略不能提高自己效用,即每一方的战略 对于他方的战略而言都是最优的,称为最优反应 纯战略)纳什均衡4(a1,a2)≥4(42a2),a1∈{123}, (a,a2)≥2(a1,a2),a2∈{12} 非常数和 M={mn32=20 M=2221博弈(双矩 2.21 阵表示) 不存在(纯)NE (纯)NE:a=(an1,a2)=(2,2)
博弈的解的概念：纳什均衡 (NE: Nash Equilibrium) 不存在(纯)NE ( , ) ( , ), {1,2}. ( , ) ( , ), {1,2,3}, 2 2 * 2 1 * 2 * 2 1 1 * 1 1 2 * 2 * 1 1 u a a u a a a (纯战略)纳什均衡 u a a u a a a Nash: 1994年获诺贝尔经济学奖 NE: 单向改变战略不能提高自己效用，即每一方的战略 对于他方的战略而言都是最优的, 称为最优反应. − = = 2 1 2 0 1 0 { } M mij 3 2 (纯)NE: a *=(a1 * , a2 * ) =(2, 2) − − − − = 2,2 1, 1 2, 2 2,1 1, 1 1,1 ' M 非常数和 博弈(双矩 阵表示)
数学模型 混合战略(策略: Strategy) 盟军的混合战略集 S1={(p,p2p2)0≤p≤1∑=1 德军的混合战略集 S2={q(q1,q2)|0≤9s1∑q1=1 32 期望收益U1(,)=p2=∑∑pm U2(p,q)=-U/1(P,q 盟军 max pMO p∈S1 完全信息静态博弈 有限博弈矩阵博弈(2人) 德军 min pl g∈S2 零和博弈常数和博弈
混合战略（策略：Strategy) 盟军的混合战略集 期望收益 •盟军 •德军 S1={p=(p1 , p2 , p3 ) | ｝ = = 3 1 0 1, 1 i pi pi 德军的混合战略集 S2={ q=(q1 , q2 ) | ｝ = = 2 1 0 1, 1 i qi qi T p S pMq 1 max T q S pMq 2 min 完全信息 静态博弈 有限博弈 矩阵博弈 (2人) 零和博弈 常数和博弈 ( , ) ( , ) ( , ) 2 1 3 1 2 1 1 U p q U p q U p q pMq p m q i j i i j j T = − = = = =
数学模型 模型求解mxpM pM T mIn p∈ q∈S2 理性推理:不管自己怎么做,另一方总是希望尽量 使自己得分尽量低.(二人零和博弈,完全竞争) 从一个给定的战略中期望得到的赢得,总是 采用该策略时他们可能得到的最坏的赢得! 盟军可以用 min pM来衡量策略p的好坏 德军可以用 max Mq来衡量策略q的好坏 盟军max(p)= min pM 线性P2=35,p3=2/5 德军min()=maxM7规划g=15,q2=4/5 (p,q):混合(策略)纳什均衡( Mixed ne)最优值均为2/5
模型求解 理性推理：不管自己怎么做，另一方总是希望尽量 使自己得分尽量低. （二人零和博弈，完全竞争） •盟军 •德军 T p S pMq 1 max T q S pMq 2 min 线性 规划 从一个给定的战略中期望得到的赢得，总是 采用该策略时他们可能得到的最坏的赢得！ 盟军可以用min pM来衡量策略p的好坏 max U1 (p) = min pM min U2 (q) = max MqT 德军可以用max MqT来衡量策略q的好坏 (p * , q * ): 混合(策略)纳什均衡(Mixed NE) p2 *=3/5，p3 *=2/5 q1 *=1/5，q2 *=4/5 最优值均为2/5
数学模型 模型评述 00 M=10 占优( dominate):盟军的行动2占优于1 (前面的非常数和博弈M类似) 混合策略似乎不太可行!但概率可作为参考. 现实:盟军让预备队原地待命(行动2),而德军 没有选择撤退(行动2),结果德军大败 °博弈规则至关重要的,如参与人决策的时间顺序 决策时拥有哪些信息等. 多人(或非常数和博弈问题,一般不能用上面的线性 规划方法求解,而通过纳什均衡的定义求解
•占优(dominate)：盟军的行动2占优于1 （前面的非常数和博弈M’类似） •混合策略似乎不太可行! 但概率可作为参考. ----现实：盟军让预备队原地待命（行动2），而德军 没有选择撤退（行动2），结果德军大败. 模型评述 • 博弈规则至关重要的，如参与人决策的时间顺序、 决策时拥有哪些信息等. − = 1 1 1 0 0 0 M •多人(或非常数和)博弈问题，一般不能用上面的线性 规划方法求解，而通过纳什均衡的定义求解
数学模型 小结:博弈模型的基本要素 参与人 行动空间(及战略空间) 效用函数 理性假设参与者完全理性最大化效用) 纳什均衡单向改变战略不能提高自己效用 其他因素 行动顺序(静态、动态) 信息结构(完全、不完全)
小结：博弈模型的基本要素 • 参与人 理性假设 • 行动顺序（静态、动态） • 信息结构（完全、不完全） • 行动空间（及战略空间） • 效用函数 参与者完全理性(最大化效用) 其他因素 纳什均衡 单向改变战略不能提高自己效用