For example, you certainly have no guarantee that the two of you order these in lexicographically the same way. So how could you possibly coordinate on a tie-breaking strategy?

You can't, unless you can communicate in some way, such as by talking to eachother or reading eachother's source code. In that case it's easy.