Arbitrary Precision for Game Equilibrium Refinements

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 220 papers35 conceptsfrozen 2026-10-04

In game theory, the Nash equilibrium is the standard tool for predicting agent behavior. However, Nash equilibria can sometimes be "unreasonable," predicting strategies that rely on threats that would never actually be carried out. To fix this, researchers use equilibrium refinements—like perfect, proper, or sequential equilibria—which assume players might make infinitesimal mistakes, often called "trembles."

While these refinements are theoretically elegant, they introduce a massive computational hurdle: they require math that is too precise for standard computers to handle.

The Failure of Floating Point

Most modern software relies on 64-bit floating-point arithmetic. This works well for physics simulations or machine learning, but it fails catastrophically when computing equilibrium refinements.

The core of the problem lies in the "trembling hand" metaphor. To ensure an equilibrium is robust, we introduce a perturbation parameter $\epsilon$ representing the probability of a mistake. We then look at what happens as $\epsilon$ approaches zero. As Gabriele Farina, Nicola Gatti, and Tuomas Sandholm explain in Practical exact algorithm for trembling-hand equilibrium refinements in games, modeling these mistakes requires handling values so small they vanish into rounding errors.

When $\epsilon$ becomes smaller than the "machine epsilon" (the smallest difference a computer can track), the logic of the equilibrium collapses. In Comparison of Algorithms for Simple Stochastic Games, Jan Kretinsky and colleagues demonstrate that even small games can require precision far beyond 64-bit limits, leading solvers to produce flatly incorrect results or fail to converge.

Symbolic and Arbitrary Precision

To bypass the limitations of hardware, researchers have turned to two primary techniques: symbolic perturbations and arbitrary-precision arithmetic.

Instead of picking a tiny number for $\epsilon$ (like $10^{-15}$), symbolic methods treat $\epsilon$ as a variable. Nicola Gatti and Claudio Iuliano pioneered this in Computing an Extensive-Form Perfect Equilibrium in Two-Player Games, using symbolic variables to represent infinitesimal probabilities. This ensures that the "logic" of the limit is preserved exactly, regardless of how small the mistake probability becomes.

However, symbolic math is computationally expensive. The alternative is arbitrary-precision arithmetic, where the computer uses as much memory as needed to represent a number exactly as a fraction of two massive integers. This is critical for "path-following" algorithms. As Nicola Gatti and Tuomas Sandholm note in Combining local search techniques and path following for bimatrix games, without this high-precision tracking, a solver can literally "lose the path" to the equilibrium due to a single rounding error, wandering into an irrelevant part of the solution space.

The Doubly Exponential Challenge

The need for precision isn't just a minor implementation detail; it is a fundamental complexity barrier. Recent work by Ioannis Anagnostides and Maria Florina Balcan in The Complexity of Equilibrium Refinements in Potential Games shows that in multi-player games, the perturbations required to reach a refined equilibrium might need to be doubly exponentially small.

This means that as the game grows, the number of digits required to represent the strategy grows at an explosive rate. This "bit-level complexity" is why exact solvers often fail on large-scale games. As Hanyu Li and David Mguni highlight in their survey on Nash equilibria, the bottleneck for practical game theory isn't just raw processing time—it's the numerical robustness of the underlying math.

From Theory to Verification

These high-precision techniques are now moving from abstract game theory into formal verification. Tools like PRISM-games 3.0, developed by Marta Kwiatkowska and David Parker, are beginning to integrate arbitrary-precision representations. This allows engineers to verify that autonomous systems—like robots or financial algorithms—will behave correctly even in the presence of the "trembles" and uncertainties of the real world.

By treating numerical stability as a first-class citizen, researchers are finally making it possible to compute strategies that are not just mathematically sound, but practically robust.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 20 papers
  2. Version 1 · 2026-10-04 · 20 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_floating_point_instability_9eabe4d8,
  title = {floating-point instability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/floating-point-instability/rdr_9eabe4d8e6f64c909be15c1ac10e4dd9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_arbitrary_precision_for_game_equilibrium_9eabe4d8_v1,
  title = {Arbitrary Precision for Game Equilibrium Refinements},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/arbitrary-precision-for-game-equilibrium-refinements/rdr_9eabe4d8e6f64c909be15c1ac10e4dd9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}