🧬 biology

Evolution of memory strategies in alternating stochastic games

This study reveals that in alternating stochastic games, environmental feedback significantly promotes cooperation through a firm-but-fair strategy and stable multi-strategy alliances, challenging the dominance of the win-stay, lose-shift approach observed in synchronous interactions.

Original authors: Zhihai Rong, Jing Zhang, Zhi-Xi Wu, Bin Xu, Xiaofan Wang

Published 2026-09-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhihai Rong, Jing Zhang, Zhi-Xi Wu, Bin Xu, Xiaofan Wang

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

Cooperation is a puzzle that has long fascinated scientists who study how living things interact. In the natural world and in human societies, individuals often face a choice: act in their own immediate self-interest, or work together for a shared benefit that is greater than what they could achieve alone. Evolutionary biology tells us that selfishness usually wins out because it offers a quick, easy reward. To keep cooperation alive, nature often relies on a mechanism called direct reciprocity. This is the simple idea that if I help you today, you will help me tomorrow. For decades, researchers have studied this by imagining two people playing a game over and over again, where their choices in one round affect the next. Traditionally, these studies assumed that both players make their decisions at the exact same time, like two people flipping coins simultaneously. However, in the real world, interactions are rarely so perfectly synchronized. Often, one person acts first, and the other responds after seeing that action, creating a sequence where information is shared unevenly.

A team of researchers has now taken a closer look at what happens when these sequential interactions occur in a world where the environment itself changes based on what people do. They built a model where players take turns making choices, and those choices not only determine their immediate rewards but also shift the quality of the world they are playing in. Imagine a garden that flourishes when people work together but turns barren when they fight. The researchers wanted to know: in a game where the rules change based on the players' history, and where one player always moves before the other, what kind of behavior allows cooperation to survive? They focused on simple strategies that players might use, looking at how these strategies compete and evolve over time in a large group.

The study reveals that the old rules of cooperation do not apply when the environment is dynamic and the players take turns. In many previous studies of games played at the same time, a strategy known as "win-stay, lose-shift" was considered the champion of cooperation. This approach is straightforward: if you did well in the last round, do the same thing again; if you did poorly, change your behavior. The researchers found that in their new model of alternating turns, this famous strategy actually fails. When a mistake happens—perhaps a player accidentally defects when they meant to cooperate—the "win-stay, lose-shift" player gets trapped in a cycle of alternating cooperation and betrayal. Because the players take turns, the error sends them spiraling into a bad state where the environment is harsh, and they cannot easily find their way back to a good state. The strategy simply cannot correct the mistake fast enough to save the relationship.

Instead, the researchers discovered that a different approach, which they call "firm-but-fair," is the key to keeping cooperation alive in this setting. This strategy is slightly more forgiving and more rigid in its expectations. When a player using this approach makes a mistake, the system allows them to quickly return to a state of mutual cooperation. The "firm-but-fair" player is willing to cooperate again as soon as the other player shows they are ready, effectively resetting the game before the environment can degrade. The study shows that when the environment is set up so that mutual cooperation keeps the world in a "good" state with high rewards, and any act of betrayal pushes the world into a "bad" state with low rewards, this "firm-but-fair" strategy becomes the dominant force. It is strong enough to resist invasion by selfish players who always try to defect, yet flexible enough to recover from errors.

The researchers also found that the size of the difference between the good and bad environments matters greatly. If the gap in rewards is small, selfish behavior tends to take over. But as the difference grows larger—meaning the penalty for a bad environment becomes severe and the reward for a good one becomes rich—a stable alliance of cooperative strategies emerges. In these conditions, the population can settle into a state where different types of cooperative players coexist. They do not need to be identical; some might be slightly more generous than others, but they all share the common goal of maintaining the good state. This alliance is robust, meaning it can withstand the constant introduction of new, random strategies, including those that try to defect. The study suggests that the combination of taking turns and having an environment that reacts to behavior creates a unique pressure that favors these specific, resilient forms of cooperation.

