Can I read Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games on EtoBox?

Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games by Zhang, Brian Hu; Sandholm, Tuomas is a scholarly article available to read on EtoBox.

What is Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games about?

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 equi

Author

Zhang, Brian Hu; Sandholm, Tuomas

Published

2022

Language

EN