《博弈论原理模型与教程》第06章扩展式博弈第01节

1、博弈论：原理、模型与教程第二部分 完全信息动态博弈第 6 章 扩展式博弈（已精细订正！ ）对博弈问题的规范性描述是科学、系统地分析博弈问题的基础。 前面介绍了一种常用的博弈问题描述方式 战略式博弈 ，虽然这种博弈模型结构简单，只要给出博弈 问题的三个基本构成要素（即 参与人 、参与人的战略集 及 参与人的支付 ），就可完成对博弈问题的 建模但是，由于战略式博弈假设每个参与人仅选择一次行动或行动计划 （战略），并且参与人同时进行选择， 因此从本质上来讲战略式博弈是一种静态模型 ，一般适用于描述不需要考虑博弈进程的完全信息静态博弈 问题。虽然战略式博弈也可以对动态博弈问题进行建模，但是从所得到的模

2、型中只能看到博弈的结果，而无 法直观地了解到博弈问题的 动态特性。本章将介绍一种新的博弈问题描述方式 扩展式博弈 。从扩展式博弈模型中，不仅可以看到博弈的结 果，而 且还能直观地看到博弈的进程 。在介绍扩展式博弈构成的基础上，还将对扩展式博弈的战略和解进 行讨论。6.1 扩展式博弈（文字描述、博弈树描述）所谓扩展式博弈（ extensive form game ）， 是博弈问题的一种规范性描述。与战略式博弈侧重博弈结 果的描述相比，扩展式博弈更注重对参与人在博弈过程中所遇到决策问题的序列结构的详细分析。一般而言，要了解一个博弈问题的具体进程，就必须弄清楚以下两个问题：（ 1 ）每个参与人在什么

3、时候行动（决策、选择） ；（ 2 ）每个参与人行动时，他所面临决策问题的结构，包括参与人行动时可供他选择的行动方案 及所了解的信息（集）。 注：行文中频繁出现的“行动”一词，有两义：其一，动词的“行动” ，指选择、决策。其二，名词的“行动” ，指策略、战略、谋略、行动方案、方案。 上述两个问题构成了参与人在博弈过程中所遇到决策问题的 序列结构 。对于一个博弈问题，如果能够 说清楚博弈过程中参与人的决策问题的 序列结构 ，那么就意味着知道了博弈问题的 具体进程 。定义 6 1 扩展式博弈包括以下要素：（1） 参与人集合1,2,., n ；（2）参与人的行动顺序，即每个参与人在何时行动；（ 3 ）

4、 每个参与人行动时面临的决策问题，包括参与人行动时可供他选择的行动方案及他所了解的信息 （集）；（4）参与人的支付函数，即博弈结束时每个参与人得到的博弈结果。从上述定义可以看到： 如果要用扩展式博弈对一个博弈问题进行建模 （或者描述） ，那么除了要说明博 弈问题所涉及的参与人及每位参与人的支付函数以外，还必须对博弈过程中参与人所遇到的决策问题的序 列结构进行详细的解释，说清楚每个参与人在何时行动，以及参与人行动时可供选择的行动方案和所了解 到的信息。【例 6-1】 考察一个“新产品开发博弈” 。试用扩展式博弈 对两个企业都知道市场需求且企业 同时决策 的 博弈情形，即完全信息静态的“新产品开发

5、博弈”进行建模。企业 2不开发，获利润 800万元 需求大企业1 开发（ a）:投入 2000元资金企业 2开发，获利润 300元 企业 2不开发，获利润 200万元 需求小企业2开发，赔 400万元不开发（ b）：不投入资金，利润 为0。图 1-1 新产品开发的投入 - 产出图解：文字描述如下：根据定义 6-1 ，完全信息静态的“新产品开发博弈”的扩展式博弈 包括以下要素：1）参与人是企业 1 和企业 2；2）两个企业同时行动，即同时选择产量；3）每个企业行动时有两种选择“开发”和“不开发”，并且每个企业行动时不知道对方的选择4）两个企业的支付如图 1-1 所示。企业 2不开发，获利润 80

6、0万元 需求大企业1 开发（ a）:投入 2000元资金企业 2开发，获利润 300元 企业 2不开发，获利润 200万元 需求小企业2开发，赔 400万元不开发（ b）：不投入资金，利润 为0。1 注意， 虽然此时每个企业都不知道对方的选择， 但用扩展式博弈进行建模时仍然假设参与 人都同时看到了图 1-1 所示的投入 - 产出图，即图 1-1 对两个企业来说为 共同知识 。图 1-1 新产品开发的投入 - 产出图【例 6-2】 继续考察“新产品开发博弈” 。试用 扩展式博弈 对两个企业都知道市场需求且企业1 先决策，企业 2观测到企业 1 的选择后再进行选择的博弈情形，即完全信息动态的“新产

