Tom Lidbetter is an LSE Fellow in the Department of Mathematics. His research is concerned with using game theory to analyse models of hide-and-seek such as those described above. In particular, he developed a new theory of searching for multiple targets by considering the best randomised strategies both for searching and hiding. For more information about Tom’s research, see his website.
Recently, the nation has been gripped by the Channel 4 show, Hunted, which documents the pursuit of several “fugitives” by a crack squad of expert investigators. The fugitives face the challenge of avoiding detection for as long as possible, equipped with only a budget of £450 and a gritty determination.
Of course, the team of 30 investigators has access to some pretty sophisticated technology including automatic number plate recognition, ‘phone trackers and CCTV recordings. However, technology alone is not enough for the crack surveillance team to track down the fugitives; a large part of the investigative process involves trying to get into the minds of the off-grid fugitives by looking at social media or speaking to their friends and relatives in order to predict their movements. Intelligence expert, Ben Owen (one of the “hunters”), says:
“Human beings make patterns every day. A skilful fugitive will try not to make a pattern…but no individual is truly random. All the decisions…a fugitive makes are based on that person and who they are. Once we work that out, we’re going to be one step ahead.”
Human beings have enormous difficulty acting randomly. Indeed, another of the hunters, Cindy Storer, is a former CIA analyst and remarks:
“We all establish patterns to get through the day…and so it’s really hard for people to be random…As human beings, we tend to repeat ourselves. It’s a survival tactic, it’s in our DNA.”
In the first episode of Hunted, two fugitives are discovered after only a few days once Storer spots a pattern to their behaviour and predicts the bus route that they are likely to take. Their lack of ability to randomise was the fugitives’ downfall.
When analysing games of hide-and-seek using game theory, the mathematics predicts that the “optimal” solution generally involves randomisation: the kind of randomisation that human beings find so difficult. Consider the following very simple hide-and-seek game played between a single hunter and a fugitive; in this game the fugitive can choose to hide in one of two cities, say Edinburgh or Glasgow. Once she’s made her choice, we assume she has run out of money and can’t leave the city. The hunter knows that the fugitive is in one of these two locations, and if he picks the correct city he will find the fugitive for certain after a day of searching. If he picks the wrong one then he must spend an extra day searching the other city.
In our simple game, the ability of the fugitive to behave randomly makes a difference. First, suppose she is unable to choose randomly between the two cities: say she is biased towards choosing Glasgow because of a childhood memory or a connection to her favourite book; she risks the hunter being able to discover this information which will, in turn, lead him to the correct location. In the worst case scenario, the fugitive will be found after only one day of searching.
Now suppose the fugitive is able to randomise – she flips a coin and chooses one of the two cities with equal probability. Then there is no personal information which can assist the hunter. If he searches, say, Glasgow first followed by Edinburgh then there’s 50% chance he’ll find the fugitive after one day and 50% chance he’ll find her after two days. On average, that’s one and a half days that she can avoid capture (i.e. (0.5 x 1) + (0.5 x 2) = 1.5). The same time lapse applies if the hunter searches the cities in the opposite order so that’s a little better for the fugitive than the one day of evasion she can guarantee if she is unable to randomise.
The ability to randomise helps even more if there are 100 different cities to choose from. If the fugitive acts deterministically (i.e. without randomness) then, again, in the worst case scenario she may be caught after only a day of searching by the wily hunter if he is able to learn something about her preferences. If she behaves truly randomly then on average, the hunter will have to search about half – in this instance 50 – of the selected cities before finding her. That’s a massive improvement for the fugitive!
Of course, this simple game doesn’t go anywhere near modelling the complex factors involved in a real hunter-fugitive situation such as the one featured in the Channel 4 show, but it does show that even in such a simplified version of reality, the ability to act randomly offers a massive advantage.
The theory of search games can be used to model strategic situations like this in which “players” seek and hide from each other. It asks questions about how the hider should best randomise in order to maximise the time they’d expect to be able to remain hidden. For instance, in our example it made sense to hide in Edinburgh or Glasgow with equal probability because the cities are roughly the same size and would take the same amount of time to search. Imagine, though, if it were a choice between Edinburgh and London. In that case it would make sense for the fugitive to randomise in such a way that she chooses to hide in London with a higher probability since it would take the hunter so much longer to search the English capital. Using game theory, the best choices for these probabilities can be calculated precisely in hide-and-seek games.
One of the more successful fugitives on Hunted is Emily Dredge, who, after several episodes still managed to evade capture. In the first episode, one of the investigators, Steve Hersee, spent some time learning about Dredge by prying into her personal life via her laptop. Hersee commented:
“She’s definitely complex…and will be quite unpredictable, I think. She’s just a free spirit and she does what she likes. There’s just no reasoning.”
He was right! Her unpredictability made her especially difficult to track down. This is a justification of how effective the kind of the randomness predicted by game theory can be.