A min-max random game on a graph that is not a tree
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912014542045184 |
|---|---|
| author | Cardona-Tobón, Natalia Sturm, Anja Swart, Jan M. |
| author_facet | Cardona-Tobón, Natalia Sturm, Anja Swart, Jan M. |
| contents | We study a random game in which two players in turn play a fixed number of moves. For each move, there are two possible choices. To each possible outcome of the game we assign a winner in an i.i.d. fashion with a fixed parameter p. In the case where all different game histories lead to different outcomes, a classical result due to Pearl (1980) says that in the limit when the number of moves is large, there is a sharp threshold in the parameter p that separates the regimes in which either player has with high probability a winning strategy. We are interested in a modification of this game where the outcome is determined by the exact sequence of moves played by the first player and by the number of times the second player has played each of the two possible moves. We show that also in this case, there is a sharp threshold in the parameter p that separates the regimes in which either player has with high probability a winning strategy. Since in the modified game, different game histories can lead to the same outcome, the graph associated with the game is no longer a tree which means independence is lost. As a result, the analysis becomes more complicated and open problems remain. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_02660 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A min-max random game on a graph that is not a tree Cardona-Tobón, Natalia Sturm, Anja Swart, Jan M. Probability Primary: 82C26, Secondary: 60K35, 91A15, 91A50 We study a random game in which two players in turn play a fixed number of moves. For each move, there are two possible choices. To each possible outcome of the game we assign a winner in an i.i.d. fashion with a fixed parameter p. In the case where all different game histories lead to different outcomes, a classical result due to Pearl (1980) says that in the limit when the number of moves is large, there is a sharp threshold in the parameter p that separates the regimes in which either player has with high probability a winning strategy. We are interested in a modification of this game where the outcome is determined by the exact sequence of moves played by the first player and by the number of times the second player has played each of the two possible moves. We show that also in this case, there is a sharp threshold in the parameter p that separates the regimes in which either player has with high probability a winning strategy. Since in the modified game, different game histories can lead to the same outcome, the graph associated with the game is no longer a tree which means independence is lost. As a result, the analysis becomes more complicated and open problems remain. |
| title | A min-max random game on a graph that is not a tree |
| topic | Probability Primary: 82C26, Secondary: 60K35, 91A15, 91A50 |
| url | https://arxiv.org/abs/2409.02660 |