第6章：扩展式博弈及其均衡)

P(x) = { y ∈ X | y ≺ x}
2） x 的后续结 T (x) （the set of successors）：
T(x) = { y ∈ X | x ≺ y}
若 (x) = φ， x为 点 ； T 则 终 结 若 (x) = φ， x为 始 。 P 则 初 结
3） x 的直接前列结 P(x) x 不为初始结) ( （immediate predecessor）
性质1）、2）意味着 ≺为一半序 （partial order）或偏序。应注意的是 ≺ 不一定具有连通性（connectedness） 或完备性（completeness），即：
∀ 1, x2 ∈ X , 必 x 有 x ≺ x2 1 或 x2 ≺ x 1
关于节的基本概念
1） x 的前列集 P(x) （the set of predecessors）：
1结
决策结（decision nodes）：参与人采取行 动的时点； 终点结（terminal nodes）：博弈行动路径 的终点。
用 X表示所有决策结的集合。 ∈ X 为某一特定 x 的决策结。
用 ≺ 表示定义在 X上的顺序关系 （precedence relation）或者二元关 系（binary relation）：
扩展式的构成要素：
1) 参与人集合 Γ ={1,2,...,n} ； 2) 参与人的行动顺序（the order of moves）：谁在什么时候行动 i(x) ； 3) 参与人的行动空间（action set）：在 每次行动时，参与人有些什么选择
A(x)
；
扩展式的构成要素：
4) 参与人的信息集（information set）： 每次行动时，参与人知道些什么 H(x) ； 5) 参与人的支付函数：在行动结束时，每 次参与人得到些什么（支付是所有行动 的函数）； 6) 外生事件（即自然的选择）的概率分布。
休息一会！！！
第二部分 完全信息动态博弈
第六章 博弈的扩展式表示
例1 Nim游戏
三枚硬币如图排列。A、B 两人轮流取硬币，每一轮 每个选手必须至少拿走一 枚硬币，不允许在两行中 挑选硬币。取走最后一枚 硬币的选手为获胜者。 假设A先行动，问A该如何选择才能获胜？
例1 Nim游戏
A B A B B获胜 A A B B获胜 A获胜 A获胜 A获胜
甲 乙
4) 博弈满足“完美记忆”（perfect recall）的要求。 “完美记忆” ： 没有参与人会忘记自己以前知道的 事情，所有参与人都知道自己以前的选 择。
1 U D 2 R L R 1
N
1 U 2 L R L D U
1 D
R 1
第六章 扩展式表述博弈的Nash均衡
以新产品开发为例。
定义1：设 S = (s , s ,..., s ， S*为扩 ) 展式的一个Nash均衡，当且仅当 ∀i ∈Γ
* * 1 * 2 * n
s ∈argmaxUi (si , s−i )
* i * si∈Si
或者∀si ∈Si， i (si , s ) ≥ Ui (si , s )。 U
* −i * −i
5 i(⋅) : X →{1 ） ,2,..., n, N}
即 i(x) 定义为从决策结集合到参与人集合 的函数。可解释为在决策结 x参与人 i 行动，决定了“谁在什么时候行动”的 i(0) 问题。如前图中， = A 。 函数 i(x) 给出了博弈中参与人行动顺 序的完全描述（扩展式的第二个要素）。
博弈树
人有限战略博弈的扩展式描述可以 用博弈树来表示，如新产品开发博弈。 N
大 开发 小
A
不开发 大
N
小
B
开发 不开发 开发
B
不开发
B
开发 不开发 开发
B
不开发
博弈树几乎包含了有限博弈的所有 信息，其最基本的构成： 1）结（node）； 2）枝（branch）； 3）信息集（information set）。
N
大
开发 小
A
不开发 大
N
小
B
B
B
B
B知道N的选择但不知道A的选择。 此时，B的信息集由两个组成。
N
大
开发 小
A
不开发 大
N
小
B
B
B
B
B对A，N的选择都不知道。B 只存在一个信息集。
信息集的结构说明：
博弈的结构是共同知识，即所有 人都可看到博弈树。
如果博弈树的所有信息集都是单结 的，则称该博弈为完美信息博弈（game of perfect information）。 它意味着没有两个人同时行动，并 且所有后行动者确切知道前行动者的选 择，所有参与人观测到自然选择。
A N B B B N B
B知道A、N的选择，但A不知道N的选择。
A B
大
N
小
A B
B
B
假定：自然的信息集为单结的
A B
大
N
小
A B
B
B
B A
大
N
小
B A
A

