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

Edward Hughes, Thomas W. Anthony, Tom Eccles, Joel Z. Leibo, David Balduzzi, Yoram Bachrach

Abstract

While artificial intelligence has achieved superhuman performance in two-player zero-sum games like Chess and Go, many-player environments present a fundamentally different challenge: "alliance dilemmas." These are social dilemmas where agents must cooperate to succeed but face individual incentives to defect. This paper formalizes these dilemmas, demonstrates that standard reinforcement learning (RL) fails to overcome them, and introduces a peer-to-peer contract mechanism that enables agents to discover and enforce stable partnerships.

Introduction: Beyond the 1v1 Duel

In two-player zero-sum games, the Minimax theorem guarantees an optimal strategy that protects a player regardless of the opponent's actions. However, in games with more than two players, the zero-sum nature does not preclude cooperation. Two players can often improve their outcomes by forming an alliance against a third.

The core difficulty is that forming such an alliance constitutes a social dilemma. To benefit, agents must trust their partners, yet they are constantly tempted to "betray" them for higher immediate rewards. Standard Multi-Agent Reinforcement Learning (MARL) agents often fail to navigate this tension, resulting in suboptimal outcomes for all potential allies.

Methods

The researchers combined game-theoretic formalization with deep reinforcement learning to address these challenges.

Alliance Dilemma Formalization

An "alliance dilemma" is mathematically defined as a situation where a subset of players faces a social dilemma (analogous to the Prisoner's Dilemma) given the fixed policies of the remaining players.

Binding Contracts and Enforcement

The primary innovation is a peer-to-peer contract mechanism. Agents are equipped with a secondary "policy head" for a dedicated contract channel. An agent can propose a specific reciprocal deal (e.g., "If you do Action X, I will do Action Y"). If two agents submit matching offers, the environment enforces the agreement by masking actions that would violate it.

The authors also explored "temporal contracts" where violations result in a negative reward (punishment), mimicking a legal system. To encourage exploration, a "trembling hand" policy was used, occasionally forcing agents to sign random contracts during training.

Results

Prevalence and Categorization of Dilemmas

By sampling 1,000 random 3-player games, the authors found that alliance dilemmas are a fundamental property of many-player competition. Approximately 54% of these games contained alliance dilemmas, with 12% classified as "strict" dilemmas.

Prevalence of alliance dilemmas in random 3-player games (A) and across different stubborn agent strategies (B).

The Failure of Naïve Reinforcement Learning

Standard gradient-based RL agents consistently fail to reach cooperative states in these dilemmas. In the Gifting Game, agents quickly learn to never gift anything to avoid exploitation, leading to a three-way stalemate. Phase portraits of learning trajectories show that without specialized mechanisms, agents are driven away from the cooperative "alliance" equilibrium.

Phase portraits showing the learning trajectories of agents in alliance dilemmas, illustrating the failure of standard RL to reach cooperative states.

Success through Contracting

Agents equipped with the contract mechanism successfully formed stable two-way alliances in the Gifting Game. These pairs achieved a reward of 0.5 (a two-way draw), effectively excluding the third player. A significant positive correlation was observed between the number of contracts signed and an agent's total points, suggesting that contracts act as an "economic stimulus" that enables productive resource exchange.

Discussion and Future Work

While the contract mechanism proves effective in controlled environments, several challenges remain for scaling:

  • Granularity: Proposing contracts for every atomic action is impractical for complex games. Future research should focus on contracts over high-level abstractions.
  • Scalability: The contract action space grows exponentially with the number of players and actions.
  • Communication: Moving from a hard-coded contract menu to emergent communication represents a more flexible path for autonomous alliance formation.

Summary updated

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ïve 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.
BibTeX
@inproceedings{hughes2020learning,
  author = {Edward Hughes and Thomas W. Anthony and Tom Eccles and Joel Z. Leibo and David Balduzzi and Yoram Bachrach},
  title = {{Learning to Resolve Alliance Dilemmas in Many-Player Zero-Sum Games}},
  booktitle = {AAMAS},
  year = {2020},
  url = {https://openreview.net/forum?id=Gmvdk9fpGzj},
}
Figure