For common notions of correlated equilibrium in extensive-form games, computing an optimal (e.g., welfare-maximizing) equilibrium is NP-hard. Other equilibrium notions -- communication (Forges 1986) and certification (Forges & Koessler 2005) equilibria -- augment the game with a mediator that has the power to both send and receive messages to and from the players -- and, in particular, to remember the messages. In this paper, we investigate both notions in extensive-form games from a computational lens. We show that optimal equilibria in both notions can be computed in polynomial time, the latter under a natural additional assumption known in the literature. Our proof works by constructing a mediator-augmented game of polynomial size that explicitly represents the mediator's decisions and actions. Our framework allows us to define an entire family of equilibria by varying the mediator's information partition, the players' ability to lie, and the players' ability to deviate. From this perspective, we show that other notions of equilibrium, such as extensive-form correlated equilibrium, correspond to the mediator having imperfect recall. This shows that, at least among all these equilibrium notions, the hardness of computation is driven by the mediator's imperfect recall. As special cases of our general construction, we recover 1) the polynomial-time algorithm of Conitzer & Sandholm (2004) for automated mechanism design in Bayes-Nash equilibria and 2) the correlation DAG algorithm of Zhang et al (2022) for optimal correlation. Our algorithm is especially scalable when the equilibrium notion is what we define as the full-certification equilibrium, where players cannot lie about their information but they can be silent. We back up our theoretical claims with experiments on a suite of standard benchmark games.
翻译:对于广义游戏中关联平衡的共同概念来说,我们从计算角度来调查广泛形式游戏中的概念, 计算最佳( 福利最大化) 平衡是NP- 硬的。 其他平衡概念 -- 沟通( Forges 1986) 和认证( Forges & Koessler 2005), equilibria -- -- 与一个拥有向玩家发送和接收信息的权力的调解人一起增加游戏 -- -- 特别是记住信息。 在本文件中, 我们从计算角度来调查广泛形式游戏中的两个概念。 我们显示, 两种概念中的最佳对等平衡可以在多式时间中计算, 后者可以在文献中已知的自然的额外假设下计算。 我们通过构建一个调解人强化的游戏, 明确代表调解人的决定和行动。 我们的框架允许我们通过改变调解人的信息分布、 玩家的说谎能力以及玩家的偏差能力。 我们从这个角度显示, 两个概念的最佳平衡概念, 比如, 广泛化的相互关联性关系, 后者在文献中, 自然的额外的相对性,, 也就是我们大脑结构的正变的正变。