To reach these conclusions, the team used a mix of mathematical theory and computer simulations. They modeled a large population of individuals playing repeated games where the environment could switch between a beneficial state and a harmful one. They tested sixteen different simple strategies to see which ones would survive and spread. They ran these simulations under two different conditions: one where mutations (random changes in strategy) were extremely rare, and another where they happened more frequently. In both cases, the results were consistent. The "firm-but-fair" strategy consistently outperformed the traditional "win-stay, lose-shift" approach. The simulations showed that when the environmental feedback was strong enough, the population could maintain a high level of cooperation for long periods, even when errors occurred.

The findings challenge the long-held belief that the "win-stay, lose-shift" strategy is the universal solution for cooperation. While it works well when players act simultaneously, the researchers showed that the timing of actions changes everything. In a world where one person moves first and the other follows, the ability to quickly correct a mistake becomes more important than the ability to punish a defector. The study highlights that the structure of the interaction—whether it is simultaneous or sequential—and the nature of the environment are just as important as the strategies themselves. By understanding how these factors work together, scientists can better explain why cooperation persists in complex systems, from the sharing of food among animals to the formation of social contracts among humans. The research suggests that cooperation is not just about being nice; it is about having the right strategy for the specific rhythm and rules of the world you live in.

Technical Summary: Evolution of Memory Strategies in Alternating Stochastic Games

Problem Statement

Cooperation in social and biological systems is often modeled using repeated games, where direct reciprocity allows individuals to sustain mutual cooperation through memory of past interactions. However, existing literature predominantly focuses on simultaneous games, where players act with identical historical information. In contrast, many real-world interactions (e.g., food sharing in vampire bats, grooming in primates) are sequential or alternating, creating information asymmetry where the second mover observes the first mover's action before deciding.

While previous studies have shown that alternating interactions generally suppress cooperation compared to simultaneous ones, and that classical strategies like Win-Stay, Lose-Shift (WSLS) fail to correct errors in alternating settings, a critical gap remains: how does dynamic environmental feedback interact with sequential decision-making? In reality, individual actions often alter the environmental state, which subsequently reshapes payoffs and future decisions. This paper investigates the evolution of classical pure memory-one strategies within an alternating stochastic game framework, where players take turns making decisions that influence both immediate payoffs and the transition probabilities between environmental states (e.g., "good" vs. "bad" states).

Methodology

Model Framework

