Cops, Robbers and Alarms

About the Game:        
          Cops, Robbers and Alarms is a variation of Cops and Robbers in which the Cop has imperfect information—that is, she doesn’t know the exact location of the robber. Imperfect information makes intercepting her nefarious evader considerably more challenging, so the cop must install alarms on her beat. The game is played on a finite, undirected, copwin graph as in classical Cops and Robbers, but now the cop may set alarm systems on some of the vertices.

          When the robber occupies an “alarmed” vertex, the alarm will go off and the robber’s position is revealed to the cop. The alarms do not reveal the robber’s preimage, however, so the cop does not know the robber’s direction. (There is a variation called Cops, Robbers and Video Cameras, in which there are video surveillance systems that give the robber’s direction.)     

Rules of the Game:   

          Of course the cop cannot set alarms willy-nilly around the graph—that would be too easy! After all, classic Cops and Robbers is played on the trivial, fully-alarmed graph. Instead, the cop must obey a set of conditions determined at the beginning of the game. Let’s first consider a game with relatively lenient conditions:

1.               Each unalarmed vertex must have at least one alarmed neighbor
2.               Unalarmed vertices may not have unalarmed neighbors

          When these conditions are applied to an arbitrary undirected, copwin graph G, we get something like this (Figure 1). Open circles represent alarmed vertices. 

Figure 1. A copwin graph G with liberal alarm placement.

          This particular graph would make for a very quick game of Cops and Robbers on account of its many corners and alarms. In fact, the robber could not move anywhere on the graph undetected, due to condition 2. BORING…

          So let’s tighten up the conditions on G. Suppose we created an undirected, copwin graph G on which the alarmed vertices form a dominating set. A dominating set is a subset D of G such that every element not in the intersection of D and G is adjacent to at least one element of D. When we impose this condition on the graph in figure 1, we get the following:

Figure 2. A copwin graph G, where the set of alarmed vertices forms a dominating set.  

          This new restriction eliminated a few more alarms, making it easier for the robber to evade the cop. This new alarm configuration is only slightly better for the robber though. He has a path of five unalarmed vertices in the leftmost portion of the graph on which he could move. If he remains in that central location, however, he is likely to run into the cop or get forced into a corner—not to mention that going undetected can be just as telling as setting off alarms.      

         

Alarm Number and Capture Time:

          It's clear that the alarm number, A(G), plays a critical role in determining capture time. Alarm number also determines the finiteness of the game. In some cases, graphs that are copwin in classic play become robberwin (infinite game) if there aren't enough alarms.

Witness Version of Cops and Robbers:

          Cops, Robbers and Witnesses is another variation of Cops and Robbers that warrants consideration here. Cops, Robbers and Witnesses is similar to Cops, Robbers and Alarms in that it is also based on the premise of imperfect information. In the witness version of the game, the cop is given information from witnesses either irregularly or k-regularly. 

          With irregular information, sightings of the robber are reported at random time intervals during the game. A graph is copwin with irregular information if the graph is a tree—an undirected graph in which any two vertices are connected by one unique path.

          In the case of k-regular sightings, the cop is informed of the robber's position every k units of time. A graph on which a cop can win with k-regular information is said to be k-winnable. 

Conclusion:

          Cops, Robbers and Alarms is unique in its treatment of imperfect information vis-à-vis Hunter vs. Mole or Cop vs. Gambler. Capture time and the success of gameplay depend entirely on the alarm number, A(G) (or the k-regularity of information), rather than on probability. We will continue our exploration of the game and look at some different game conditions and graph types in class on Tuesday. 

Works Consulted:

Jeliazkova, D. (2006). "Aspects of the Cops and Robber Game Played with Incomplete Information." Acadia University.

Clarke, N.E. (2008). A Witness Version of the Cops and Robber Game." Discrete Mathematics. 309(10). pp. 3292-3298.