In this paper we introduce the concept of intransitiveness for games, which is the condition for which there is no first-player winning strategy, and the second player can statistically win. We show that the game can be converted into a random walk on a graph, i.e., a Markov process, and therefore we can extend the intransitiveness concept to such systems. The end of the game generally consists in the appearance of a pattern chosen by one of the player. In the language of random walk this corresponds to an absorbing trap, since once that the game has reached this condition the game itself comes to an end. Therefore, the intransitiveness of the game can be mapped into a problem of competition among traps. We analyse in details this problem for the Penney game (an extension of the heads or tails game which is intransitive for sequences longer than three), for walks on a circle and for a scale-free network, reminiscent of the structure of the world wide web. We also introduce several variations: traps can be partially absorbing, the walk can be biased and the initial distribution can be arbitrary. We found that the intransitiveness concept can be quite useful for characterizing the properties of a graph, and that the consequences of the above mentioned extensions are not trivial.
Intransitiveness in Games and Random Walks / Baldi A.; Cencetti G.; Fanelli D.; Bagnoli F.. - STAMPA. - 11938:(2019), pp. 204-216. (Intervento presentato al convegno 6th International Conference on Internet Science, INSCI 2019 tenutosi a fra nel 2019) [10.1007/978-3-030-34770-3_15].
Intransitiveness in Games and Random Walks
Cencetti G.;Fanelli D.;Bagnoli F.
2019
Abstract
In this paper we introduce the concept of intransitiveness for games, which is the condition for which there is no first-player winning strategy, and the second player can statistically win. We show that the game can be converted into a random walk on a graph, i.e., a Markov process, and therefore we can extend the intransitiveness concept to such systems. The end of the game generally consists in the appearance of a pattern chosen by one of the player. In the language of random walk this corresponds to an absorbing trap, since once that the game has reached this condition the game itself comes to an end. Therefore, the intransitiveness of the game can be mapped into a problem of competition among traps. We analyse in details this problem for the Penney game (an extension of the heads or tails game which is intransitive for sequences longer than three), for walks on a circle and for a scale-free network, reminiscent of the structure of the world wide web. We also introduce several variations: traps can be partially absorbing, the walk can be biased and the initial distribution can be arbitrary. We found that the intransitiveness concept can be quite useful for characterizing the properties of a graph, and that the consequences of the above mentioned extensions are not trivial.File | Dimensione | Formato | |
---|---|---|---|
BaldiCencettiFanelliBagnoli-Intransitiveness-INSCI2019.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
690.02 kB
Formato
Adobe PDF
|
690.02 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.