Learning to Resolve Alliance Dilemmas in Many-Player Zero-Sum Games

• URL: http://arxiv.org/abs/2003.00799v1
• Date: Thu, 27 Feb 2020 10:32:31 GMT
• Title: Learning to Resolve Alliance Dilemmas in Many-Player Zero-Sum Games
• Authors: Edward Hughes, Thomas W. Anthony, Tom Eccles, Joel Z. Leibo, David Balduzzi, Yoram Bachrach
• Abstract summary: We argue that a systematic study of many-player zero-sum games is a crucial element of artificial intelligence research. Using symmetric zero-sum matrix games, we demonstrate formally that alliance formation may be seen as a social dilemma. We show how reinforcement learning may be augmented with a peer-to-peer contract mechanism to discover and enforce alliances.
• Score: 22.38765498549914
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zero-sum games have long guided artificial intelligence research, since they possess both a rich strategy space of best-responses and a clear evaluation metric. What's more, competition is a vital mechanism in many real-world multi-agent systems capable of generating intelligent innovations: Darwinian evolution, the market economy and the AlphaZero algorithm, to name a few. In two-player zero-sum games, the challenge is usually viewed as finding Nash equilibrium strategies, safeguarding against exploitation regardless of the opponent. While this captures the intricacies of chess or Go, it avoids the notion of cooperation with co-players, a hallmark of the major transitions leading from unicellular organisms to human civilization. Beyond two players, alliance formation often confers an advantage; however this requires trust, namely the promise of mutual cooperation in the face of incentives to defect. Successful play therefore requires adaptation to co-players rather than the pursuit of non-exploitability. Here we argue that a systematic study of many-player zero-sum games is a crucial element of artificial intelligence research. Using symmetric zero-sum matrix games, we demonstrate formally that alliance formation may be seen as a social dilemma, and empirically that na\"ive multi-agent reinforcement learning therefore fails to form alliances. We introduce a toy model of economic competition, and show how reinforcement learning may be augmented with a peer-to-peer contract mechanism to discover and enforce alliances. Finally, we generalize our agent model to incorporate temporally-extended contracts, presenting opportunities for further work.

Related papers

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Leading the Pack: N-player Opponent Shaping [52.682734939786464]
  We extend Opponent Shaping (OS) methods to environments involving multiple co-players and multiple shaping agents. We find that when playing with a large number of co-players, OS methods' relative performance reduces, suggesting that in the limit OS methods may not perform well.
  arXiv  Detail & Related papers  (2023-12-19T20:01:42Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning [95.78031053296513]
  No-press Diplomacy is a complex strategy game involving both cooperation and competition. We introduce a planning algorithm we call DiL-piKL that regularizes a reward-maximizing policy toward a human imitation-learned policy. We show that DiL-piKL can be extended into a self-play reinforcement learning algorithm we call RL-DiL-piKL.
  arXiv  Detail & Related papers  (2022-10-11T14:47:35Z)
• Formal Contracts Mitigate Social Dilemmas in Multi-Agent RL [4.969697978555126]
  Multi-agent Reinforcement Learning (MARL) is a powerful tool for training autonomous agents acting independently in a common environment. MARL can lead to sub-optimal behavior when individual incentives and group incentives diverge. We propose an augmentation to a Markov game where agents voluntarily agree to binding transfers of reward, under pre-specified conditions.
  arXiv  Detail & Related papers  (2022-08-22T17:42:03Z)
• Cooperative Artificial Intelligence [0.0]
  We argue that there is a need for research on the intersection between game theory and artificial intelligence. We discuss the problem of how an external agent can promote cooperation between artificial learners. We show that the resulting cooperative outcome is stable in certain games even if the planning agent is turned off.
  arXiv  Detail & Related papers  (2022-02-20T16:50:37Z)
• Reinforcement Learning In Two Player Zero Sum Simultaneous Action Games [0.0]
  Two player zero sum simultaneous action games are common in video games, financial markets, war, business competition, and many other settings. We introduce the fundamental concepts of reinforcement learning in two player zero sum simultaneous action games and discuss the unique challenges this type of game poses. We introduce two novel agents that attempt to handle these challenges by using joint action Deep Q-Networks.
  arXiv  Detail & Related papers  (2021-10-10T16:03:44Z)
• Explore and Control with Adversarial Surprise [78.41972292110967]
  Reinforcement learning (RL) provides a framework for learning goal-directed policies given user-specified rewards. We propose a new unsupervised RL technique based on an adversarial game which pits two policies against each other to compete over the amount of surprise an RL agent experiences. We show that our method leads to the emergence of complex skills by exhibiting clear phase transitions.
  arXiv  Detail & Related papers  (2021-07-12T17:58:40Z)
• Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games [27.510231246176033]
  This paper introduces and analyze a class of competitive settings where both the agents and the games they play evolve strategically over time. Populations of agents compete against each other in a zero-sum competition that itself evolves adversarially to the current population mixture. Remarkably, despite the chaotic coevolution of agents and games, we prove that the system exhibits a number of regularities.
  arXiv  Detail & Related papers  (2020-12-15T15:54:46Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
  arXiv  Detail & Related papers  (2020-07-10T09:33:05Z)
• Learning to Play No-Press Diplomacy with Best Response Policy Iteration [31.367850729299665]
  We apply deep reinforcement learning methods to Diplomacy, a 7-player board game. We show that our agents convincingly outperform the previous state-of-the-art, and game theoretic equilibrium analysis shows that the new process yields consistent improvements.
  arXiv  Detail & Related papers  (2020-06-08T14:33:31Z)

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.