Strategies and first-absorption times in the random walk game

M. I. Krivonosov ; S. N. Tikhomirov

Izvestiya VUZ. Applied Nonlinear Dynamics, Tome 31 (2023) no. 3, pp. 334-350.

Résumé

Purpose of this work is to determine the average time to reach the boundaries, as well as to identify the strategy in the game between two players, controlling point movements on the finite square lattice using an independent choice of strategies. One player wants to survive, i. e., to stay within the interior of the square, as long as possible, while his opponent wants to reach the absorbing boundary. A game starts from the center of the square and every next movement of the point is determined by independent strategy choices made by the players. The value of the game is the survival time that is the number of steps before the absorption happens. In addition we present series of experiments involving both human players and an autonomous agent (bot) and analysis of the survival time probability distributions. Methods. In this work, methods of the theory of absorbing Markov chains were used to analyze strategies and absorption times, as well as the Monte Carlo method to simulate trajectories. Additionally, a large-scale field experiment was conducted using the developed mobile application. Results. The players’ strategies are experimentally obtained for the cases of playing against an autonomous agent (bot), as well as human players against each other. A comparison with optimal strategies and a random walk is made: the difference between the experimental strategies and the optimal ones is shown, however, the resulting strategies show a much better result of games than a simple random walk. In addition, especially long-running games do not show the Markovian property in case of the simulation corresponding strategies. Conclusion. The sampled histograms indicate that the game-driven walks are more complex than a random walk on a finite lattice but it can be reproduced with a Markov Chain model

Détail

Keywords: random walk, markov chain, random walk game, mobile application, game experiment.

Bibliographie

[1] Coolidge J. L., “The gambler's ruin”, Annals of Mathematics, 10:4 (1909), 181–192 | DOI

[2] Feller W. D., An Introduction to Probability Theory and Its Applications, New York, Wiley, 1950, 704 pp.

[3] Redner S., A Guide to First-Passage Processes, Cambridge University Press, Cambridge, 2001, 312 pp. | DOI

[4] Hausner M., Games of Survival. Report No. RM-776, The RAND Corporation, Santa Monica, 1952, 7 pp.

[5] Peisakoff M. P., More on Games of Survival. Report No. RM-884, The RAND Corporation, Santa Monica, 1952, 20 pp.

[6] Kmet A., Petkovšek M., “Gambler's ruin problem in several dimensions”, Advances in Applied Mathematics, 28:2 (2002), 107–118 | DOI

[7] Romanovskii I. V., “Game-type random walks”, Theory of Probability Its Applications, 6:4 (1961), 393–396 | DOI

[8] Nisan N., Roughgarden T., Tardos E., Vazirani V. V., Algorithmic Game Theory, Cambridge University Press, Cambridge, 2007, 754 pp. | DOI

[9] Pearson K., “The problem of the random walk”, Nature, 72 (1905), 294 | DOI

[10] Zaburdaev V., Denisov S., Klafter J., “Lévy walks”, Reviews of Modern Physics, 87:2 (2015), 483–530 | DOI

[11] Bénichou O., Loverdo C., Moreau M., Voituriez R., “Intermittent search strategies”, Reviews of Modern Physics, 83:1 (2011), 81–129 | DOI

[12] Rhee I, Shin M, Hong S, Lee K, Kim SJ, Chong S., “On the Levy-walk nature of human mobility”, IEEE/ACM Transactions on Networking, 19:3 (2011), 630–643 | DOI

[13] Fauchald P., “Foraging in a hierarchical patch system”, The American Naturalist, 153:6 (1999), 603–613 | DOI

[14] Scanlon T. M., Caylor K. K., Levin S. A., Rodriguez-Iturbe I., “Positive feedbacks promote power-law clustering of Kalahari vegetation”, Nature, 449:7159 (2007), 209–212 | DOI

[15] Reynolds A., Ceccon E., Baldauf C., Karina Medeiros T., Miramontes O., “Lévy foraging patterns of rural humans”, PLOS ONE, 13:6 (2018), e0199099 | DOI

[16] Pyke G. H., “Understanding movements of organisms: it's time to abandon the Lévy foraging hypothesis”, Methods in Ecology and Evolution, 6:1 (2015), 1–16 | DOI

[17] LaScala-Gruenewald D. E, Mehta R. S, Liu Y., Denny M. W., “Sensory perception plays a larger role in foraging efficiency than heavy-tailed movement strategies”, Ecological Modelling, 404 (2019), 69–82 | DOI

[18] Krivonosov MI, Tikhomirov SN., Random Walk Game, 2020 https://play.google.com/store/apps/details?id=com.scigames.RWGame

[19] Taylor H. M, Karlin S., An Introduction to Stochastic Modeling, Academic Press, San Diego, 2008, 648 pp.

[20] Kemeny J. G, Snell J. L., Finite Markov Chains, Springer-Verlag, New York, 1983, 226 pp.

[21] Darroch J. N, Seneta E., Journal of Applied Probability, 2:1 (1965), On quasi-stationary distributions in absorbing discrete-time finite Markov shains | DOI

[22] Zhang J., Calabrese C., Ding J., Liu M. , Zhang B., “Advantages and challenges in using mobile apps for field experiments: A systematic review and a case study”, Mobile Media Communication, 6:2 (2018), 179–196 | DOI