Shmuel Gal

Informatics Department, University of Geneva

Repeated hide-seek and pursuit-evasion games

[When and where]

A predator (searcher) looks for a prey (hider) in a search space consisting ofnlocations. The hider chooses a location and the searcher inspects k different locations, where k is a parameter of the game (the giving-up time for the continuous version). If the predator visits a location i at which the prey hides, then the game moves into a pursuit-evasion phase. In this phase capture is not certain but occurs with probability p_i: In a previous work we showed that for all k smaller than an easily calculated threshold, it is optimal to hide with probability proportional to 1/p_i for each location i: If k exceeds the threshold, then the optimal hiding strategy is always to stay at the location with the smallest p_i.

We extend this game to a repeated game. During the k looks among the different locations within a single patch, there can be any of three events. First, if the searcher does not find the hider, then the game ends with zero payoff for the searcher and a payoff of one to the hider. Second, if the searcher finds the hider and catches it, then the game ends with a payoff of one to the searcher and zero to the hider. Finally, if the searcher finds the hider but does not catch it then the hider escapes to another patch and the process restarts. We show that in this game the optimal hiding strategy is to always make all the locations equally "attractive" for the searcher, no matter how large is k: This situation is quite different from the one stage game in which solutions of this type occur only if k is below the threshold.

We actually present a general framework of repeated discounted games. We solve a family of games depending on the discount factor \beta, 0 ≤ \beta ≤ 1. The two extreme cases occur for \beta = 0 and for \beta = 1 in which we get the undiscounted repeated game. We obtain an explicit expression for the discount factor above which the equally attractive solution is optimal.

We also analyze the stochastic game version of the game in which the number of looks is reduced by one after each look even if the hider escapes to a different patch. We present a computational scheme for solving this game.

sgal@univ.haifa.ac.il

Invited talk Mini-symposium 3 .

Updated May 13, 2015, by Minus