Maker-Breaker on Galton-Watson trees
Vilkas, Timo LU
(2024)
p.1-34
- Abstract
- We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an edge to permanently secure it from deletion. Breaker has won once the tree's root is contained in a finite component, otherwise Maker wins by building an infinite path starting at the root. It will be analyzed both as a positional game (the tree is known to both players at the start) and with more restrictive levels of information (the players essentially explore the tree during the game). Reading the number of available edges for play as a random walk on Z allows us to derive the winning... (More)
- We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an edge to permanently secure it from deletion. Breaker has won once the tree's root is contained in a finite component, otherwise Maker wins by building an infinite path starting at the root. It will be analyzed both as a positional game (the tree is known to both players at the start) and with more restrictive levels of information (the players essentially explore the tree during the game). Reading the number of available edges for play as a random walk on Z allows us to derive the winning probability of Breaker via fixed point equations in three natural information regimes. These results provide new insights into combinatorial game theory and random structures, with potential applications to network theory, algorithmic game design and probability theory. (Less)
- Abstract (Swedish)
- We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an edge to permanently secure it from deletion. Breaker has won once the tree's root is contained in a finite component, otherwise Maker wins by building an infinite path starting at the root. It will be analyzed both as a positional game (the tree is known to both players at the start) and with more restrictive levels of information (the players essentially explore the tree during the game). Reading the number of available edges for play as a random walk on Z allows us to derive the winning... (More)
- We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an edge to permanently secure it from deletion. Breaker has won once the tree's root is contained in a finite component, otherwise Maker wins by building an infinite path starting at the root. It will be analyzed both as a positional game (the tree is known to both players at the start) and with more restrictive levels of information (the players essentially explore the tree during the game). Reading the number of available edges for play as a random walk on Z allows us to derive the winning probability of Breaker via fixed point equations in three natural information regimes. These results provide new insights into combinatorial game theory and random structures, with potential applications to network theory, algorithmic game design and probability theory. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/bf2a0166-b418-442e-b8be-abdeeb18b68b
- author
- Vilkas, Timo
LU
- organization
- publishing date
- 2024-12-11
- type
- Working paper/Preprint
- publication status
- published
- subject
- keywords
- Maker-Breaker game, Galton-Watson tree, branching process, percolation games, phase transition, random walk on Z with drift
- pages
- 34 pages
- publisher
- arXiv.org
- DOI
- 10.48550/arXiv.2412.08334
- language
- English
- LU publication?
- yes
- id
- bf2a0166-b418-442e-b8be-abdeeb18b68b
- date added to LUP
- 2025-03-10 10:15:13
- date last changed
- 2025-04-04 15:41:18
@misc{bf2a0166-b418-442e-b8be-abdeeb18b68b,
abstract = {{We consider the following combinatorial two-player game: On the random tree arising from a branching process, each round one player (Breaker) deletes an edge and by that removes the descendant and all its progeny, while the other (Maker) fixates an edge to permanently secure it from deletion. Breaker has won once the tree's root is contained in a finite component, otherwise Maker wins by building an infinite path starting at the root. It will be analyzed both as a positional game (the tree is known to both players at the start) and with more restrictive levels of information (the players essentially explore the tree during the game). Reading the number of available edges for play as a random walk on Z allows us to derive the winning probability of Breaker via fixed point equations in three natural information regimes. These results provide new insights into combinatorial game theory and random structures, with potential applications to network theory, algorithmic game design and probability theory.}},
author = {{Vilkas, Timo}},
keywords = {{Maker-Breaker game; Galton-Watson tree; branching process; percolation games; phase transition; random walk on Z with drift}},
language = {{eng}},
month = {{12}},
note = {{Preprint}},
pages = {{1--34}},
publisher = {{arXiv.org}},
title = {{Maker-Breaker on Galton-Watson trees}},
url = {{http://dx.doi.org/10.48550/arXiv.2412.08334}},
doi = {{10.48550/arXiv.2412.08334}},
year = {{2024}},
}