Search Games with Predictions

We introduce the study of search games between a mobile Searcher and an immobile Hider in a new setting in which the Searcher has some potentially erroneous information, or prediction, on the Hider’s position. The objective is to establish tight tradeoffs between the consistency of a search strategy (i.e., its worst-case expected payoff assuming the prediction is correct) and its robustness (i.e., the worst-case expected payoff without any assumptions on the quality of the prediction). Our study is the first in the realm of learning-augmented algorithms to address the full power of mixed (randomized) strategies; previous work focused only on deterministic strategies, or relied on stochastic assumptions that do not guarantee worst-case robustness in adversarial situations. We provide a framework for proving the optimality of consistency/robustness tradeoffs in search games over both discrete and continuous as well as bounded and unbounded spaces. We illustrate the approach using three well-known problems, namely, searching in discrete locations, searching with stochastic overlook, and searching in the infinite line. Our techniques are not limited to search games, but they can be applied, more broadly, to any two-person zero-sum games in learning-augmented settings.

Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-23-1-0556]. This work was partially funded by the project PREDICTIONS [Grant ANR-23-CE48-0010] from the French National Research Agency (ANR).

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2024.1498.