马尔可夫博弈中的正规形式相关性

arXiv:2610.03621v1 公告类型：cross 摘要：近年来，关于马尔可夫博弈中相关均衡概念的研究迅速增加。然而，现有成果主要关注弱于正规形式相关均衡（NFCE）的概念，因此，如何计算此类均衡这一更具挑战性的问题仍未解决；该问题可追溯至 Papadimitriou 和 Roughgarden 的开创性工作（JACM'08）。本文首次为具有固定玩家数量 $n$ 的有限时域马尔可夫博弈建立了计算 NFCE 的高效算法。具体而言，对于具有 $S$ 个状态、时域长度 $H$ 且每名玩家至多有 $A$ 个动作的博弈，该算法能在 $S(AH/\epsilon)^{O(n)}$ 时间内计算出一个 $\epsilon$-NFCE。这是首个在正规形式之外的一个重要问题类别中，同时关于 $1/\epsilon$ 和博弈描述规模均为多项式时间的 NFCE 算法。此外，在通常假设各状态之间的推荐相互独立的情况下，我们证明了该问题是 PPAD 完全的——也就是说，在计算上等价于求解 Nash 均衡——这一结论要么适用于多玩家博弈，要么适用于精度指数级微小的情形。我们方法的核心思想是对一系列辅助阶段博弈执行逆向归纳，但其中的关键变化在于：在每一步中，我们计算一个常期望相关均衡。这是相关均衡的一种自然细化，其中，遵循推荐所获得的条件期望收益与推荐内容无关。事实上，我们的归约可以双向进行，从而建立了马尔可夫博弈中常期望相关均衡与 NFCE 之间的等价性。对于固定数量的玩家，通过结合线性规划与适当的离散化，我们发现可以近似计算常期望相关均衡。相比之下，在以下情形中，该问题是 PPAD-hard 的：i）具有常数精度的 polymatrix（多玩家）博弈；ii）具有指数级微小精度的双玩家博弈。后一个结果源于一个出人意料的联系：秩为 2 的双玩家博弈。