有了信息集的概念，扩展式也可用来表 示静态博弈。 乙 坦白 坦白 －8，－8 甲 抵赖 －10，0 抵赖
0，－10 －1，－1
甲 乙 乙 乙
∀x1, x2 ∈ X ,
≺
x1 ≺ x2 ⇔ x1在 2之 x 前
1）传递性（transitivity）：
≺满足：
∀x1, x2 , x3 ∈ X , 若 1 ≺ x2，x2 ≺ x3,则 x x1 ≺ x3
2）反对称性（asymmetricity）：
∀x1, x2 ∈ X , 若 1 ≺ x2， x 则 x2 ≺ x1 不 立 成 。
开发
-0.3,-0.3 -0.3,-0.3 0.1,0 0,0.1 0,0 0,0.1
0.1,0 0,0
A
不开发
注意：均衡与均衡结果是不同的!!!
SA = A(h(O))
= {开发，不开发 ; }
SB = A(h(x1)) × A(h(x2 )) ={{开发，开发},开发，不开发}, { {不开发，开发},不开发，不开发} { }
信息集是决策结集合 X 的子集。 当一个参与人在作出决策时，他知道的 和不知道的“之前”所发生的所有事情。
N
大
开发 小
A
不开发 大
N
小
B
B
B
B
B知道A、N的决策，存在7个决策结。 7个信息集，A一个，N两个，B四个 。
N
大
开发 小
A
不开发 大
N
小
B
B
B
B
B只知道A的选择，而不知道N的选择。 此时，B的信息集由四个变成了两个。
所有参与人的一个纯战略组合
s = (s1, s2 ,..., sn )
决定了博弈树上的一个路径，例如（开发， {不开发，开发}）决定了博弈路径： A (0.1,0) 开发 B 不开发
战略组合（不开发，{开发，开发}）决定了 博弈路径： A (0,0.1) 不开发 B 开发
不同的纯战略组合可能决定同一个路 径，例如，战略组合（开发，{不开发， 开发}）和（开发，{不开发，不开发}） 决定了： A (0.1,0) 开发 B 不开发
N
大 小 开发
O A B
X1
A
不开发
A B B B
B
X2 不开发 不开发 开发
B
开发
A、B知道N的选择， B知道A的选择
完美信息博弈
SA ={开发，不开发}(A只有一个信息集， 两个可选择行动)。 SB ={{开发,开发}，{开发,不开发}， {不开发,开发}，{不开发,不开发}}
B
开发，开发 开发，不开发 不开发，开发 不开发，不开发
∗
定义3：如果一个扩展式博弈有有限 个参与人，且有有限信息集，每个信息 集上参与人有有限个行动选择，则这个 博弈为有限博弈。
定理1（Zermelo,1913;Kuhn,1953）一 个有限完美信息博弈有一个纯战略Nash均 衡。 定理1的证明可利用动态规划中的“逆 向归纳法”（backward induction）来证明 的。
设 (x) ∈P(x)， x′ ∈P(x) p ∀ 且 ′ ≠ p(x)， x′ ≺ p(x)， 称 x 若 则 p(x)为 的 接 列 x 直 前 结 （ 然 (x)唯 ） 显 p 一 。
4） 的直接后续结 t(x) x 不为终点结） （ x （immediate successor）
设 (x) ∈T(x)， ∃x′ ∈T(x),使 t 若 x′ ≺ t(x) 则 t(x)为 的 接 续 称 x 直 后 结 （ 一 唯 ） 不 定 一 。
静态博弈——参与人同时行动。 用战略(标准)式描述。 动态博弈——参与人的行动顺序有先后。 用扩展式描述。
Si
战略式的构成元素：
参与人集合
Γ；
i
参与人的战略集合 S ； 参与人的支付 Ui
。
G =< Γ; Si ,..., Sn ;U1,...,Un > 或 G =< Si ,..., Sn ;U1,...,Un >
2枝 枝是一个决策结到它的直接后续结的连线， 每一个枝代表在该决策结行动的参与人的 行动选择。
这意味着：从给定结点出发，当且仅 当参与人选择不同的行动时，才会达到不 同的直接后续结。 枝不仅完整的描述了每一决策结参与 人的行动空间（第三要素），而且给出了 从一个决策结到下个决策结的路径。
3 信息集
扩展式：
扩展式主要是对参与人的战略集 Si 进 行“扩展”，即要给出每个战略的动态描 述：在某一时刻，谁行动，怎么行动即行 动方案由哪些组成，依据什么行动(即信息 是什么)。