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.
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.
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