Memory Asymmetry and Complexity in Graph Games

55 concepts22 papers1 proposal

When designing reactive systems—such as an autonomous rover navigating an alien terrain or an embedded controller managing a smart power grid—we frequently model the scenario as a two-player game played on a graph. The system acts as the protagonist, attempting to satisfy a specific performance or safety requirement, while the environment acts as the adversary, introducing unpredictable events and obstacles.

A central question in this domain is: how much memory does a player need to win? A memoryless (or positional) strategy depends solely on the current state of the game. A finite-memory strategy tracks history using a separate finite-state machine, while an infinite-memory strategy requires tracking an unbounded history of play.

Intuitively, one might expect that if a game's objective is complex, both players would require equally complex strategies to play optimally. However, research into graph games reveals a deep structural phenomenon: strategy memory asymmetry and non-elementary memory explosions. Understanding why these memory requirements diverge or skyrocket is key to synthesizing efficient real-world controllers.

The Intuition Behind Memory Asymmetry

Why would one player need massive memory while their opponent needs none? Consider a game with combined qualitative and quantitative objectives, such as an energy parity game. Here, the protagonist must satisfy a logical sequence condition (parity) while keeping a resource counter (such as a battery level) above zero.

In Energy Parity Games, Laurent Doyen et al. demonstrated that the protagonist requires exponential memory relative to the number of states and weights to track resource levels and ensure compliance. Conversely, the adversary can always win using a completely memoryless strategy.

The root of this asymmetry lies in the nature of their goals:

  • The Protagonist's Burden: To win, the protagonist must maintain a delicate balancing act across an infinite timeline. It must track the exact resource level to avoid bankruptcy while simultaneously fulfilling the parity condition. This requires tracking historical accumulation.
  • The Adversary's Advantage: The adversary only needs to find one failure point. If there is a way to force the protagonist's energy to zero or violate the parity condition, the adversary can exploit that vulnerability purely based on the current state, without needing to remember how the game arrived there.

This structural asymmetry appears across many game variants. In Perfect-Information Stochastic Mean-Payoff Parity Games, the authors showed that the system player requires infinite memory to balance long-term averages and logical priorities in a stochastic environment, whereas the adversary can play optimally using only positional strategies. Similarly, in Finitary Winning in omega-Regular Games, Krishnendu Chatterjee et al. established that an environment player might require infinite memory to defeat a bounded response requirement by forcing progressively longer delays over time, while the system player can remain entirely memoryless.

Information Asymmetry and Non-Elementary Explosions

The memory requirements become even more extreme when players do not share the same view of the game. Suppose one player has superior information compared to a partially blind opponent. Intuitively, having more information should make winning easier. While it increases the likelihood of winning, it paradoxically causes a non-elementary explosion in the memory needed to execute that winning strategy.

As shown by the authors in Games with a Weak Adversary, when a protagonist has more information than the adversary, the memory required to execute a winning strategy can grow as a tower of exponentials ($2^{2^{\dots^2}}$), making the resulting controllers practically impossible to implement in physical hardware.

To understand why, we must look at how strategies operate under partial observation. When a player cannot see the exact state of the game, they must maintain a belief state—a probability distribution or set of possible states they could be in.

In Partial-Observation Stochastic Games: How to Win when Belief Fails, Laurent Doyen et al. proved that for reachability objectives, the memory required grows faster than any fixed stack of exponentials. To exploit an opponent's uncertainty, a well-informed protagonist cannot merely track the physical state; it must track nested beliefs. The protagonist must maintain a belief about the adversary's belief about the protagonist's state. This recursive tracking of what the opponent knows (and what they know you know) causes the state space of the strategy to balloon non-elementarily.

Multi-Dimensional Balancing and the Pareto Frontier

Another major driver of memory complexity is the transition from single-resource to multi-resource constraints. If a system only needs to minimize a single cost, it can often do so with minimal memory. But when it must balance multiple quantitative objectives simultaneously—such as minimizing fuel consumption while maximizing speed and minimizing wear-and-tear—the problem changes fundamentally.

In Generalized Mean-Payoff and Energy Games, Krishnendu Chatterjee et al. proved that restricting players to memoryless strategies shifts the decision problem's complexity to NP-complete, highlighting a severe trade-off between strategy representation and the ability to find winning conditions. When multiple dimensions are introduced, the protagonist must maintain a history of past payoffs to ensure that all dimensions stay balanced over the long run. As the authors showed in Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives, this tracking requirement scales exponentially with the number of states controlled by the adversary.

This dimensional bottleneck is vividly illustrated in "window" objectives, which approximate long-run payoffs over a local time horizon. The authors of Looking at Mean-Payoff and Total-Payoff through Windows revealed a sharp divergence: while single-dimensional window games require only linear memory relative to the window size, multi-dimensional window games demand exponential memory. The system can no longer just track a single running total; it must track an entire frontier of incomparable trade-offs (a Pareto frontier), meaning that a choice that favors one resource now must be remembered to compensate for another resource later.

The Boundaries of Finite Memory

Given these explosions, a critical line of research focuses on identifying exactly when finite memory is guaranteed to suffice. One powerful approach is "one-to-two-player lifting," which attempts to predict the complexity of an adversarial game based on a single-player version (like a puzzle or a Markov Decision Process).

In One-to-Two-Player Lifting for Mildly Growing Memory, Alexander Kozachinskiy established a sharp memory barrier: if a payoff function requires only sublinear memory relative to the arena size in a single-player game, it is guaranteed to remain winnable with finite memory when an adversary is introduced. However, once the single-player memory requirement reaches linear growth, this guarantee shatters, and the transition to a two-player game can cause the memory requirement to explode to infinity.

Furthermore, the type of information a strategy can observe matters deeply. In Infinite Separation between General and Chromatic Memory, Alexander Kozachinskiy demonstrated that a player who can see the exact sequence of graph nodes visited might need only two states of memory, whereas a player who can only see the "colors" or labels of those nodes may require infinite memory to achieve the exact same safety objective.

Ultimately, memory requirements in graph games are dictated by the flow of information and the dimensionality of the goals. When a player must balance competing resources, track nested opponent beliefs, or operate under restricted observation, memory ceases to be a minor implementation detail—it becomes an unavoidable, and sometimes non-elementary, complexity bottleneck.

Key Foundational Work

Generalized Mean-payoff and Energy Games (2010) — contributed 4 concept elements to this direction.
Energy Parity Games (2010) — contributed 2 concept elements to this direction.
Finitary Winning in omega-Regular Games (2006) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_elementary_memory_requirements_d4567138,
  title = {non-elementary memory requirements},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-elementary-memory-requirements/rdr_d4567138ab1d4018b0e5e9c70886b1bf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_elementary_memory_requirements_d4567138_v1,
  title = {non-elementary memory requirements},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-elementary-memory-requirements/rdr_d4567138ab1d4018b0e5e9c70886b1bf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake