《序贯决策博弈》PPT课件.ppt

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