7、品开发博弈”进行建模。解：文字描述如下：根据定义 6-1 ，完全信息动态的“新产品开发博弈”的扩展式博弈 包括以下要素：（1）参与人是企业 1 和企业 2；（2）企业 1 先行动，企业 2 后行动；（3）企业 1行动时有两种选择“ 开发”和“不开发 ”，企业 1行动时不知道企业 2的行动；企业 2行动 时有两种选择“ 开发”和“ 不开发 ”，但企业 2行动时已经知道企业 1的行动；（4）两个企业的支付仍然有如图 1-1 所示。上述两个例子中，用 文字描述 的方法给出了 博弈问题的扩展式描述 。对于一些简单的博弈问题，这种文字表述的方法也许是简单可行的。但可以想象，如果遇到的是更为 复杂的博弈问

8、题，如参与人人数大于 2 ，每个参与人可以多次行动且每次行动时可供选择的行动方案不同 等，文字描述所给出的模型就会显得繁冗拖沓，极不直观，因此 需要寻找一种简便易行的扩展式博弈的描述方式。下面就以“新产品开发博弈”为例，介绍一种不仅简单方便，而且十分直观的扩展式博弈的描述方式 博弈树 。所谓博弈树 ，就是由 结和有向枝 构成的 “有向树”。图 6-1 给出的是当市场需求为大时，完全信息动态的“新产品开发博弈 ”的博弈树。在图 6-1 所示的博弈树中，最上端的一个点 x1（ 用空心圆表示 ） 表示 博弈的开始 ，将“企业 1”标示在 点 x1 上，表示博弈开始于企业 1 的选择。企业 1 的选择

9、有“开发”和“不开发” ，分别用标有“开发”和 “不开发”的 有向枝 表示。若企业 1 选择“开发” ，则博弈从点 x1达到 x2 （用实心圆表示 ）；若企业 1 选 择“不开发”，则博弈从点 x1达到点 x3 （用实心圆表示 ）。点 x2（或 x3 ）上标有“企业 2”，表示企业 2 在博弈到达点 x2 （或 x3 ）时，即企业 1 选择“开发” （或“不开发” ）后，再进行选择；企业 2 的行动也 有“开发”和“不开发” ，同样分别用标有“开发”和“不开发”的 有向枝 表示。若企业 2选择“开发” ， 则博弈从点 x2（或 x3 ）达到点 x4（或x6 ）（都用实心圆表示） ；若企业 2选

10、择“不开发”，则博弈从点 x2 （或 x3 ）达到点 x5（或 x7 ）（都用实心圆表示） 。由于企业 2选择后博弈结束， 因此点 x4、x5、x6和 x7 都表示博弈的结束。在点 x4 、 x5 、 x6 和 x7 旁标有 支付向量 ，表示博弈达到该点时企业的所得。其中，支付向量中的第一个数字表示企业 1 的所得，第二个数字表示企业 2 的所得图 6-1 博弈树图 6-1 中，点 x1、 x2 、 x3 、 x4 、 x5 、 x6 和 x7 称为 博弈树的结（ node），其中标有参与人（即企业）的结 x1、 x2和x3称为决策结（ decision node） ,表示参与人在此选择行动；

11、标有支付向量的结x4 、x5 、 x6和 x7 表示博弈结束，称为 终点结（ terminal node ）。在决策结中，决策结 x1表示博弈的开始， 亦称为博弈树的初始结 或根（ root ）。结与结的连线称为博弈树的枝（ branch ），表示博弈从枝的一个结达 到另一个结参与人需要选择的行动。例如，博弈从决策结x1达到 x2 ，需要企业 1选择行动“开发” ，所以在连接 x1和x2的枝上标有行动“开发” 。在博弈树中， 枝是有向的 ，表示博弈只能从枝的一个结达到另一 个结。例如，在连接 x1和 x3 的枝上，标有行动“不开发” ，表示当企业 1 选择“不开发”时，博弈从 x1达到 x3

