Maker-Breaker on Galton-Watson trees
Timo Vilkas · 2024
Read Maker-Breaker on Galton-Watson trees by Timo Vilkas (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08334.txt.
Description
Timo Vilkas studies a two-player cutting and claiming game played on a random branching tree, in a 2024 probability paper. Each round, Breaker deletes an edge and everything below it, while Maker claims an edge forever. Breaker wins if the root is trapped in a finite piece; Maker wins by securing an endless path from the root. The game is studied when the tree is fully known in advance and when players must discover it as they play.
Counting the edges open for play as a random walk turns the problem into fixed point equations. Vilkas derives Breaker's winning chance under three levels of information. The results speak to network defense and to games on random structures more broadly.
Catalog record
| CREATOR | Timo Vilkas |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-08334