提出在不完美信息博弈中高效识别占优行动的方法，可大幅压缩博弈树规模。
Dominated Actions in Imperfect-Information Games
- 基于混合策略定义占优行动，设计多项式时间判定算法
- 可在两人完美记忆博弈中高效移除占优动作，减少博弈树规模
- 实测验证其在德州扑克中的有效性，适合博弈求解前处理
占优是博弈论中的基础概念。在标准形式博弈中，占优策略可在多项式时间内识别，因此可通过迭代删除占优策略高效压缩博弈规模，作为计算纳什均衡的预处理步骤。对于展开形式的不完美信息博弈，虽可转换为标准形式后进行相同操作，但此转换可能导致博弈规模指数级膨胀。本文定义并研究了不完美信息博弈中的占优行动。主要成果是在具有公开可观测动作的双人完美记忆博弈中，提出了判定某行动是否被任何混合策略严格或弱占优的多项式时间算法，该方法可扩展至迭代删除占优行动。这使得在计算纳什均衡前能高效缩减博弈树规模。我们通过实验考察了占优行动在‘全下或弃牌’无限制德州扑克中的作用。
原文摘要 · Abstract (English)
Dominance is a fundamental concept in game theory. In normal-form games dominated strategies can be identified in polynomial time. As a consequence, iterative removal of dominated strategies can be performed efficiently as a preprocessing step for reducing the size of a game before computing a Nash equilibrium. For imperfect-information games in extensive form, we could convert the game to normal form and then iteratively remove dominated strategies in the same way; however, this conversion may cause an exponential blowup in game size. In this paper we define and study the concept of dominated actions in imperfect-information games. Our main result is a polynomial-time algorithm for determining whether an action is dominated (strictly or weakly) by any mixed strategy in two-player perfect-recall games with publicly observable actions, which can be extended to iteratively remove dominated actions. This allows us to efficiently reduce the size of the game tree as a preprocessing step for Nash equilibrium computation. We explore the role of dominated actions empirically in "All In or Fold" No-Limit Texas Hold'em poker.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。