Searching for a mobile hider in a directed bipartite graph
研究一个动态搜索博弈，隐藏者可在有向二分图的两部分间移动，搜索者每次选一个顶点检查，目标是找到最小化期望搜索时间的策略，并给出上下界和有限时域近似解。
We examine a dynamic search game played between two players, the hider and the searcher. The game takes place in a directed bipartite graph, consisting of two partitions A and B , such that all arcs go from vertices in A to vertices in B . The hider chooses an initial vertex and hides there, and at any period, if she is in a vertex in partition A , she has the option to stay or to travel along one of the outgoing arcs to a vertex in B . The searcher at each period chooses an arbitrary vertex of the graph, and if the hider is there, then the hider is found and the game ends. The hider does not observe which vertex is searched by the searcher. The searcher’s goal is to minimize the expected search time, whereas the hider’s goal is to maximize it. One interpretation of the game is that a rescue team searches possible locations of an injured person on two sides of a river, while considering the worse-case scenario. Our results are as follows: (i) We prove that these games admit a value and each player has an optimal strategy. (ii) We determine upper and lower bounds on the value and simple strategies guaranteeing these bounds, and in some special classes we improve on these bounds. (iii) Given an error-term ϵ > 0 , we identify a finite horizon such that the solutions of the finite horizon game yield ϵ -optimal solutions for the original game, and vice versa.