Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation

• URL: http://arxiv.org/abs/2203.07181v1
• Date: Mon, 14 Mar 2022 15:21:18 GMT
• Title: Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
• Authors: Brian Zhang, Gabriele Farina, Andrea Celli, Tuomas Sandholm
• Abstract summary: We study the problem of finding optimal correlated equilibria of various sorts. We introduce the correlation DAG, a representation of the space of correlated strategies whose size is dependent on the specific solution concept. We also introduce two new benchmark games: a trick-taking game that emulates the endgame phase of the card game bridge, and a ride-sharing game.
• Score: 99.00383370823839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of finding optimal correlated equilibria of various sorts: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). This is NP-hard in the general case and has been studied in special cases, most notably triangle-free games, which include all two-player games with public chance moves. However, the general case is not well understood, and algorithms usually scale poorly. First, we introduce the correlation DAG, a representation of the space of correlated strategies whose size is dependent on the specific solution concept. It extends the team belief DAG of Zhang et al. to general-sum games. For each of the three solution concepts, its size depends exponentially only on a parameter related to the game's information structure. We also prove a fundamental complexity gap: while our size bounds for NFCCE are similar to those achieved in the case of team games by Zhang et al., this is impossible to achieve for the other two concepts under standard complexity assumptions. Second, we propose a two-sided column generation approach to compute optimal correlated strategies. Our algorithm improves upon the one-sided approach of Farina et al. by means of a new decomposition of correlated strategies which allows players to re-optimize their sequence-form strategies with respect to correlation plans which were previously added to the support. Our techniques outperform the prior state of the art for computing optimal general-sum correlated equilibria. For team games, the two-sided column generation approach vastly outperforms standard column generation approaches, making it the state of the art algorithm when the parameter is large. Along the way we also introduce two new benchmark games: a trick-taking game that emulates the endgame phase of the card game bridge, and a ride-sharing game.

Related papers

• The Computational Complexity of Single-Player Imperfect-Recall Games [37.550554344575]
  We study extensive-form games with imperfect recall, such as the Sleeping Beauty problem or the Absent Driver game. For such games, two natural equilibrium concepts have been proposed as alternative solution concepts to ex-ante optimality.
  arXiv  Detail & Related papers  (2023-05-28T19:41:25Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Safe Subgame Resolving for Extensive Form Correlated Equilibrium [47.155175336085364]
  Correlated Equilibrium is a solution concept that is more general than Nash Equilibrium (NE) and can lead to better social welfare. We apply textitsubgame resolving, a technique extremely successful in finding NE in zero-sum games to solving general-sum EFCEs. Subgame resolving refines a correlation plan in an textitonline manner: instead of solving for the full game upfront, it only solves for strategies in subgames that are reached in actual play.
  arXiv  Detail & Related papers  (2022-12-29T14:20:48Z)
• Learning in Multi-Player Stochastic Games [1.0878040851638]
  We consider the problem of simultaneous learning in games with many players in the finite-horizon setting. While the typical target solution for a game is a Nash equilibrium, this is intractable with many players. We turn to a different target: algorithms which generate an equilibrium when they are used by all players.
  arXiv  Detail & Related papers  (2022-10-25T19:02:03Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  We focus on the problem of finding an optimal strategy for a team of two players that faces an opponent in an imperfect-information zero-sum extensive-form game. In that setting, it is known that the best the team can do is sample a profile of potentially randomized strategies (one per player) from a joint (a.k.a. correlated) probability distribution at the beginning of the game. We provide an algorithm that computes such an optimal distribution by only using profiles where only one of the team members gets to randomize in each profile.
  arXiv  Detail & Related papers  (2020-09-21T17:51:57Z)
• Polynomial-Time Computation of Optimal Correlated Equilibria in Two-Player Extensive-Form Games with Public Chance Moves and Beyond [107.14897720357631]
  We show that an optimal correlated equilibrium can be computed in time in two-player games with public chance moves. This results in the biggest positive complexity result surrounding extensive-form correlation in more than a decade.
  arXiv  Detail & Related papers  (2020-09-09T14:51:58Z)
• No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium [76.78447814623665]
  We give the first uncoupled no-regret dynamics that converge to correlated equilibria in normal-form games. We introduce a notion of trigger regret in extensive-form games, which extends that of internal regret in normal-form games. Our algorithm decomposes trigger regret into local subproblems at each decision point for the player, and constructs a global strategy of the player from the local solutions.
  arXiv  Detail & Related papers  (2020-04-01T17:39:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.