Optimal Hiding with Partial Information of the Seeker's Route
For researchers in game theory and search problems, this provides a theoretical analysis of partial information and relocation in sequential search.
The paper studies a hide-and-seek game where the Hider can relocate the treasure after observing a prefix of the Seeker's route, with a switching cost. It derives upper bounds on the value of information and shows that Seeker awareness reduces the game value, with the benefit of relocation decreasing as switching cost increases or reveal occurs later.
We consider a hide-and-seek game between a Hider and a Seeker over a finite set of locations. The Hider chooses one location to conceal a stationary treasure, while the Seeker visits the locations sequentially along a route. As the search progresses, the Hider observes a prefix of the Seeker's route. After observing this information, the Hider has the option to relocate the treasure at most once to another unvisited location by paying a switching cost. We study two seeker models. In the first, the Seeker is unaware of the fact that the Hider can relocate. In the second, the Seeker select its route while accounting for the possibility that the Hider observes its path and reallocates. For the restricted case, we define the value-of-information created by the reveal and derive upper bounds in terms of the switching cost using a worst-case evaluation over routes. We also show that seeker awareness reduces the game value, with the difference between the restricted and feedback models bounded by the entry-wise gap between the corresponding payoff matrices. Numerical examples show how this benefit decreases as the switching cost increases and as the reveal occurs later along the route.