Fastest way to meet, without communication, on a sphere?

I was puzzled by a question my colleague asked me, and now seeking your help.

Suppose you and your friend* end up on a big sphere. There are no visual cues on where on the sphere you both are, and the sphere is way bigger than you two. There are no means of communication. You can determine your relative position and direction by navigating the stars**. You can move anywhere, and your friend too.

Upon inspecting the sphere, you see it is rock-solid, so you cannot create markings. To protect the environment, you are not allowed to leave other stuff, like a blood trace or breadcrumbs.

You have been put on the sphere without being able to communicate a plan.

How would you be able to find each other (come within a certain distance $\epsilon$?) What would be the optimal strategy to move?

*Since you are here, you must be a rational person. For this puzzle we assume your friend is rational too.._{Which makes it odd that you end up on that sphere anyway}

**While you can determine your position relatively, you are on a sphere in a galaxy so far away that you cannot determine absolute 'north', 'south' etc. by the stars.

Move at random.

Any deterministic strategy you choose has a chance that your partner will choose the exactly opposite strategy, so you end up moving along more or less antipodal paths and never meet. So deterministic strategies have to be avoided.

You might make some adjustments to your random strategy. For example, you could prefer to walk longer distances in a straight line as opposed to choosing a completely new direction after every centimeter of movement. Depending on what your partner does, some of that might improve things. But to accurately judge whether it does, you'd need some probabilistic model of what plan your partner is likely to choose, and getting that right would pretty much amount to a pre-agreed plan. So you can't even know the probability distribution of plans for your partner, hence you can't quantitatively compare strategies against one another.

As per "You have been put on the sphere without being able to communicate a plan." I'm going to assume you cannot even assume what plan your partner may come up with and there is no prior collaboration.

Given the potential symmetric nature of the problem, there must be a random element to break that symmetry, should you both accidentally choose mirror strategies. The problem is there's no guarantee that your friend will select an optimal strategy, however, if your friend is smart and/or exhaustive, they will realise two things:

1. If you are both moving, the chances of running into each other can be nil given non-overlapping patterns.
2. If one of you stays still, the other can eventually find you with an exhaustive search.

So the first thing to do is to calculate the size of the sphere (by picking a direction and walking until you arrive back at the start point or some other, more efficient technique). At that point, you can work out an exhaustive search pattern and the duration to perform one (a spiral pattern is close to optimal but difficult for a human to perform). That duration becomes your frequency of decision making.

Once per period, you flip a coin. Heads, you do an exhaustive search. Tails, you stay put. Each of the longer period (e.g. the less efficient search pattern), you have a 50/50 chance of doing the opposite of your partner and thus discovering each other in the course of the exhaustive search.

There's two extreme cases that are covered by this approach. If you partner decides to never move, obviously they will be found on your first exhaustive search. If they decide to permanently move, either randomly, or according to some pattern, there's always the chance of happening upon them accidentally during your search sweeps, which you have to rely on if they're not being exhaustive and their movement does not cover your 'stay put' spot. Otherwise, when you stay put you guarantee they'll eventually find you.

move on spirals like this:

_{(source: forum.cad.de)}

where the distance between spiral arms is $2\epsilon$.

I assume you have a measure of distance on your sphere, or else you couldn't determine the winning condition.

Here there are some points.

1. Here it seems a bit redundant to me to talk about strategies, because it is more of a static game with complete information than a dynamic game.

   First of all, I assume that for you this is a game with complete information. To do so more explicitly, we – roughly – simply have to add to your sentence "There are no visual cues on where on the sphere you both are, and the sphere is way bigger that you two. There is no means of communication. You can determine your position and direction by navigating the stars. You can move anywhere, and your friend too." the words "you both know this, you both know that you both know this, and so on."

   Then, the game is static because the temporal element is not really relevant. You choose an action, your friend another, and that's pretty much it, because you cannot really change what you are doing given what your friend is doing, considering that you have no access to that information. Hence, we can get rid of the term "strategy", that in static games with complete information collapses to the term "action".

2. Now, is any of your actions dominated (i.e. you could take an action that gives you a higher payoff, no matter what your friend does)? Not really. Hence, basically all your actions can be rationalized by some conjecture of your friend. Of course, due to the symmetric nature of the game, the same applies to you.

3. Does the game have a solution? Well, it does depend on the solution criterion you think of, and also on how you conceive it. For example, IMO the game has an obvious Nash Equilibrium (please, note that I am not a rocket astronomer...): you and your friend go north, until you both can roughly find with some rough estimation that you are at the north pole of your sphere, and then you wait that the other shows up. You should end up in some $\varepsilon$ distance to each other. Note that here I am assuming the interpretation of Nash Equilibrium as a self-enforcing agreement. Note also, that this action profile should correspond in an objective correlated equilibrium, where the objective device is roughly the pole star.

PS: Of course, the all point behind points (2) and (3) is in order to define exactly what you think "optimal" means here (something that is always problematic). An additional point is that I am assuming that in order to coordinate, the players need to have some objective reference point (north pole - pole star).