Ten Open Problems in Rendezvous Search - Search Theory: A Game Theoretic Perspective - page 215

5. Mozart Café problem. Two friends agree to meet for lunch on the first day
of the millennium year 2,000 at the Mozart Café in Vienna. When the time
comes, each arrives at Vienna Airport and asks a cab to take them to the
Mozart Café. Each is troubled to hear the answer 'There are four of them;
Which one do you want?' On the first day the four cafes are indistinguish-
able so each can do no better than picking one at random. If they don't
meet on the first day (1 January) then they can choose to return on day 2
to the same cafe, or to go to a random new one. And so on. What is the
best strategy, assuming both players use the same one (with independent
randomization)?

This is the first discrete time rendezvous problem. It remains open if there are at
least n 2 cafes, Anderson and Weber [ 16 ]showed

that the random strategy (pick randomly every day) is optimal. They proposed
a general strategy AW

= 4 cafes. If there are only n =

for the case of n cafes: If you haven't met on day 1,
do the following in every successive interval of n

( n )

− 1 days; with probability p n ,

search the other n − 1 cafes in random order; with probability 1 − p n − 1 , stay

where you are for another n 1days.Weber[ 35 ] has recently used an elegant

but elaborate argument to show that AW

−

( 3 ) is indeed optimal for the 3 cafe

problem, but that AW ( 4 ) is not optimal for n = 4 .

6. Mozart Cafe problem with river. Suppose there are 2 n cafes, with n of
them on each side of the Danube. The problem has changed, because after
not meeting on day 1 for example, a player has three choices for the next
day: the same cafe, a different one on the same side of the river, a random
cafe on the other side of the river.

Nothing is known about this version of the problem. The players can ignore
the additional information, so they should be able to meet in the same expected