Cops and robber with decoys

We introduce a variation of the Cops and Robber game in which the robber side consists of a robber and a decoy which are indistinguishable to the cops except under certain conditions. The cops win when one of them moves onto the same vertex as the actual robber (i.e.~not the decoy) after a finite number of turns. The robber can throw the decoy to a neighbouring vertex on any turn beyond his first; such a turn for the robber consists of throwing (or dropping) the decoy and then moving. The current decoy disappears as the next is thrown so there is only a single decoy in play at any time. We characterize decoy-copwin graphs in the case where the cop can distinguish between the robber and decoy only when he is on the same vertex as one of them. We also characterize such graphs if the cop can distinguish between the robber and decoy only when he has cornered at least one of them

Authors

Publication Details

Journal
AcadiaU-DEV
Published
2026-01-01
DOI
https://doi.org/10.26108/haz2-nn67
Primary Topic
Artificial Intelligence in Games
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Cops and robber with decoys

Davita DesRoches, James S. Diamond, Nancy E. Clarke, Mohammed M. Islam
AcadiaU-DEV
Artificial Intelligence in Games
article

Cops and robber with decoys

Davita DesRoches, James S. Diamond, Nancy E. Clarke, Mohammed M. Islam
article en

Abstract

We introduce a variation of the Cops and Robber game in which the robber side consists of a robber and a decoy which are indistinguishable to the cops except under certain conditions. The cops win when one of them moves onto the same vertex as the actual robber (i.e.~not the decoy) after a finite number of turns. The robber can throw the decoy to a neighbouring vertex on any turn beyond his first; such a turn for the robber consists of throwing (or dropping) the decoy and then moving. The current decoy disappears as the next is thrown so there is only a single decoy in play at any time. We characterize decoy-copwin graphs in the case where the cop can distinguish between the robber and decoy only when he is on the same vertex as one of them. We also characterize such graphs if the cop can distinguish between the robber and decoy only when he has cornered at least one of them

AcadiaU-DEV
Peace, Justice and strong institutions
Openalex Percentile: Top 9%
Artificial Intelligence in Games
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.