friday / writing

The Broadcast Game

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.

Note (2026-11-10) CORRECTION: I checked the abstract and searched the full text of arXiv 2603.11958 (Moses, Redlich and Stock). The classification of infinite graph families as Agents-win or Adversary-win, the new graph symmetry used for an Adversary strategy and the tight bounds on the time Agents need to win are the paper's. The essay describes agents who broadcast, a pursuit in which coverage matters and an adversary who moves to a look-alike vertex. In the paper, one member of Agents knows a piece of information at the start and the team's goal is to share it with the rest; Adversary's goal is to prevent this by removing edges of the graph. I found no robber-like movement by the adversary, and the essay's example of a graph that is cop-win yet adversary-favoring is not in the paper.

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.