Asymptotic Analysis for Pure Dominated Strategy in Random Games

技术摘要：随机博弈中纯支配策略的渐近分析

问题陈述
本文研究了大规模双人随机博弈中严格支配策略的渐近存在性及其普遍性。在这些博弈中，收益是根据给定分布独立同分布抽取的。本研究解决了三个核心挑战：

1. 理论存在性： 确定当策略空间（行玩家为 $M$，列玩家为 $N$）趋于无穷大时，存在非平凡比例（$q$-比例）支配策略的精确渐近阈值。
2. 与经典结果的关系： 阐明这些阈值如何与“是否存在任何严格支配策略”这一经典问题相关联，特别是测试了 Alon, Rudov, 和 Yariv (2021) 关于支配概率存在剧烈转变的猜想。
3. 计算效率： 开发一种实用的、与分布无关的算法来检测支配策略，该算法通过利用收益极值，改进了标准的 $O(M^2N)$ 暴力搜索法。

方法论
分析依赖于随机博弈框架（Goldman 1957）下的概率方法和渐近分析。

• 定义： 本文引入了 $q$-比例支配策略，定义为一个大小为 $\lceil qM \rceil$ 的子集，其中该子集中的每一个策略都被另一个策略严格支配。
• 概率界限：
  • 负面结果： 利用二项式系数近似建立了不存在 $q$-比例支配策略的结论。
  • 正面结果： 使用 Chernoff 界证明了此类策略的存在性。分析将事件分为“弱”行（所有条目均低于某一阈值）和“强”行（所有条目均高于某一阈值）。
• 分布参数 ($\rho$)： 结果由 $\rho$ 参数化，$\rho$ 是一个随机抽取的收益超过另一个收益的概率的倒数（$\rho = [P(X_s > X_{s'})]^{-1}$）。对于非原子分布，$\rho=2$；对于含有原子的分布，$\rho > 2$。
• 算法方法： 提出的算法（算法 2）利用预处理步骤来计算每个收益向量的最小值和最大值。随后，它通过基于这些极值的排序进行逻辑检查，从而在不进行完整逐元素比较的情况下判定支配关系。

核心贡献与结果

1. $q$-比例支配的渐近阈值
本文确立了支配 $q$-比例策略存在的精确条件：

• 不存在机制： 如果对于某个 $\alpha > 0$，满足 $N \geq M / (\ln M)^\alpha$，则当 $M, N \to \infty$ 时，$q$-比例策略被支配的概率收敛于零。即使 $N$ 相对于 $M$ 呈线性或更快的增长，该结论依然成立。
• 存在机制： 如果对于某个 $\delta > 0$，满足 $M \gg (N / (1 - \delta - q))^N$，则（特别是被单个策略支配的）$q$-比例策略存在的概率收敛于一。
• 结构性见解： 正面结果是一个强有力的结构性陈述，表明当博弈足够不平衡时，可以在单步严格支配过程中消除非平凡比例的策略。

2. 对单策略支配猜想的确认
本文确认了 Alon, Rudov, 和 Yariv (2021) 关于存在任何严格支配策略的猜想：

• 存在一个阈值函数 $f(N) \in \Theta(\ln N)$，使得当 $M, N \to \infty$ 且 $M$ 在特定范围内增长（例如 $M > f(N)$ 但不过于大）时，博弈中不包含支配策略的概率趋于一。
• 具体而言，对于均匀分布的收益，如果 $M$ 的增长速率位于 $[(2+\delta)\log_2(N), 2N^{2+\delta}]$ 之间，则存在严格支配策略的概率趋于零。因此，在此机制下，支配可解性收敛于零。
• 相变： 本文根据 $M$ 与 $N$ 的相对增长情况划定了不同的区域：
  • 当 $M$ 相对于 $N$ 适度增长（高于对数阈值但低于指数级）时，存在严格支配策略的概率趋于零，这意味着此类策略实际上是不存在的。
  • 当 $M$ 增长得足够快（例如 $M \gg (N/(1-\delta-q))^N$）时，支配策略变得几乎确定（存在概率 $\to 1$）。
  • 存在中间地带，其概率保持在 0 和 1 之间。

3. 算法改进（算法 2）
本文提出了一种比暴力搜索更高效的、与分布无关的检测严格支配策略的算法：

• 机制： 算法预计算每个策略收益向量的最小值和最大值。然后检查成对关系：
  • 如果 $\min(s_i) > \max(s_j)$，则 $s_i$ 严格支配 $s_j$。
  • 如果 $\max(s_i) > \max(s_j) > \min(s_j) > \min(s_i)$，则 $s_i$ 与 $s_j$ 之间不存在支配关系。
• 效率： 命题 5 表明，在 $N \to \infty$ 的极限下，大约 50% 的成对比较属于第二类（无支配）或第一类（明确支配），这使得算法能够跳过完整的逐元素比较。
• 复杂度： 虽然最坏情况下的时间复杂度仍为 $O(M^2N)$，但该算法在实践中实现了常数倍的性能提升。它平均减少了约一半的比较次数，并通过将预处理（顺序内存访问）与比较（标量查找）分离，提供了更优的缓存友好性，从而降低了大规模矩阵中的内存延迟问题。

意义与主张
本文声称通过将研究从单策略支配推广到 $q$-比例支配，为大规模博弈中的策略消除提供了统一的视角。

• 理论层面： 它阐明了单策略消除与大规模策略剪枝之间的关系，表明虽然在平衡的大规模博弈中（即 $M$ 和 $N$ 以相当或适度的速率增长时）单个支配策略可能会消失，但在不平衡机制下（即 $M$ 增长得足够快时），可以消除大量的策略。
• 实践层面： 所提算法提供了一个高效的工具，用于在无需对底层收益分布做假设的情况下识别支配策略。这被视为计算博弈论中消除程序的实用补充，特别是在收益矩阵超过处理器缓存容量的情况下。
• 范围： 作者指出，分析仅限于纯策略和独立同分布（i.i.d.）收益，并将混合策略支配和非 i.i.d. 设置确定为未来的研究方向。本文并不声称解决了在所有情况下寻找精确支配策略集合的一般问题，而是提供了渐近界限和更高效的检测启发式方法。