12、，因此连接 x1到 x3 的枝的方向是从 x1指向 x3通过以上介绍，再考察图 6-1 中的博弈树， 可以得到这样的信息：1）博弈中的参与人是企业 1 和企业 2；2）博弈中企业 1 先选择，企业 2 后选择；3）企业 1选择时有行动“ 开发”和“不开发”，企业 2选择的行动有 “开发” 和“不开发”；4）博弈中企业的支付。1 一般情形下，支付向量中数字的顺序与博弈树中参与人的行动顺序相对应。4也就是说 ，除了“ 企业 2行动时是否观测到企业 1的选择”这一点暂时无法从图 6-1 中知道以外，完 全信息动态的“新产品开发博弈”的扩展式描述所需要的信息（或要素）都可以从图 6-1 中得到。如果还

13、能够直接从博弈树中知道 “企业 2 行动时是否观测到企业 1 的选择”，那么给出博弈树， 就意味 着给出了完全信息动态的“新产品开发博弈”的扩展式描述。下面探讨如何在博弈树中，将“企业 2 行动时是否观测到企业 1 的选择”这一 信息 表示出来。在完全信息动态的“新产品开发博弈”中 ，企业 2 决策时企业 1 已经做出选择，此时企业 2 面临的决 策情形无非只有 以下两种 ： 第一种：企业 2 知道企业 1 的选择； 第二种：企业 2 不知道企业 1 的选择。对于第一种情形，企业 2 知道企业 1的选择，即知道企业 1 选择“开发”还是“不开发” ，因此企业 2 知道博弈是从 x1到了 x2还

14、是从 x1到了 x3 。这就意味着当轮到企业 2决策时，他知道自己是在点 x2 上还 是在点 x3 上。对于第二种情形，企业 2 不知道企业 1 的选择，即不知道博弈是从 x1到了 x2 还是从 x1到 了 x3 。因此，当轮到企业 2 决策时，他不知道自己是在点 x2 上还是在点 x3 上。 所以，“企业 2 行动时是 否观测到企业 1的选择”这一问题，实际上就等价于 “企业 2行动时是否知道自己是在博弈树中的点x2 上还是在点 x3 上”。为了将“企业 2 行动时是否知道自己是在博弈树中的点x2 上还是在点 x3 上”这一点说清楚，需要引入“信息集”（ information set ）的

15、概念 。在博弈树中 ，参与人 i 的一个信息集（用 Ii 表示）是参与人 i 决策结的一个集合，它 满足以下条件 ： （ 1 ） I i 中的每个决策结都是参与人 i 的决策结；（2）当博弈到达信息集 Ii （即博弈到达 I i中某个决策结）时，参与人 i 知道自己是在信息集 Ii中的决策 结上，但不知道自己究竟在 Ii 中哪个决策结上。因此，参与人 i 的信息集 Ii可以用来描述当轮到参与人 i行动时他所了解到的信息， 即他知道什么 （知 道自己位于哪一个信息集上） 、不知道什么（不知道自己位于信息集中哪一个决策结上） 。例如，在“新产品开发博弈”中，假设企业1先行动，企业 2 后行动，但企

16、业 2行动时不知道企业 1的行动，那么在如图 6-1 所示的博弈中当企业 2 行动时就只知道博弈要么到达点 x2 ，要么到达点 x3 ，但 具体在哪一点上，企业 2不清楚。也就是说，企业 2只知道自己位于决策结集合 x2,x3 上，但不知道位 于 x2, x3中哪一个决策结上。在这种情况下， x2 , x3 就是企业 2的一个信息集 。如果假设企业 2行动 时知道企业 1 的行动，那么在如图 6-1 所示的博弈中，当企业 2 行动时就知道博弈是到达了点 x2 ，还是 到达了点 x3 。此时，企业 2的决策结集 x2和x3 都是企业 2 的信息集 1。设 X 为一决策结集合，用 Ii(X) 表示

17、参与人 i 的由决 策结集 X 构成的一个 信息集 。例如， I2( x2,x3 )表示企业 2的由决策结集 x2,x3 构成的信息集， I2( x2 ) 和 I2( x2,x3 ) 分别表示企业 2 的由决结集 x2 和 x3 构成的信息集。为了更好地理解信息集这个概念 ，考虑如图 62 所表示的博弈情形中参与人 3 的信息集 2 (顺便考虑 参与人 2、参与人 3 的信息集)。由于参与人 3 选择时，参与人 1 和参与人 2 都已经做出选择，因此参与人 3 选择时可能面临的决策情 形就有以下 4 种：1) 既知道参与人 1的选择，也知道参与人 2 的选择；2) 知道参与人 1的选择，但不知

