Geodesic
Optimal strategies in the game of patrol on a graph
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 2 (2015), pp. 61-76 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the game-theoretic model of patrolling on a graph in which an attacker has $m$ time units to attack a node of the graph and the strategy of patroller is a selection of a path in the graph. The equilibrium in the zero-sum game and the mean length of the patrolling path are derived for different graphs. Bibliogr. 7. Il. 1. Table 13.
Keywords: search game, graph, patrol, attacker, optimal strategies. 
@article{VSPUI_2015_2_a5,
     author = {V. V. Gusev and V. V. Mazalov},
     title = {Optimal strategies in the game of patrol on a graph},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {61--76},
     year = {2015},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2015_2_a5/}
}
TY  - JOUR
AU  - V. V. Gusev
AU  - V. V. Mazalov
TI  - Optimal strategies in the game of patrol on a graph
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2015
SP  - 61
EP  - 76
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2015_2_a5/
LA  - ru
ID  - VSPUI_2015_2_a5
ER  - 
%0 Journal Article
%A V. V. Gusev
%A V. V. Mazalov
%T Optimal strategies in the game of patrol on a graph
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2015
%P 61-76
%N 2
%U http://geodesic.mathdoc.fr/item/VSPUI_2015_2_a5/
%G ru
%F VSPUI_2015_2_a5
V. V. Gusev; V. V. Mazalov. Optimal strategies in the game of patrol on a graph. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 2 (2015), pp. 61-76. http://geodesic.mathdoc.fr/item/VSPUI_2015_2_a5/

[1] Garnaev A., Search games and other applications of game theory, Lecture Notes in Economics and Mathematical Systems, 485, Springer, Budapest, 2000, 153 pp. | MR | Zbl

[2] Alpern S., Gal S., The theory of search games and rendezvous, Kluwer Academic Publ., Boston, 2003, 319 pp. | MR | Zbl

[3] Alpern S., Morton A., Papadaki K., Optimizing randomized patrols, Operational Research working papers, LSEOR 09.116, Operational Research Group, London School of Economics and Political Science, London, UK, 2009 | Zbl

[4] Gal S., “On the Optimality of a Simple Strategy for Searching Graphs”, Intern. Journal of Game Theory, 29 (2001), 533–542 | MR | Zbl

[5] Alpern S., Baston V., Gal S., Network Search Games With Immobile Hider, Without a Designated Searcher Starting Point, Research Report CDAM 2006-03, Centre for Discrete and Applicable Mathematics, London, 2006, 16 pp.

[6] Mazalov V. V., Mathematical theory of games and applications, a tutorial, “Lan” Publ., St. Petersdurg, 2010, 448 pp. (in Russ.)

[7] Vorobjov N. N., Theory of games for economists-cyberneticists, Leningr. State University Press, Leningrad, 1974, 160 pp. (in Russ.) | MR