The search and rescue game on a cycle

Thomas Lidbetter, Yifan Xie

Research output: Contribution to journalArticlepeer-review


We consider a search and rescue game introduced recently by the first author. An immobile target or targets (for example, injured hikers) are hidden on a graph. The terrain is assumed to be dangerous, so that when any given vertex of the graph is searched, there is a certain probability that the search will come to an end, otherwise with the complementary success probability the search can continue. A Searcher searches the graph with the aim of finding all the targets with maximum probability. Here, we focus on the game in the case that the graph is a cycle. In the case that there is only one target, we solve the game for equal success probabilities, and for a class of games with unequal success probabilities. For multiple targets and equal success probabilities, we give a solution for an adaptive Searcher and a solution in a special case for a non-adaptive Searcher. We also consider a continuous version of the model, giving a full solution for an adaptive Searcher and approximately optimal solutions in the non-adaptive case.

Original languageEnglish (US)
Article number114016
JournalTheoretical Computer Science
StatePublished - Jul 26 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Cycles
  • Game theory
  • Search and rescue
  • Search games


Dive into the research topics of 'The search and rescue game on a cycle'. Together they form a unique fingerprint.

Cite this