Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2601.17521 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908835154755584 |
|---|---|
| author | Kraizberg, Dean |
| author_facet | Kraizberg, Dean |
| contents | We study two-player games with alternating moves played on infinite trees. Our main focus is on the case where the trees are full (regular) and the winning set is open (with respect to the product topology on the tree). Gale and Stewart showed that in this setting one of the players always has a winning strategy, though it is not known in advance which player. We present simple necessary conditions for the first player to have a winning strategy, and establish an equivalence between winning sets that guarantee a win for the first player and maximal prefix codes. Using this equivalence, we derive a necessary algebraic condition for winning, and exhibit a family of games for which this algebraic condition is in fact equivalent to winning. We introduce the concept of coverings, and show that by covering the tree of the game with an infinite labeled tree corresponding to the free group, we can use "game-theoretic tools" to derive a simple trait of maximal prefix codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17521 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Winning Criteria for Open Games: A Game-Theoretic Approach to Prefix Codes Kraizberg, Dean Optimization and Control Computer Science and Game Theory Information Theory 91A44, 20E05, 94A45, 68R15 We study two-player games with alternating moves played on infinite trees. Our main focus is on the case where the trees are full (regular) and the winning set is open (with respect to the product topology on the tree). Gale and Stewart showed that in this setting one of the players always has a winning strategy, though it is not known in advance which player. We present simple necessary conditions for the first player to have a winning strategy, and establish an equivalence between winning sets that guarantee a win for the first player and maximal prefix codes. Using this equivalence, we derive a necessary algebraic condition for winning, and exhibit a family of games for which this algebraic condition is in fact equivalent to winning. We introduce the concept of coverings, and show that by covering the tree of the game with an infinite labeled tree corresponding to the free group, we can use "game-theoretic tools" to derive a simple trait of maximal prefix codes. |
| title | Winning Criteria for Open Games: A Game-Theoretic Approach to Prefix Codes |
| topic | Optimization and Control Computer Science and Game Theory Information Theory 91A44, 20E05, 94A45, 68R15 |
| url | https://arxiv.org/abs/2601.17521 |