An invitation to pursuit-evasion games and graph theory. (English) Zbl 1500.91001

Bonato, Anthony

Student Mathematical Library 97. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-6763-0/pbk; 978-1-4704-7100-2/ebook). xx, 254 p. (2022).

In this textbook, the author provides a thorough introduction to pursuit-evasion games, a class of dynamic interactions that take place on a graph. In a pursuit-evasion game, there is a set of vertices and a set of edges linking them. Time is discrete and measured in rounds. One player, the evader, can move across vertices of the graph according to fixed rules. One or more other players, the pursuers, can move according to their own rules. The goal of the pursuers is to reach the same location as the evader, or to surround or locate the evader. A classic example is Cops and Robbers, where the evader and pursuers move in alternating rounds, and each may move along a single edge to a neighboring vertex.
The book begins with a concise, seven-page introduction or refresher on graph theory and then covers several classes of pursuit-evasion games in more detail. By focusing on pursuit-evasion fames specifically, the author is able to go into substantial depth across many of the important topics in the field. Two areas that the book does not devote much attention to are algorithmic approaches and stochastic modeling.
The text is primarily intended to support a one-semester course for graduate students or outstanding undergraduates who have already taken a class on graph theory. It could also be a useful entrance point for mathematicians who want an overview of pursuit-evasion games. The author provides many exercises, as well as several suggestions for more ambitious research projects.
Overall, the book is reader friendly and engaging, with many helpful figures and illustrations. The author writes in the preface that the book aims to be “self-contained, understandable, and accessible to a broad mathematical audience”, and it achieves that goal.

Reviewer: Thomas Wiseman (Austin)

MSC:

91-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to game theory, economics, and finance
91A24	Positional games (pursuit and evasion, etc.)
91A43	Games involving graphs
05C57	Games on graphs (graph-theoretic aspects)

Keywords:

pursuit-evasion games; graph theory; dynamic games