Preserving Strategic Properties Across Game Representations

18 concepts10 papers1 proposal

When modeling multi-agent systems, researchers frequently need to switch between different representations of a system. We might abstract a highly complex concurrent game into a simplified state-transition system to make verification tractable, or translate a graphical game into an extensive-form tree to compute its equilibria.

In traditional computer science, bisimulation is the gold standard for establishing that two systems are behaviorally equivalent. If System A takes a step, System B must be able to match it with an equivalent step, and vice versa. However, when autonomous agents with distinct goals are introduced, standard behavioral equivalence breaks down. A strategy is not merely a sequence of actions; it is a conditional plan dependent on history and information. Ensuring that two models share the same behavior does not guarantee they share the same strategic outcomes.

A growing body of research addresses this challenge by developing strategy-preserving mappings, specialized bisimulations, and representation-invariant transformations.

The Alignment Problem of Behavioral Equivalence

Why does standard bisimulation fail to preserve game-theoretic properties? The issue lies in how strategies are represented. As demonstrated by Julian Gutierrez et al. in Nash Equilibrium and Bisimulation Invariance, two game structures can be perfectly bisimilar on a step-by-step level, yet fail to preserve Nash equilibria under conventional strategy models.

This mismatch occurs because standard strategies can condition their choices on the exact history of states visited. If a bisimulation collapses two histories that the strategy treats differently, a Nash equilibrium in the original game can disintegrate in the behaviorally equivalent game. To resolve this, the authors showed that one must restrict or redefine strategies—such as using trace-based or explicitly bisimulation-invariant run-based strategies—to ensure that game-theoretic stability aligns with behavioral equivalence.

Strategy Simulators and Structural Translations

To safely transfer strategic properties between different game models, we need a mechanism that explicitly maps a strategy from one domain to another without losing its core guarantees. This is particularly difficult in games with imperfect information, where agents cannot fully distinguish between certain states of the world.

To bridge this gap, Francesco Belardinelli et al. introduced the concept of strategy simulators in A Hennessy-Milner Theorem for ATL with Imperfect Information. A strategy simulator acts as a constructive translator: it takes a valid strategy from one game structure and maps it to another while strictly maintaining the uniformity requirements imposed by imperfect information. This ensures that if an agent is forced to take the same action across indistinguishable states in the original game, their mapped strategy respects the same constraints in the target game.

With these strategy-preserving mappings, formal equivalences can be established across entirely different modeling formalisms:

  • Graphical Models and Trees: Multi-Agent Influence Diagrams (MAIDs) offer a compact way to represent structural independencies in games, but classical equilibrium concepts are defined on massive extensive-form trees. Lewis Hammond et al. developed bidirectional mappings between these formats in Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice. Their transformations guarantee that complex equilibrium refinements, such as subgame perfection and trembling-hand perfection, are preserved, allowing designers to solve compact graphical models without sacrificing classical rigor.
  • Security Trees and Extensive Games: In security modeling, attack-defense trees (ADTs) capture the interplay between an attacker and a defender. Barbara Kordy et al. proved a formal equivalence between ADTs and two-player binary zero-sum extensive form games in Attack-Defense Trees and Two-Player Binary Zero-Sum Extensive Form Games Are Equivalent. By mapping tree conjunctions and disjunctions directly to player choices, they ensured that a player's win condition in the game corresponds exactly to their success in the security tree.
  • Distributed Synthesis Formalisms: When synthesizing distributed systems with causal memory, developers alternate between control games and Petri games. Raven Beutner et al. established a strategy-equivalence notion based on weak bisimulation in Translating Asynchronous Games for Distributed Synthesis, proving that winning strategies can be directly transferred between these two distinct distributed frameworks.

Verifying Strategic Abilities via Abstraction

The primary practical motivation for preserving strategic properties is model simplification. Verifying whether a coalition of agents has the strategic ability to achieve a goal (often formulated in Alternating-time Temporal Logic, or ATL*) is computationally expensive. If we can construct a smaller, abstract model that preserves these abilities, we can verify the property on the abstraction and guarantee that it holds in the real system.

[ Concrete Model ]  --- (Strategic Bisimulation) --->  [ Abstract Model ]
        |                                                      |
  Does a winning                                         Does a winning
  strategy exist?   <--- (Guaranteed Equivalence) ---   strategy exist?
  (Hard to solve)                                        (Easy to solve)

In Bisimulations for Verifying Strategic Abilities with an Application to ThreeBallot, Francesco Belardinelli et al. proved a Preservation Theorem for multi-agent systems with imperfect information. They demonstrated that if two concurrent game structures are strategically bisimilar, they satisfy the exact same ATL* formulas. This allowed the authors to verify complex real-world protocols, like the ThreeBallot voting system, by reducing them to highly simplified, verifiable abstractions.

Similarly, Yves Lespérance et al. extended this paradigm to infinite-state systems in Abstraction of Situation Calculus Concurrent Game Structures. They showed that if an abstract model and a detailed concrete implementation are bound by a strategic equivalence relation, any goal achievable by a coalition at the high level is guaranteed to be executable in the concrete environment.

The Game-Theoretic Nature of Bisimulation Checking

An elegant symmetry in this field is that the act of checking whether two models are strategically equivalent is itself framed as a game. Instead of exhaustively exploring an entire state graph, modern verification algorithms reduce the simulation check to a two-player, turn-based game between an Attacker and a Defender.

As surveyed by Kim G. Larsen et al. in Simulation Relations and Applications in Formal Methods, this framework provides an intuitive approach to verification: the Attacker continually attempts to find a behavioral discrepancy or a step that cannot be matched, while the Defender attempts to maintain the simulation relation.

This game-theoretic reduction yields significant algorithmic advantages:

  • On-the-Fly Optimization: In Efficient on-the-fly Algorithm for Checking Alternating Timed Simulation, Peter Bulychev et al. leveraged this turn-based structure to optimize verification in timed game automata. Because the problem is reduced to finding a winning strategy in the verification game, the algorithm can terminate early the moment a winning path is found or disproven, avoiding an exhaustive exploration of the state space.
  • Complexity Analysis: Steven J. Ramsay et al. applied the Attacker-Defender paradigm to data-driven systems in Bisimilarity in fresh-register automata. By analyzing the strategic interactions required to maintain or break bisimilarity in automata that generate fresh symbols, the authors established tight complexity bounds for verifying systems with infinite data domains.

Key Foundational Work

Attack-Defense Trees and Two-Player Binary Zero-Sum Extensive Form Games Are Equivalent (2010) — contributed 5 concept elements to this direction.
Efficient on-the-fly Algorithm for Checking Alternating Timed Simulation (2009) — contributed 3 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_equilibrium_refinement_preservation_aef4f15c,
  title = {equilibrium refinement preservation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/equilibrium-refinement-preservation/rdr_aef4f15c704d4d918932cfad265f7035},
  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_equilibrium_refinement_preservation_aef4f15c_v1,
  title = {equilibrium refinement preservation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/equilibrium-refinement-preservation/rdr_aef4f15c704d4d918932cfad265f7035/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