Search Games with Predictions

Searching with Advice You Cannot Fully Trust Searching for a hidden target is a classic problem in operations research, arising in contexts such as search-and-rescue missions, exploration for natural resources, and robotic navigation. In many real-world scenarios, the searcher is not completely in the dark: it may have some prior information suggesting where the hider might be located. Such predictions can be helpful—but they may also be wrong. In “Search Games with Predictions,” Angelopoulos, Lidbetter, and Panagiotou present the first study of search games in a fully randomized setting where both the Searcher and the Hider employ mixed strategies, and the prediction may be erroneous. The paper identifies strategies that optimally balance two competing objectives: the search performance when the prediction is correct, and the performance when there are no assumptions on the quality of the prediction. The paper demonstrates this approach on several classic search problems such as box search with or without overlook, line search, and star search. The results quantify both the benefits and limitations of predictive information and provide a framework that does not apply only to search games, but to two-player zero-sum games more broadly.