18、道参与人 2 的选择；3) 知道参与人 2的选择，但不知道参与人 1 的选择；4) 既不知道参与人 1 的选择，也知道参与人 2 的选择1 注意，这是一种信息退化了的情况，即信息集中只含有一个决策结(亦称 单结信息集 )。 此时，虽然信息集的定义要求参与人不知道自己在信息集哪一个决策结上，但由于只有一 个决策结，实际上也意味着参与人知道自己在哪一个决策结上。2 在图 6 2 中，省略了参与人的支付，但这样并不影响对问题的分析下面对上述 4 种情形分别进行考察：首先考察第二种情形， 即参与人 3 知道参与人 1 的选择，但不知道参与人 2 的选择 。参与人 3 知道参与人 1 的选择，就意味着当

19、轮到他选择时，他知道博弈进入了博弈的左边（如果参与 人 1 选择 L ）还是右边（如果参与人 1 选择 R ）；但由于参与人 3 不知道参与人 2 的选择，因此当轮到他 选择时，他不知道自己是在 x4上还是在 x5上，或者x6上还是 x7上。但是，参与人 3知道自己要么就在 x4或者 x5上，要么就在 x6或者 x7上，所以参与人 3的决策结集 x4,x5 和 x6,x7 都为参与人 3的信息 集。在博弈树中，用虚线将属于同一信息集的决策结连起来，表示它们属于同一信息集。例如， 62 中，用虚线将点 x4和 x5连起来，表示它们都属于信息集x4,x5 ，用虚线将点 x6和 x7连起来，表示它们

20、都属于与信息集 x6,x7 。其次考察第三种情形 ，即参与人 3知道参与人 2的选择，但不知道参与人 1 的选择虽然参与人 3 知道参与人选择了L 还是 R ，但由于他不知道参与人1 的选择，因此当参与人 2选择 L 时，参与人 3 知道自己是在x4 或者 x6 上，但究竟在哪一点上参与人3 并不清楚，所以决策集合x4,x6 是参与人 3的一个信息集 。当参与人 2选择 R 时，参与人 3知道自己是在 x5或者 x7上，但究竟在哪一个点上并不清楚，所以决策结集合x5,x7 是参与人 3 的另一个信息集 。在图中 63 中，用虚线将点 x4和x6连起来，表示它们都属于信息集 x4,x6 ，用虚线

21、将点 x5和 x7 连起来，表示它们都属于信息集 x5,x7 。图 6-3 博弈树：知道 2 的选择；不知道 1 的选择考察第四种情形 ，即参与人 3既不知道参与人 1的选择也不知道参与人 2的选择 。由于参与人 1和参与人 2的选择参与人 3 都不知道，因此当轮到参与人 3 行动时，他只知道自己位 于点 x4、 x5、 x6和 x7四点中的某一点上，但究竟在哪一点上参与人3 并不清楚，所以决策结集合x4,x5,x6,x7 是参与人 3的一个信息集 。在图 6 4中，用虚线将点 x4、 x5 、 x6和x7 连起来，表示 它们都属于信息集 x4,x5,x6,x7 。图 6-4 博弈树：既不知道

22、 1 的选择；也不知道 2 的选择最后考察第一种情形 ，即参与人 3既知道参与人 1的选择也知道参与人 2的选择 。由于参与人 3既知道参与人 1的选择，又知道参与人 2 的选择，因此当轮到参与人 3 行动时，他知 道自己在点 x4 、 x5 、 x6 和 x7 四点中的哪一点上，所以决策集合x4 、 x5 、 x6 和 x7 都是参与人 3 的信息集（参见图 6 5）。图 6-5 博弈树：既知道 1 的选择；也知道 2 的选择从上面分析可以看到： 如果有了信息集这个概念，同时又在博弈中用特定的方式将信息标示出来 1， 那 么给出一个博弈问题的博弈树时，实际上就意味着给出了这个博弈问题的扩展事

23、描述 。例如，如果读者现 在看到的是如图 6 2（ 或者图 63、图 64、图 6 5）所示的博弈树，那么就应该从图 62 中得到一个 博弈问题的扩展事描述，这种描述 包含了扩展事博弈的所有要素 。当然，当采用“将参与人属于同一信息集的决策结用虚线连起来”的方式表示参与人的信息集时，在图 62图65隐含了参与人 2行动时已经观察到参与人 1的行动，因为在图 62图 65中，参 与人 2的信息集都是 单结信息集 （即值 包含一个决策结的信息集 ）2。【例 6 3】 考察“新产品开发博弈” 。试用博弈树描述“两个企业都知道市场要求，且企业 1 先决策， 企业 2 观察到企业 1 的选择后在进行选择”的博弈情形。1 即将属于同一信息集问题结用虚线连起来这种方式来标示博弈中的信息集。2 在博弈考试时