### Learning the Game of Pursuit

26Jan15

Recently, I have unexpectedly shift my reading to game theory. This is due to a visit by Bakhadyr Khoussainov to the institute. I knew of game theory only from its association to mathematical economics, mostly through names like John von Neumann and John Nash but had not made any efforts to seriously pick up a book and read about the subject. Little did I know that its use is pervasive and is considered widely in computer science. Bakhadyr was interested in games played on graphs (discrete). A colleague in the institute, Ibragimov Gafurjan was interested in differential games (continuous) and hence their pairing.

Games on graphs probably would take up more explanation than its continuous counterpart but a seemingly good introduction to this may be given by Khoussainov’s article “On Some Games Played on Finite Graphs“, Bull. Sect. Logic 31 (2002) 71-79. Differential games are perhaps slightly familiar to physicists since it uses differential equations. Mathematically, I would consider differential games as part of the subject of dynamical systems with multiple control options allowing decision-making. In a game, there will be two players, each with its own control parameter $u(\cdot),\ v(\cdot)$. One simple game is simply the game of pursuit: say, player 1 (the pursuer P) is trying to catch player 2, while player 2 (the evader E) tries to run away. Suppose the states of player 1 and player are given by their positions say $x(t),\ y(t)$, then player would want to minimize the distance $\rho(x(t),y(t))$ between the players while player 2 would rather maximize it. Their own positions may follow some dynamical equations which depends on the strategies taken by the players through each control parameter:

$\dot{x}=f(x,u(x,y,t))\qquad;\qquad \dot{y}=g(y,v(x,y,t))\quad .$

Note that the control parameters themselves are dependent on the players’ positions. These seemingly innocent looking equations contain a rich plethora of situations depending on what the functions $f,\ g,\ u,\ v$ are. I will not be able to do justice to the topic but a book that discusses this pursuit-evasion game in detail is the book “Differential Games of Pursuit” by Leon Petrosjan. Presently reading it slowly to get a feeling of the subject matter. Questions of interest to this pursuit-evader games are whether one can decide whether the pursuer or evader wins given a particular specification. Consider the case of pursuit-evasion game in one dimension. In the situation of perfect information (each player knows the position and velocity of the other player), then it can be decided which player wins. Otherwise, it can be undecidable.

Now perhaps, one may ask why should one be interested in such “simple” game. Apparently this has applications in computer science such as search algorithms, virus detection and network security (for example see the thesis by Nicolas Nisse). These three applications themselves would have been enough to make us understand the importance of the study of pursuit-evasion games.