Revolutionaries and Spies

Revolutionaries and Spies   is a game, G(G,r,s,k)G(G,r,s,k), played on a graph GG between two teams: one team consists of rr revolutionaries, the other consists of ss spies. To start, each revolutionary chooses a vertex as its position. The spies then do the same. (Throughout the game, there is no restriction on the number of revolutionaries and spies that may be positioned on any given vertex.) The revolutionaries and spies then alternate moves with the revolutionaries going first. To move, each revolutionary simultaneously chooses to stay put on its vertex or to move to an adjacent vertex. The spies move in the same way. The goal of the revolutionaries is to place kk of their team on some vertex vv in such a way that the spies cannot place one of their spies at vv in their next move; this is a win for the revolutionaries. If the spies can prevent this forever, they win. There is no hidden information; the positions of all revolutionaries and spies is known to both sides at all times.We will present a number of basic results as well as the result that if G(Z2,r,s,2)G(Z2,r,s,2) is a win for the spies, then s≥6⌊r8⌋. (Here allowable moves in Z2Z2 consist of one-step horizontal, vertical or diagonal moves.)