ON THE MOZART CAFE PROBLEM IN RENDEZVOUS SEARCH THEORY

We have found a formulation that improves upon the best values for rendezvous search on the complete graph developed in 1990 by Anderson and Weber. The markstart formulation was first proposed by Baston and Gal and we have proved their ideas and developed expansions of the problem on the complete graph. Utilizing tokens is only worthwhile when there are n locations and no more than n−1 tokens. For the n=3 case, we proved an optimal solution where players do not wait at the start and have an expected rendezvous time of t=2.The use of the markstart formulation improved the existing optimal solution by 25%. Furthermore, we introduced using Anderson-Weber strategies to determine an expected rendezvous time when players do not converge to one distinct location by reducing the n location problem to the n−2 case. This is shown in detail for n=4. This strategy improved upon the existing expected rendezvous values of rendezvous search on the complete graph below n=10. Lastly, for all n, we formulated general equations when both players only have one token and introduced a strategy for when players have enough tokens to reduce the problem to a distinct location or AW strategy. We see that the markstart formulation when players do not wait at their starting location improves the expected rendezvous time compared to the traditional case for 2≤n≤9