博弈树game tree

博弈树是扩展型的一种形象化表述。它能给出有限博弈的几乎所有信息。其基本构建材料包括结、枝和信息集。结包括决策结和终点结两类；决策结是参与人采取行动的时点，终点结是博弈行动路径的终点。枝是从一个决策结到它的直接后续结的连线（有时用箭头表述），每一个枝代表参与人的一个行动选择。博弈树上的所有决策结分割成不同的信息集。每一个信息集是决策集集合的一个子集，该子集包括所有满足下列条件的决策结：(1)每一个决策结都是同一参与人的决策结；(2)该参与人知道博弈进入该集合的某个决策结，但不知道自己究竟处于哪一个决策结。

博弈树

表示有限参与者进行有限策略动态博弈的一种树形图。用博弈树形式来表示的、有限参与者所进行的有限策略动态博弈，称为“扩展式博弈”。博弈树清楚地表明了博弈的行动顺序，给出了有限博弈的几乎所有信息。博弈树由结、枝和信息集组成。 (1) 结： 包括决策结和终点结两种。决策结是参与者采取行动的时点。博弈开始的那个决策结又称为“初始结”，图中以空心圆圈表示；其他决策结用实心圆圈表示。终点结是博弈行动路径的终点，每个终点结给出博弈的一种结果，图中以方框表示。在博弈树中，从初始结到任何一个结都只有唯一的一条路径。习惯上，终点结上的收益矩阵的第一列数字是博弈树上第一个参与者的收益，第二列数字是博弈树上第二个参与者的收益。(2) 枝： 在博弈树中，枝是从一个决策结到它的直接后续结的连线。每一个枝代表参与者的一个行动选择。当且仅当参与者选择不同的行动时，从一个给定的决策结出发才会到达不同的直接后续结。博弈树的枝不仅完整地描述了每一个决策结上参与者的行动空间，而且给出了从一个决策结到下一个决策结的路径。(3) 信息集： 博弈树上的所有决策结分割成不同的信息集，每一个信息集是所有决策结所构成的集合的一个子集。图中，所有属于同一信息集的结点由虚线连接起来(为简明起见，本图只画出一个信息集)。一个信息集可能包含多个决策结，也可能只包含一个决策结。每一个决策结均属于一个信息集，并且只属于一个信息集。只包含一个决策结的信息集称为“单结信息集”。
现以生产冰淇淋的两家企业的博弈为例。图中初始结为企业1采取行动的时点。从初始结引出的两个枝代表企业1可能的行动选择： 推出巧克力冰淇淋或水果冰淇淋(图中省“冰淇淋”字样)。然后是企业2对企业1选择的可能反应。在企业1推出巧克力冰淇淋的情况下，从企业2的决策结可引出两个枝： 一个枝是企业2也推出巧克力冰淇淋，这样，在终点结表明，企业1和企业2的利润收益均为-10个单位；另一个枝是企业2推出水果冰淇淋，这样，在终点结表明，企业1和企业2的利润收益分别为20个和30个单位。同样，可以得到企业1推出水果冰淇淋的情况下两家企业的收益组合。为了找出该扩展式博弈的解，可从终点结向前推导。对企业1来说，最好的结果是它赚到利润30个单位、企业2赚到利润20个单位的双方行动。因此可以向前推导出： 企业1应该推出水果冰淇淋，因为此时企业2的最优反应是推出巧克力冰淇淋。在这个博弈中，先行动者具有明显的优势。