Revolutionaries and Spies (2010)

Originator: Jozef Beck    (presented by David Howard - REGS 2010)

Definition: We define a combinatorial game with four parameters. Player 1 has r revolutionaries and Player 2 has s spies. The game is played on the vertices of a graph G. The goal of the revolutionaries is to have a meeting of size k at some vertex with no spy present at the end of a round. In the initial round, first Player puts all r revolutionaries at vertices. Player 2 then places the s spies on vertices of G. In each subsequent round every revolutionary may remain in place or move to an adjacent vertex, and then each spy may remain in place or move to an adjacent vertex. The revolutionaries win if a round ends with k revolutionaries and no spy on some vertex. The spies win if they have a strategy to protect against this forever.

Question 1: For which G, k, r, s do the revolutionaries win?

Comments: The spies win whenever G has at most s vertices. If r≥k(s+1), then the revolutionaries win whenever G has at least s+1 vertices. Increasing r cannot hurt the revolutionaries.

Question 2: Given G and k, what is the threshold for r as a function of s such that the revolutionaries win? Here G may be a highly structured infinite graph or a sequence of graphs that grow with s. In particular, what is the threshold when k=2 and G is the 2-dimensional integer lattice in which edges can change one or both coordinates by 1 (king's moves)? Call this graph ZZ.

Comments: When G is a tree with more than s vertices, Howard and Smyth [HS] proved that the revolutionaries win if and only if r≥k(s+1) (not easy). For ZZ with k=2, they proved that the revolutionaries win if r≥(4/3)s+1 (hard), but the spies win if r≤s+2. The latter is easy: s-1 of the spies follow particular revolutionaries, so it suffices to show that one spy can prevent an unprotected meeting when r=3. They conjectured that the revolutionaries win as soon as r≥s+3.

In REGS discussion, it was noted that when k=2 and G is a sufficiently long cycle, the revolutionaries win if and only if ≥2s+1. Motivated by grids and cycles, another sensible class of graphs to consider is toroidal grids. Puleo, West, and Zamani are working toward a solution of the threshold problem for k=2 on the infinite complete bipartite graph.

One can also change the problem by changing the speed of movement of revolutionaries or spies or changing the number of spies needed to block a meeting.

References:
D. Howard and C. Smyth, Revolutionaries and spies.