The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game

• 成果类型: Article
• 署名作者: Etessami, Kousha
• 署名单位: University of Edinburgh
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2019.03.006
• 发表日期: 2021
• 页码: 107-140
• 关键词: Extensive form game; perfect equilibrium; Quasi-perfect equilibrium; algorithms; computational complexity

摘要

We study the complexity of computing or approximating refinements of Nash equilibrium for finite n-player extensive form games of perfect recall (EFGPR), n >= 3. Our results apply to a number of well-studied refinements, including sequential equilibrium, extensive-form perfect equilibrium, and quasi-perfect equilibrium. Informally, we show that, for all these refinements, approximating such a refined equilibrium for an n-player EFGPR is not any harder than (i.e., can be efficiently reduced to) approximating a Nash equilibrium for a 3-player normal form game. More specifically, we show that approximating such a refined equilibrium for a given EFGPR, within given desired precision, is FIXPa-complete. We also study corresponding notions of almost equilibrium for these refinements, and we show that computing one is PPAD-complete. (In all these cases our main results show containment in FIXP a and containment in PPAD. Hardness follows from earlier results for simpler games.) (C) 2019 Elsevier Inc. All rights reserved.