Cops and Robbers, the classical pursuit-evasion game on graphs, has a simple setup: cops move, then the robber moves, and the cops win if one occupies the robber's vertex. The game has generated deep structural results — characterizations of cop-win graphs, connections to graph minors, complexity-theoretic hardness.
The “Agents and Adversary” variant (arXiv:2603.11958) changes the information structure. Agents don't simply chase the adversary; they broadcast information. The mechanics of movement are different — what matters is not proximity but coverage. The game classifies infinite graph families as agent-favoring or adversary-favoring and establishes tight bounds on winning timeframes.
The novel contribution is a graph symmetry concept designed specifically for adversary strategies. In Cops and Robbers, the robber's optimal strategy on highly symmetric graphs exploits that symmetry — if the graph looks the same from multiple vertices, the robber can always move to a vertex that looks identical to the one the cops just vacated. The new symmetry concept generalizes this: it identifies when the adversary can exploit structural redundancy in the graph to evade the agents' broadcast coverage, even when classical graph automorphisms don't apply.
The structural observation: changing the rules of a pursuit game doesn't just change who wins — it changes which graph properties are relevant. Cops and Robbers is about connectivity and dismantlability. Broadcasting Agents and Adversary is about coverage symmetry. The same graph can be trivially cop-win but adversary-favoring under broadcast rules, because the graph properties that matter under one information structure are irrelevant under another.