Exploring dominant strategies in iterated and evolutionary games: a multi-agent reinforcement learning approach

Long Wang, Qi Su, H. Wang, Yu XiaResearch Square 2024 · DOI

Abstract

Exploring dominant strategies in iterated games holds profound theoretical and practical significance across diverse domains. Previous studies, through mathematical analysis of limited cases, have unveiled classic strategies such as tit-for-tat, generous-tit-for-tat, win-stay-lose-shift, and zero-determinant strategies. While these strategies offer valuable insights into human decision-making, they represent only a small subset of possible strategies, constrained by limited mathematical and computational tools available to explore larger strategy spaces. To bridge this gap, we propose a novel approach using multi-agent reinforcement learning to delve into complex decision-making processes that go beyond human intuition. Our approach has led to the discovery of a new strategy, i.e., memory-two bilateral reciprocity (MTBR) strategy. MTBR consistently outperforms a wide range of strategies in pairwise interactions while achieving high payoffs. When introduced into an evolving population with diverse strategies, MTBR demonstrates dominance and fosters higher levels of cooperation and social welfare in both homogeneous and heterogeneous structures, as well as across various game types. This high performance is verified by simulations and mathematical analysis. Our work highlights the potential of multi-agent reinforcement learning in uncovering dominant strategies in complex environments, offering a new perspective on strategy exploration in iterated games.

Introduction

In the study of iterated games, such as the Prisoner’s Dilemma, the central challenge is identifying strategies that maximize payoffs over repeated interactions. For decades, the most effective known strategies—such as Tit-for-Tat (TFT) or Win-Stay-Lose-Shift (WSLS)—have been constrained by human intuition and the need for mathematical simplicity. Most research has focused on "memory-one" strategies, where players only consider the immediate previous move. This limitation exists because increasing memory length causes the strategy space to grow exponentially, making traditional mathematical proofs nearly impossible.

This research addresses this "complexity wall" by employing multi-agent reinforcement learning (MARL) to explore the vast landscape of memory-two strategies. The goal was to discover a dominant approach that not only wins individual matches but also steers entire populations toward higher cooperation and prosperity. This effort led to the discovery of Memory-Two Bilateral Reciprocity (MTBR), a strategy that uses a two-step memory to foster cooperation and break deadlocks.

Methods and Experimental Setup

The researchers developed a Multi-agent Q-Learning framework specifically tailored for evolutionary games. This framework allowed agents to learn optimal behaviors through iterative interaction and reward optimization.

The Multi-agent Reinforcement Learning (MARL) framework used to discover the MTBR strategy.

The MARL Framework

The setup involved 49 "learning agents" trained by interacting with 49 "mentors" programmed with classic heuristic and mathematical strategies. The core of the learning process was a novel reward function designed to balance two objectives:

  1. Relative Advantage: Outperforming the opponent's average score.
  2. Absolute Payoff: Maximizing the agent's own total reward.

Strategies were represented as Q-tables mapping the last two rounds of actions (resulting in 16 possible states) to the best subsequent move. This allowed the AI to identify complex patterns beyond simple "eye-for-an-eye" reciprocity.

Datasets and Environments

The study utilized two primary sets of mentor strategies:

  • Mentor Strategy Set 1: Seven classic heuristic strategies (e.g., TFT, GTFT, WSLS).
  • Mentor Strategy Set 2: Eight representative "Zero-Determinant" (ZD) strategies, which are mathematically sophisticated and known for their ability to unilaterally control an opponent's payoff.

To test the robustness of the discovered strategy, simulations were conducted across various social architectures, including well-mixed populations, lattice grids, and scale-free networks.

Key Insights and Results

The discovery of MTBR revealed several sophisticated behaviors that go beyond human-designed heuristics:

  • Strategic Forgiveness: MTBR learned that if it cooperates and the opponent defects in the very first round, it should cooperate again in the second. This initial "forgiveness" prevents a downward spiral of mutual defection before a cooperative relationship can be established.
  • Deadlock Resolution: If both players defect for two consecutive rounds, MTBR switches to cooperation to "reset" the game. This mechanism effectively breaks the low-payoff traps that often ensnare simpler strategies like TFT.
  • Evolutionary Dominance: In evolutionary simulations where successful strategies are imitated, MTBR consistently became the most abundant strategy, often driving others to extinction.
  • Enhanced Social Welfare: While designed for dominance, MTBR's presence benefits the entire population. In populations with exploitative ZD strategies, the introduction of MTBR raised the average global payoff from 1.93 to 2.937 (where 3.0 represents perfect mutual cooperation).
  • Cross-Game Robustness: MTBR remained dominant across different game types, including the Snowdrift and Stag-hunt games, and across various network topologies.

Conclusion and Future Directions

The use of MARL has successfully broken a decades-old bottleneck in game theory, uncovering a strategy that outperforms human-designed alternatives by leveraging a two-step history. However, challenges remain. While memory-two is a significant advancement, longer memories (memory-three or four) could lead to "overfitting," where strategies become too specialized and lose adaptability.

Future research may explore strategies that adapt specifically based on "first impressions"—the initial moves of a game—which this study found to be highly influential. Additionally, scaling this MARL approach to multiplayer environments, such as the Public Goods Game, remains a significant computational challenge for future exploration.

Summary updated

Abstract

<title>Abstract</title> Exploring dominant strategies in iterated games holds profound theoretical and practical significance across diverse domains. Previous studies, through mathematical analysis of limited cases, have unveiled classic strategies such as tit-for-tat, generous-tit-for-tat, win-stay-lose-shift, and zero-determinant strategies. While these strategies offer valuable insights into human decision-making, they represent only a small subset of possible strategies, constrained by limited mathematical and computational tools available to explore larger strategy spaces. To bridge this gap, we propose a novel approach using multi-agent reinforcement learning to delve into complex decision-making processes that go beyond human intuition. Our approach has led to the discovery of a new strategy, i.e., memory-two bilateral reciprocity (MTBR) strategy. MTBR consistently outperforms a wide range of strategies in pairwise interactions while achieving high payoffs. When introduced into an evolving population with diverse strategies, MTBR demonstrates dominance and fosters higher levels of cooperation and social welfare in both homogeneous and heterogeneous structures, as well as across various game types. This high performance is verified by simulations and mathematical analysis. Our work highlights the potential of multi-agent reinforcement learning in uncovering dominant strategies in complex environments, offering a new perspective on strategy exploration in iterated games.
BibTeX
@inproceedings{wang2024exploring,
  author = {Long Wang and Qi Su and H. Wang and Yu Xia},
  title = {{Exploring dominant strategies in iterated and evolutionary games: a multi-agent reinforcement learning approach}},
  booktitle = {Research Square},
  year = {2024},
  doi = {10.21203/rs.3.rs-5462150/v1},
}

Loading related content...

Figure