Public Information Representation for Adversarial Team Games

• URL: http://arxiv.org/abs/2201.10377v1
• Date: Tue, 25 Jan 2022 15:07:12 GMT
• Title: Public Information Representation for Adversarial Team Games
• Authors: Luca Carminati, Federico Cacciamani, Marco Ciccone, Nicola Gatti
• Abstract summary: adversarial team games reside in the asymmetric information available to the team members during the play. Our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one.
• Score: 31.29335755664997
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The peculiarity of adversarial team games resides in the asymmetric information available to the team members during the play, which makes the equilibrium computation problem hard even with zero-sum payoffs. The algorithms available in the literature work with implicit representations of the strategy space and mainly resort to Linear Programming and column generation techniques to enlarge incrementally the strategy space. Such representations prevent the adoption of standard tools such as abstraction generation, game solving, and subgame solving, which demonstrated to be crucial when solving huge, real-world two-player zero-sum games. Differently from these works, we answer the question of whether there is any suitable game representation enabling the adoption of those tools. In particular, our algorithms convert a sequential team game with adversaries to a classical two-player zero-sum game. In this converted game, the team is transformed into a single coordinator player who only knows information common to the whole team and prescribes to the players an action for any possible private state. Interestingly, we show that our game is more expressive than the original extensive-form game as any state/action abstraction of the extensive-form game can be captured by our representation, while the reverse does not hold. Due to the NP-hard nature of the problem, the resulting Public Team game may be exponentially larger than the original one. To limit this explosion, we provide three algorithms, each returning an information-lossless abstraction that dramatically reduces the size of the tree. These abstractions can be produced without generating the original game tree. Finally, we show the effectiveness of the proposed approach by presenting experimental results on Kuhn and Leduc Poker games, obtained by applying state-of-art algorithms for two-player zero-sum games on the converted games

Related papers

• Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach [2.908482270923597]
  This paper shows how to disentangle decision variables while maintaining optimality under hierarchical information sharing. Our approach reveals that extensive-form games always exist with solutions to a single-stage subgame, significantly reducing time complexity.
  arXiv  Detail & Related papers  (2024-02-05T12:33:05Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  We consider the problem of decentralized multi-agent reinforcement learning in Markov games. We show that no algorithm attains no-regret in general-sum games when executed independently by all players. We show that our lower bounds hold even for seemingly easier setting in which all agents are controlled by a centralized algorithm.
  arXiv  Detail & Related papers  (2023-03-22T03:28:12Z)
• Abstracting Imperfect Information Away from Two-Player Zero-Sum Games [85.27865680662973]
  Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This work shows that certain regularized equilibria do not possess the aforementioned non-correspondence problem. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games.
  arXiv  Detail & Related papers  (2023-01-22T16:54:06Z)
• Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract) [68.8204255655161]
  We present an incomplete-time approach to determining the winning regions of parity games via graph neural networks. It correctly determines the winning regions of $$60% of the games in our data set and only incurs minor errors in the remaining ones.
  arXiv  Detail & Related papers  (2022-10-18T15:10:25Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solving [31.29335755664997]
  emphEx ante correlation is becoming the mainstream approach for emphsequential adversarial team games, where a team of players faces another team in a zero-sum game. This work shows that we can recover from this weakness by bridging the gap between sequential adversarial team games and 2-player games. We propose a new, suitable game representation that we call emphteam-public-information, in which a team is represented as a single coordinator who only knows information common to the whole team and prescribes to each member an action for any possible private state.
  arXiv  Detail & Related papers  (2022-06-18T10:02:08Z)
• Revisiting Game Representations: The Hidden Costs of Efficiency in Sequential Decision-making Algorithms [0.6749750044497732]
  Recent advancements in algorithms for sequential decision-making under imperfect information have shown remarkable success in large games. These algorithms traditionally formalize the games using the extensive-form game formalism. We show that a popular workaround involves using a specialized representation based on player specific information-state trees.
  arXiv  Detail & Related papers  (2021-12-20T22:34:19Z)
• Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion [10.817873935576412]
  This paper initiates the algorithmic information design of both emphpublic and emphprivate signaling in games with negative externalities. For both public and private signaling, we show that the optimal information design can be efficiently computed when the number of resources is a constant.
  arXiv  Detail & Related papers  (2021-09-25T22:02:32Z)
• Discovering Multi-Agent Auto-Curricula in Two-Player Zero-Sum Games [31.97631243571394]
  We introduce a framework, LMAC, that automates the discovery of the update rule without explicit human design. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance. We show that LMAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO.
  arXiv  Detail & Related papers  (2021-06-04T22:30:25Z)
• 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)
• From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization [49.368421783733815]
  We show how adapting the reward can give strong convergence guarantees in monotone games. We also show how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium.
  arXiv  Detail & Related papers  (2020-02-19T21:36:58Z)

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.