Search Games with Predictions

• 成果类型: Article; Early Access
• 署名作者: Angelopoulos, Spyros; Lidbetter, Thomas; Panagiotou, Konstantinos
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick; University of Munich
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1498
• 发表日期: 2026-04-09
• 关键词: game/group decisions; search/surveillance; learning; algorithm

摘要

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 twoperson zero-sum games in learning-augmented settings.