博弈论——扩展式博弈(Extensive Game)

在扩展式博弈中，玩家按照博弈的进程在不同阶段进入决策而不是同时决策，因此决策实际上是一个树形结构，博弈从根节点开始，沿一条路径到达叶节点结束。
- 非叶节点处某一玩家做出决策
- 不同分支为不同决策后博弈的走向
- 叶节点为博弈结果
在普通博弈基础上扩展式博弈的组成增加了：
- 历史(Histories)H：从根节点到当前决策节点的路径中经过的决策的序列(有序集)。特别的，根节点历史为 $\phi$
- Player Function: $P(h)$ 表示在历史h后进行决策的玩家。
因此扩展式博弈可以表示为： $G=\{N,H,P,\{u_i\}\}$

例如在如下博弈中：

$N=\{1,2\}$

$H=\{\phi,A,B,AL,AR\}$

$P:P(\phi)=1; P(A)=2$

纯策略：玩家i的纯策略可以定义为： $\times_{h\in H}\{a^S:(h,a^S)\in H,P(h)=i\}$ ，即所有决策玩家为i的节点决策集的笛卡儿积。（按照从根节点开始按层次书写）
- 纯策略的纳什均衡可由列表法直接计算得出。
- 定理：完全信息的扩展式博弈至少存在一个纯策略纳什均衡（因为每个节点都必须要选出一个最佳策略）
initial history： $A(h)=\{a:(h,a)\in H\}$ ，即h后的所有候选决策集。
terminal history set： $Z=\{(a^1...a^i):i\rightarrow \inf\ or\ a^{i+1}\notin H\}$
博弈长度： $l(G)=\max\limits_{h\in H}\{|h|\}$ ，即博弈树高度
$s_i$ 为玩家i的纯策略，则定义 $s_i(h)=a,a\in A(h),a\in s_i, P(h)=i$ ，即玩家i在策略 $s_i$ 下在h的终点节点所做选的策略。

子博弈(Subgame)：即博弈树的一个高度大于1的子树。特别的，博弈树也是一个子博弈。
- 子博弈可表示为 $G(h)=\{N,H|_h,P|_h,\{u_i|_h\}\}$
- $s_i|_h(h')=s_i(h,h')$
子博弈完美均衡(Subgame Perfect Equilibrium)：博弈结果为为子博弈完美的当且仅当每一个子博弈都达到纳什均衡。
- 定理：完全信息的扩展式博弈中一定存在完美子博弈
- SPE可以通过后向归纳法求得，即不断用子博弈的均衡结果代替子树，直到到达根节点。
单步偏离原则(One Deviation Principlr)：

$s\ is\ SPE\iff\forall i\in N, \forall h\in \{H-Z\}\ s.t.P(h)=i$

$u_i|_h(s^*_i|_h,s^*_{-i}|h)\geq u_i|_h(s_i,s^*_{-i}|h)$ ，其中 $s_i和s_i^*$ 只在 $A(h)$ 中选取不同决策。

即对有限博弈树，判断是否为SPE只需考虑当前节点决策是否最优，而不需要考虑历史决策。

主从博弈(Stackleberg Competition)

规则和古诺均衡类似，两家公司决定产量，不过Player1先决定产量以后Player2再决定产量。

收益满足 $u_i(q_1,q_2)=(max\{0,a-b(q_1+q_2)\}-c)q_i$

Player2：对于Player2决策节点构成的子博弈， $q_1$ 为已知量，最大收益为导数为0时，因此 $q_2=(a-c-bq_1)/2b$ ，和古诺均衡一致。
Player1：由后向归纳法，可以将Player2决策的节点收缩为收益为 $(a-c-bq_1)/2b$ 的叶节点，因此此时Player1的收益为 $(a-b(q_1+\frac{a-c-bq_1}{2b})-c)q_1$ ，导数为零时 $q_1=\frac{a-c}{2b}$
回代得， $q_2=\frac{a-c}{4b}$ ，Player1收益更多。