  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.