The authors model an infinitely repeated donation game (a variant of the Prisoner's Dilemma) played by two players, $X$ and $Y$ , in an alternating sequence.

Strategies: Players employ pure memory-one strategies, defined by a vector $p = (p_{CC}, p_{CD}, p_{DC}, p_{DD})$ , representing the probability of cooperating given the previous action pair. The study focuses on the set of 16 deterministic strategies ( $K=16$ ), including AllD, Grim, WSLS, Tit-for-Tat (TFT), and Firm-but-Fair (FBF).
Environmental States: The game occurs in two distinct states: a Good state (G) with benefit $b_1$ and a Bad state (B) with benefit $b_2$ ( $b_1 > b_2$ ). The difference $\Delta b = b_1 - b_2$ is a key parameter.
State Transitions: Transitions are governed by a rule $z = (z_{CC}, z_{CD}, z_{DC}, z_{DD})$ , where $z_{a\tilde{a}}$ is the probability of transitioning to state G given the current action pair. The primary focus is on the rule $z = (1, 0, 0, 0)$ , where mutual cooperation sustains the good state, and any defection switches the environment to the bad state.
Errors: The model incorporates "trembling hand" or "fuzzy mind" errors with probability $\epsilon \to 0$ , ensuring the transition matrix is regular.

Analytical and Numerical Approaches

Markov Chain Analysis: The interaction between strategies and environmental states is modeled as a Markov chain. The authors derive the stationary distribution to calculate the expected cooperation rate and payoffs for any pair of strategies.
Equilibrium Analysis: The study analyzes Weak Nash Equilibria and dominance relationships among strategies. A strategy $p_i$ is a weak Nash equilibrium if $\pi(p_i, p_i) \geq \pi(p_j, p_i)$ for all $p_j$ .
Evolutionary Dynamics:
- Rare Mutations ( $\mu \to 0$ ): The population is assumed to be nearly homogeneous. The authors use pairwise comparison dynamics and fixation probabilities (Fermi rule) to determine which strategies can invade or resist invasion.
- Positive Mutations ( $\mu > 0$ ): Agent-based simulations are conducted with a mutation rate $\mu = 0.01$ to observe the long-term abundance of strategies in a mixed population.

Key Contributions and Results

1. The Failure of WSLS and the Rise of FBF

In simultaneous games, WSLS is a dominant strategy for maintaining cooperation. However, the authors demonstrate that in alternating interactions, WSLS suffers a "double punishment":

Error Sensitivity: An occasional error triggers a cycle of alternating cooperation and defection, trapping players in the bad environment.
Payoff Reduction: The expected payoff for two WSLS players drops significantly compared to the good state.
FBF Superiority: In contrast, the Firm-but-Fair (FBF) strategy ( $p_{FBF} = (1, 0, 1, 1)$ ) can efficiently correct errors. When an error occurs, FBF players rapidly restore mutual cooperation, maintaining the good environment. Theoretical analysis shows FBF dominates WSLS under the transition rule $z=(1,0,0,0)$ , provided $b_2 > c$ .

2. Environmental Feedback Expands the Equilibrium Space

The introduction of environmental feedback fundamentally alters the stability of cooperative strategies compared to static alternating games:

FBF as a Foundation: Under the rule $z=(1,0,0,0)$ , FBF becomes a weak Nash equilibrium if $(2z_{CC} - z_{DD})\Delta b + b_2 - 2c \geq 0$ . This condition is easier to satisfy than in single-state games, allowing FBF to resist invasion by AllD even when the environmental difference $\Delta b$ is moderate.
Emergence of Generous Strategies: As $\Delta b$ increases, more generous strategies like Always-Cooperate-Unless-Defect (ACUD) and AllC also become Nash equilibria. The condition for their stability is $(2z_{CC} - z_{CD} - z_{DC})\Delta b - 2c \geq 0$ .
Multi-Strategy Alliance: In the high $\Delta b$ regime, the population forms a stable, multi-strategy cooperative alliance. FBF acts as an "evolutionary bridge," resisting defectors while allowing neutral drift toward ACUD and AllC, which collectively sustain high cooperation rates.

3. Robustness Across Mutation Rates

Rare Mutations: The evolutionary trajectory depends on $\Delta b$ . Low $\Delta b$ leads to AllD dominance; intermediate $\Delta b$ stabilizes FBF; high $\Delta b$ enables a coalition of FBF, ACUD, and AllC.
Positive Mutations: Numerical simulations confirm that these findings are robust even with a positive mutation rate ( $\mu = 0.01$ ). An appropriate level of mutation facilitates high cooperation by introducing diverse cooperative strategies that form a resilient alliance.

4. Role of Information Asymmetry

The paper highlights that the structural sequence of decision-making (alternating vs. simultaneous) reshapes payoff landscapes. While simultaneous games favor WSLS, the information asymmetry in alternating games, combined with environmental feedback, shifts the evolutionary advantage to FBF and other conditional strategies that can correct errors and manage state transitions.

Significance and Claims

The paper claims to provide novel insights into how environmental feedback and sequential interactions jointly shape the evolution of cooperation. Specifically:

It challenges the prevailing view that alternating interactions inherently suppress cooperation, showing instead that dynamic environmental feedback can substantially promote cooperation in sequential settings.
It identifies FBF as the primary strategy for sustaining cooperation in alternating stochastic games, replacing the role WSLS plays in simultaneous games.
It demonstrates that environmental feedback mechanisms can create a stable, multi-strategy cooperative alliance, offering a theoretical paradigm for understanding multi-stability in complex collective behaviors.
The findings suggest that the interplay between information asymmetry and dynamic environmental states is a crucial, previously under-explored factor in the evolutionary resilience of cooperation.

The authors conclude that while the current model focuses on pure memory-one strategies in well-mixed populations, the framework opens avenues for exploring mixed memory strategies, adaptive learning, and coevolutionary dynamics in structured networks.