迭代剔除受极策略

迭代剔除受极策略（Iterated Elimination of Dominated Strategies）

迭代剔除受极策略（IEDS，又称迭代剔除劣势策略）是博弈论中的一种经典求解方法。其核心思想是：理性玩家不会选择严格受极策略（strictly dominated strategy）——即存在另一策略，无论对手如何行动，该策略的收益都严格更优。通过反复移除这些"劣势"策略，博弈的规模逐步缩小，最终得到一个简化博弈，其留存策略组合即为博弈的解。这一过程依赖于共同知识（common knowledge）的假设：所有玩家知道所有玩家是理性的，且所有玩家知道所有玩家知道……如此无限递推。

基本定义与逻辑

设玩家$i$的策略集为$S_i$。策略$s_i\in S_i$被严格受极，若存在另一策略$s_i'\in S_i$使得对所有对手策略组合$s_{-i}\in S_{-i}$均有：

此时称$s_i'$严格支配（strictly dominates）$s_i$。类似地，若不等式弱化为$\ge$且至少对一个$s_{-i}$取严格不等号，则称弱受极（weakly dominated）。IEDS的标准形式针对严格受极策略。

迭代剔除的步骤为：

1. 找出当前博弈中所有玩家的所有严格受极策略；
2. 将这些策略从策略集中移除；
3. 在缩减后的新博弈中重复前两步，直至无任何受极策略可移除。

与占优策略均衡的关系

占优策略均衡（dominant strategy equilibrium）是IEDS的一种特例。若每个玩家都存在一个占优策略（无论对手如何选择，该策略均严格优于其他所有策略），则一轮剔除即可收敛至该均衡。囚徒困境是典型例子：对每名囚徒而言，"坦白"严格支配"沉默"，一轮剔除后即得（坦白，坦白）。IEDS的适用范畴更广——它不要求每名玩家拥有全局占优策略，仅要求通过逐轮缩小策略集逐步导出唯一解。

严格受极 vs. 弱受极

严格受极策略的剔除顺序不影响最终结果：无论先剔除谁的策略、按何种顺序剔除，最终留存策略集唯一。这一性质称为顺序无关性（order independence）。弱受极策略则不具备此性质。剔除顺序不同可能导致不同的纳什均衡被保留，因此弱受极策略的剔除须谨慎处理，通常仅在特定假设下使用（如玩家偏好"安全"策略时，剔除弱受极策略可缩小解集至帕累托占优均衡）。

与纳什均衡的关系

IEDS的解集与纳什均衡（Nash equilibrium）存在重要关联：

• 任何IEDS留存策略组合必定是纳什均衡？否。反例：猜硬币博弈（零和博弈）无纯策略纳什均衡，但无任何严格受极策略可剔除（所有策略均为最佳应对某些对手策略），IEDS不改变原博弈，故留存策略集包含非纳什均衡组合。
• 任何纳什均衡必定由IEDS留存策略构成？是。纳什均衡中的策略不会是严格受极策略，因此不会被剔除。
• 若IEDS最终只剩唯一策略组合，则该组合必为纳什均衡，且为占优可解（dominance solvable）博弈。古诺模型（Cournot duopoly）在标准假设下即为占优可解博弈。

实例分析

例1：简单2×2博弈。设玩家1可选择{U, D}，玩家2可选择{L, R}。收益矩阵如下（行=玩家1，列=玩家2）：$(2,1)$对(U,L)，$(1,0)$对(U,R)，$(3,0)$对(D,L)，$(0,2)$对(D,R)。第一轮：对玩家1，U的收益(2,1)与D的收益(3,0)比较——当对手选L时U<D，当对手选R时U>D，无严格支配关系，故无受极策略。博弈已简化至无剔除可能。例2：占优可解博弈。将上述矩阵修改：$(3,1)$对(U,L)，$(2,0)$对(U,R)，$(1,0)$对(D,L)，$(0,2)$对(D,R)。第一轮：对玩家2，L支配R（1>0对U，0=0对D——此处适用严格支配需对所有对手策略严格优，但R对D时0=0，故L并不严格支配R。此处应改为严格情形：设D对L为(1,-1)，对R为(0,2)——则L对U时1>0，对D时-1<2，无支配。若调整使得L严格优于R：$(3,2)$对(U,L)，$(2,1)$对(U,R)，$(1,3)$对(D,L)，$(0,0)$对(D,R)。第一轮：玩家2——L严格支配R（2>1且3>0），剔除R。第二轮：缩减后玩家1只剩L可选，U(3)>D(1)，剔除D。唯一留存：(U, L)，为纳什均衡。

经典应用——古诺双寡头：两企业同时选择产量$q_i\in[0,\infty)$，市场需求$P=a-bQ$，边际成本$c$。企业i利润$\pi_i=(a-b(q_i+q_j)-c)q_i$。对任意$q_j$，企业i的最优反应函数$q_i^*(q_j)=\frac{a-c}{2b}-\frac{q_j}{2}$。从$q_i$的定义域出发：任何$q_i>\frac{a-c}{b}$（即超过垄断产量的两倍）在任何$q_j\ge0$下均为负利润，而被$q_i=\frac{a-c}{b}$支配（后者至少为零利润）。第一轮剔除后策略集收缩至$[0,\frac{a-c}{b}]$。第二轮：在此区间内，任何$q_i>\frac{a-c}{2b}+\frac{1}{2}\cdot\frac{a-c}{b}=\frac{3(a-c)}{4b}$？更精确地，通过重复应用最优反应函数，策略空间不断向内收缩，最终收敛至古诺纳什均衡$q_i^*=\frac{a-c}{3b}$。该过程说明IEDS可收敛至唯一均衡，即使初始无占优策略。

局限性与理论意义

IEDS的主要局限包括：

1. 计算复杂性：对策略空间连续的博弈（如古诺模型），IEDS的收敛性依赖于函数性质，且剔除过程需无限轮次；对离散大策略集博弈，逐轮枚举受极策略在计算上可能昂贵。
2. 共同知识假设强：IEDS要求理性为共同知识——玩家1知玩家2理性，玩家2知玩家1知玩家2理性……若共同知识不成立，剔除结果可能不可靠。
3. 弱受极的歧义性：如上所述，弱受极策略的剔除顺序影响解集，限制了方法的普适性。
4. 预期收益最大化假设：IEDS要求玩家严格偏好更高收益，对风险偏好等因素未直接建模。

尽管如此，IEDS奠定了博弈论中理性推理（rationalizable reasoning）的基础。可理性化策略（rationalizable strategies）将IEDS的假设弱化为"玩家相信对手理性"，而非无限递推的共同知识，从而拓宽了适用范围。在实践中，IEDS广泛应用于产业组织理论、拍卖理论、合同理论及实验经济学，用于检验人类的策略推理能力。实验研究表明，多数受试者能进行1-2轮IEDS推理，但更深层次的迭代推理（3轮以上）对大多数人而言存在困难——这反映了级数理性（level-k reasoning）的认知局限性。

总而言之，迭代剔除受极策略是博弈分析的基本工具之一，它不仅提供了求解博弈的直接方法，更揭示了理性推理的深层结构：通过共同知识的层层递推，看似复杂的策略博弈可简化为可预测的结果。