# Infinite games with finite knowledge gaps

arXiv: https://arxiv.org/abs/1411.5820 · HTML: https://mlsanity.com/paper/1411.5820/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2014.

## Built on by (most cited first, 2 of 2)

- [Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives](https://mlsanity.com/paper/2412.12063/) (2024)
- [Model Checking Strategic Abilities in Information-sharing Systems](https://mlsanity.com/paper/2204.08896/) (2022)

## Abstract (arXiv)

Infinite games where several players seek to coordinate under imperfect information are deemed to be undecidable, unless the information is hierarchically ordered among the players. We identify a class of games for which joint winning strategies can be constructed effectively without restricting the direction of information flow. Instead, our condition requires that the players attain common knowledge about the actual state of the game over and over again along every play. We show that it is decidable whether a given game satisfies the condition, and prove tight complexity bounds for the strategy synthesis problem under ω-regular winning conditions given by parity automata.