第4讲:完全信息动态博弈 完美信息动态博弈 李婷,ling@fudan.edu.cn 复旦大学
第4讲:完全信息动态博弈 完美信息动态博弈 李婷, liting@fudan edu cn liting@fudan.edu.cn 复旦大学
进入博弈 在位垄断者面临潜在进入者进入的可能性。 潜在进入者可以选择进入或退出。 如果潜在进入者进入,那么在位垄断者可以选择容纳或者攻击。 双方收益公开。 Challenger Out Incumbent 第一个数字是潜在进入者的 A 收益,第二个数字是在位垄 断者的收益。 2,1 2
进入博弈 在位垄断者面临潜在进入者进入的可能性。 潜在进入者可以选择进入或退出。 如果潜在进入者进入,那么在位垄断者可以选择容纳或者攻击。 双方收益公开。 Challenger In Out Incumbent A F 1, 2 第一个数字是潜在进入者的 A F 收益 第二个数字是在位垄 , 2 1 0 0 收益,第二个数字是在位垄 断者的收益。 2 2, 1 0, 0
硬币匹配 两个参与者各自拥有一个硬 Player 1 币 ■参与者1先选择正面或反面 H ■在观察参与者1的选择后,参 与者2选择正面或反面 所有参与者都清楚以下规则 Player 2 Player 2 如果两个硬币都是正面或 反面,那么参与者2赢走 T H T 参与者1的硬币。 反之,参与者1赢走参与 者2的硬币。 1,1 1,1
硬币匹配 两个参与者各自拥有一个硬 币。 参与者1先选择正面或反面 Player 1 参与者1先选择正面或反面 H T 在观察参与者1的选择后, 参 与者2选择正面或反面 所有参与者都清楚以下规则 Player 2 H T Player 2 所有参与者都清楚以下规则: 如果两个硬币都是正面或 反面,那么参与者2赢走 Player 2 H T Player 2 反面 那 参与者 赢走 H T 参与者1的硬币。 反之,参与者1赢走参与 者2的硬币。 -1, 1 1, -1 1, -1 -1, 1 2的硬币。 3
完全信息动态博弈 ■参与者 ■谁在什么时候轮到行动,可以选择什么决策 ■在参与者决策时知道什么信息? ■参与者的收益由所有参与者的策略组合决定 ■收益函数
完全信息动态博弈 参与者 谁在什么时候轮到行动 ,可以选择什么决策 在参与者决策时知道什么信息 ? 参与者的收益由所有参与者的策略组合决定 收益函数 4
定义:扩展式表达 博弈的扩展式表述如下: 博弈中的参与者 什么时间参与者轮到行动 每个参与者轮到行动时可以选择什么策略 每个参与者轮到行动时知道什么信息 每个参与者的收益
定义:扩展式表达 博弈的扩展式表述如下: 博弈中的参与者 什么时间参与者轮到行动 每个参与者轮到行动时可以选择什么策略 每个参与者轮到行动时知道什么信息 每个参与者的收益 5
完全信息动态博弈 完全信息 所有之前的决策在下一步决策时都可被观察 到 在进行决策前,每个参与者知道是谁做了什 么选择
完全信息动态博弈 完全信息 所有之前的决策在下 步决策时都可被观察 所有之前的决策在下 一步决策时都可被观察 到。 在进行决策前,每个参与者知道是谁做了什 么选择 。 6
博弈树 个博弈树有一系列的从x到x唯x 节点 节点和一系列的路径, 路径 使得 每一个路径链接两个节 对于每一组节点,有 个唯一的路径。 连救,到x的路径
博弈树 一个博弈树有一系列的 节点和一系列的路径 x0 节点 从x0 到x4唯 一路径 节点和 系列的路径, 使得 每 个路径链接两个节 一个路径链接两个节 x x 点。 对于每一组节点 有一 x1 x2 对于每 组节点,有 个唯一的路径。 x3 x4 x5 x6 x7 x8 连接x1 到 x5的路径 7
博弈树 个路径是一个节点的序列y1y2从x到x的路x 连的¥,使得y 径 我们锐是贝 y1到yn的路径。 路径的长度是路径中包含的边数。 例子1:x0,x2,x3,X是一个3步长 ax. 的路径。 例子2:X4,X1,X0,x2,x6是一个4步 长的路径。 8
博弈树 一个路径是一个节点的序列y1, y2, y3, ..., yn-1, yn ,使得yi 和yi+1 是相 连的 i=1 2 n-1 我们说是从 x0 从x0 到x4的路 径 连的, i=1, 2, ..., n-1。我们说是从 y1 到 yn的路径。 路径的长度是路径中包含的边数。 例子 1 是 个3步长 x x : x0, x2, x3, x7 是一个3步长 的路径。 例子 2: x4, x1, x0, x2, x6 是一个4步 长的路径 x1 x2 4 1 0 2 6 长的路径。 x3 x4 x5 x6 x7 x8 8
博弈树 ■这里的特殊节点ⅹ被叫做博弈 树的根,是博弈的开端。 与X0相临的节点是x的后继点。 的后继点是x1,x2 ■对于任何两个相邻节点,通过较 ax. 长路径连接到根节点的节点是另 节点的后继节点。 例子3:X7是x3的一个后继点, 因为他们是相邻的,从X7到x0 的路径比x3到Xo的路径长。 8
博弈树 这里的特殊节点x0 被叫做博弈 树的根,是博弈的开端。 x0 与x0 相临的节点是x0 的后继点。 x0 的后继点是x1, x2 对于任何两个相邻节点,通过较 x x 长路径连接到根节点的节点是另 一节点的后继节点。 x1 x2 例子 3: x7 是x3 的一个后继点, 因为他们是相邻的,从x7 到 x0 的路径比x3 到x0 的路径长。 x3 的路径比x x4 x5 x6 3 到x0 的路径长。 6 x7 x8 9
博弈树 ■如果节点x是另一个节点 的y的后继节点,则y被 称为x的前导节点。 在博弈树中,除根以外的 隼智 何节点都具有唯一的前 ax. ■任何没有后继节点的节点 做终点,是博弈中可能 的结果。 终点节4x5x8,x,x是x 例子4:X 8
博弈树 如果节点 x 是另一个节点 的 y 的后继节点,则 y 被 称为 的前导节点 x0 x 。 在博弈树中,除根以外的 任何节点都具有唯一的前 x x 导节点。 任何没有后继节点的节点 x1 x2 任何没有后继节点的节点 叫做终点,是博弈中可能 的结果。 例子 4 是 x3 x4 x5 x6 例子 4: x 4, x 5, x 6, x 7, x 8 是 终点节点。 6 x7 x8 10