A new theoretical preprint offers a way to identify when improvement dynamics in a finite game can reach an equilibrium, even if some allowed moves form cycles. It gives three equivalent ways to recognize weak acyclicity: through the game’s directed moves, through a mathematical object called a weak potential, or through the existence of a route from every starting profile to an equilibrium.
The work concerns finite games with finite player and strategy sets, and it treats strategies as pure choices rather than mixtures. The analysis uses game graphs, formal proofs and constructed examples to examine when sequences of unilateral changes can settle at equilibrium.
A weaker form of convergence
The distinction between acyclicity and weak acyclicity is the key to the paper. In an acyclic system, the relevant directed moves contain no cycle. Weak acyclicity asks for less: from each starting profile, there must be some equilibrium-reaching path, even if other choices can keep moving around a loop. The paper places these properties in a one-way hierarchy: I-acyclicity implies BI-acyclicity, which implies weak BI-acyclicity, which in turn implies weak I-acyclicity.
The moves are represented as edges in a directed improvement graph. Each edge records a profitable unilateral deviation, meaning that one player changes strategy and improves their outcome. A best-improvement graph applies the corresponding best-improvement rule. This graph language lets the paper ask not only whether cycles exist, but also whether at least one path leads to equilibrium from every starting point.
Potentials turn the graph into a test
For the stronger, acyclic case, the paper shows an equivalence among three ideas. A game and its priority rules are acyclic exactly when a potential exists and exactly when every walk can be extended only finitely before reaching equilibrium. A potential is a formal score used to describe the direction of permitted improvement, so the result supplies both a structural description and a way to recognize the property.
The weaker result has the same three-part shape, but it concerns paths rather than every possible walk. Weak acyclicity is equivalent to the existence of a weak potential and to having an equilibrium-reaching path from every starting profile. That difference matters: weak acyclicity permits unproductive routes, provided the graph also contains a route to equilibrium from each starting point.
What game structure is enough
The analysis then tests structural conditions that may guarantee weak convergence under best-improvement moves. It finds that solvability by repeatedly removing strategies that are never a player’s best reply implies weak BI-acyclicity. It also finds that a unique equilibrium in every subgame is sufficient for weak BI-acyclicity, while the weaker condition of merely having an equilibrium in every subgame does not even ensure weak I-acyclicity.
A cube-like illustrative game shows why these conditions should not be blurred together. The example is weakly acyclic but not acyclic, is not solvable by iterated elimination of never-best-reply strategies, and nevertheless has a unique equilibrium in every subgame. In other words, the absence of a universal cycle-free route is not required for the weaker, equilibrium-reaching property.
Perfect information does not remove every cycle
The paper applies the framework to finite perfect-information extensive-form games. It finds that the parsimonious-change I-priority and BI-priority rules are acyclic. Yet a separate illustrated game shows that a finite perfect-information extensive-form game need not be BI-acyclic: its best-improvement graph contains a closed walk.
The broader conclusion is more measured. Every finite perfect-information extensive-form game is weakly BI-acyclic, so an equilibrium-reaching best-improvement path exists from every starting profile, even though the full best-improvement graph may contain a loop. The single-decision-node subclass is stronger still: when each player has only one decision node, the game is I-acyclic.
Why the representation result matters
The results also impose a restriction on how these games can be represented. Acyclicity or weak acyclicity is necessary for a finite game to be the agent normal form or normal form of a perfect-information extensive-form game. In the normal-form case, even a subgame may fail to be weakly acyclic, underscoring that equilibrium existence alone does not settle the behavior of improvement dynamics.
These conclusions are confined to finite games with finite player and strategy sets and pure strategies. The supplied analysis does not address whether the characterizations extend to infinite games or to settings that allow mixed strategies.
The primary text does not name a journal, while the supplied metadata classifies the item as an arXiv preprint. No funding statement is reported in the supplied material.
Paper data and sources
Original title: Potentials and Weak Potentials in Acyclic and Weakly Acyclic Games
Authors: Igal Milchtaich
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text