63、序贯决策理论中的博弈问题解析

序贯决策理论中的博弈问题解析

1. 序贯博弈树的优化与求解

在序贯博弈中，博弈树的探索存在优化空间。当按照深度优先顺序探索博弈树时，有些子节点（甚至整个子树）无需探索。例如，若玩家 P2 的响应会导致比玩家 P1 选择另一个动作所能确保的成本更高，就可以选择另一个动作。这种情况可能出现在树的任何层级，当某个动作无需考虑时，整个子树都可被排除。

1.1 计算鞍点

• 交替行动模型 ：玩家 P1 的安全计划是该模型下博弈的有效解，玩家 P2 只需在每个阶段对 P1 的计划做出最优响应。
• 逐阶段模型 ：“解”的概念是鞍点，即上值和下值重合时的情况。若上下值不重合，则需为玩家制定随机安全计划。在随机计划空间中，鞍点总是存在的，意味着博弈总有一个随机值。可以从下往上计算这个鞍点，类似于计算安全计划的方法。

以一个具体例子说明，通过将博弈树的底层转化为矩阵博弈，计算每个矩阵博弈的随机值并替换原树中的相应部分，最终确定原序贯博弈的解。这种方法的好处是，若矩阵没有确定性鞍点，可计算其随机值。

1.2 将树转换为单阶段博弈

对于开环模型，玩家在游戏结束并收到成本之前没有信息交换，可将序贯博弈等效为一个大型单阶段博弈。以图 10.13 的博弈为例，玩家 P1 和 P2 各有四种可能的计划，可排列成一个 4×4 的矩阵博弈。此矩阵博弈没有确定性鞍点，需求解一个四维线性规划问题来找到随机值和均衡，这与其他两种信息模型的解有很大不同。

在逐阶段模型下，序贯博弈的计划空间更大。例如图 10.13 的