📈 economics

Characterisation of reactive Nash equilibria in repeated additive games

This paper characterizes all symmetric reactive Nash equilibria in repeated additive games by establishing a one-to-one correspondence between equilibrium classes and subsets of actions, and further evaluates their evolutionary relevance through social learning simulations.

Original authors: Franziska Lesigang, Christian Hilbe, Nikoleta E. Glynatsi

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Franziska Lesigang, Christian Hilbe, Nikoleta E. Glynatsi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where two people play a game over and over again, like a never-ending round of "Rock, Paper, Scissors." In this world, the rules are simple: your move today depends only on what your opponent did last time. This is what the paper calls a reactive strategy.

The authors of this paper wanted to solve a massive puzzle: If everyone in a crowd is playing this "reactive" way, what are the stable patterns of behavior that will emerge? In game theory, a stable pattern is called a Nash equilibrium—a situation where no one has a reason to change their strategy because they are already doing the best they can given what everyone else is doing.

Here is the breakdown of their discovery, using everyday analogies:

1. The Game: A Simple "Additive" Scoreboard

The paper focuses on a specific type of game called an additive game. Think of this like a game where your final score is just the sum of two separate things:

What you did (e.g., "I chose to be nice").
What your opponent did (e.g., "They chose to be mean").

It doesn't matter how those choices happened together in a complex dance; the score is just a simple addition of your action's value and their action's value. This covers famous scenarios like the "Donation Game" (where you can give money to someone at a cost to yourself) or games where you can punish someone.

2. The Big Discovery: The "S-Group" Rule

The authors found that all the possible stable outcomes (equilibria) can be sorted into neat categories based on a simple rule they call S-supporting.

Imagine the list of all possible moves in the game is a menu of dishes (e.g., Soup, Salad, Steak).

An S-supporting equilibrium is a strategy where, when you play against a copy of yourself, you only order from a specific subset of that menu (the set S).
For example, if S is just {Soup}, the strategy is: "If you order Soup, I order Soup. If you order anything else, I ignore it."
If S is {Soup, Salad}, the strategy is: "We only ever order Soup or Salad. We never touch the Steak."

The paper proves a one-to-one match: Every possible non-empty group of dishes (S) corresponds to a specific family of stable strategies.

3. The Magic of "Equalizers"

There is a special case in this theory. If your set S includes every single dish on the menu, you get what the paper calls an Equalizer Strategy.

The Analogy: Imagine a restaurant where the chef is so skilled that no matter what you order, you get exactly the same satisfaction level.
In the game, this means if you play this strategy, your opponent gets the exact same score whether they play "Cooperation," "Defection," or anything in between. They can't gain an advantage by changing their move. This is a famous concept in game theory, and the paper shows it's just the "all-inclusive" version of their new S-supporting rule.

4. Why Some Groups Win and Others Lose (The Evolutionary Test)

The authors didn't just do the math; they ran computer simulations to see which of these "S-groups" actually survive in a population where people learn from each other. They treated the game like a biological ecosystem.

They found that the "popularity" of a strategy depends on two factors:

How easy it is to invent: Some strategies are like a simple recipe with few ingredients (few "degrees of freedom"). They are hard to stumble upon by accident. Others are complex recipes with many variables, making them easier to "mutate" into.
How tough they are against invaders: Once a strategy is established, can a new "mutant" strategy sneak in and take over?

The Surprising Result:

Small Groups Win: Strategies that rely on a very small set of actions (like only playing "Cooperation" or only playing "Defection") are the most robust. They are hard to invade and, surprisingly, they are also the most common in the simulations.
The "Equalizer" Trap: The strategies that use all actions (the Equalizers) are mathematically large and complex (they have many variables), so you might think they would be common. However, the simulations showed they are very fragile. It's easy for a mutant to break them, so they rarely survive in the long run.

Summary

The paper provides a "map" for all the stable ways people can behave in repeated, simple games.

The Map: Every stable behavior belongs to a "club" defined by the specific moves it uses when playing against itself.
The Rule: If you are in a club, you treat everyone in the club the same, and you ignore everyone outside the club.
The Winner: In the real world of learning and evolution, the "clubs" that stick to a small, simple set of moves are the ones that tend to survive and thrive, while the "all-inclusive" clubs are too fragile to last.

The authors achieved this by finding a clever mathematical shortcut that let them calculate the game's outcome without getting bogged down in complex, endless calculations, turning a messy problem into a clean system of simple equations.

Technical Summary: Characterisation of Reactive Nash Equilibria in Repeated Additive Games

