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

CREATORTimo Vilkas
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08334

Browse the full library · About the Tower of Babel