Steve Alpern

Steve Alpern, Mark Broom

A divisible treasure is located at a node $H$ of a network. From a given start node a group of $n$ Searchers each seek to reach $H$ first, dividing the treasure equally with the other first arrivers. This type of search game is called competitive search, where the conflict is not between hider and searcher but between searchers. Examples are search for oil deposits or for a pilot downed over enemy territory. In our model, the Searchers have a common Satnav (GPS) which points to $H$ at each branch node with a known probability $p<1$ and each Searcher chooses the probability $q$ with which they follow the pointer. We consider a family of star graphs where the Searchers start at the center and $H$ lies at one of the $k$ leaf nodes. We show that for all parameter values $n,k,p,$ there is a unique trust probability $q$ which forms a symmetric equilibrium. The equilibrium $q$ is increasing in $p,$ decreasing in $n$ and increasing in $k$. Furthemore for fixed $k$ and $p$ we have $q$ equal to $p$ in the limit of $n$ tending to infinity. This last fact is a new example where what is known in behavioural science as probability matching is in fact rational.

Steve Alpern

This paper optimizes motion planning when there is a known risk that the road choice suggested by a Satnav (GPS) is not on a shortest path. At every branch node of a network Q, a Satnav (GPS) points to the arc leading to the destination, or home node, H - but only with a high known probability p. Always trusting the Satnav's suggestion may lead to an infinite cycle. If one wishes to reach H in least expected time, with what probability q=q(Q,p) should one trust the pointer (if not, one chooses randomly among the other arcs)? We call this the Faulty Satnav (GPS) Problem. We also consider versions where the trust probability q can depend on the degree of the current node and a `treasure hunt' where two searchers try to reach H first. The agent searching for H need not be a car, that is just a familiar example -- it could equally be a UAV receiving unreliable GPS information. This problem has its origin not in driver frustration but in the work of Fonio et al (2017) on ant navigation, where the pointers correspond to pheromone markers pointing to the nest. Neither the driver or ant will know the exact process by which a choice (arc) is suggested, which puts the problem into the domain of how much to trust an option suggested by AI.

Steve Alpern, Paul Chleboun, Stamatios Katsikas

Patrolling Games were introduced by Alpern, Morton and Papadaki (2011) to model the adversarial problem where a mobile Patroller can thwart an attack at some location only by visiting it during the attack period, which has a prescribed integer duration m. Here, we modify the problem by allowing the Attacker to go to his planned attack location early and observe the presence or the absence there of the Patroller (who wears a uniform). To avoid being too predictable, the Patroller may sometimes remain at her base when she could have been visiting a possible attack location. The Attacker can then choose to delay attacking for some number of periods d after the Patroller leaves his planned attack location. As shown here, this extra information for the Attacker can reduce thwarted attacks by as much as a factor of four in specific models. Our main finding, is that the attack should begin in the second period the Patroller is away (d = 2) and that the Patroller should never attack the same location in consecutive periods.