CMSC 5728 Decision Analysis & Game Theory - Lecture 05
- The Iterated prisoners’ Dilemma
- Subgame Perfection
The Iterated prisoners’ Dilemma
考虑以下囚徒困境，合作（C）、背叛（D）
我们令这个博弈只重复一次，那么就有两个阶段，同时我们从后往前分析。在第二阶段也就是最后一个阶段，由于没有下一步交互了，所以双方都会在这一阶段收到 payoff。我们选择最优反应 D，那么 （D， D）就是这个 subgame 的 NE。
注意对于每个玩家在整个博弈来看，纯策略集合是 S = {CC, CD, DC, DD}。但是我们只关注 subgame perfect NE，所以我们只考虑 {CD, DD}。
分析上面的博弈，整个博弈的 NE 是 (D, D) 。所以整个博弈的 subgame perfect NE 是选在两个阶段都选 D。
stationary strategy
固定策略是在每个阶段选择动作的规则都相同的策略。但这并不意味着在每个阶段选择的动作都相同。
e.g.
- 在每个阶段选 C
- 在每个阶段选 D
- 如果其他玩家不选 D ，那么选 C；反之亦然
我们令 SC 为 “每个阶段选 C”，SD 为 “每个阶段选D”，那么它们的总 payoff 分别为
这就会带来一些困扰，因此引入 discount factor δ (0 < δ < 1)，于是总 payoff 就是
于是上面的两个 payoff 可以表示为
trigger strategy
当一次背叛触发行为改变时，该策略称为触发策略
e.g.
我们令 SG 为”一开始合作，并一直合作到其他玩家背叛，然后在之后就一直背叛“
如果两个玩家都采用 SG，那么
(SG, SG) 是 NE 吗（非正式分析）
假设两个玩家被限制选择纯策略集 S = {SG, SC, SD}
假设 P1 决定使用 SC，那么 payoff 就是
同样，P2 选择 SC 的话结果也不会比 (SG, SG) 更好。
假设 P2 选择 SD，那么结果就是
计算
结果为 δ ≥ 1/2。所以当 δ ≥ 1/2 的时候，(SG, SG) 是一个 NE。
练习
同样是囚徒困境，我们令它的纯策略集为 S1 = S2 = {SD, SC, ST, SA}，其中
- ST 表示 “一开始合作，然后做其他玩家前一个阶段的同样的选择”
- SA 表示 “一开始背叛，然后做其他玩家前一个阶段的同样的选择”
那么 δ 需要什么条件才能满足 (ST, ST) 是 NE 呢？
Subgame Perfection
如果两个玩家都采用了 trigger strategy SG，那么它是一个 subgame perfect NE 策略吗。
正式分析
因为这是一个无限迭代的博弈，因此在博弈的任何时候，博弈的未来（即 subgame）都等同于整个博弈。
可能的 subgame 可以分为以下四类
两个玩家都不选 D
双方都不选 D，因此会一直是合作，直到其他玩家背叛。(SG, SG) 是 subgame 的 NE，因为它是整个博弈的 NE。
两个玩家都选 D
两个玩家都选 D，因此会是一直背叛。(SD, SD) 是 subgame 的NE，因为它是整个博弈的 NE。
P1 在最后阶段选 D，P2 不选
在这个情况下，
- 因为 P2 之前选了 C，SG 会让 P1 选 C 并且 P2 选 D。总而言之就是 P1 会是 C, D, D…，而 P2 会是 D, D, D,….
- 所以此 subgame 采用 (SG, SD)
- 但是 (SG, SD) 并不是 subgame 的 NE，因为 P1 通过选择 SD 获得了更好的 payoff
P2 在最后阶段选 D，P1 不选
同上
因此，整个博弈的 NE，(SG, SG)，没有让每个玩家都在各个可能的 subgame 中都是 NE，所以并不是subgame perfect。
虽然 (SG, SG) 不是 subgame perfect NE，我们可以考虑下面类似的策略，即 subgame perfect NE 策略。
我们让 Sg 表示为“一开始合作，并一直合作到任一玩家背叛，然后在之后一直背叛”。这个原因是：
- P1 或 P2 在情况1跟情况2选择 (Sg, Sg)（对于情况2，实际上是 (SD, SD)）
- 情况3和情况4的 P1 和 P2 选择(SD, SD)。
进一步分析
我们证明了 (SG, SG) 是整个博弈的 NE，这是假设策略集是有限的。是否可以允许更多的策略集呢？如果允许更多策略，(SG, SG) 仍然是 NE吗？
如果我们限制自己达到 subgame perfect NE，那么我们首先需要 one-stage deviation principle。
定义
如果两个玩家都无法通过在任何单个阶段单方面偏离其策略并随后返回制定策略来增加收益，则一对策略满足 one-stage deviation principle。
- 情况一
- 如果两个玩家都已经合作，那么 Sg 在此阶段会指定合作
- 如果在此阶段任何一个玩家改为 D，那么 Sg 就会指定一直使用 D。进行此更改的玩家的预期未来收益为
，如果 δ ＞ 1/2，那么这个收益会小于持续合作的收益
。因此玩家不会进行改变。
- 情况二
- 如果任何一个玩家在之前背叛了，那么 Sg 会在此阶段为两个玩家都指定背叛
- 如果在此阶段任一玩家改为 C，那么 Sg 会仍然在之后指定为 D。进行此更改的玩家预期未来收益为
， 如果 δ < 1，那么这个收益会小于一直为 D 所获得的收益。
因此，(Sg, Sg) 在 1/2 < δ < 1 的情况下会满足 one-stage deviation condition。
定理
一对策略是 discounted 重复博弈的 subgame perfect NE，前提是当且仅当满足 one-stage deviation condition