博弈论 中,与正則形式 相应,扩展形式 (英語:Extensive-form game )通过树 来描述博弈。每个节点 (称作决策节点 )表示博弈进行中的每一个可能的状态。博弈从唯一的初始节点 开始,通过由参与者决定的路径到达终端节点 ,此时博弈结束 ,参与者得到相应的收益。每个非终端节点只属于一个参与者;参与者在该节点选择其可能的行动,每个可能的行动通过边 从该节点到达另一个节点。
和正则形式不同,扩展形式允许互动的显式模型(explicit modeling of interactions),互动中,一个参与者可以在博弈中多次行动,并且在不同的状态中可以做出不同的行为。
表述
完整的扩展形式表述包括:
博弈中的参与者
每个参与者能行动的所有机会。
每个参与者在行动时的选择
每个参与者在行动时所知道的情况
每个参与者通过各种可能的行动之后的收益。
一个扩展形式的博弈
右图是一个双人博弈:1和2。每个非终端节点上的数字表示该节点所属的参与者。终端节点上的数字表示参与者的收益(例如:2,1表示参与者1得到2,参与者2得到1)。图片里每个边上的符号是这个边所代表的行动的名字。
初始节点属于参与者1,表示该参与者先动。博弈顺序如下:参与者1选择U 或者D ;参与者2观察到参与者1的选择,然后选择U' 或者D' ,最后得到最终收益。四个终端节点代表四个结果:(U,U'),(U,D'),(D,U')和(D,D')。每个结果得到的收益分别是(0,0),(2,1),(1,2)和(3,1)。
如果参与者1选择D ,参与者2为了最大化收益,会选择U' ,最后参与者1只能得到1。但是如果参与者1选择U ,参与者2为了最大化收益,会选择D' ,此时参与者1得到2。所以参与者1会选择U ,参与者2选择D' 。即是子博弈完美均衡 。
无限行动空间
参与者在一个特定的决策节点上可能有无数种可能的行动可以选择。其表示方法是用弧形来连接从该决策节点延伸出的两条边。如果行动空间是在两个数字之间的闭联集(continuum),那么把这两个表示上下界限的数字分别放在弧的上方和下方,并用一个变量来表示其支付。此时无数个决策节点可以用一个在弧中心的节点所代替。这种表示方式同样可以用在一个有限的行动空间中,只要该行动空间足够大,此时不可能用边来表示每个行动。
用扩展形式中无限行动空间表示的博弈
左侧的树表示这样一个博弈:该博弈或者有一个无限行动空间(任何0到5000的实数 ),或者有一个很大的行动空间(可能是任何在0到5000的整数 )。如果我们在这里假设它表示两个参与Stackelberg竞争 的企业。公司的支付表示在左边,其中q1和q2表示先行者公司以及追随者公司分别采用的策略,c1和c2是常数(表示公司的机会成本)。该博弈的子博弈完美纳什均衡 可以通过对支付函数求追随者策略变量(q2)的一阶偏导数 表示其利润最大化,并求出其最优反应函数,
q
2
(
q
1
)
=
(
5000
− − -->
q
1
− − -->
c
2
)
/
2
{\displaystyle q2(q1)=(5000-q1-c2)/2}
。用同样的方法计算先行者的最优反应函数,并假定先行者知道追随者会选择上述的行动,通过一阶偏导数来解出
q
1
∗ ∗ -->
=
(
5000
+
c
2
− − -->
2
c
1
)
/
2
{\displaystyle q1*=(5000+c2-2c1)/2}
。在将q1*代入到追随者的最优反应函数中,
q
2
∗ ∗ -->
=
(
5000
+
2
c
1
− − -->
3
c
2
)
/
4
{\displaystyle q2*=(5000+2c1-3c2)/4}
,此时(q1*,q2*)就是子博弈完美纳什均衡。如果假设 c1=c2=1000,那么子博弈完美纳什均衡的解就是(2000,1000)。
不完美信息
树图清楚地表示了参与者1先动,参与者2观察到参与者1的行动。然而,一些博弈并不是这样。参与者并不是一直能观察到另一个人的选择(例如,同时行动或者行动被隐藏)。信息集 是决策节点的组合:
每个节点都属于一个参与者。
参与者无法区分信息集里的多个节点。也就是说:如果信息集有多个节点,信息集所属的参与者就不知道能往哪个节点移动。
扩展形式中的不完美信息
完美信息 的博弈是指在博弈的任何阶段,每个参与者都清楚博弈之前发生的所有行动,也即每个信息集都是一个单元素集合 。没有完美信息的博弈具有不完美信息。
左图中的博弈中,参与者2行动时不知道参与者1的选择,除此之外和第一个博弈相同。第一个博弈具有完美信息;而左图中的没有。如果两个参与者都是理性的,并且都知道对方也是理性人,对方知道的信息,自己也能获得(即参与者1知道参与者2知道参与者1是理性的,参与者2同样也知道,如此循环下去),
公理的公式化
博弈论是一种数学理论,所以上述的博弈树结构可以转化为公式表达。
扩展形式的有限树是这样一个结构
Γ Γ -->
=
⟨ ⟨ -->
K
,
H
,
[
(
H
i
)
i
∈ ∈ -->
I
]
,
{
A
(
H
)
}
H
∈ ∈ -->
H
]
,
a
,
ρ ρ -->
,
u
⟩ ⟩ -->
{\displaystyle \Gamma =\langle {\mathcal {K}},\mathbf {H} ,[(\mathbf {H} _{i})_{i\in {\mathcal {I}}}],\{A(H)\}_{H\in \mathbf {H} }],a,\rho ,u\rangle }
其中:
K
=
⟨ ⟨ -->
V
,
v
0
,
T
,
p
⟩ ⟩ -->
{\displaystyle {\mathcal {K}}=\langle V,v^{0},T,p\rangle }
表示一个有限的树。
V
{\displaystyle V}
是树的所有节点,
v
0
∈ ∈ -->
V
{\displaystyle v^{0}\in V}
表示唯一的初始节点,
T
⊂ ⊂ -->
V
{\displaystyle T\subset V}
表示所有的终端节点(
D
=
V
∖ ∖ -->
T
{\displaystyle D=V\setminus T}
是决策节点)以及函数
p
:
V
→ → -->
D
{\displaystyle p:V\rightarrow D}
表示博弈的规则,
H
{\displaystyle \mathbf {H} }
表示
D
{\displaystyle D}
里包含的信息,
A
(
H
)
{\displaystyle A(H)}
是信息集
H
∈ ∈ -->
H
{\displaystyle H\in \mathbf {H} }
所允许的可能的行动。所有的行动表示为
A
{\displaystyle {\mathcal {A}}}
。
参考文献
参见