Metraipolis › archive › dc_0a537337eb3e

A Numerical Approach to the Realizability Problems for Memoryless Nash and Epsilon Equilibria in Concurrent Multiplayer Reachability Games — arXiv:2609.04396

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.04396
License (as archived): CC0-1.0
Archived: 2026-10-16T22:45:35.543Z
SHA-256 of the archived text: 2c35879f9e737b4353b2197a3e99f82bcb4376c002dc16eeae18773ec8b5b637
Stable URL of this page: https://metraipolis.com/documento/dc_0a537337eb3e

How to cite

A Numerical Approach to the Realizability Problems for Memoryless Nash and Epsilon Equilibria in Concurrent Multiplayer Reachability Games — arXiv:2609.04396 — arXiv (en), https://arxiv.org/abs/2609.04396 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0a537337eb3e (Metraipolis archive dc_0a537337eb3e, sha256 2c35879f9e737b4353b2197a3e99f82bcb4376c002dc16eeae18773ec8b5b637)

BibTeX

@misc{dc0a537337eb3e,
  title = {A Numerical Approach to the Realizability Problems for Memoryless Nash and Epsilon Equilibria in Concurrent Multiplayer Reachability Games — arXiv:2609.04396},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04396},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0a537337eb3e; sha256 2c35879f9e737b4353b2197a3e99f82bcb4376c002dc16eeae18773ec8b5b637},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04396. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The existence of equilibria, which is called the realizability problem in the formal methods community, for probabilistic undiscounted state-based systems has proven to be an incredibly challenging research setting. In this paper, we consider a restricted version of the classic realizability problem by focusing on equilibria that are both memoryless and numerically constrained. While the restriction to memoryless strategies is relatively common in the literature, numerical constraints, to the best of our knowledge, represent a new and powerful approach. First, we consider the existence of memoryless equilibria when all numbers involved must be rational numbers of a pre-defined limited size. Then, we extend this analysis to field extensions of the rational numbers created through radical algebraic generators. When the basis is provided for the latter, both realizability problems are NP-complete for both exact and epsilon Nash equilibria. Finally, we consider an unconstrained numerical setting. While the characterization of the exact Nash equilibria realizability problem as ETR-complete is one of the most celebrated results in the literature, we demonstrate that the constructions underlying this result are flawed as presented. We then mend said constructions to preserve the ETR upper bound, and note that the lower bound in the literature does not apply to the epsilon-equilibrium setting. Overall, this paper demonstrates an interesting relationship between the complexity of the realizability problem and the "complexity" of the numbers involved in the representations of strategies.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-07 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.04396 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T22:29:53.693Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).