Saul and Clara would like to meet in Brussels, and as both arrive by train, they decided to meet at the café in the train station. Alas, there are three train stations in Brussels: Brussels South, Brussels Central and Brussels North, and it turns out that they arrived to different stations. Once they realized that there are three train stations, and that they do not have cell-phones, they have to start looking for each other. None of them has any clue regarding the location of the other, so that they assign probability 1/2 to each alternative. What is the search method that minimizes their expected searching time?
Suppose that Saul arrived to Brussels South, and Clara to Brussels Central. The best method is simple: Clara waits, and lets Saul do the search; Saul searches Clara in both Brussels Central and Brussels North in a random order. Assuming the travel time from one train station to another is 1 hour, Saul will find Clara in 3/2 hours.
But this method assumes asymmetry between the two parties: Clara waits while Saul searches. What if Clara is supposed to meet Sandra in Brussels, so that they cannot use gender to create asymmetry?
So suppose that the two players are indistinguishable, and they must use the same strategy. Also, suppose that the three locations are symmetric, and there is no focal point. In that case, to ensure that they meet, they have to use a mixed strategy. But which one is optimal?
In 1990, Anderson and Weber conjectured that the following strategy is optimal: play is divided into blocks of size 2. At the beginning of each block, each player decides whether to stay at his current location (probability 1/3), or look for the other player in the current block (probability 2/3). In the former case, the player remains in his current location during the two stages of the current block. In the latter case, the player visits the other two locations in a random order. Simple arithmetic shows that the expected time until the two parties meet is 5/2. In a recent paper Weber proved that this strategy is indeed optimal. A must read.
The field of location games offers many other open problems that are easy to state. An expert in the field told me that the following problem is still open: locations are the integers (so for each integer z, positive or negative, there is a train station called Brussels-z). Two players are located in two neighboring stations (Brussles-z and Brussels-z+1). It takes one hour to move between neighboring train stations, and the players must use the same strategy. What is the strategy that minimizes the time until they meet?