Problem Statement
The paper addresses the challenge of characterizing symmetric Nash equilibria in repeated games where players employ "reactive strategies." A reactive strategy (specifically memory-1) conditions a player's current action solely on the opponent's previous action, representing one of the simplest forms of response to past interactions. While verifying if a strategy is a Nash equilibrium is generally non-trivial due to the uncountably infinite set of potential deviations, previous work has shown that for memory- $n$ strategies, it suffices to check deviations against pure strategies. However, characterizing the entire set of such equilibria remains difficult, particularly because calculating a strategy's "self-payoff" (the payoff when playing against itself) typically requires solving complex stationary distributions, a task that scales poorly with the number of actions. Furthermore, most existing characterizations are restricted to two-action games (like the Prisoner's Dilemma) or specific strategy subclasses. This paper seeks to provide a complete characterization of reactive Nash equilibria for additive games with an arbitrary finite number of actions.

Methodology
The authors focus on additive games, defined as stage games where payoffs can be decomposed into two summands, each depending only on one player's action (e.g., the donation game). The core methodological innovation is a representation of the self-payoff of a reactive strategy that avoids explicit calculation of the stationary distribution's full matrix.

Reduction to Unconditional Strategies: The authors leverage the property that in additive games, payoffs depend only on the frequency of actions chosen, not the specific sequence of action profiles. They prove (via Lemma 3.2) that against a reactive strategy, any opponent strategy (even memory- $n$ ) yields the same long-term payoff as a specific unconditional strategy (one that plays actions with fixed probabilities independent of history).
Convex Combination of Pure Payoffs: Building on the above, they demonstrate (Lemma 3.3 and Corollary 3.4) that the self-payoff of a reactive strategy $p$ can be expressed as a convex combination of the payoffs obtained when $p$ plays against pure unconditional strategies (strategies that always play a single action $a$ ). The coefficients of this combination are determined by the stationary distribution of $p$ against itself.
Linear Characterization: By expressing the self-payoff in terms of pure unconditional strategies, the conditions for a Nash equilibrium are reduced to a system of linear equalities and inequalities involving the strategy parameters. This eliminates the need for complex non-linear optimization or explicit stationary distribution computation to verify equilibrium conditions.

Key Contributions and Results

Theorem 3.1 (Characterization): The paper establishes that a reactive strategy $p$ is a Nash equilibrium if and only if there exists a non-empty subset $S$ of the action set such that:
1. $p$ only plays actions in $S$ when facing an opponent playing actions in $S$ .
2. The stationary distribution of $p$ against itself is supported entirely on $S$ .
3. All pure unconditional strategies playing actions within $S$ yield the same payoff against $p$ .
4. Any pure unconditional strategy playing an action outside $S$ yields a payoff less than or equal to those in $S$ .
  The authors define these as $S$ -supporting equilibria.
One-to-One Correspondence: There is a one-to-one correspondence between non-empty subsets of the action set and disjoint classes of Nash equilibria. The paper defines each equilibrium as belonging to the class of the minimal supporting set $S$ .
- Special Case: When $S$ is the entire action set, the resulting class corresponds to the well-known equalizer strategies, where every opponent receives the same payoff regardless of their strategy.
Dimensionality Analysis (Proposition 3.8): The authors analyze the "size" of these equilibrium classes by calculating the number of free parameters (degrees of freedom). They find that the dimension is symmetric around $(m+1)/2$ (where $m$ is the number of actions). Classes supported on very small sets (e.g., single actions, akin to partner strategies) and very large sets (equalizers) occupy the largest volumes of the strategy space, while intermediate support sets are more constrained.
Evolutionary Dynamics (Simulation): Using a pairwise comparison process (imitation dynamics with rare mutations) on a three-action donation game (Cooperation, Moderation, Defection), the authors assess which equilibrium classes are evolutionarily relevant.
- Findings: The prevalence of an equilibrium class is determined by two factors: generability (how likely it is to be sampled via mutation, related to dimensionality) and robustness (resistance to invasion).
- Observation: While equalizers (full support) and single-action equilibria have high dimensionality, equalizers are frequently invaded. Single-action equilibria (and small support sets) are both robust and, in certain payoff regimes, highly abundant. Conversely, intermediate support classes are often rare due to lower dimensionality.

Significance and Claims
The paper claims to provide the first explicit, tractable characterization of all symmetric Nash equilibria for reactive strategies in repeated additive games with arbitrary finite actions.

Theoretical Advancement: It moves beyond the restriction to two-action games or specific strategy subclasses (like partner strategies) by showing that the equilibrium set has a simple structure defined by linear conditions.
Computational Tractability: By avoiding explicit self-payoff calculations, the authors provide a direct method to compute all reactive Nash equilibria.
Unification: The framework naturally recovers existing concepts, such as equalizer strategies and partner strategies, as special cases of $S$ -supporting equilibria.
Evolutionary Insight: The study suggests that the evolutionary success of an equilibrium class is not solely a function of its stability or its size in strategy space, but a combination of both. Classes that are easy to generate (high dimension) but fragile (high invasibility) may not dominate, whereas robust classes with moderate dimensionality can be highly prevalent.

The authors conclude that their results offer a foundational framework for understanding strategic interactions in social and biological models involving additive payoffs, such as donation games with punishment or reward options, without requiring the complexity of general repeated game analysis.