Date: Tuesday, February 18th
Presenter: Benoit Duvocelle
Authors: Benoit Duvocelle, János Flesch, Mathias Staudigl, Dries Vermeulen (KE, UM)
Title: A competitive search game with a moving target
Abstract: We introduce a discrete-time search game, in which two players compete to find an object first. The object moves according to a Markov chain on finitely many states. The players know the Markov chain and the initial probability distribution of the object, but do not observe the current state of the object. Player 1 is active at odd periods, and player 2 is active at even periods. At each period, the active player chooses a state, and this choice is observed by the other player. If the object is in the chosen state, this player wins and the game ends. Otherwise, the item moves according to the Markov chain and the game continues at the next period. The play of the game is continued as long as the object is not found, with a possibly infinite duration. We prove that an epsilon-equilibrium always exists in pure strategies, for all epsilon>0. Moreover, if the Markov chain is irreducible and aperiodic then the game even admits a 0-equilibrium in pure strategies. As an example demonstrates, a 0-equilibrium does not always exist. We also define and analyze a refinement of epsilon-equilibrium adapted to this setting. Finally, we study two relevant classes of strategies and show that they perform reasonably well against any strategy of the opponent.