1.什么是博弈树
博弈树是指由于动态博弈参与者的行动有先后次序,因此可以依次将参与者的行动展开成一个树状图形。[1]
博弈树是扩展型的一种形象化表述。它能给出有限博弈的几乎所有信息。其基本构建材料包括结、枝和信息集。结包括决策结和终点结两类;决策结是参与人采取行动的时点,终点结是博弈行动路径的终点。枝是从一个决策结到它的直接后续结的连线(有时用箭头表述),每一个枝代表参与人的一个行动选择。博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策集集合的一个子集,该子集包括所有满足下列条件的决策结:(1)每一个决策结都是同一参与人的决策结;(2)该参与人知道博弈进入该集合的某个决策结,但不知道自己究竟处于哪一个决策结。[2]
2.博弈树的特点[3]
(1) 博弈的初始格局是初始节点。
(2) 在博弈树中,"或"节点和"与"节点是逐层交替出现的。自己一方扩展的节点之间是"或"关系,对方扩展的节点之间是"与"关系。双方轮流地扩展节点。
(3) 所有自己一方获胜的终局都是本原问题,相应的节点是可解节点;所有使对方获胜的终局都认为是不可解节点。