Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games

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 [11] and certification [12] 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.