Intransitiveness: From Games to Random Walks
Many games in which chance plays a role can be simulated as a random walk over a graph of possible configurations of board pieces, cards, dice or coins. The end of the game generally consists of the appearance of a predefined winning pattern; for random walks, this corresponds to an absorbing trap....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Future Internet |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-5903/12/9/151 |
| _version_ | 1797554731954995200 |
|---|---|
| author | Alberto Baldi Franco Bagnoli |
| author_facet | Alberto Baldi Franco Bagnoli |
| author_sort | Alberto Baldi |
| collection | DOAJ |
| description | Many games in which chance plays a role can be simulated as a random walk over a graph of possible configurations of board pieces, cards, dice or coins. The end of the game generally consists of the appearance of a predefined winning pattern; for random walks, this corresponds to an absorbing trap. The strategy of a player consist of betting on a given sequence, i.e., in placing a trap on the graph. In two-players games, the competition between strategies corresponds to the capabilities of the corresponding traps in capturing the random walks originated by the aleatory components of the game. The concept of dominance transitivity of strategies implies an advantage for the first player, who can choose the strategy that, at least statistically, wins. However, in some games, the second player is statistically advantaged, so these games are denoted “intransitive”. In an intransitive game, the second player can choose a location for his/her trap which captures more random walks than that of the first one. The transitivity concept can, therefore, be extended to generic random walks and in general to Markov chains. We analyze random walks on several kinds of networks (rings, scale-free, hierarchical and city-inspired) with many variations: traps can be partially absorbing, the walkers can be biased and the initial distribution can be arbitrary. We found that the transitivity concept can be quite useful for characterizing the combined properties of a graph and that of the walkers. |
| first_indexed | 2024-03-10T16:36:14Z |
| format | Article |
| id | doaj.art-c7cfd1abc8244f208d08271fb53eec9c |
| institution | Directory Open Access Journal |
| issn | 1999-5903 |
| language | English |
| last_indexed | 2024-03-10T16:36:14Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Future Internet |
| spelling | doaj.art-c7cfd1abc8244f208d08271fb53eec9c2023-11-20T12:27:48ZengMDPI AGFuture Internet1999-59032020-09-0112915110.3390/fi12090151Intransitiveness: From Games to Random WalksAlberto Baldi0Franco Bagnoli1Department of Physics and Astronomy and CSDC, University of Florence, via G. Sansone 1, 50019 Sesto Fiorentino, ItalyDepartment of Physics and Astronomy and CSDC, University of Florence, via G. Sansone 1, 50019 Sesto Fiorentino, ItalyMany games in which chance plays a role can be simulated as a random walk over a graph of possible configurations of board pieces, cards, dice or coins. The end of the game generally consists of the appearance of a predefined winning pattern; for random walks, this corresponds to an absorbing trap. The strategy of a player consist of betting on a given sequence, i.e., in placing a trap on the graph. In two-players games, the competition between strategies corresponds to the capabilities of the corresponding traps in capturing the random walks originated by the aleatory components of the game. The concept of dominance transitivity of strategies implies an advantage for the first player, who can choose the strategy that, at least statistically, wins. However, in some games, the second player is statistically advantaged, so these games are denoted “intransitive”. In an intransitive game, the second player can choose a location for his/her trap which captures more random walks than that of the first one. The transitivity concept can, therefore, be extended to generic random walks and in general to Markov chains. We analyze random walks on several kinds of networks (rings, scale-free, hierarchical and city-inspired) with many variations: traps can be partially absorbing, the walkers can be biased and the initial distribution can be arbitrary. We found that the transitivity concept can be quite useful for characterizing the combined properties of a graph and that of the walkers.https://www.mdpi.com/1999-5903/12/9/151transitivityrandom walkPenney gamenetwork theory |
| spellingShingle | Alberto Baldi Franco Bagnoli Intransitiveness: From Games to Random Walks Future Internet transitivity random walk Penney game network theory |
| title | Intransitiveness: From Games to Random Walks |
| title_full | Intransitiveness: From Games to Random Walks |
| title_fullStr | Intransitiveness: From Games to Random Walks |
| title_full_unstemmed | Intransitiveness: From Games to Random Walks |
| title_short | Intransitiveness: From Games to Random Walks |
| title_sort | intransitiveness from games to random walks |
| topic | transitivity random walk Penney game network theory |
| url | https://www.mdpi.com/1999-5903/12/9/151 |
| work_keys_str_mv | AT albertobaldi intransitivenessfromgamestorandomwalks AT francobagnoli intransitivenessfromgamestorandomwalks |